2016年郑州轻工业学院数学与信息科学学院数据结构考研复试题库
● 摘要
一、选择题
1． 某计算机有16个通用寄存器，采用32位定长指令字操作码字段（含寻址方式位）为8位，Store 指令的源操作数和目的操作数分别采用寄存器直接寻址和基址寻址方式，若基址寄存器可使用任一通用寄存器，且偏移量用补码表示，则Store 指令中偏移量的取值范围是（ ）
A.-32768〜+32767
B.-32767〜+32768
C.-65536〜+65535
D.-65535〜+65536
答:A
【解析】寄存器个数
指令编址方式如下所示：
16位补码取值范围为-32768〜+32767，所以偏移量取值范围为-32768〜+32767
2． 下列选项中，属于多级页表优点的是（ ）
A .加快地址变换速度
B. 减少缺页中断次数
C. 减少页表项所占字节数
D. 减少页表所占的连续内存空间
答:D
【解析】多级页表避免了把所有的页表一直保存在内存中
3． 当在一个有序的顺序存储表上查找一个数据时，既可用折半查找，也可用顺序查找，但前者比后者的查找速度（ ）。
A. 必定快
B. 不一定
C. 在大部分情况下要快
D. 取决于表递增还是递减
答:C
【解析】对于有序顺序存储表折半查找的效率较高，但是不是所有情况下都是如此，比如要查找的元素就是第一个时，用顺序查找比它就快的多了。这类情况外折半都高于顺序查找。
第 2 页，共 43 页 偏移量有32-8-4-4=16位
4． 设被排序的结点序列共有N 个结点，在该序列中的结点已十分接近排序的情况下，用直接插入法、归并法和一般的快速排序法对其排序，这些算法的时间复杂性应为（ ）。
答:C
【解析】因为该序列中的结点已经十分接近排序的情况，对于直接插入法，大部分结点只需要直接插入后面即可，因此时间复杂度为
的时间复杂度为
此时的时间复杂度为
5． —个栈的入栈序列为的个数是（ ）
A.n-3
B.n-2
C.n-1
D. 无法确定
答:C
【解析】除了3本身以外，其他的值均可以取到，因此可能取值的个数为n-1。
6． 设n 是描述问题规模的非负整数，下面程序片段的时间复杂度是（ ）。
答:A
【解析】其中，以基本的原操作重复执行的次数作为算法的时间度量。题目中的基本运算是，则有语句设其执行时间为T （n ）
7． 对任意一棵树，设它有n 个结点，这n 个结点的度数之和为（ ）。
A.n B. C. D.
答:C
总的结点数减一，即n-1。
8． 下列选项中会导致进程从执行态变为就绪态的事件是（ ）。
A. 执行P （wait ）操作
第 3 页，共 43 页 对于采用归并法，它是一种稳定的排序方法，它对于一般的快速排序法，序列越接近有序，所需要的比较次数越多， 其出栈序列是若，则则可能取值 【解析】每个结点（除根节点外）都是一个分支，即所有结点的度数之和等于分支个数等于