《2017年南昌大学信息工程学院882数据结构考研导师圈点必考题汇编.doc》由会员分享，可在线阅读，更多相关《2017年南昌大学信息工程学院882数据结构考研导师圈点必考题汇编.doc（5页珍藏版）》请在金锄头文库上搜索。
1、2017年南昌大学信息工程学院882数据结构考研导师圈点必考题汇编一、选择题1 若查找每个记录的概率均等，则在具有n 个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度【答案】C【解析】最快查找一次成功，最慢查找n次成功。平均查找次数为那么 2 排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（ ）。I. 简单选择排序II. 希尔排序III. 快速排序IV . 堆排V . 二路归并排序A. 仅 I 、III 、IVB. 仅 I 、II 、IIIC. 仅 II 、III 、IVD ?仅III 、
2、IV 、V【答案】A 。【解析】其中简单选择排序、堆排序属于选择类排序，每一趟排序结束时将确定最大（或最小）关键字所在的位置。快速排序每一趟排序结束时将确定基准关键字所在的位置。希尔排序、二路归并排序每一趟排序结束时不一定能确定一个元素的最终位置。 3 下列选项中，属于多级页表优点的是（ ）A .加快地址变换速度B. 减少缺页中断次数C. 减少页表项所占字节数D. 减少页表所占的连续内存空间【答案】D【解析】多级页表避免了把所有的页表一直保存在内存中 4 若一个栈以向量存储，初始栈顶指针top 为n+1，则下面X 入栈的正确操作是（ ）。 【答案】C【解析】题中初始栈顶指针top 为n+1,
3、而栈顶指针又位于最大下标以上，此时入栈应进行先减一操作。第 2 页，共 41 页 为（ ）。 5 以下与数据的存储结构无关的术语是（ ）。A. 循环队列B. 链表C. 哈希表D. 栈【答案】D【解析】循环队列体现线性表是以顺序存储。用散列法存储的线性表称散列表。链表说明线性表是以链式结构存储的。栈不能体现出是顺序还是链式存储结构。 6 循环队列存放其元素值，用front 和rear 分别表示队头和队尾，则当前队列中的元素数是（ ）。 【答案】A【解析】对于循环队列，需要深刻理解队头在队尾进行进队操作。和队尾的概念，在队头进行出队操作，如果为负则元可能为正也可能为负，为正时元素个数=素的个数=所
4、以统一的公式就是 7 当在一个有序的顺序存储表上查找一个数据时，既可用折半查找，也可用顺序查找，但前者比后者的查找速度（ ）。A. 必定快B. 不一定C. 在大部分情况下要快D. 取决于表递增还是递减【答案】C【解析】对于有序顺序存储表折半查找的效率较高，但是不是所有情况下都是如此，比如要查找的元素就是第一个时，用顺序查找比它就快的多了。这类情况外折半都高于顺序查找。 8 下列二叉排序树中查找效率最高的是（ ）。A. 平衡二叉树B. 二叉查找树C. 没有左子树的二叉排序树D. 没有右子树的二叉排序树【答案】A【解析】平衡二叉树的左子树和右子树的深度之差的绝对值不超过1。这就保证了二叉树的深度是
5、级别的。二叉查找树或者是一颗空数；或者是具有下列性质的二叉树：若左子树不空，则左子树上所有结点的值均小于它的根结点的值；若右子树不空，则右子树上所有结点的第 3 页，共 41 页值均大于它的根结点的值；左、右子树也分别为二叉排序树。B 、C 、D 三项均不能保证左子树和右子树的深度之差的绝对值不超过1，甚至很大，因此查找效率低。 9 某网络的IP 地址空间为采用定长子网划分，子网掩码为网络的最大子网个数、每个子网内的最大可分配地址个数分别是（ ）。A.32, 8B.32, 6C.8, 32D.8, 30【答案】B【解析】子网号为5位，在CIDR 中可以表示个子网，主机号为3位，除去全0和全1的
6、情况可以表示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.60B.66C.18000D.33【答案】B第 4 页，共 41 页 则该一、选择题考研试题
