2018年东北农业大学电气与信息学院838数据结构考研强化五套模拟题
● 摘要
一、单项选择题
1． 进程P0和P1的共享变量定义及若进程P0和P1访问临界资源的类C 伪代码实现如下:
则并发执行进程P0和PI 时产生的情况是（ ）.
A. 不能保证进程互斥进入临界区，会出现“饥饿”现象
B. 不能保证进程互斥进入临界区，不会出现“饥饿”现象
C. 能保证进程互斥进入临界区，会出现“饥饿”现象
D. 能保证进程互斥进入临界区，不会出现“饥饿”现象
【答案】D
【解析】这是皮特森算法(Peterson‟SAlgorithm)的实现，保证进入临界区的进程合理安全. 该算法为了防止两个进程为进入临界区而无限期等待，设置变量tum ，表示不允许进入临界区的编号，每个进程在先设置自己标志后再设置turn 标志，不允许另一个进程进入，这时，再同时检测另一个进程状态标志和不允许进入标志，这样可以保证当两个进程同时要求进入临界区时只允许一个进程进入临界区. 保存的是较晚的一次赋值，则较晚的进程等待，较早的进程进入. 先到先人，后到等待，从而完成临界区访问的要求.
2． 在有向图的邻接表存储结构中，顶点v 在链表中出现的次数是（ ）。
A. 顶点v 的度
B. 顶点v 的出度
C. 顶点v 的入度
D. 依附于顶点v 的边数
【答案】B
【解析】在有向图中，第j 个链表中的结点个数只是顶点的出度，为求入度，必须遍历整个邻接表。因此顶点V 在链表中出现的次数是顶点V 的出度。
3． 当系统发生抖动(thrashing)时, 可以采取的有效措施是（ ）。
Ⅰ. 撤销部分进程
Ⅱ. 增加磁盘交换区的容量
Ⅲ. 提高用户进程的优先级
A. 仅Ⅰ
B. 仅Ⅱ
C. 仅Ⅲ
D. 仅Ⅰ、Ⅱ
【答案】A
【解析】“抖动”现象是指刚刚被换出的页很快又要被访问, 为此, 又要换出其他页, 而该页又很快被访问, 必须换入, 如此频繁地置换页面, 以致操作系统的大部分时间都花在页面置换上, 引起系统性能下降甚至崩溃。引起系统抖动现象的原因是对换的信息量过大, 内存容量不足, 置换算法选择不当。所以解决的办法就是降低交换页面数量, 加大内存容量, 改变置换选择算法。但是降低交换页面数量和改变置换选择算法对于一个应用系统来讲是不可能的, 只能增加内存容量。增加内存容量可以是直接添加物理内存(大型计算机都可以在不关机的情况下增加物理内存条) , 或者, 降低进程数量, 相对地增加内存。而增加交换区容量并不能解决物理内存不足的问题, 提高用户进程的优先级会使系统的状态更加恶化。
4． 若平衡二叉树的高度为6, 且所有非叶结点的平衡因子均为1, 则该平衡二叉树的结点总数为（ ）。
A.12
B.20
C.32
D.33
【答案】B 。
【解析】本题的实际问题是, 具有6层结点的平衡二叉树含有最少的结点数是多少。
深度为h 的平衡二叉树中含有的最少结点数, 有
由此可得。对应的平衡二叉树如下图所示。 表示
5． 数据链路层采用后退N 帧(GBN)协议，发送方已经发送了编号为0〜7的帧. 当计时器超时，若发送方只收到0、2、3号帧的确认，则发送方需要重发的帧数是（ ）.
A.2
B.3
C.4
D.5
【答案】C
【解析】后退N 帧协议，即策略的基本原理是，当接收方检测出失序的信息帧后，要求发送方重发最后一个正确接收的信息帧之后的所有未被确认的帧；或者当发送方发送了N 个帧后，若发现该N 帧的前一个帧在计时器超时后仍未返回其确认信息，则该帧被判为出错或丢失，此时发送方就不得不重新发送出错帧及其后的N 帧. 本题收到3号帧的确认，说明0，1，2，3号帧已经收到，丢失的是4，5，6，7号帧，共4帧. 因此答案为C 项.
6． 在下图所示的平衡二叉树中, 插入关键字48后得到一棵新平衡二叉树。在新平衡二叉树中, 关键字37所在结点的左、右子结点中保存的关键字分别是（ ）。
A.13、48
B.24、48
C.24、53
D.24、90
【答案】C
【解析】题目中, 插入48以后, 树根结点的平衡因子由-1变为-2, 失去平衡。这属于RL(先右后左) 型平衡旋转, 需做两次(先右旋后左旋转) 旋转操作。过程如下图所示: