2016年大连海事大学航海学院X01数据结构考研复试题库
● 摘要
一、选择题
1． 用邻接表存储图所用的空间大小（ ）。
A. 与图的顶点数和边数都有关 B. 只与图的边数有关
C. 只与图的顶点数有关 D. 与边数的平方有关
答:A
【解析】邻接表就是对图G 中的每个顶点Vi 建立一个单链表，第i 个单链表中的结点表示依附于顶点V i 的边，这个单链表就称为顶点Vi 的边表。因此邻接表既存储图的所有顶点，也存储顶点之间的边的信息。
2． 分区分配内存管理方式的主要保护措施是（ ）。
A. 界地址保护
B. 程序代码保护
C. 数据保护
D. 栈保护
答:A
【解析】对于连续分配算法，无论固定分区或动态分区方法，程序都必须全部调入内存，不同的进程放于不同的内存块中，相互之间不可越界，因此需要进行界地址保护。通常的界地址保护方法采用软硬件结合的方法。考生要注意本题与虚拟存储方法的区别。
3． —个非空广义表的表尾（ ）。
A. 不能是子表
B. 只能是子表
C. 只能是原子
D. 是原子或子表
答:B
【解析】广义表的定义是一个递归定义，当广义表非空时，称第一个元素是它的表头，称其余元素构成的表称为它的表尾。因此一个非空广义表的表尾只能是子表。
4． 在参考摸型中，下列功能需由应用层的相邻层实现的是（ ）
A. 对话管理
B. 数据格式转换
C. 路由选择
D. 可靠数据传输
答:B
【解析】应用层的相邻层即为表示层，表示层负责管理数据的压缩、加密与解密、格式装换等，故答案为B 。
5． 下列选项中，在
I.
A. 仅 I 、II
B. 仅 I 、III
C. 仅 II 、III
D.I 、II 、III
答:D 。
【解析】
在
总线的数据线上传输的信息包括接口中的命令字、状态字以及真正的数据，而中断类型号也是通过数据线传输的。
6． 下列AOE 网表示一项包含8个活动的工程。通过同时加快若干进度可以缩短整个工程的工期。下列选项中，加快其进度就可以缩短工程工期的是（ ）
总线的数据线上传输的信息包括（ ）。
接口中的状态字III. 中断类型号 接口中的命令字
II.
A.c 和e
B.d 和e
C.f 和d
D.f 和h
答:C
【解析】根据AOE 网的定义可知，同时缩短几条关键路径上的活动时间，可以缩短整个工期。
7． —棵二叉树高度为h ，所有结点的度或为0或为2，则这棵二叉树最少有（ ）个结点。
A.2h B. C. D.
答:B
【解析】此树满足哈夫曼树，除根节点外每层有两个节点。