2017年湖南师范大学数据结构复试仿真模拟三套题
● 摘要
一、应用题
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 页，共 21 页
则平均旋
转延迟为5ms ，总的旋转延迟时间为20ms ，读取一个扇区的平均时间为0.1ms , 故读取4个扇区所
（3）采用先来先服务（FCFS ）调度策略更高效，因为Flash 半导体存储器的物理结构不需要
考虑寻道时间和旋转延迟，可直接按请求的先后顺序服务。
2． 队列可以用循环单链表来实现，故可以只设置一个头指针或者只设置一个尾指针。请你分析对于循环单链表实现的队列，用哪种方案更合适。
【答案】循环单链表若只设头指针，则出队操作时间复杂度是是
若只设尾指针，则出队和入队操作时间复杂度都是
列，设置一个尾指针更合适。
3． 对下面的关键字集
而如对操作时间复杂度
因此，用循环单链表来实现队
若查找表的装填因子为0.8，采用线性探
测再哈希方法解决冲突，做：（1）设计哈希函数；（2）画出哈希表；（3）计算查找成功和查找失败的平均查找长度；（4）写出将哈希表中某个数据元素删除的算法。
【答案】（1）由于装填因子为0.8，关键字有8个，所以表长为哈希函数，哈希函数为
（2）哈希表如表所示：
表 哈希表
（3）计算查找失败时的平均查找长度，必须计算不在表中的关键字，
当其哈希地址为
时的查找次数。本例中
（4）算法如下：
4． 快速排序的最大递归深度是多少? 最小递归深度是多少？
【答案】设待排序记录的个数为n ，则快速排序的最小递归深度为
第 3 页，共 21 页
用除留余数法设计
故查找失败和查找成功时的平均查找长度分别为：
最大递归深度n 。
5． 在一棵表示有序集S 的二叉搜索树（binary search tree ）中，任意一条从根到叶结点的路径将S 分为3部分：在该路径左边结点中的元素组成的集合S1:在该路径上的结点中的元素组成的集合S2:在该路径右边结点中的元素组成的集合S3; S=S1US2US3, 若对于任意的
是否总有a ≤b ≤c? 为什么？
【答案】该结论不成立。例如，本题中对于任一f 的左子树上。对于从a 到根结点路径上的所有均有a 6． 下面程序段的时间复杂度是什么？ 【答案】赋值语句一共被执行了m*n次，所以该程序段的时间复杂度是O （m*n）。 7． 设G=（V , E）以邻接表存储，如图所示，试画出图1的深度优先生成树和广度优先生成树。 ，可在S2中找到a 的最近祖先f 。a 在，有可能f 在b 的右子树上，因而a 也就在b 的右子树上，这时a>b，因此a 图1 【答案】设从顶点1开始遍历，则深度优先生成树如图2所示，广度优先生成树如图3所示： 图2 图3 8． 我们知道，对于n 个元素组成的线性表进行快速排序时，所需进行的比较次数与这n 个元素的初始排序有关。问： （1）当n=7时，在最好情况下需进行多少次比较? 请说明理由。 （2）当n=7时，给出一个最好情况的初始排序的实例。 （3）当n=7时，在最坏情况下需进行多少次比较? 请说明理由。 （4）当n=7时，给出一个最坏情况的初始排序的实例。 【答案】（1）在最好情况下，每次划分能得到两个长度相等的子文件。假设文件的长度 第 4 页，共 21 页