2017年青海民族大学计算机学院827计算机综合之数据结构考研导师圈点必考题汇编
目录2017年青海民族大学计算机学院827计算机综合之数据结构考研导师圈点必考题汇编（一） 2 2017年青海民族大学计算机学院827计算机综合之数据结构考研导师圈点必考题汇编（二）.........
目录
2017年青海民族大学计算机学院827计算机综合之数据结构考研导师圈点必考题汇编（一） 2 2017年青海民族大学计算机学院827计算机综合之数据结构考研导师圈点必考题汇编（二）
........................................................................................................................................ 15 2017年青海民族大学计算机学院827计算机综合之数据结构考研导师圈点必考题汇编（三）
........................................................................................................................................ 29 2017年青海民族大学计算机学院827计算机综合之数据结构考研导师圈点必考题汇编（四）
........................................................................................................................................ 41 2017年青海民族大学计算机学院827计算机综合之数据结构考研导师圈点必考题汇编（五）
........................................................................................................................................ 54
第 1 页，共 68 页
,
2017年青海民族大学计算机学院827计算机综合之数据结构考研导师圈点必考题汇
编（一）
说明：①本资料为VIP 学员内部使用，整理汇编了历届导师圈点的重点试题及常考试题。
——————————————————————————————————————————
一、选择题
1． 如果本地域名服务无缓存，当采用递归方法解析另一网络某主机域名时，用户主机、本地域名服务器发送的域名请求消息数分别为（ ）。
A.1条，1条
B.1条，多条
C. 多条，1条
D. 多条，多条
【答案】A
【解析】所谓递归查询方式就是：如果主机所询问的本地域名服务器不知道被查询域名的IP 地址，那么本地域名服务器就以DNS 客户的身份向其他服务器继续发出查询请求报文，而不是让该主机自行下一步的查询。所以主机只需向本地域名服务器发送一条域名请求，采用递归查询方法，本地域名服务器也只需向上一级的根域名服务器发送一条域名请求，然后依次递归。正确选项为A 。
2． 串的长度是指（ ）。
A. 串中所含不同字母的个数
B. 串中所含字符的个数
C. 串中所含不同字符的个数
D. 串中所含非空格字符的个数
【答案】B
【解析】串中字符的数目n 称为字符的长度，不必考虑其中单个字符是否相等。
3． 下列序列中，（ ）是执行第一趟快速排序后所得的序列。
【答案】C
【解析】快速排序将数据划分成两部分，其中一部分关键字比另一部分关键字小。
4． 对矩阵压缩存储是为了（ ）。
A. 方便运算
B. 方便存储
C. 提高运算速度
第 2 页，共 68 页
,
D. 减少存储空间
【答案】D
【解析】压缩存储也就是对那些没用的元素不进行存储或者对那些具有一定规律的相同元素放在一个存储空间，目的就是为了节省空间。
5． 栈和队的共同点是（ ）。
A. 都是先进后出
B. 都是后进先出
C. 只允许在端点处插入和删除元素
D. 没有共同点
【答案】C
【解析】栈和队列的区别是栈是先进后出的数据结构，队列是先进先出的数据结构，栈和队列的共同点是都只能在端点处插入和删除元素。
6． 哈希函数有一个共同的性质，即函数值应当以（ ）取其值域中的每个值。
A. 最大概率
B. 最小概率
C. 平均概率
D. 同等概率
【答案】D
7． 设与某资源相关联的信号量初值为3, 当前为1，若M 表示该资源的可用个数，N 表示等待该资源的进程数，则M ，N 分别是（ ）。
A.0、1
B.1、0
C.1、2
D.2、0
【答案】B
【解析】信号量初值是3表示资源数有3个，当前为1表示已经用掉2个，剩余可用的资源数就只有1个了，由于资源有剩余，可见没有其他进程等待使用该资源，故进程数为0。
8． 以下数据结构中，（ ）是非线性数据结构。
A. 树
B. 字符串
C. 队
D. 栈
【答案】A
第 3 页，共 68 页
,
【解析】非线性结构是指存在一对多或者多对一的关系。常见的非线性结构有树结构和图结构。
9． 下列排序算法中，占用辅助空间最多的是（ ）。
A. 归并排序
B. 快速排序
C. 希尔排序
D. 堆排序
【答案】A
【解析】
归并排序的辅助空间为
快速排序所占用的辅助空间为堆排序所占 用的辅助空间为
10．在下图所示的平衡二叉树中，插入关键字48后得到一棵新平衡二叉树。在新平衡二叉树中，关键字37 所在结点的左、右子结点中保存的关键字分别是（ ）。
A.13、48
B.24、48
C.24、53
D.24、90
【答案】C
【解析】题目中，插入48以后，树根结点的平衡因子由-1变为-2, 失去平衡。这属于RL （先右后左）型平衡旋转，需做两次（先右旋后左旋转）旋转操作。过程如下图所示：
显然，在调整后的新平衡二叉树中，关键字37所在结点的左、右子结点中保存的关键字分别是24, 53。
11．下列有关总线定时的叙述中，错误的是（ ）。
A. 异步通信方式中，全互锁协议最慢
第 4 页，共 68 页