2018年河南大学921专业基础课(C++程序设计、数据结构)[专业硕士]之数据结构考研仿真模拟五套题
● 摘要
一、单项选择题
1． 某计算机的指令流水线由4个功能段组成，指令流经各功能段的时间(忽略各功能段之间的缓存时间) 分别为90ns 、80ns 、70ns 和60ns ，则该计算机的CPU 时钟周期至少是（ ）.
A.90ns
B.80ns
C.70ns
D.60ns
【答案】A
【解析】对于各功能段执行时间不同的指令流水线，计算机的CPU 时钟周期应当以最长的功能段执行时间为准.
2．
协议对0111110001111110组帧后对应的比特串为（ ）
A.011111000011111010
B.011111000111110101111110
C.01111100011111010
D.011111000111111001111101
【答案】A
【解析】HDLC 协议对比特串进行组帧时, HDLC 数据帧以位模式
个“0”。所以答案为A 。
3． 希尔排序的组内排序采用的是（ ）。
A. 直接插入排序
B. 折半插入排序
C. 快速排序
D. 归并排序
【答案】A
【解析】希尔排序基本思想是:先将整个待排元素序列按某个增量分割成若干个子序列, 在子序列内进行直接插入排序, 然后依次缩减增量再进行排序, 待整个序列中的元素基本有序(增量足够小) 时, 再对全体元素进行一次直接插入排序。
标识每一个帧的开始和结束, 因此在帧数据中凡是出现了5个连续的位“1”的时候, 就会在输出的位流中填充一
4． 对于一个线性表既要求能够进行较快速地的插入和删除，又要求存储结构能反映数据之间的逻辑关系，则应该用（ ）。
A. 顺序存储方式
B. 链式存储方式
C. 散列存储方式
D. 以上均可以
【答案】B
5． 某计算机存储器按字节编址, 主存地址空间大小为64MB ,
现用
32MB 的主存储器, 则存储器地址寄存器MAR 的位数至少是（ ）。
A.22位
B.23位
C.25位
D.26位
【答案】D
【解析】虽然实际的主存储器(RAM区) 只有32MB , 但不排除还有ROM 区, 考虑到存储器扩展的需要, MAR 应保证能访问到整个主存地址空间。因为主存的地址空间大小为64MB , 所以MAR 的位数至少需要26位。
6． 现有容量为10GB 的磁盘分区, 磁盘空间以簇(duster)为单位进行分配, 簇的大小为4KB , 若采用位图法管理该分区的空闲空间, 即用一位(bit)标识一个簇是否被分配, 则存放该位图所需簇的个数为（ ）
A.80
B.320
C.80K
D.320K
【答案】A
【解析】磁盘的簇的个数为:
个
而一个簇的位示图能管理的簇的个数为:
所以需要簇的个数为
个
7． 基于比较方法的n 个数据的内部排序。 最坏情况下的时间复杂度能达到的最好下界是（ ）。
A. B.
C. O (n) D.
位的RAM 芯片组成
【答案】A
【解析】在内部排序中，最坏情况下的时间复杂度为
8． 下列选项中, 在用户态执行的是（ ）。
A. 命令解释程序
B. 缺页处理程序
C. 进程调度程序
D. 时钟中断处理程序
【答案】A
【解析】题目是问用户态执行, 可见是有关操作系统基本概念的问题。四个选项中, 用户唯一能面对的是命令解释程序, 缺页处理程序和时钟中断都属于中断, 在核心态执行, 而进城调度属于系统调用在核心态执行。只有命令解释程序属于命令接口, 可以运行在用户态, 接受用户的命令操作控制。
9． 若将关键字1, 2, 3, 4, 5, 6, 7依次插入到初始为空的平衡二叉树T 中, 则T 中平衡因子为0的分支结点的个数是（ ）
A.0
B.1
C.2
D.3
【答案】D
【解析】将图中给定的关键字序列依次插入到平衡树中, 构成的平衡树如下图所示, 由图可知平衡因子为0的分支结点为3个叶子结点, 故答案为D 。
。
图
10．对矩阵压缩存储是为了（ ）。
A. 方便运算
B. 方便存储
C. 提高运算速度
D. 减少存储空间
【答案】D