2017年扬州大学信息工程学院858程序设计与数据结构之数据结构考研强化模拟题
● 摘要
目录
2017年扬州大学信息工程学院858程序设计与数据结构之数据结构考研强化模拟题（一）.... 2
2017年扬州大学信息工程学院858程序设计与数据结构之数据结构考研强化模拟题（二）.. 13
2017年扬州大学信息工程学院858程序设计与数据结构之数据结构考研强化模拟题（三）.. 23
2017年扬州大学信息工程学院858程序设计与数据结构之数据结构考研强化模拟题（四）.. 33
2017年扬州大学信息工程学院858程序设计与数据结构之数据结构考研强化模拟题（五）.. 45
一、选择题
1． 有关二叉树下列说法正确的是（ ）。
A_二叉树的度为2
B. —棵二叉树的度可以小于2
C. 二叉树中至少有一个结点的度为2
D. 二叉树中任何一个结点的度都为2
【答案】B
【解析】树的度=MAX（结点1的度，结点2的度，结点3的度，... ，结点n 的度）。二叉树之所以称为二叉树，是因为二叉树中节点的度最大是2，也可以小于2。
2． 已知一棵有2011个结点的树，其叶结点个数为116, 该树对应的二叉树中无右孩子的结点个数是（ ）。
A.115
B.116
C.1895
D.1896
【答案】D
【解析】每个非终端结点转换成二叉树后都对应一个无右孩子的结点（因为一个非终端结点
，另外，树根结点转至少有一个孩子结点，其最右边的孩子结点转换成二叉树后一定没有右孩子）
换成二叉树后也没有右孩子。题目中树的总结点数是2011，叶结点个数是116, 则非终端结点个数是2011-116=1895, 则该树对应的二叉树中 无右孩子的结点个数是1895+1=1896。
3． 若一棵二叉树的前序遍历序列和后序遍历序列分别为1，2, 3, 4和4, 3, 2, 1，则该二叉树的中序遍历序列不会是（ ）。
A.1, 2.3.4
B.2，3, 4.1
C.3, 2, 4, 1
D.4, 3, 2, 1
【答案】C
【解析】题目中的二叉树的先序序列和后序序列正好相反，这样的二叉树每层只有一个结点。该二叉树的形态如下图所示。
从左至右，这8棵二叉树的中序序列分别为：
（1）4. 3. 2. 1，
（2）3, 4, 2, 1
（3）2, 4, 3, 1
（4）2, 3, 4，1
（5）1，4，3, 2
（6）1, 3, 4, 2
（7）1，2, 4, 3
（8）1, 2, 3, 4
显然选项C 的中序序列不会出现。
4． 在下面的程序段中，对x 的赋值语句的时间复杂度为（ ）
【答案】C
【解析】两个循环嵌套，那么语句x :=x＋l :
则被执行了次。
5． 无向图G=（V , E ）, 其中：V={a, b , c , d , e , f ）}, E={（a , b ）, （a , e ）, （a , c ），，（b , e ）, （c , f ）
，（f , d ）（e , d ）, 对该图进行深度优先遍历，得到的顶点序列正确的是（ ）。
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 邻接的所有顶点都被访问过为止。
，，，，，根据E={（a , b ）（a ，e ）（a ，c ）（b ，e ）（c , f ）（f ，d ）, （e ，d ）}可知各顶点之间的邻
接关系。依据上面的原则遍历，得出遍历顺序a , e ，d ，f ，c , b 。
6． 下列选项中，满足短任务优先且不会发生饥饿现象的调度算法是（ ）。
A. 先来先服务
B. 高响应比优先
C. 时间片轮转
D. 非抢占式短任务优先
【答案】B
【解析】分析该题目可以看到，本题所提到的问题是涉及短任务调度也就是属于作业调度，因此首先排除时 间片轮转算法；因为作业调度算法中没有时间片轮转的算法。其次，因为问题提到短任务，则先来先服务的算法也可以排除了，它与短任务无关。剩余高响应比优先算法和非抢占式短任务优先是哪一个? 我们可以通过分析得到，非抢占式短任务优先算法不能解决饥饿问题，因为当一个系统短任务源源不断到达是，长任务必然会得不到 调度，产生饥饿。而解决此方法的最好方式就是采用计算响应比的方法，并以高响应比值优先调度。这样，无论短任务或长任务，均可以得到调度，而且，较短任务会得到优先的调度。故满足短任务优先且不会发生饥饿现象的调度算法只有尚响应比优先算法。
7． 下列选项中，用于设备和控制器（
A.PCI
B.USB
C.AGP
D.PCI-Express
【答案】B ’接口）之间互连的接口标准是（ ）
【解析】设备和设备控制器之间的接口是USB 接口，其余选项不符合，故答案为B 。
8． 下列选项中，不能改善磁盘设备性能的是（ ）。
A.
重排请求次序
B. 在一个磁盘上设置多个分区
C. 预读和滞后写
D. 优化文件物理块的分布
【答案】B 。
【解析】磁盘
的一个瓶颈。“重排性能主要是指其读写速度。相对而言，磁盘的性能是计算机性能提高请求次序”可以优化磁臂调度的算法，减少读写时间，故正确；“预读和滞
性能，后写”是利用内存作为磁盘的缓存，使得对磁盘的访问变为对内存的访问，也可以在总体上提高其“优化文件物理块的分布”减少磁臂调度和旋转调度的等待时间，也可以提高磁盘性能；
而磁盘分区仅在磁盘空间的组织上进行划分， 对磁盘性能的提升没有什么帮助，
是不能改善磁盘设备性能的，故答案为B 。
9． 在文件的索引节点中存放直接索引指针10个，一级二级索引指针各1个，磁盘块大小为1KB 。每个索引指针占4个字节。若某个文件的索引节点已在内存中，到把该文件的偏移量（按字节编址）为1234和307400 处所在的磁盘块读入内存。需访问的磁盘块个数分别是（ ）。
A.1, 2