2016年沈阳师范大学教师专业发展学院数据结构(同等学力加试)复试笔试最后押题五套卷
● 摘要
一、选择题
1． 在采用中断I/O方式控制打印输出的情况下，CPU 和打印控制接口中的I/O端口之间交换的信息不可能是（ ）。
A. 打印字符
B. 主存地址
C. 设备状态
D. 控制命令
答:B
【解析】I/O接口的功能包括：①选址功能；②传送命令功能；③传送数据功能；④反映I/O设备工作状态功能。A 项为数据，C 项为设备状态，D 项为命令。B 项，主存地址在中断方式控制下是不需要的，因此，它不可能是CPU 和打印控制接口中的I/O端口之间交换的信息。
2． 已知小根堆为8，15，10，21，34， 16，12，删除关键字8之后需重建堆，在此过程中，关键字之间的比较数是（ ）。
A.1
B.2
C.3
D.4
答:C
【解析】堆排序中，依次输出堆顶的最小值，然后重新调整堆，如此反复执行，便得到一个有序序列。本题中，删除堆顶元素8后将最后一个元素12置于堆顶，然后调整堆：首先与15比较，12小于15, 所以不用交换；然后与10比较，因为10小于12，所以交换10和12的位置；调
整后12再与16比较，12小于16，调整堆过程结束。因此12共与15、10、16进行了三次比较。
3．
协议对组帧后对应的比特串为（ ）
A.011111000011111010
B.011111000111110101111110
C.01111100011111010
D.011111000111111001111101
答:A
HDLC 协议对比特串进行组帧时，HDLC 数据帧以位模式0111 1110标识每一个帧的【解析】
开始和结束，因此在帧数据中凡是出现了 5个连续的位“1”的时候，就会在输出的位流中填充一个“0”。所以答案为A 。
4． 对任意一棵树，设它有n 个结点，这n 个结点的度数之和为（ ）。
A.n B. C. D.
答:C
【解析】每个结点（除根节点外）都是一个分支，即所有结点的度数之和等于分支个数等于总的结点数减一，即n-1。
5． 设哈希表
长哈希函
数表中已有4个结点
：
其余地址为空，如用二次探测
再哈希法解决冲突，关键字为49的结点的地址是（ ）。
答:D
【解析】15，38，61，84用哈希函数
为5，发生冲突，用二次探测再散列法解决冲突：
仍然发生冲突。
仍然发生冲突。
不再发生冲突。
6． 在下列存储形式中，哪一个不是树的存储形式？（ ）
A. 双亲表示法
B. 孩子链表表示法
C. 孩子兄弟表示法
D. 顺序存储表示法
答:D
【解析】顺序存储就是利用一段连续的存储单元依次存储线性表中的元素。树中某个结点的孩子可以有多个，这就意味着，无论用哪种顺序将树中所有的结点存储到数组中，结点的存储位置都无法直接反映逻辑关系。因此简单的顺序存储表示不能满足树的基本要求。常用的三种树的表示法为：双亲表示法、孩子链表示法、孩子兄弟表示法。
7． 下列选项中，不可能在用户态发生的事件是（ ）。
A. 系统调用
B. 外部中断
C. 进程切换
D. 缺页
答:C 。
【解析】我们在学习操作系统中知道，任何一个进程在现代操作系统中为了共享和保护，设
，在用户态运行用户的程序，在内核定了用户态和内核态（可以通过设置软、硬件标志位来实现）
计算后得地址：4，5，6，7。49计算后
运行系统的程序。所以，从选 项来看，系统调用可以在任何态发生，用户可以发起系统调用，系统也可以；外部中断是不可控的，也会在任何时刻发生，缺页的发生也是不可控的，可以发生在用户代码之间；而进程切换却不会在用户态发生。我们可以考虑一下情形，进程切换是在什么时候发生的，进程切换前必定运行的是进程调度，只有进程调度选择了下一次被调度的进程，进程切换才可以进行。进程调度是scheduler , 进程切换是dispather , 这体现了现代操作系统策略与机制
，必定分离的设计思想。所以，进程切换必定不会在用户态发生（所谓发生指其起始的源头时刻）
是在内核态（进程调度）发生的。
8． 用直接插入排序方法对下面4个序列进行排序
，（由小到大）元素比较次数最少的是（ ）。
答:C
9． 下列关于USB 总线特性的描述中，错误的是（ ）。
A. 可实现外设的即插即用和热插拔
B. 可通过级联方式连接多台外设
C. 是一种通信总线，可连接不同外设
D. 同时可传输2位数据，数据传输率高
答:D 。
【解析】USB 总线即通用串行总线，它的特点有：（1）即插即用；（2）热插拔；（3）有很强的链接能力能将所有外设链接起来，且不损失带宽；（4）有很好的可扩展性；（5）高速传输，速度可达480Mbps 。所有A , B, C都符合USB 总线的特点。对于选项D , USB 是串行总线，不能同时传输两位数据，所以答案为D 。
10．
对个权值均不相同的字符构成哈夫曼树。下列关于该哈夫曼树的叙述中，错误的是（ ）。
A. 该树一定是一棵完全二叉树
B. 树中一定没有度为1的结点
C. 树中两个权值最小的结点一定是兄弟结点
D. 树中任一非叶结点的权值一定不小于下一层任一结点的权值
答:A
【解析】哈夫曼树为带权路径长度最小的二叉树，但不一定是完全二叉树，选项A 错误；哈夫曼树中没有度为1的结点，选项B 正确；构造哈夫曼树时，最先选取两个权值最小的结点作为左右子树构造一棵新的二叉树，C 正确；哈夫曼树中任一非叶结点P 的权值为其左右子树根结点权值之和，其权值不小于其左右子树根结点的权值，在与结点P 的左右子树根结点处于同一层的结点中，若存在权值大于结点P 权值的结点Q ，那么结点Q 与其兄弟结点中权值较小的一个应该与结点P 作为左右子树构造新的二叉树，由此可知，哈夫曼树中任一非叶结 点的权值一定不小于