2017年杭州电子科技大学计算机学院851数据结构考研仿真模拟题
● 摘要
一、填空题
1． 设为哈夫曼树的叶结点数日，则该哈夫曼树共有_____个结点。
【答案】
【解析】哈夫曼树只有度为0和2的节点。
2． —棵有个结点的满二叉树有_____个度为1的结点、有_____个分支（非终端）结点和_____个叶子，该满二叉树的深度为_____。
【答案】
或
【解析】满二叉树没有度为1的结点，度为0的结点等于度为2的结点个数+1。
3． 文件由_____组成；记录由_____组成。
【答案】记录；数据项
4． 在拓扑分类中，拓扑序列的最后一个顶点必定是_____的顶点。
【答案】出度为0
【解析】如果最后一个顶点的出度不为0, 则必定还有顶点存在，与题目所说的最后一个顶点矛盾，所有最 后一个顶点的出度必定为零。
5． 无用单元是指_____，例_____
【答案】用户不再使用而系统没有回收的结构和变量；
6． 对于一个具有n 个结点的二叉树，当它为一棵_____二叉树时具有最小高度，当它为一棵_____ 时. 具有最大高度
【答案】完全；只有一个叶结点的二叉树
7． 在一棵m 阶的个数是_____。
【答案】
【解析】m 阶树除根结点和叶子结点外，结点中关键字个数最多是最少
8． 在顺序存储的二叉树中，编号为i 和j 的两个结点处在同一层的条件是_____。
【答案】
树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的
关键字的个数是_____；若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字
【解析】用顺序存储结构存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，
要加“虚结点”。
设编号为
和
的结点在顺序存储中的下标为
和
。
9． 如果按关键码值递増的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为_____。
【答案】
【解析】如果关键码是排好序的，构建二叉排序树就会形成一个单支树，它的查找效率和顺 序查找效率一样为
10．求最短路径的Dijkstra 算法的时间复杂度为_____。
【答案】
11．VSAM 系统是由_____、_____、_____构成的。
【答案】索引集；顺序集；数据集
12．下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。
【答案】
，
则结点
和
在同一层上的条件是
【解析】快速排序（quicksort ）的基本思想是，通过一趟排序将待排记录分割成独立的两部
分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
二、选择题
13．下列有关
B.
接口的叙述中错误的是：（ ）
端口
端口
指令，
A. 状态端口和控制端口可以合用同一寄存器
接口中CPU 可访问寄存器，称为C. 采用独立编址方式时，【答案】D
【解析】采用统一编码方式，存储器和
端口共用统一的地址空间，不需要专用的
任何对存储器数据进行操作的指令都可用于端口的数据操作。所以D 错误
14．无向图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 。
15．设与某资源相关联的信号量初值为3, 当前为1，若M 表示该资源的可用个数，N 表示等待该资源的进程数，则M ，N 分别是（ ）。
A.0、1 B.1、0 C.1、2 D.2、0 【答案】B
【解析】信号量初值是3表示资源数有3个，当前为1表示已经用掉2个，剩余可用的资源数就只有1个了，由于资源有剩余，可见没有其他进程等待使用该资源，故进程数为0。
端口地址和主存地址可能相同
D. 采用统一编址方式时，CPU 不能用访存指令访问
相关内容
相关标签