2018年武汉科技大学汽车与交通工程学院856数据结构(C语言版)考研核心题库
● 摘要
目录
2018年武汉科技大学汽车与交通工程学院856数据结构（C 语言版）考研核心题库（一） . ... 2
2018年武汉科技大学汽车与交通工程学院856数据结构（C 语言版）考研核心题库（二） . . 13
2018年武汉科技大学汽车与交通工程学院856数据结构（C 语言版）考研核心题库（三） . . 28
2018年武汉科技大学汽车与交通工程学院856数据结构（C 语言版）考研核心题库（四） . . 39
2018年武汉科技大学汽车与交通工程学院856数据结构（C 语言版）考研核心题库（五） . . 51
一、单项选择题
1． 如果本地域名服务无缓存，当采用递归方法解析另一网络某主机域名时，用户主机、本地域名服务器发送的域名请求消息数分别为（ ）.
A.1条，1条
B.1条，多条
C. 多条，1条
D. 多条，多条
【答案】A
【解析】所谓递归查询方式就是:如果主机所询问的本地域名服务器不知道被查询域名的IP 地址，那么本地域名服务器就以DNS 客户的身份向其他服务器继续发出查询请求报文，而不是让该主机自行下一步的查询. 所以主机只需向本地域名服务器发送一条域名请求，采用递归查询方法，本地域名服务器也只需向上一级的根域名服务器发送一条域名请求，然后依次递归. 正确选项为A.
2． 如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用下列哪一种查找方法（ ）。
A. 分块
B. 顺序
C. 折半
D. 哈希
【答案】A
【解析】分块查找，把线形表分成若干块，块间是顺序存储的，所以查找速度较快。在每一块中的数据元素的存储顺序是任意的，所以便于线性表的动态变化。
3． 下列程常段的时间复杂度是（ ）
A.O()
B.O(n) C.O() D.O()
【答案】C
【解析】外部循环的退出条件是k>n, 而对于k , 每次循环都执行
内部循环的退出条件是j>n, 对于j , 每次循环都执行
) , 即选C 。 段的时间复杂度为O(
4． 当系统发生抖动(thrashing)时, 可以采取的有效措施是（ ）。
Ⅰ. 撤销部分进程
Ⅱ. 增加磁盘交换区的容量
Ⅲ. 提高用户进程的优先级
A. 仅Ⅰ
B. 仅Ⅱ
C. 仅Ⅲ
D. 仅Ⅰ、Ⅱ
【答案】A , 所以循环次数为; , 所以每次循环次数为n 次。所以此程序
【解析】“抖动”现象是指刚刚被换出的页很快又要被访问, 为此, 又要换出其他页, 而该页又很快被访问, 必须换入, 如此频繁地置换页面, 以致操作系统的大部分时间都花在页面置换上, 引起系统性能下降甚至崩溃。引起系统抖动现象的原因是对换的信息量过大, 内存容量不足, 置换算法选择不当。所以解决的办法就是降低交换页面数量, 加大内存容量, 改变置换选择算法。但是降低交换页面数量和改变置换选择算法对于一个应用系统来讲是不可能的, 只能增加内存容量。增加内存容量可以是直接添加物理内存(大型计算机都可以在不关机的情况下增加物理内存条) , 或者, 降低进程数量, 相对地增加内存。而增加交换区容量并不能解决物理内存不足的问题, 提高用户进程的优先级会使系统的状态更加恶化。
5． 一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（ ）。
A. 其中任意一个结点均无左孩子
B. 其中任意一个结点均无右孩子
C. 其中只有一个叶结点
D. 其中度为2的结点最多为一个
【答案】C
【解析】前序序列是“根左右”，后序序列是“左右根”，若要这两个序列相反，只有单支树才有可能，所以本题的A 项和B 项均对，单支树的特点是只有一个叶结点，故C 项是最合适的。A 项或B 项都不全。
6． —个多道批处理系统中仅有P1和P2两个作业, P2比P1晚5ms 到达。它们的计算和作顺序如下:P1:计算60ms
, , 计算20ms ; P2:计算120ms
,
不考虑调度和切换时间, 则完成两个作业需要的时间最少是（ ）。
A.240ms
B.260ms
操, 计算40ms 若
C.340ms
D.360ms
【答案】B 。
【解析】考查处理系统的性能计算, 由于P2比P1晚5ms 到达, P1先占用CPU , 根据P1和P2的执行过程, 作业运行的甘特图如下所示, 故答案为B 。
图 甘特图
7． 元素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 。
8． 若将关键字1, 2, 3, 4, 5, 6, 7依次插入到初始为空的平衡二叉树T 中, 则T 中平衡因子为0的分支结点的个数是（ ）
A.0
B.1
C.2
D.3
【答案】D
【解析】将图中给定的关键字序列依次插入到平衡树中, 构成的平衡树如下图所示, 由图可知