2016年武汉纺织大学数学与计算机学院数据结构考研复试题库
● 摘要
一、选择题
1． 相对于微程序控制器，硬布线控制器的特点是（ ）。
A. 指令执行速度慢，指令功能的修改和扩展容易
B. 指令执行速度慢，指令功能的修改和扩展难
C. 指令执行速度快，指令功能的修改和扩展容易
D. 指令执行速度快，指令功能的修改和扩展难
答:D
【解析】在同样的半导体工艺条件下，硬布线（组合逻辑）控制器的速度比微程序控制器的速度快。这是因为硬布线控制器的速度主要取决于逻辑电路的延迟，而微程序控制器增加了一级控制存储器，执行的每条微指令都要从控制存储器中读取，影响了速度。由于硬布线控制器一旦设计完成就很难改变，所以指令功能的修改和扩
展难。因此，硬布线控制器的特点是指令执行速度快，指令功能的修改和扩展难。
2． 和顺序栈相比，链栈有一个比较明显的优势是（ ）。
A. 通常不会出现找满的情况
B. 通常不会出现栈空的情况
C. 插入操作更容易实现
D. 删除操作更容易实现
答:A
3． 广义表答:D
head 操作就是得到广义表中第一个的原子。【解析】操作就是得到除第一个原子外剩下元
素构成的表。也就是toil 得到的元素需要在外层再加一个（ ）。
4． 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。
A. 单链表
B. 仅有头指针的单循环链表
C. 双链表
D. 仅有尾指针的单循环链表
答:D
第 2 页，共 42 页 则式子 的值为（ ）。
【解析】仅有尾指针的单循环链表，在最后插入元素和删除第一个元素都会用到这个尾指针。
5． 对于栈操作数据的原则是（ ）。
A. 先进先出
B. 后进先出
C. 后进后出
D. 不分顺序
答:B
【解析】先进先出是队列操作数据的原则。先进后出是栈操作数据的原则，栈限定在表尾进行插入和删除。
6． 为提高散列（Hash ）表的查找效率，可以采用的正确措施是（ ）。
I .增大装填（载）因子
II. 设计冲突（碰撞）少的散列函数
III. 处理冲突（碰撞）时避免产生聚集（堆积）现象
A. 仅I B. 仅 II C. 仅 I 、II D. 仅 II 、III
答:D
【解析】散列表的查找效率（比较次数）取决于：散列函数、处理冲突的方法和散列表的装填因子a 。CX 标 志着散列表的装满程度，通常情况下，（X 越小，发生冲突的可能性越小；反之，a 越大，表示已填入的记录越多， 再填入记录时，发生冲突的可能性越大。因此选项I 错误，越是增大装填因子，发生冲突的可能性就越大，查找 效率也越低。选项II 正确。选项III 正确。采用合适的处理冲突的方法避免产生聚集现象，也将提高查找效率。例如，用拉链法解决冲突时不存在聚集现象，用线性探测法解决冲突时易引起聚集现象。
7． 若将关键字1，2, 3, 4, 5, 6, 7依次插入到初始为空的平衡二叉树T 中，则T 中平衡因子为0的分支结点的个数是（ ）
A.0
B.1
C.2
D.3
答:D
【解析】将图中给定的关键字序列依次插入到平衡树中，构成的平衡树如下图所示，由图可知平衡因子为0的分支结点为3个叶子结点，故答案为D 。
第 3 页，共 42 页