2018年解放军信息工程大学控制工程(专业学位)820数据结构[专业硕士]考研核心题库
● 摘要
一、填空题
1． 设为哈夫曼树的叶结点数目，则该哈夫曼树共有_____个结点。
【答案】
【解析】哈夫曼树只有度为0和2的节点。
2． 无用单元是指_____，例_____
【答案】用户不再使用而系统没有回收的结构和变量；
3． 堆是一种有用的数据结构。堆排序是一种_____排序，堆实质上是一棵_____结点的层次序列。对含有N 个元素的序列进行排序时，堆排序的时间复杂度是_____，所需的附加存储结点是_____。关键码序列05, 23, 16, 68, 94, 72, 71, 73是否满足堆的险质_____ 。
【答案】选择；完全二叉树；
；O(1)；满足堆的性质
4． 求最短路径的Dijkstra 算法的时间复杂度为_____。
【答案】
5． 设T 是一棵结点值为整数的二叉排序树，A 是一个任意给定的整数。在下面的算法中，free_tree(T)在对二叉排序树丁进行后序遍历时释放二又排序树T 的所有结点
；
，首先在二叉排序树T 中查找值为A 的结点，根据查找情况分别进行如下
处理:(1)若找不到值为A 的结点，则返回根结点的地址(2)若找到值为A 的结点，则删除以此结点为根的子树，并释放此子树中的所有结点，若值为A 的结点是查找树的根结点，删除后变成空的二叉树，则返NULL ; 否则返回根结点的地址。
【答案】
6． 克鲁斯卡尔算法的时间复杂度为_____，它对_____图较为适合。
【答案】
；边稀疏
二、单项选择题
7． —个进程的读磁区操作完成后, 操作系统针对该进程必做的是（ ）
A. 修改进程状态为就绪态 B. 降低进程优先级 C. 进程分配用户内存空间 D. 增加进程的时间片大小 【答案】A
【解析】进程等待的操作完成便会从等待状态转移到就绪状态。
8． 以太网交换机进行转发决策时使用的PDU 地址是（ ）.
A. 目的物理地址 B. 目的IP 地址 C. 源物理地址 D. 源IP 地址 【答案】A
【解析】交换机会监测发送到每个端口的数据帧，通过数据帧中的有关信息(源结点的MAC 地址、目的结点的MAC 地址) ，就会得到与每个端口所连接结点的MAC 地址，并在交换机的内部建立一个“
端口
地址”映射表. 建立映射表后，当某个端口接收到数据帧后，交换机会读取
出该帧中的目的结点的MAC 地址，并通过“端口-MAC 地址”的对应关系，迅速将数据帧转发到相应的端口，注意这里的交换机工作在数据链路层，因此关于IP 地址的选项是不对的，因此答案为A.
9． 在下图所示的平衡二叉树中, 插入关键字48后得到一棵新平衡二叉树。在新平衡二叉树中, 关键字37所在结点的左、右子结点中保存的关键字分别是（ ）。
A.13、48 B.24、48 C.24、53
D.24、90 【答案】C
【解析】题目中, 插入48以后, 树根结点的平衡因子由-1变为-2, 失去平衡。这属于RL(先右后左) 型平衡旋转, 需做两次(先右旋后左旋转) 旋转操作。过程如下图所示:
显然, 在调整后的新平衡二叉树中, 关键字37所在结点的左、右子结点中保存的关键字分别是24, 53。
10．—个多道批处理系统中仅有P1和P2两个作业, P2比P1晚5ms 到达。它们的计算和作顺序如下:P1:计算60ms
,
, 计算20ms ; P2:计算120ms
,
不考虑调度和切换时间, 则完成两个作业需要的时间最少是（ ）。
A.240ms B.260ms C.340ms D.360ms
【答案】B 。
【解析】考查处理系统的性能计算, 由于P2比P1晚5ms 到达, P1先占用CPU , 根据P1和P2的执行过程, 作业运行的甘特图如下所示, 故答案为B 。
操
, 计算40ms 若
图 甘特图
11．若一棵完全二叉树有768个结点, 则该二叉树中叶结点的个数是（ ）。
A.257 B.258 C.384 D.385
【答案】C
【解析】由
和
可知,
, 即
, 显然
则
384, 所以二叉树的叶结点个数是384。