2017年东北师范大学数据结构(跨学科加试)考研复试核心题库
● 摘要
一、应用题
1． 在如图1所示的伙伴系统中，回收两块首地址分别为768及128、大小为的存储块，请画出回收后该伙伴系统的状态图。
图1
【答案】因为
小为
因为所以768和所以首址大小为互为伙伴，伙伴合并后，首址为768，块大的块和首址512、大小为的块合并，成为首址
将其插入可利用空间表中。回其伙伴地址为512、；大小为的空闲块。因为收后该伙伴系统的状态图如图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． 给出一组关键字：29，18，25，47，58，12，51，10，分别写出按下列各种排序方法进行排序时的变化过程：
（1）归并排序，每归并一次书写一个次序。
（2）快速排序，每划分一次书写一个次序。
（3）堆排序，先建成一个堆，然后每从堆顶取下一个元素后，将堆调整一次。
【答案】（1）2—路归并第一趟：18，29，25，47，12，58，10，51:
第二趟：18，25，29， 47，10，12，51，58;
第三趟：10，12，18，25，29，47，51，58
（2）快速排序第一趟：10，18，25，12，29，58，51，47;
第二趟：10，18，25，12，29，47，51，88;
第三趟：10，12，18，25，29，47，51，88
（3）堆排序
建大堆：58，47，51，29，18，12，25，10;
①51，47，25，29，18，12，10，58;
②47，29，25，10，18，12，51，58;
③29，18，25，10，12，47，51，58;
④25，18，12，10，29，47，51，58;
⑤18，10，12，25，29， 47，51，58;
⑥12，10，18，25，29，47，51，58;
⑦10，12，18，25，29， 47，51，58
4． 某计算机采用16位定长指令字格式，其CPU 中有一个标志寄存器，其中包含进位/借位标志CF 、零标志ZF 和符号标志NF 。假定为该机设计了条件转移指令，其格式如下：
其中，00000为操作码OP ; C、Z 和N 分别为CF 、ZF 和NF 的对应检测位，某测位为1时表示需检测对应标志，需检测的标志位中只要有一个为1就转移，否则就不转移，例如，
若
OFFSET 是相对偏移则需检测CF 和NF 的值，当CF=1或NF=1时发生转移；
量，用补码表示。转移执行时，转移目标地址为
为请回答下列问题。
（1）该计算机存储器按字节编址，还是按字编址？该条件转移指令向后（反向）最多可跳转最多少条指令？
（2） 某条件转移指令的地址为200CH ，指令内容如下图所示，若该执行
时
则该指令执行后PC 的值是多少？若该指令执行时
则该指令执行后PC 的值又是多少？请给出计算过程。
（3）实现“无符号数比较小于等时转移”功能的指令中，C 、Z 和N 应各是什么？
（4）以下是该指令对应的数据通路示意图，要求给出中部件①〜③的名称或功能说明。 顺序执行时，下条指令地址