2017年河北大学电子信息工程学院929数据结构(电)考研强化模拟题
● 摘要
一、选择题
1． 某计算机采用微程序控制器，共有32条指令，公共的取指令微程序包含2条微程序，各指令对应的微程序平均由4条微指令组成，采用断定法（下址字段法）确定下条微指令的地址，则微指令中下址字段的位数至少是：（ ）
A.5 B.6 C.8 D.9
【答案】C
【解析】所以至少需要8位才能表示完130个地址。
2． 对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（ ）
。
【答案】B
【解析】快速排序是将待排记录分割成独立的两部分，其中一部分的关键字均比另一部分记录的关键字小。
第一次比较：28比72小，不交换； 第二次比较：28比5大，交换，此时为第三次比较：16比28小，不交换； 第四次比较：32比28大，交换，此时为第五次比较：28比2大，交换，此时为第六次比较：28比12大，不交换； 第七次比较：28比60小，交换，此时为一次划分结束。
3． 已知循环队列存储在一维数组rear 的值分别是（ ）。
A.0, 0 B.0, n-1 C.n-1, 0 D.n-1, n-1
【答案】B
【解析】题目要求队列非空时front 和rear 分别指向队头元素和队尾元素，若初始时队列为空，
中，且队列非空时front 和rear 分别指向队头元素和
队尾元素。若初始时队列为空，且要求第1个进入队列的元素存储在A[0]处，则初始时front 和
且要求第1 个进入队列的元素存储在A[0]处，则此时front 和rear 的值都为0。由于进队操作要执行（rear+1） % n，则初始 时front 的值为0、rear 的值为n-1。
4． 元素a , b , c , d , e 依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d 开头的序列个数是（ ）。
A.3 B.4 C.5 D.6
【答案】B
【解析】d 首先出栈后的状态如下图所示。
此时可有以下4种操作：
（1）e 进找后出栈，出梭序列为decba 。 （2）c 出找，e 进找后出栈，出找序列为dceba 。 （3）cb 出找，e 进找后出栈，出找序列为dcbea 。
（4）cba 出找，e 进找后出找，出找序列为dcbae 。
5． 在对n 个元素的序列进行排序时，堆排序所需要的附加存储空间是（ ）。
【答案】B 【解析】堆排序需要一个空间用于交换，因此堆排序所需要的附加存储空间为
6． 折半查找的时间复杂性为（ ）。
【答案】D
【解析】顺序查找的事件复杂度为
因为折半查找是查找效率最高的算法，它的事件复杂
度为
7． 对下图进行拓扑排序，可以得到不同的拓扑序列的个数是（ ）。
A.4
B.3 C.2 D.1
【答案】B
【解析】拓扑排序的步骤为：
（1）在有向图中选一个没有前驱的顶点并且输出它；
（2）从图中删除该顶点和以它为尾的弧。重复上述两步，直至全部顶点均已输出。由于没有前驱的顶点可能不唯一，所以拓扑排序的结果也不唯一。题中所给图有三个不同的拓扑棑序序列，分别为abced ，abecd ，aebcd 。
8． 将一棵树t 转换为孩子兄弟链表表示的二叉树h ，则t 的后序遍历是h 的（ ）。
A. 前序遍历 B. 中序遍历 C. 后序遍历 【答案】B
【解析】树的后序遍历恰好对应于二叉树的中序遍历。
9． 组内的所有元素和小于后一组内的所有元素，若采用基于比较的排序，其时间下界应为（ ）。
A. B. C. D. 【答案】B
【解析】因组与组之间已有序，故将
个组分别排序即可，基于比较的排序方法每组的时
间下界为
0全部时间下界为
10．单链表中，增加一个头结点的目的是为了（ ）。
A. 使单链表至少有一个结点 B. 标识表结点中首结点的位置 C. 方便运算的实现
D. 说明单链表是线性表的链式存储 【答案】C
【解析】单链表中增加一个头结点的目的是为了方便运算的实现，使得对第一个元素的操作与其它元素的操作相同。
二、判断题