2018年西安交通大学生命科学与技术学院814计算机基础综合之数据结构考研仿真模拟五套题
● 摘要
一、单项选择题
1． 下列选项中会导致进程从执行态变为就绪态的事件是（ ）。
A. 执行P(wait)操作
B. 申请内存失败
C. 启动设备
D. 被高优先级进程抢占
【答案】D
【解析】D 项, 被高优先级进程抢占, 进程会由执行态变为就绪态。ABC 三项, 程序由于缺少资源而由执行态转为阻塞态。
2． 某计算机处理器主频为50MHz , 采用定时查询方式控制设备A 的
则CPU 用于设备A 的
A. B. C. D.
【答案】C , 查询程序运行一次所用的时钟周期数至少为500。在设备A 工作期间, 为保证数据不丢失, 每秒需对其查询至少200次, 的时间占整个CPU 时间的百分比至少是（ ）。 【解析】对于设备A , 每秒中查询至少200次, 每次查询至少500个时钟周期, 总的时钟周期数为100000, 又因为处理器主频为50MHz 。所以CPU 用于设备A 的
百分比至少为100000/50。
3． 下列选项中, 不能改善磁盘设备
A. 重排请求次序
B. 在一个磁盘上设置多个分区
C. 预读和滞后写
D. 优化文件物理块的分布
【答案】B 。
【解析】
磁盘
的一个瓶颈。“重排性能主要是指其读写速度。相对而言,
磁盘的性能是计算机性能提高请求次序”可以优化磁臂调度的算法, 减少读写时间, 故正确; “预读和滞的时间占整个CPU 时间的性能的是（ ）。 后写”是利用内存作为磁盘的缓存, 使得对磁盘的访问变为对内存的访问, 也可以在总体上提高其
性能; “优化文件物理块的分布”减少磁臂调度和旋转调度的等待时间, 也可以提高磁盘而磁盘分区仅在磁盘空间的组织上进行划分, 对磁盘
盘设备性能的, 故答案为B 。
4． 和顺序栈相比，链栈有一个比较明显的优势是（ ）。
A. 通常不会出现栈满的情况
B. 通常不会出现栈空的情况
C. 插入操作更容易实现
D. 删除操作更容易实现
【答案】A
5． 若一棵完全二叉树有768个结点, 则该二叉树中叶结点的个数是（ ）。
A.257
B.258
C.384
D.385
【答案】C
【解析】由
和可知, , 即, 显然
性能, 性能的提升没有什么帮助, 是不能改善磁则384, 所以二叉树的叶结点个数是384。
还可以根据完全二叉树的另一个性质:
最后一个分支结点的序号为, 故非叶子结点数为384, 而叶子结点的个数为) 。 。(表示不大于x 的最大整数, 比如
6． 数据序列(8，9，10，4，5，6，20，1，2) 只能是下列排序算法中的（ ）的两趟排序后的结果。
A. 选择排序
B. 起泡排序
C. 插入排序
D. 堆排序
【答案】C
【解析】选择排序、起泡排序和堆排序两趟排序后，在序列的某一端应该有序列的两个最大值或者最小值。
7． 二叉树在线索化后，仍不能有效求解的问题是（ ）。
A. 前序线索二叉树中求前序后继
B. 中序线索二叉树中求中序后继
C. 中序线索二叉树中求中序前驱
D. 后序线索二叉树中求后序后继
【答案】D
【解析】后序线索二叉树求后序后继要分3种情况，比较复杂，不是仅仅线索化后就能求解的，算法上还要要分情况讨论。
8． 进程P0和P1的共享变量定义及若进程P0和P1访问临界资源的类C 伪代码实现如下:
则并发执行进程P0和PI 时产生的情况是（ ）.
A. 不能保证进程互斥进入临界区，会出现“饥饿”现象
B. 不能保证进程互斥进入临界区，不会出现“饥饿”现象
C. 能保证进程互斥进入临界区，会出现“饥饿”现象
D. 能保证进程互斥进入临界区，不会出现“饥饿”现象
【答案】D
【解析】这是皮特森算法(Peterson’SAlgorithm)的实现，保证进入临界区的进程合理安全. 该算法为了防止两个进程为进入临界区而无限期等待，设置变量tum ，表示不允许进入临界区的编号，每个进程在先设置自己标志后再设置turn 标志，不允许另一个进程进入，这时，再同时检测另一个进程状态标志和不允许进入标志，这样可以保证当两个进程同时要求进入临界区时只允许一个进程进入临界区. 保存的是较晚的一次赋值，则较晚的进程等待，较早的进程进入. 先到先人，后到等待，从而完成临界区访问的要求.
9． 输入序列为ABC ，可以变为CBA 时，经过的栈操作为（ ）。
A.push ，pop ，push ，pop ，push ，pop
B.push ，push ，push ，pop ，pop ，pop
C.push ，push ，，pop ，pop ，push ，pop
D.push ，pop ，push ，push ，pop ，pop
【答案】B
【解析】根据输入序列和输出序列可知，输入序列全部进找，然后再出找。从中可以看出，push 的数目始终大于等于pop 的数目。
相关内容
相关标签