2017年北京信息科技大学经管学院817数据结构和C语言之数据结构考研题库
● 摘要
一、选择题
1． 已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则该完全二叉树的结点个数最多是（ ）。
A.39 B.52 C.111 D.119
【答案】C
【解析】完全二叉树的一个特点是：叶子结点只能出现在最下层和次下层。题目中没有说明完全二叉树的高度，首先由完全二叉树的特点确定题目中树的高度。根据题意，一棵完全二叉树的第6层（设根为第1层）有8个叶结点，可知此二叉树的高度是6或7。题目中求二叉树的结点数最多的情况，因此此完全二叉树的高度为7。由于高度为7的完全二叉树的前6层是一棵满二叉树，根据二叉树的性质2可知，高度为6的满二叉树的结点数是-1=63。又根据二叉树的性质1可知，题目中二叉树的第6层结点数是
=32个结点，已知有8个叶子结点，那么其余32-8=24
个结点均为分支结点，这些结点在第7层上最多有48个子结点（即叶子结点）。所以此二叉树的结点数最多可达-1+（-8）×2=lll。
2． 在采用中断I/O方式控制打印输出的情况下，CPU 和打印控制接口中的I/O端口之间交换的信息不可能是（ ）。
A. 打印字符 B. 主存地址 C. 设备状态 D. 控制命令 【答案】B
【解析】I/O接口的功能包括：①选址功能；②传送命令功能；③传送数据功能；④反映I/O设备工作状态功能。A 项为数据，C 项为设备状态，D 项为命令。B 项，主存地址在中断方式控制下是不需要的，因此，它不可能是CPU 和打印控制接口中的I/O端口之间交换的信息。
3． 若一个栈以向量
存储，初始栈顶指针top 为n+1，则下面X 入栈的正确操作是（ ）。
【答案】C
【解析】题中初始栈顶指针top 为n+1, 而栈顶指针又位于最大下标以上，此时入栈应进行先减一操作。
4． 下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是（ ）。
A. 选择排序法B. 插入排序法C. 快速排序法D. 堆排序法 【答案】A
【解析】选择排序的基本思想是：
第i 趟排序开始时，当前有序区和无序区分别为则是从当前无序区中选出关键字最小的记录和
分别变为新的有序区和新的无序区。
和
该趟排序
交换，使
将它与无序区的第1个记录
5． 将森林转换为对应的二叉树，若在二叉树中，结点u 是结点v 的父结点的父结点，则在原来的森林中，u 和v 可能具有的关系是（ ）。
I. 父子关系 II. 兄弟关系
III.u 的父结点与v 的父结点是兄弟关系 A. 只有I B.I 和II C.I 和III D.I 、II 和III 【答案】B
【解析】首先，在二叉树中，若结点U 是结点v 的父结点的父结点，那么u*v的关系有如下4种情况：
接下来，根据森林与二叉树的转换规则，将这4种情况还原成森林中结点的关系。其中： ，在原来的森林中U 是V 的父结点的父结点； 情况（1）
，在森林中u 是v 的父结点； 情况（2）
，在森林中u 是v 的父结点的兄弟； 情况（3）
，在森林中u 与v 是兄弟关系。 情况（4）
由此可知，题目中的I 、II 是正确的。
6． 现有容量为10GB 的磁盘分区，磁盘空间以簇（cluster ）为单位进行分配，簇的大小为4KB , 若采用位图法管理该分区的空闲空间，即用一位（bit ）标识一个簇是否被分配，则存放该位图所需簇的个数为（ ）
A.80 B.320
C.80K D.320K 【答案】A
【解析】磁盘的簇的个数为：
而一个簇的位示图能管理的簇的个数为：
所以需要簇的个数为
7． 设有向图G= （V ，E ），顶点集能得到的不同遍历序列个数是（ ）。
A.2 B.3 C.4 D.5
【答案】D
【解析】根据题意知有向图的结构如图所示。深度优先遍历的特点是尽可能先对纵深方向进行搜索，所以可 能得到的不同遍历序列分别是：
8． 用邻接表存储图所用的空间大小（ ）。
A. 与图的顶点数和边数都有关 B. 只与图的边数有关 C. 只与图的顶点数有关 D. 与边数的平方有关 【答案】A
【解析】邻接表就是对图G 中的每个顶点Vi 建立一个单链表，第i 个单链表中的结点表示依附于顶点V i 的边，这个单链表就称为顶点Vi 的边表。因此邻接表既存储图的所有顶点，也存储顶点之间的边的信息。
9． 设X 是树T 中的一个非根结点，B 是T 所对应的二叉树。在B 中，X 是其双亲的右孩子，下列结论正确的是（ ）。
A. 在树T 中，X 是其双亲的第一个孩子 B. 在树T 中，X —定无右兄弟 C. 在树T 中，X —定是叶结点 D. 在树T 中，X —定有左兄弟 【答案】D
【解析】由树和二叉树的转换关系可知，X 一定有左兄弟，X 是其双亲的第二个孩子，不能
个
V={V0, VI ，V2, V3}，边
集
若从顶点V0开始对图进行深度优先遍历，则可
相关内容
相关标签