2017年西北民族大学中国民族信息技术研究院849计算机学科专业基础之数据结构考研冲刺密押题
● 摘要
一、选择题
1． 在对n 个元素的序列进行排序时，堆排序所需要的附加存储空间是（ ）。
【答案】B
【解析】堆排序需要一个空间用于交换，因此堆排序所需要的附加存储空间为
2． 下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序（ ）。
A. 二叉排序树
B. 哈夫曼树
C.
D. 堆
【答案】D
【解析】堆的定义：
n 个关键字序列
（1）
（2）
且且或 称为堆，当且仅当该序列满足如下性质（简称为堆性质）： 树
满足第（1）种情况的堆，称为小顶堆；满足第（2）种情况的堆，称为大顶堆。
由堆的定义可知堆可以满足上述性质。
3． 某计算机主存容量为64KB , 其中ROM 区为4KB , 其余为RAM 区，按字节编址。现要用2Kx8位的ROM 芯片和4Kx4位的RAM 芯片来设计该存储器，则需要上述规格的ROM 芯片数和RAM 芯片数分别是（ ）。
A.1、15
B.2、15
C.1、30
D.2、30
【答案】D
【解析】主存储器包括RAM 和ROM 两部分，由于ROM 区为4KB ，则RAM 区为60KB 。存储容量的扩展方法有字扩展、位扩展、字和位同时扩展三种。选用2Kx8位的ROM 芯片，只需
/4*2采用2片芯片进行字扩展便可得到4KB 的ROM 区；选用4Kx4位的RAM 芯片，需采用（60）
片芯片进行字和位同时扩展便可得60KB 的RAM 区。
4． 下列进程调度算法中，综合考虑进程等待时间和执行时间的是（ ）。
A. 时间片轮转调度算法
B. 短进程优先调度算法
C. 先来先服务调度算法
D. 尚响应比优先调度算法
【答案】D
【解析】时间片轮转法和先来先服务算法都是公平的方法，并未考虑进程等待时间和执行时间，而短进程优先考虑的是进程执行时间。最高响应比优先调度算法是最先执行响应比最尚的进程（响应比=1＋等待时间/估计运行时间）。该算法综合了先来先服务（FCFS ）和短作业优先（SJF ）算法，FCFS 只考虑每个作业的等待时间，而未考虑执行时间的长短。SJF 只考虑执行时间的长短，而未考虑等待时间的长短，HRRN 算法则同时考虑执行时间和等待时间。
5． 下面关于哈希（Hash ，杂凑）查找的说法正确的是（ ）。
A. 哈希函数构造的越复杂越好，因为这样随机性好，冲突小
B. 除留余数法是所有哈希函数中最好的
C. 不存在特别好与坏的哈希函数，要视情况而定
D. 若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单地将该元素删去即可
【答案】C
【解析】若数据结构中存在关键字和K 值相等的记录，则必定在
不需要进行比
较便可直接取得所查记录。在此，称这个对应关系f 为哈希（Hash ）函数，哈希函数的选择要视具体情况而定。
6． 若线性表最常用的操作是存取第I 个元素及其前驱和后继元素的值，为节省时间应采用的存储方式（ ）。
A. 单链表
B. 双向链表
C. 单循环链表
D. 顺序表
【答案】D
【解析】线性表采用顺序表，便于进行存取任一指定序号的元素。
的存储位置上，由此，
7． 在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（ ）个。
A.4
B.5
C.6
D.7
【答案】C
【解析】设度为0的结点数为x 则度为3的树总结点数n=度为0的结点数+度为1的结点数+度为2的结点数+度为3的结点数
为3
的树总结点数
8． 链表不具有的特点是（ ）。
A. 插入、删除不需要移动元素
B. 可随机访问任一元素
C. 不必事先估计存储空间
D. 所需空间与线性长度成正比
【答案】B
【解析】B 项是顺序表的特点。只要确定了顺序线性表的起始位置，线性表中的任一数据元素都可随机存取。
9． 某设备中断请求的相应和处理时间为100m ，每400ns 发出一次中断请求，中断相应所容许的最长延迟时间为50ns , 贝U 在该设备持续工作过程中CPU 用于该设备的
百分比至少是（ ）
A.
B.
C.
D.
【答案】B
【解析】每400m 响应一次中断并且用100m 进行处理，所以该设备的时间占用CPU 时间
百分比为中断响应容许的延迟时间对此没有影响，属于干扰条件。
10．下列命中组合情况中，一次访存过程中不可能发生的是（ ）。
A.TLB 未命中，Cache 未命中，Page 未命中
B.TLB 未命中，Cache 命中，Page 命中
C.TLB 命中，Cache 未命中，Page 命中
D.TLB 命中，Cache 命中，Page 未命中
【答案】D
【解析】TLB （快表）和慢表（页表，Page ）构成二级存储系统，若TLB 命中，则Page 必命中。因此不可能发生的是D 选项。
从每个结点所指向的结点数的和的角度来计算度两种方法所计算出来的n 相等，所以 时间占整个CPU 时间