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

一、应用题

1． 将下列出三棵树组成的森林转换为二叉树（只要求给出转换结果）。

图1

【答案】森林转换为二叉树分以下三步：

（1）连线（将兄弟结点相连，各树的根看作兄弟）。

（2）切线（保留最左边子女为独生子女，将其他子女分支切掉）。 （3）旋转（以最左边树的根为轴. 顺时针向下旋转45度）。 所以由上面三棵树转换得到的二叉树如图2所示：

图2

2． 假设计算机系统采用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 。综上所述，读取磁道上所有扇区所花的总时间为

则平均旋

转延迟为5ms ，总的旋转延迟时间为20ms ，读取一个扇区的平均时间为0.1ms , 故读取4个扇区所

（3）采用先来先服务（FCFS ）调度策略更高效，因为Flash 半导体存储器的物理结构不需要考虑寻道时间和旋转延迟，可直接按请求的先后顺序服务。

3． 为什么在倒排文件组织中，实际记录中的关键字域可删除以节约空间? 而在多重表结构中这样做为什么要牺牲性能？

【答案】因倒排文件组织中，倒排表有关键字值及同一关键字值的记录的所有物理记录号，可方便地查询具有同一关键字值的所有记录；而多重表文件中次关键字索引结构不同，删除关键字域后查询性能受到影响。

4． 用单链表保存m 个整数，节点的结构为（data , link ）, 且点而删除其余绝对值相等的节点。

例如若给定的单链表head 如下

（n 为正整数）。现要求

设计一个时间复杂度尽可能高效地算法，对于链表中绝对值相等的节点，仅保留第一次出现的节

删除节点后的head 为

要求

（1）给出算法的基本思想 （2）使用c 或

语言，给出单链表节点的数据类型定义。

语言描述算法，关键之处给出注释。

（3）根据设计思想，采用c 或【答案】（1）算法思想：

定义一个大小为n 的布尔数组flag ，初始时所有的元素都赋值为false , 用来标识遍历过程中是否出现元素绝对值为flag 的节点。然后遍历链表，遍历过程中，每一个当前结点data 域的绝对值，则将flag 位置为真（true ）所对应的flag 位：若为真，则删除该结点；若为假（false ）。

（2）节点的数据结构定义如下：

（3）

全局数组标志节点的绝对值是否出现过

如果此绝对值已经在节点值的绝对值中出现过则删除该节点

否则，将flag 中对应的位置置为true ，并将指针指向下一个元素

（4）说明所涉及算法的时间复杂度和空间复杂度。