2017年杭州电子科技大学数据结构考研复试核心题库
● 摘要
一、应用题
1． 某计算机字长16位，主存地址空间大小为128KB , 按字编址，采用单字长指令格式，指令各字段定义如下：
源操作数目的操作数
转移指令采用相对寻址方式，相对偏移量用补码表示，寻址方式定义如下：
注：（X ）表示存储器地址X 或寄存器X 的内容。请回答下列问题：
（1）该指令系统最多可有多少条指令? 该计算机最多有多少个通用寄存器? 存储器地址寄存器（MAR ）和存储器数据寄存器（MDR ）至少各需要多少位？
（2）转移指令的目标地址范围是多少？
（3）若操作码0010B 表示加法操作（助记符为add ）, 寄存器R4和R5的编号分别为100B 和101B ，R4的内容为1234H ，R5的内容为5678H , 地址1234H 的内容为5678H ，地址5678H 中的内容为1234H ，则汇编语句
改变后的内容是什么？
【答案】（1）指令操作码占4位，则指令系统最多可有
量为128KB ，计算机字长为16位，故主存有
需16位。
（2）由于寄存器字长为16位，所以转移指令的目标地址范围为0000H 〜FFFFH 。。
（3）汇编语句
寄存器
R5和地址为5678H 的存储单元的内容会改变，改变后的内容分别为
：
第 2 页，共 33 页 （逗号前为源操作数，逗号后为目的操作数）对应的机器码是什么（十六进制表示）？该指令执行后，哪些寄存器和存储单元的内容会改变? 条不同的指令；指令操作上占6个通用寄存器；主存容个存储单元，故MDR 和MAR 至少各位，寻址方式占3位，于是寄存器编号占3位，该计算机最多可以有+对应的机器码为该指令执行后，
2． 设某文件经内排序后得到100个初始归并段（初始顺串），若使用多路归并排序算法，并要求三趟归并完成排序，问归并路数最少为多少？
【答案】设归并路数为k ，归并趟数为s ，则因且k 为整数，故k=5，即最少5-路归并完成排序。
3． 在二叉树的Llink-Rlink 存储表示中，引入“线索”的好处是什么？
【答案】在二叉链表表示的二叉树中，引入线索的目的主要是便于査找结点的前驱和后继，因为若知道各结点的后继，二叉树的遍历就非常简单。利用二叉链表结构查结点的左右子女非常方便. 但其前驱和后继是在遍历中形成的。为了将非线性结构二叉树的结点排成线性序列，利用结点的空链域，左链为空时作为前驱指针，右链为空时作为后继指针。再引入左右标记ltag 和rtag ，规定：当ltag=0时，lchild 指向左子树，当ltag=1时，lchild 指向前驱：当rtag=0时，rchild 指向右子树，当rtag=l时，rctiild 指向后继。这样，在线索二叉树（特别是中序线索二叉树）上遍历就消除了递归，也不使用栈（利用后序线索二叉树査后扔继续要栈）。
4． 某请求分页系统的局部页面置换策略如下：系统从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）适合。理由：如果程序的时间局部性越好，从空闲页框链表中重新取回的机会越大，该策略的优势越明显。
第 3 页，共 33 页 P 依次访问的<虚拟页号，访问时刻>是
：请回答下列问题。 时，对应的页框号是什么？ 时，对应的页框号是什么? 说明理由。 . 时，对应的页框号是什么? 说明理由。 （4）该策略是否适合于时间局部性好的程序? 说明理由。
5． 对给定文件（28，07，39，10，65，14，61，17，50，21）选择第一个元素28进行划分，写出其快速排序第一遍的排序过程。
【答案】快速排序的思想如下：首先将待排序记录序列中的所有记录作为当前待排序区域，
，凡其关键字不大干枢轴的记录均移动至该记录之前，以第一个记录的关键字作为枢轴（或支点）
凡关键字不小于枢轴的记录均移动至该记录之后。致使一趟排序之后，记录的无序序
割成两部分：和和
且
将分然后再递归地将进行快速排序。快速排序在记录有序时蜕变为起泡排序，可用“三者取中”法改善其性能，避免最坏情况的出现。本题解答如下：
初始序列：[28]，07，39，10，65，14，61，17，50，21
21移动：21，07，39，10，65，14，61，17，50，[]
39移动：21，07，[]，10，65，14，61，17，50，39
17移动：21，07，17，10，65，14，61，[]，50，39
65移动：21，07，17，10，[]，14，61，65，50，39
14移动：21，07，17，10，14，[28]，61，65，50，39
6． 设度为m 的树采用多重链表存储，毎个结点有m+1个域，其中有1个数据域，m 个指向孩子的指针。 则空指针的数目是多少？说明这种存储方式的利弊。
【答案】（1）空指针数目：n （n>0）个结点的m 度树共有nm 个链域，除根结点外，每个结点均有一个指针所指，故该树的空链域有nm-（n-1）=n（m-l ）+1个。
（2）利弊：这种存储结构统一，便于处理但空链域造成存储效率低。
7． 带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径，假设从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法：
①该最短路径初始时仅包含初始顶点，令当前顶点为初始顶点； ②选择离最近且尚未在最短路径中的顶点V ，加入到最短路径中，修改当前顶点
请证明之；否则请举例说明。
【答案】题目中方法不一定能（或不能）求得最短路径。举例说明：
图（a ）
图（b ）
第 4 页，共 33 页 ③重复步骤②，直到是目标顶点时为止。请问上述方法能否求得最短路径? 若该方法可行，