2018年江西理工大学理学院873数据结构考研强化五套模拟题
● 摘要
一、单项选择题
1． 用有向无环图描述表达式
A.5
B.6
C.8
D.9
【答案】A ，至少需要顶点的数目为（ ）。
，6条边【解析】一共5个结点。
2． 在一个有N 个元素的有序单链表中查找具有给定关键字的结点，平均情况下的时间复杂性为（ ）。
A.O(1)
B.O(N)
C.O(N2) D.
【答案】B
【解析】二分查找的时间复杂度为。在一个用N 个元素的有序单链表中查找具有给定
关键字的结点，因为查找是从头结点开始的，需要使用指针顺序往下查找，因此时间复杂度为0(N)。
3． 直接插入排序在最好情况下的时间复杂度为（ ）。 A.
B.O(n) C. 2D.O(n)
【答案】B
【解析】当序列是按照直接插入排序的顺序有序时，此时进行插入时，每次都只需要和末尾的一个元素进行比较，此时的时间复杂度最好，为O(n)。
4． 下列选项中, 能缩短程序执行时间的措施是（ ）。
Ⅰ. 提高CPU 时钟频率
Ⅱ. 优化数据通路结构
Ⅲ. 对程序进行编译优化
A. 仅Ⅰ和Ⅱ
b. 仅Ⅰ和Ⅲ
c. 仅Ⅱ和Ⅲ
d. Ⅰ、Ⅱ和Ⅲ
【答案】D
【解析】一般说来, CPU 时钟频率(主频) 越高, CPU 的速度就越快; 优化数据通路结构, 可以有效提高计算机系统的吞吐量; 编译优化可得到更优的指令序列。所以Ⅰ、Ⅱ、Ⅲ都是有效措施。
5． 假定有k 个关键字互为同义词，若用线性探测法把这k 个关键字存入哈希表中，至少要进行多少次探测？（ ）
A.k －1次
B.k 次
C.k+1次 D.
【答案】D
【解析】至少探测次数。
6． 响应外部中断的过程中, 中断隐指令完成的操作, 除保护断点外, 还包括（ ）。
Ⅰ. 开关中断
Ⅱ. 保存通用寄存器的内容
Ⅲ. 形成中断服务程序入口地址并送PC
A. 仅Ⅰ、Ⅱ
B. 仅Ⅰ、Ⅲ
C. 仅Ⅱ、Ⅲ
D. Ⅰ、Ⅱ、Ⅲ
【答案】B 。
【解析】中断隐指令完成的操作有3个:
①保存断点; ②关中断; ③引出中断服务程序(形成中断服务程序入口地址并送PC) 。
而保存通用寄存器内容的操作是由软件来实现, 不是由中断隐指令实现的。
7． 引入二叉线索树的目的是（ ）。
A. 加快查找结点的前驱或后继的速度
B. 为了能在二叉树中方便地进行插入与删除
C. 为了能方便地找到双亲
D. 使二叉树的遍历结果唯一
【答案】A
【解析】二叉线索树有指向前驱和后继的指针，因此加快了查找前驱和后继结点的速度。 次
8． 若某单处理器多进程系统中有多个就绪态进程, 则下列关于处理机调度的叙述中, 错误的是（ ）。
A. 在进程结束时能进行处理机调度
B. 创建新进程后能进行处理机调度
C. 在进程处于临界区时不能进行处理机调度
D. 在系统调用完成并返回用户态时能进行处理机调度
【答案】C 。
【解析】对于A 、B 、D 显然是可以进行处理机调度的, 对于C , 当进程处于临界区时, 只要不破坏临界资源的使用规则, 是不会影响处理机调度的, 比如, 通常访问临界资源可能是慢速的外设(如打印机) , 如果在进程访问打印机时, 不能处理机调度, 那么系统的性能将是非常低的。几种不进行处理机调度的情况如下:
①在处理机中断的过程中;
②进程在操作系统内核程序临界区中;
③其他需要完全屏蔽中断的原子操作过程中。
9． 单处理机系统中，可并行的是（ ）.
(1)进程与进程
(2)处理机与设备
(3)处理机与通道
(4)设备与设备
A. (1)、(2)和(3)
B. (1)、(2)和(4)
C. (1)、(3)和(4)
D. (2)、(3)和(4)
【答案】D
【解析】注意区分并发和并行. 在单处理机系统中，进程只能并发. 微观上同一时刻占用处理机的进程只有一个，因此，进程之间不是并行的. 通道是独立于CPU 控制的输入/输出的设备，处理机与通道两者是可以并行. 显然，设备和设备之间也是可以并行的.
10．一棵二叉树高度为h ，所有结点的度或为0或为2，则这棵二叉树最少有（ ）个结点。
A.2h
B.2h ﹣1
C.2h ＋l
D.h ＋1
【答案】B
【解析】此树满足哈夫曼树，除根节点外每层有两个节点。