2017年南昌大学信息工程学院882数据结构考研导师圈点必考题汇编
● 摘要
一、选择题
1． 若查找每个记录的概率均等，则在具有n 个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度
【答案】C
【解析】最快查找一次成功，最慢查找n
次成功。平均查找次数为
那么
2． 排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（ ）。
I. 简单选择排序II. 希尔排序III. 快速排序IV . 堆排V . 二路归并排序
A. 仅 I 、III 、IV
B. 仅 I 、II 、III
C. 仅 II 、III 、IV
D •仅III 、IV 、V
【答案】A 。
【解析】其中简单选择排序、堆排序属于选择类排序，每一趟排序结束时将确定最大（或最小）关键字所在的位置。快速排序每一趟排序结束时将确定基准关键字所在的位置。希尔排序、二路归并排序每一趟排序结束时不一定能确定一个元素的最终位置。
3． 下列选项中，属于多级页表优点的是（ ）
A .加快地址变换速度
B. 减少缺页中断次数
C. 减少页表项所占字节数
D. 减少页表所占的连续内存空间
【答案】D
【解析】多级页表避免了把所有的页表一直保存在内存中
4． 若一个栈以向量
存储，初始栈顶指针top 为n+1，则下面X 入栈的正确操作是（ ）。
【答案】C
【解析】题中初始栈顶指针top 为n+1, 而栈顶指针又位于最大下标以上，此时入栈应进行先减一操作。
第 2 页，共 41 页 为（ ）。
5． 以下与数据的存储结构无关的术语是（ ）。
A. 循环队列
B. 链表
C. 哈希表
D. 栈
【答案】D
【解析】循环队列体现线性表是以顺序存储。用散列法存储的线性表称散列表。链表说明线性表是以链式结构存储的。栈不能体现出是顺序还是链式存储结构。
6． 循环队列存放其元素值，用front 和rear 分别表示队头和队尾，则当前队列中的元素数是（ ）。
【答案】A
【解析】对于循环队列，需要深刻理解队头在队尾进行进队操作。和队尾的概念，在队头进行出队操作，如果为负则元可能为正也可能为负，为正时元素个数=
素的个数=所以统一的公式就是
7． 当在一个有序的顺序存储表上查找一个数据时，既可用折半查找，也可用顺序查找，但前者比后者的查找速度（ ）。
A. 必定快
B. 不一定
C. 在大部分情况下要快
D. 取决于表递增还是递减
【答案】C
【解析】对于有序顺序存储表折半查找的效率较高，但是不是所有情况下都是如此，比如要查找的元素就是第一个时，用顺序查找比它就快的多了。这类情况外折半都高于顺序查找。
8． 下列二叉排序树中查找效率最高的是（ ）。
A. 平衡二叉树
B. 二叉查找树
C. 没有左子树的二叉排序树
D. 没有右子树的二叉排序树
【答案】A
【解析】平衡二叉树的左子树和右子树的深度之差的绝对值不超过1。这就保证了二叉树的深度是级别的。二叉查找树或者是一颗空数；或者是具有下列性质的二叉树：①若左子树不空，则左子树上所有结点的值均小于它的根结点的值；②若右子树不空，则右子树上所有结点的
第 3 页，共 41 页
值均大于它的根结点的值；③左、右子树也分别为二叉排序树。B 、C 、D 三项均不能保证左子树和右子树的深度之差的绝对值不超过1，甚至很大，因此查找效率低。
9． 某网络的IP 地址空间为采用定长子网划分，子网掩码为
网络的最大子网个数、每个子网内的最大可分配地址个数分别是（ ）。
A.32, 8
B.32, 6
C.8, 32
D.8, 30
【答案】B
【解析】子网号为5位，在CIDR 中可以表示个子网，主机号为3位，除去全0和全1的情况可以表示6个主机地址，答案为B 。
10．在系统总线的数据线上，不可能传输的是（ ）。
A. 指令
B. 操作数
C. 握手（应答）信号
D. 中断类型号型号
【答案】C
【解析】握手（应答）信号属于通信联络控制信号应该在通信总线上传输，不可能在数据总线上传输。而指令、操作数和中断类型码都可以在数据线上传输。
11．内部异常（内中断）可分为故障（fault ）、陷讲（trap ）和终止（abort ）三类。下列有关内部异常的叙述中，错误的（ ）。
A. 内部异常的产生与当前执行指令相关
B. 内部异常的检测由CPU 内部逻辑实现
C. 内部异常的响应发生在指令执行过程中
D. 内部异常处理后返回到发生异常的指令继续执行
【答案】D
【解析】内中断分为：①由软中断指令启动的中断；②在一定条件下由CPU 自身启动的中断。D 项错误，如突然掉电引发的内中断经处理后不会继续执行。
12．有一个的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（ ）。
A.60
B.66
C.18000
D.33
【答案】B
第 4 页，共 41 页 则该