2018年江苏省培养单位南京天文光学技术研究所864程序设计之数据结构考研仿真模拟五套题
● 摘要
一、单项选择题
1． 某系统有n 台互斥使用的同类设备, 3个并发进程需要3, 4, 5台设备, 可确保系统不发生死锁的设备数n 最小为（ ）
A.9 B.10 C.11 D.12
【答案】B 【解析】
2． 设有向图G=(V, E) , 顶点集
边集
,
,
若从顶点V0开始对图进行深度优先遍历, 则可能得到的不同遍历序列个数是（ ）。 A.2 B.3 C.4 D.5
【答案】D
【解析】根据题意知有向图的结构如图所示。深度优先遍历的特点是尽可能先对纵深方向进行搜索, 所以可能得到的不同遍历序列分别是:
①④
'
; ②; ⑤
; ③。
性能的是（ ）。
;
3． 下列选项中, 不能改善磁盘设备
A. 重排
请求次序
B. 在一个磁盘上设置多个分区 C. 预读和滞后写
D. 优化文件物理块的分布 【答案】B 。 【解析】
磁盘
性能主要是指其读写速度。相对而言,
磁盘的
性能是计算机性能提高
的一个瓶颈。“重排请求次序”可以优化磁臂调度的算法, 减少读写时间, 故正确; “预读和滞
性能,
后写”是利用内存作为磁盘的缓存, 使得对磁盘的访问变为对内存的访问, 也可以在总体上提高其性能; “优化文件物理块的分布”减少磁臂调度和旋转调度的等待时间, 也可以提高磁盘而磁盘分区仅在磁盘空间的组织上进行划分, 对磁盘
性能的提升没有什么帮助, 是不能改善磁
盘设备性能的, 故答案为B 。
4． 有向带权图如下图图所示, 若采用迪杰斯特拉(Dijkstta)算法求从源点a 到其他各顶点的最短路径, 则得到的第一条最短路径的目标顶点是b , 第二条最短路径的目标顶点是c , 后续得到的其佘各最短路径的目标顶点依次是（ ）。
图 有向带权图
A.d , e , f
B.e , d , f C.f , d , e D.f , e , d 【答案】C 。
【解析】本题主要考查Dijkstta 算法的思想和解题步骤。题目执行算法过程中各步的状态如下表所示。执行Dijkstta 算法过程中各步的状态表, 故后续目标顶点依次为f , d , e 。
5． 对于循环队列（ ）。
A. 无法判断队列是否为空 B. 无法判断队列是否为满 C. 队列不可能满 D. 以上说法都不是 【答案】D
【解析】循环队列也会出现队列满的情况，并且循环队列也可以判断是否为空或满。至少可以通过两种方法进行判断:①另设一个布尔变量来区别队列是空还是满；②队满时，
(rear+1) font 。
6． 由3个“1”和5个“0”组成的8位二进制补码, 能表示的最小整数是（ ）。
A.-126 B.-125 C.-32 D.-3
【答案】B
【解析】能表示的最小整数一定是负数, 符号位占用1个“1”; 负数的补码和原码的转化是:原码符号位不变, 数值部分按位取反, 末位加“1”。
因此最小的整数的补码是“10000011”, 原码为“111111101”, 即。
7． 设系统缓冲区和用户工作均采单, 从外读入1个数据块到系统缓冲区的时间为100, 从系统缓冲区读入1个数据块到用户工作区的时间为5, 对用户工作区中的1个数据块行分析的时间为90(如下图所示) 。进程从外设读入并分析2个数据块的最短时间是（ ）
图
A.200 B.295 C.300 D.390
【答案】C
【解析】数据块1从外设到用户工作区的总时间为105, 在这段时间中数据块2没有进行操作。在数据块1进行分析处理时, 数据块2从外设到用户工作区的总时间为105, 这段时间是并行的。再加上数据块2进行处理的时间90, 总共是300, 故答案为C 。
8． 系统为某进程分配了4个页框, 该进程已访问的页号序列为2, 0, 2, 9, 3, 4, 2, 8, 2, 3, 8, 4, 5, 若进程要访问的下一页的页号为7, 依据LRU 算法, 应淘汰页的页号是（ ）。
A.2 B.3 C.4
相关内容
相关标签