2017年浙江理工大学计算机专业基础(同等学力加试)之数据结构复试实战预测五套卷
● 摘要
目录
2017年浙江理工大学计算机专业基础(同等学力加试) 之数据结构复试实战预测五套卷（一） . . 2
2017年浙江理工大学计算机专业基础(同等学力加试) 之数据结构复试实战预测五套卷（二） . . 9 2017年浙江理工大学计算机专业基础(同等学力加试) 之数据结构复试实战预测五套卷（三） 17 2017年浙江理工大学计算机专业基础(同等学力加试) 之数据结构复试实战预测五套卷（四） 24 2017年浙江理工大学计算机专业基础(同等学力加试) 之数据结构复试实战预测五套卷（五） 30
一、应用题
1．
设与记录
对应的关键字分别是
进行交换。
之前全部记录（其的关键字一定如果存在
和
使得
且成立，试证明经过一趟起泡后，一定有记录与值。由题假设知中包括在之前且则即说明和【答案】起泡排序思想是相邻两个记录的关键字比较，若反序则交换，一趟排序完成得到极是反序；设对于）中关键字最大为，故经过起泡排序前i-2次比较后，
为又因故和Rf 为反序，由此可知和必定交换，证毕。
2． 某请求分页系统的局部页面置换策略如下：系统从0时刻开始扫描，每隔5个时间单位扫描
，本轮没有被访问过的页框将被系统回收，并放入到空闲页框链一轮驻留集（扫描时间忽略不计）
尾，其中内容在下一次被分配之前不被清空。当发生缺页时，如果该页曾被使用过且还在空闲页框链表中，则重新放回进程的驻留集中；否则，从空闲页框链表头部取出一个页框。假设不考虑其他进程的影响和系统开销，初始时进程驻留集为空。目前系统空闲页框链表中页框号依次为32、15、21、41。进程
（1）访问
（2）访问
（3）访问
【答案】
（1）页框号为21。因为起始驻留集为空，而0页对应的页框为空闲链表中的第三个空闲页框，其对应的页框号为21。
（2）页框号为32。理由：因11>10故发生第三轮扫描，页号为1、3的页框32、15在第二轮已处于空闲页框链表中，此刻1页又被重新访问，因此应被重新放回到驻留集中。其页框号为32。
（3）页框号为41。理由：因为第2页从来没有被访问过，它不在驻留集中，因此从空闲页框链表中取出链表头的页框41，页框号为41。
（4）适合。理由：如果程序的时间局部性越好，从空闲页框链表中重新取回的机会越大，该策略的优势越明显。
P 依次访问的<虚拟页号，访问时刻>是
：请回答下列问题。 时，对应的页框号是什么？ 时，对应的页框号是什么? 说明理由。 . 时，对应的页框号是什么? 说明理由。 （4）该策略是否适合于时间局部性好的程序? 说明理由。
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． 某程序中有如下循环代码段p :
P 起始地址 为0804 8100H，对应的汇编代码和机器代码如下表所示
假设编译时变量sum 和i 分别分配在寄存器R1和R2中。常量N 在寄存器R6中，数组A 的首地址在寄存器R3中，程序段
执行上述代码的计算机M 采用32位定长指令字，其中分支指令Bne 采用如下格式，
Op 为操作码：Rs 和Rd 为寄存器编号：OFFSET 为偏移量，用补码表示。请回答下列问题，并说明理由。
（1）M 的存储器编址单位是什么？
（2）已知sll 指令实现左移功能，数组A 中每个元素占多少位？
（3）表中bne 指令的OFFSET 字段的值是多少？已知bne 指令采用相对寻址方式，当前PC 内容为bne 指令地址，通过分析表中指令地址和bne 指令内容，推断出bne 指令的转移目标地址计算公式。
（4）若M 采用如下“按序发射、按序完成”的5级指令流水线：IF （取指）、ID （译码及
，且硬件不采取任何转发措施，分取数）、EXE （执 行）、MEM （访存）、WB （写回寄存器）
支指令的执行均引起3个时钟周期阻塞，则P 中哪些指令的执行会由于数据相关而发生流水线阻塞？哪条指令的执行会发生控制冒险？为什么指令1 的执行不会因为与指令5的数据相关而发生阻塞？
【答案】（1）由题可知，指令为32为即4个字节，而程序执行时是以4为间隔逐条取指令的，故可知M 的存储器是采用字节编址。
（2）32位，因为sll 中实现左移，而（R2） <<2 R4即左移两位就是乘以4，所以是
位
（3）由Bne 的指令格式可知其OFFSET 为指令的后16位，而Bne 的机器码码为1446 FFFAH，所以Bne 的OFFSET 为FFFAH 即-6。
由题可知Bne 采用相对寻址方式，故有效地址
为当前Bne 指令的地址
即而取完Bne 而PC 的值指令后
，
而要跳转到指令1的地址08048100H ，两者相差了18H 也
就是24个字节，而OFFSET 是-6, 故转移目标地址计算公式为（PC
）
（4）由指令序列可知，指令1需写R4而指令2需读R4, 故指令2会因为数据相关而发生阻塞，同理指令3、指令4也会因为数据相关而发生阻塞；而指令6为分支指令，故其存在控制冒险。因为分支指令会有3个时钟周期的阻塞，故指令1的执行不会因为指令5的数据相关而发生阻塞。
5． 将算术表达式（（a+b）+c*（d+e）+f）*（g+h）转化为二叉树。
【答案】该算术表达式转化的二叉树如图所示。
图
相关内容
相关标签