2017年中国农业科学院农业信息所808数据结构考研仿真模拟题
● 摘要
一、选择题
1． 下列网络设备中，能够抑制广播风暴的是（ ）。
中继器
集线器
网桥
路由器 A.
仅
和 B.
仅C.
仅
D. 仅
和
【答案】D
【解析】中继器和集线器工作在物理层，不能抑制网络风暴。为了解决冲突域的问题，提高共享介质的利用率，通常利用网桥和交换机来分隔互联网的各个网段中的通信量，以建立多个分离的冲突域。但是，当网桥和交换机接收到一个未知转发信息的数据帧时，为了保证该帧能被目的结点正确接收，将该帧从所有的端口广播出去。于是可以看出，网桥和交换机的冲突域等于端口的个数，广播域为1。因此网桥不能抑制网络风暴。
2． 用户在删除某文件的过程中，操作系统不可能执行是（ ）
A. 删除此文件所在的目录 B. 删除与此文件关联的目录项 C. 删除与此文件对应的控制块 D. 释放与此文件关联的内存级冲区 【答案】A
【解析】删除文件不需要删除文件所在的目录，而文件的关联目录项和文件控制块需要随着文件一同删除，同时释放文件的关联缓冲区。
3． 用直接插入排序方法对下面4个序列进行排序，
（由小到大）元素比较次数最少的是（ ）。
【答案】C
4．
对（ ）。
个权值均不相同的字符构成哈夫曼树。下列关于该哈夫曼树的叙述中，错误的是
A. 该树一定是一棵完全二叉树 B. 树中一定没有度为1的结点
C. 树中两个权值最小的结点一定是兄弟结点
D. 树中任一非叶结点的权值一定不小于下一层任一结点的权值 【答案】A
【解析】哈夫曼树为带权路径长度最小的二叉树，但不一定是完全二叉树，选项A 错误；哈夫曼树中没有度为1的结点，选项B 正确；构造哈夫曼树时，最先选取两个权值最小的结点作为左右子树构造一棵新的二叉树，C 正确；哈夫曼树中任一非叶结点P 的权值为其左右子树根结点权值之和，其权值不小于其左右子树根结点的权值，在与结点P 的左右子树根结点处于同一层的结点中，若存在权值大于结点P 权值的结点Q ，那么结点Q 与其兄弟结点中权值较小的一个应该与结点P 作为左右子树构造新的二叉树，由此可知，哈夫曼树中任一非叶结 点的权值一定不小于下一层任一结点的权值。
5． 下列选项中，能引起外部中断的事件是（ ）。
A. 键盘输入 B. 除数为0 C. 浮点运算下溢 D. 访存缺页 【答案】A
【解析】所谓外部中断是指由外部事件引起的中断，在这4个选项中，只有键盘输入是真正由外部事件引起的中断。
6． 某CPU 主频为1.03GHz , 采用4级指令流水线，每个段的执行需要1个时钟周期。假定CPU
执行了100条指令，在其执行过程中没有发生任何流水线阻塞，此时流水线的吞吐率为（ ）
A. B. C. D. 【答案】C
【解析】采用4级流水线执行100条指令，在执行过程中共用
条指令/秒，故答案为C 。
个时钟周期。
CPU 的主频是1.03GHz , 也就是说每秒钟有1.03G 个时钟周期。流水线的吞吐率
为
条指令/秒
条指令/秒
条指令/秒
条指令/秒
7． 设有一棵3阶B 树，如题图所示。删除关键字78得到一棵新B 树，其最右叶结点所含的关键字是（ ）。
题图二叉树图
A.60
B.60, 62 C.62, 65 D.65
【答案】D 。
【解析】本题主要考查B 树删除操作。即被删关键字所在的结点中的关键字个数等于
而与该结点相邻的右兄弟（或左兄弟）结点中的关键字数目大于
则需将其兄弟结点中最
小（或最大）的关键字上移至双亲结点中，而将双亲结点中小于（或大于）且紧靠该上移关键字的关键字下移至被删关键字所在结点中。题目中删除关键字78得到一棵新B 树如下，其最右叶结点所含的关键字是65。
8． 若一棵二叉树的前序遍历序列为a ，e ，b ，d ，c ，后序遍历序列为b , c, d, e, a, 则根结点的孩子结点（ ）。
A. 只有e B. 有 e 、b C. 有 e 、c D. 无法确定 【答案】A 。
b , d, c, 后序遍历序列为b ，c , d, 【解析】由题目可知，若一棵二叉树的前序遍历序列为a , e，e , a , 其中a 为这棵二叉树的根结点，接下来，在前序遍历的第二个结点为e , 而后序遍历的倒数第二个结点为e , 说 明a 的孩子结点只有e 。
9． 下列选项中，满足短任务优先且不会发生饥饿现象的调度算法是（ ）。
A. 先来先服务 B. 高响应比优先 C. 时间片轮转
D. 非抢占式短任务优先