2018年佳木斯大学教育科学学院829网络与软件技术[专业硕士]之数据结构考研强化五套模拟题
● 摘要
一、单项选择题
1． 无向图G=(V，E) ，其中:
，
对该图进行深度优先遍历，得到的顶点序列正确的是（ ）。
A.a , b , e , c , d , f
B.a , c , f , e , b , d
C.a , e , b , c , f , d
D.a , e , d , f , c , b
【答案】D
【解析】图的深度优先遍历过程是:从图中某个初始顸点v 出发，首先访问初始顶点v ，然后选择一个与顶点V 相邻且没被访问过的顶点U 为初始顶点。再从U 出发进行深度优先搜索，直到图中与当前顶点V 邻接的所有顶点都被访问过为止。
根据
关系。依据
上面的原则遍历，得出遍历顺序a ，e ，d ，f ，c ，b 。
2． 下列选项中, 不能改善磁盘设备性能的是（ ）。
A. 重排请求次序
B. 在一个磁盘上设置多个分区
C. 预读和滞后写
D. 优化文件物理块的分布
【答案】B 。
【解析】
磁盘
的一个瓶颈。“重排性能主要是指其读写速度。相对而言,
磁盘的性能是计算机性能提高请求次序”可以优化磁臂调度的算法, 减少读写时间, 故正确; “预读和滞
性能, 可知各顶点之间的邻接后写”是利用内存作为磁盘的缓存, 使得对磁盘的访问变为对内存的访问, 也可以在总体上提高其性能; “优化文件物理块的分布”减少磁臂调度和旋转调度的等待时间, 也可以提高磁盘
而磁盘分区仅在磁盘空间的组织上进行划分, 对磁盘
盘设备性能的, 故答案为B 。
3． 下列存储器中, 在工作期间需要周期性刷新的是（ ）。
A.SRAM
B.SDRAM
第 2 页，共 70 页 性能的提升没有什么帮助, 是不能改善磁
C.ROM
D.FLASH
【答案】B
【解析】动态随机存储器(DRAM)是利用存储元电路中栅极电容上的电荷来存储信息的, 电容
上的电荷一般只能维持, 因此即使电源不掉电, 信息也会自动消失。为此, 每隔一定时间必须刷新。
4． 某计算机的控制器采用微程序控制方式, 微指令中的操作控制字段采用字段直接编码法, 共有33个微命令, 构成5个互斥类, 分别包含7、3、12、5和6个微命令, 则操作控制字段至少有 （ ）。
A.5位
B.6位
C.15位
D.33位
【答案】C 。
33个微命令分成5个互斥类(即5个字段) , 根据每个类中微命令的多少可以分别确定【解析】
字段的长度为3、2、4、3、3位, 又因为采用直接编码方式, 所以它们之和
作控制字段的位数。
5． 下列选项中，操作系统提供的给应用程序的接口是（ ）.
A. 系统调用
B. 中断
C. 库函数
D. 原语
【答案】A
【解析】操作系统提供给用户应用程序的接口只有两种:命令输入和系统调用. 其中，命令输入又有不同的形式，例如常规的命令行、图形化人机交互接口(GUI)、自然命令用户接口(NUI)等，而系统调用中除了常规的一些传统的系统调用(例如read （ ）) 以外，还有经过扩展的复杂调用(例如多种API) ，以及包含在Lib 库中的各种封装好的过程调用(最终都是通过系统调用陷入到操作系统中去的）等.
6． 在一棵具有15个关键字的4阶B 树中, 含关键字的结点数最多是（ ）
A.5 B.6 C.10 D.15
【答案】D
【解析】M 阶B 树非根结点含关键字个数。
4阶B 树非根结点含关键字1~3个, 所以要使关键字结点数量最多, 那么每个结点只有一个关
第 3 页，共 70 页 也就是操
键字, 一共有15个关键字那么最多有15个含有关键字的结点
7． 已知关键字序列5，8，12，19，28，20，15，22是小根堆(最小堆) ，插入关键字3，调整后的小根堆是（ ）.
A.3， 5， 12， 8， 28， 20， 15， 22， 19
B.3， 5， 12， 19， 20， 15， 22， 8， 28
C.3， 8， 12， 5， 20， 15， 22， 28， 19
D.3， 12， 5， 8， 28， 20， 15， 22， 19
【答案】A
【解析】在堆中插入或删除一个元素后，将不再满足堆的性质. 为了使其成为新堆，在输出堆顶元素后，需要调整剩余元素. 具体过程如图(1)〜(5)所示，(1)为原堆，(2)为插入3后，(3)、(4)为调整过程，(5)为调整后的小根堆
.
(3)
(4)
第 4 页，共 70 页