当前位置：问答库＞考研试题

一、应用题

1． 假设计算机系统采用CSCAN （循环扫描）磁盘调度策略。使用2KB 的内存空间记录16384个磁盘块的空闲状态。

（1）请说明在上述条件下如何进行磁盘空闲状态的管理。

（2）设某单面磁盘旋转速度为每分钟6000转，每个磁道有100个扇区，相邻磁道间的平均移动时间为lms 。若在某时刻，磁头位于100号磁道处，并沿着磁道号增大的方向移动（如下图

，所示）磁道号请求队列为50, 90, 30, 120, 对请求队列中的每个磁道需要读取1个随机分布的扇区，则读完这4个扇区总共需要多少时间? 要求给出计算过程。

图

SSD 等），（3）如果将磁盘替换为随机访问的FLash 半导体存储器（如U 盘、是否有比CSCAN

更高效的磁盘调度策略? 若有，给出磁盘调度策略的名称并说明理由；若无，说明理由。

【答案】（1）采用位示图法管理磁盘空闲块，每一位表示一个磁盘块的状态，共需要16384/32=512个字节即2KB 的空间，正好可放在系统提供的内存中。

（2）采用CSCAN 调度算法，访问磁道的顺序和移动的磁道数如下表所示：

故移动的磁道数为20+90+20+40=170, 所花的时间为170ms 。由于转速为

花的时间为0.4ms 。综上所述，读取磁道上所有扇区所花的总时间为

第 2 页，共 35 页 则平均旋 转延迟为5ms ，总的旋转延迟时间为20ms ，读取一个扇区的平均时间为0.1ms , 故读取4个扇区所（3）采用先来先服务（FCFS ）调度策略更高效，因为Flash 半导体存储器的物理结构不需要

考虑寻道时间和旋转延迟，可直接按请求的先后顺序服务。

2． 证明：具有n 个顶点和多于n-1条边的无向连通图G —定不是树。

【答案】具有n 个顶点n-1条边的无向连通图是自由树，即没有确定根结点的树，每个结点均可当根。若边数多于n-1条，因一条边要连接两个结点，则必因加上这一条边而使两个结点多了一条通路，即形成回路。形 成回路的连通图不再是树。

3． 分析ISAM 文件（IndeXed Sequential Access Methord）和VSAM 文件（Virtual storage Access Methord ）的应用场合、优缺点等。

【答案】ISAM 是一种专为磁盘存取设计的文件组织形式，采用静态索引结构，对磁盘上的数据文件建立盘组、柱面、磁道三级索引。ISAM 文件中记录按关键字顺序存放，插入记录时需移动记录并将同一磁道上最后的一个记录移至溢出区，同时修改磁道索引项，删除记录只需在存储位置作标记，不需移动记录和修改指针。经过多次插入和删除记录后，文件结构变得不合理，需周期整理ISAM 文件。

VSAM 文件采用动态索引结构，文件只有控制区间和控制区域等逻辑存储单位，与外存储

树，作为文件的索引部分可实现顺链查找和从器中柱面、磁道等具体存储单位没有必然联系。VSAM 文件结构包括索引集、顺序集和数据集三部分，记录存于数据集中，顺序集和索引集构成

根结点开始的随机查找。

优缺点：与ISAM 文件相比，VSAM 文件有如下优点：动态分配和释放存储空间，不需对文件进行重组；能保持较高的查找效率，且查找先后插入记录所需时间相同。因此，基于

文件通常作为大型索引顺序文件的标准组织。

4． 简述广义表属于线性结构的理由。

【答案】广义表中的元素，可以是原子，也可以是子表，即广义表是原子或子表的有限序列，满足线性结构的特性：在非空线性结构中，只有一个称为“第一个”的元素，只有一个称为“最后一个”的元素，第一元素有后继而没有前驱，最后一个元素有前驱而没有后继，其余每个元素有唯一前驱和唯一后继。从这个意义上说，广义表属于线性结构。

5． 设内存中可利用空间已连成一个单链表，对用户的存储空间需求，一般有哪三种分配策略？

【答案】（1）首次适配法

从链表头指针开始查找，找到第一个大于等于所需空间的结点即分配。首次适配法适合事先不知道请求分配和释放信息的情况，分配时需查询，释放时插在表头。

（2）最佳适配法

链表结点大小增序排列，找到第一个大于等于所需空间的结点即分配。最佳适配法适用于请求分配内存大小范围较宽的系统，释放时容易产生存储量很小难以利用的内存碎片，同时保留那些很大的内存块以备将来可能发生的大内存量的需求，分配与回收均需查询。

（3）最差适配法

第 3 页，共 35 页 的VSAM

链表结点大小逆序排列，总从第一个结点开始分配，将分配后结点所剩空间插入到链表适当位置。最差适配法适合请求分配内存大小范围较窄的系统，分配时不查询，回收时查询，以便插入适当位置。

6． 某博物馆最多可容纳500人同时参观，有一个出入口，该出入口一次仅允许个通过。参观者的活动描述如下：

参观者进程i :

进门；

参观;

出门；

coend

请添加必要的信号量和P 、

V

的互斥与同步。

要求写出完整的过程，说明信号量含义并赋初值。

【答案】

定义两个信号量

博物馆可以容纳的最多人数

用于出入口资源的控制

参观者进程i :

进门；

7． 对给定文件（28，07，39，10，65，14，61，17，50，21）选择第一个元素28进行划分，写出其快速排序第一遍的排序过程。

【答案】快速排序的思想如下：首先将待排序记录序列中的所有记录作为当前待排序区域，

第 4 页，共 35 页 操作，以实现上述操作过程中