2017年武汉理工大学计算机科学与技术学院852数据结构(C语言版)考研强化模拟题
● 摘要
一、选择题
1． 某计算机采用二级页表的分页存储管理方式，按字节编址，页大小为
2字节，逻辑地址结构为：
逻辑地址空间大小为
（ ）。
A.64
B.128
C.256
D.512
【答案】B
【解析】地址空间分为逻辑地址空间和物理地址空间。页的大小为
采用二级页表，一页可存放
要个页面来保存页表项，故本题答案为B 。 字节，页表项大小为2B ，字节，故最少需
’个页表项，本题中逻辑地址空间大小为页，则表示整个逻辑地址空间的页目录表中包含表项的个数至少是字节，页表项大小为
2． 中断处理和子程序调用都需要压栈以保护现场，中断处理一定会保存而子程序调用不需要保存其内容的是（ ）。
A. 程序计数器
B. 程序状态字寄存器
C. 通用数据寄存器
D. 通用地址寄存器
【答案】B 。
【解析】中断处理与子程序调用最大的区别是中断处理程序与正在运行的进程可能无关，而子程序调用与正在运行的进程有关。中断是要打断处理器的正常工作次序，并要求其去处理某一事件的一种常用手段。因此，除了要保护当前程序的地址，计数器（指针）和数据寄存器以外，还需要保存程序状态字。子程序调用是与当前进程有关，是正在运行的程序有意安排执行的，这一类调用发生的时间以及位置具有确定性，处于同一个进程内，因此不需要保存程序状态字。所以中断处理和子程序调用不同的区别是中断处理程序必定会保存程序状态字寄存器。
3． 在物理层接口特性中，用于描述完成每种功能的事件发生顺序的是（ ）。
A. 机械特性
B. 功能特性
C. 过程特性
D. 电气特性
【答案】C 。
【解析】物理层的主要任务描述为确定与传输媒体接口的一些特性；机械特性：主要定义物理连接的边界点，即接插装置；电气特性：规定传输二进制位时，线路上信号的电压高低、阻抗匹配、传输速率和距离限制；功能特性：主要定义各条物理线路的功能；规程特性：主要定义各条物理线路的工作规程和时序关系。而从题干可以 分析描述事件先后顺序的就是规程，也就是过程特性，答案是C 。
4． 5个字符有如下4种编码方案，不是前缀编码的是（ ）
A.
B.
C.
D.
【答案】D
【解析】在一个字符集中，任何一个字符的编码都不是另一个字符编码的前缀。约定左分支
表示字符
右分支表示字符则可以用从根结点到叶子结点的路径上的分支字符串作为该叶子结点字符的编码。如此得到的编码必是前缀编码。D 选项中，编码110是编码1100的前缀，故不符合前缀编码的定义。
5． 下列有关总线定时的叙述中，错误的是（ ）。
A. 异步通信方式中，全互锁协议最慢
B. 异步通信方式中，非互锁协议的可靠性最差
C. 同步通信方式中，同步时钟信号可由多设备提供
D. 半同步通信方式中，握手信号的采样由同步时钟控制
【答案】C
【解析】A 项正确，异步通信方式中，全互锁协议最慢，主从模块都需要等待确认后才能撤销其信号；B 项正确，异步通信方式中，非互锁协议没有相互确认机制，因此可靠性最差；C 项错误，同步通信要遵循统一的时钟信号，不能由多设备提供；D 项正确，半同步通信方式中，握手信号的采样由同步时钟控制。
6． 下列关于管道（Pipe ）通信的叙述中，正确的是（ ）
A. —个管道可实现双向数据传输
B. 管道的容量仅受磁盘容量大小限制
C. 进程对管道进行读操作和写操作都可以被阻塞
D. —个管道只能有一个读写进程或一个写进程对其操作
【答案】C
【解析】只有写进程才能对管道写入数据，读进程对管道进行读取数据，只能半双工通信，
即某一时刻只能单向传输。管道为空，则读操作被堵塞，而如果有写操作对管道进行写的话那就要堵塞了。那么C 正确
7． 已知小根堆为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进行了三次比较。
8． 若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结论是（ ）。
A. 存在，且唯一
B. 存在，且不唯一不唯一
C. 存在，可能不唯一
D. 无法确定是否存在
【答案】C 。
【解析】图的基本应用——拓扑排序，用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，说明该图为有向无环图，所以其拓扑序列存在，但不一定唯一，如图的邻接矩阵为则存在两个拓扑序列。
9． 知一棵二叉树的前序遍历结果为ABCDEF ，中序遍历结果为CBAEDF ，则后序遍历结果为（ ）。
A.CBEFDA
B.FEDCBA
C.CBEDFA
D. 不定
【答案】A
【解析】由前序结果可知A 为根节点，再由中序遍历结果知BC 为A 的左孩子，且C 为B 的左孩子结点，到此可排除B 项，按照这种逻辑依次推理，便可得出结果对于该类型题目，可以先根据前序遍历结果和中序遍历结果画出二叉树，然后后序遍历二叉树得到后序遍历序列。