2017年山东建筑大学计算机科学与技术学院900计算机专业综合之数据结构考研强化模拟题
● 摘要
一、填空题
1． 求最短路径的Dijkstra 算法的时间复杂度为_____。 【答案】
2． 设为哈夫曼树的叶结点数日，则该哈夫曼树共有_____个结点。 【答案】
【解析】哈夫曼树只有度为0和2的节点。
3． 顺序查找n 个元素的顺序表，若查找成功，则比较关键字的次数最多为_____次；当使用监视哨时，若查找失败，则比较关键字的次数为_____。 【答案】
【解析】最多的情况就是把整个表遍历了一遍。使用监视哨时，需要多一个存储空间来存监视哨。
4． 抽象数据类型的定义仅取决于它的一组_____，而与_____无关, 即不论其内部结构如何变化，只要它的_____不变，都不影响其外部使用。
【答案】逻辑特性；在计算机内部如何表示和实现；数学特性
5． 建立索引文件的目的是_____。
【答案】提高查找速度
6．
每一棵树都能唯一地转换为它所对应的二叉树。若已知一棵二叉树的前序序列是
中序序列是
前庁序列是_____。 【答案】
【解析】树的抑序序列对应二叉树的前序序列. 该二叉树转换成森林吋含三棵树. 其第一棵树的前序是。
7． 当广义表中的每个元素都是原子时，广义表便成了_____。
【答案】线性表
【解析】如果每个元素都是原子，则元素不可分。此时的元素是只有一对一的关系，所以广义表变成了线性表。
第 2 页，共 72 页 .
，则它的后庁序列是_____。设上述二叉树是由某棵树转换而成，则该树的
8． 文件由_____组成；记录由_____组成。
【答案】记录；数据项
9． —棵有个结点的满二叉树有_____个度为1的结点、有_____个分支（非终端）结点和_____个叶子，该满二叉树的深度为_____。 【答案】
或
【解析】满二叉树没有度为1的结点，度为0的结点等于度为2的结点个数+1。
10．按LSD 进行关键字排序，除最次位关键字之外，对每个关键字进行排序时，只能用_____的排序方法。
【答案】稳定
二、选择题
11．某二叉树结点的中序序列为BDAECF ，后序序列为DBEFCA ，则该二叉树对应的森林包括（ ）棵树。
A.1
B.2
C.3
D.4
【答案】C
【解析】由两序列可知，A 为根节点，ECF 为右子树，C 为右子树的根，F 为C 的右孩子。再由二叉树和森林的对应关系可知该二叉树对应的森林包括3棵树。根据中序序列和后序序列画出二叉树，根据二叉树得出对应的森林包含的树的棵数。
12．将森林转换为对应的二叉树，若在二叉树中，结点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种情况：
第 3 页，共 72 页
接下来，根据森林与二叉树的转换规则，将这4种情况还原成森林中结点的关系。其中：
，在原来的森林中U 是V 的父结点的父结点； 情况（1）
，在森林中u 是v 的父结点； 情况（2）
，在森林中u 是v 的父结点的兄弟； 情况（3）
，在森林中u 与v 是兄弟关系。 情况（4）
由此可知，题目中的I 、II 是正确的。
13．下列选项中，用于设备和控制器（’接口）之间互连的接口标准是（ ）
A.PCI
B.USB
C.AGP
D.PCI-Express
【答案】B
【解析】设备和设备控制器之间的接口是USB 接口，其余选项不符合，故答案为B 。
14．一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（ ）。
A. 其中任意一个结点均无左孩子
B. 其中任意一个结点均无右孩子
C. 其中只有一个叶结点
D. 其中度为2的结点最多为一个
【答案】C
【解析】前序序列是“根左右”，后序序列是“左右根”，若要这两个序列相反，只有单支树才有可能，所以本题的A 项和B 项均对，单支树的特点是只有一个叶结点，故C 项是最合适的。A 项或B 项都不全。
15．
某系统正在执行三个进程
例如下表所示。
和各进程的计算（CPUCPUCPU ）时间和时间比
为提高系统资源利用率，合理的进程优先级设置应（ ） A. B.
第 4 页，共 72 页
相关内容
相关标签