2017年武汉轻工大学数据结构(同等学力加试)考研复试核心题库
● 摘要
一、应用题
1． 设
中。
（1）将上述关键字（标识符）构造一个哈希函数，使得发生冲突尽可能地少；
（2）线性探测再散列法解决冲突。写出上述各关键字在表中位置。
【答案】（1）构造的哈希函数为：哈希函数（2）关键字在表中的位置如表所示：
表 关键字在表中的位置
2． 阅读下列算法，指出算法A 的功能和时间复杂性。
【答案】功能：将原单循环链表分解成两个单循环链表：其一包括结点h 到结点g 的前驱结点；另一个包括结点g 到结点h 的前驱结点。
时间复杂度：0（n ）。
3． 如果输入序列为123456, 试问能否通过栈结构得到以下两个序列：435612和135426; 请说明为什么不能或如何才能得到。
【答案】输入序列为123456, 不能得出435612, 其理由是，输出序列最后两元素是12, 前面4个元素（4356）得到后，栈中元素剩12, 且2在栈顶，栈底元素1不可能在栈顶元素2之前出栈。得到135426的过程如下：1入栈并出栈，得到部分输出序列1; 然后2和3入找，3出栈，部分输出序列变为13; 接着4和5入栈，5、4和2依次出栈，部分输出序列变为13542; 最后6入栈并出栈，得到最终结果135426。
五个字符的编码分别为1，2，3，4，5，并设标识符依以下次序出现
：要求用哈希（Hash ）方法将它们存入具有10个位置的表（关键字各字符编码之和）
4． 假设计算机系统采用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 半导体存储器的物理结构不需要
5． 在一棵表示有序集S 的二叉搜索树（binary search tree ）中，任意一条从根到叶结点的路径将S 分为3部分：在该路径左边结点中的元素组成的集合S1:在该路径上的结点中的元素组成的集合S2:在该路径右边结点中的元素组成的集合S3; S=S1US2US3, 若对于任意的
是否总有a ≤b ≤c? 为什么？
【答案】该结论不成立。例如，本题中对于任一
f 的左子树上。对于从a 到根结点路径上的所有
均有a 6． 画出对算术表达式 表所示。 表 操作数栈和运算符找的变化过程 ，可在S2中找到a 的最近祖先f 。a 在，有可能f 在b 的右子树上，因而a 也就在b 的右子树上，这时a>b，因此a 7． 用单链表保存m 个整数，节点的结构为（data , link ）, 且 点而删除其余绝对值相等的节点。 例如若给定的单链表head 如下 （n 为正整数）。现要求设计一个时间复杂度尽可能高效地算法，对于链表中绝对值相等的节点，仅保留第一次出现的节
相关内容
相关标签