2017年聊城大学数据结构(同等学力加试)复试实战预测五套卷
● 摘要
一、应用题
1． 带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径，假设从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法：
①该最短路径初始时仅包含初始顶点，令当前顶点为初始顶点； ②选择离最近且尚未在最短路径中的顶点V ，加入到最短路径中，修改当前顶点
请证明之；否则请举例说明。
【答案】题目中方法不一定能（或不能）求得最短路径。举例说明：
图（a ）
图（b ）
图（a ）中，假设初始顶点1到目标顶点4之间有一条边，权值x=2。显然图（a ）中这顶点1和顶点4之间的最短路径长度为2。若按照题目中给定的方法找到的路径为初始顶点1经过中间结点2、3到目标顶点4, 即初始顶
点
显然， 一目标顶点4, 所经过的边的权值分别
为 ③重复步骤②，直到是目标顶点时为止。请问上述方法能否求得最短路径? 若该方法可行，
因此按照题目中给定的方法所求得的路径并不是这两个顶点之间的最短路径。
图（b ）中，假设初始顶点为1、目标顶点为4, 欲求从顶点1到顶点4之间的最短路径。显然，按照题目中给定的方法无法求出顶点1到顶点4的路径，而事实上顶点1到顶点4的最短路径为1到4。
2． 某计算机主存按字节编址，逻辑地址和物理地址都是32位，页表项大小为4字节。请回答下列问题。
（1）若使用一级页表的分存储管理方式，逻辑地址结构为：
则页的大小是多少字节？页表最大占用多少字节？
（2）若使用二级页表的分存储管理方式，逻辑地址结构为：
设逻辑地址为LA ，请分别给出其对应的页目录号和表索引达式。
（3）采用（1）中的分页存储管理方式，一个代码段起始逻辑地址为00008000H ，其长度为8KB ，被装载到从物理地址00900000H 开始的连续主存空间中。页表从主存0020 0000H 0020 0000H 开始的物理地址处连续存放，如下图所示（地址大小自下向上递增）。请计算出该代码段对应的两个页表项物理地址、这中框号以及计算出该代码段对应的两个页表项物理地址、这中框号以及计算出该代码段对应的两个页表项物理地址、这两个页表项中的框号以及代码页面2的起始物理地址。
【答案】
（1）因为页内偏移量是12位所以页大小为4KB 页表项数为页表索引可表示为：
表项，所以第8个页表项的物理地址=页表起始地
址
如下图所示。
该一级页表最大为 页表项的字节
数（2）页目录号可表示为：（3）代码页面1的逻辑地址为0000 8000H, 表明其位于第8个页处，对应页表中的第8个页
3． 设
中。 五个字符的编码分别为1，2，3，4，5，并设标识符依以下次序出现
：要求用哈希（Hash ）方法将它们存入具有10个位置的表
（1）将上述关键字（标识符）构造一个哈希函数，使得发生冲突尽可能地少；
（2）线性探测再散列法解决冲突。写出上述各关键字在表中位置。
【答案】（1）构造的哈希函数为：哈希函数（2）关键字在表中的位置如表所示：
表 关键字在表中的位置
（关键字各字符编码之和）
4． 将下列出三棵树组成的森林转换为二叉树（只要求给出转换结果）。
图1
【答案】森林转换为二叉树分以下三步：
（1）连线（将兄弟结点相连，各树的根看作兄弟）。
（2）切线（保留最左边子女为独生子女，将其他子女分支切掉）。
（3）旋转（以最左边树的根为轴. 顺时针向下旋转45度）。
所以由上面三棵树转换得到的二叉树如图2所示：
图2
5． 已知一棵二叉树的后序遍历序列为EICBGAHDF , 同时知道该二叉树的中序遍历序列为CEIFGBADH ， 试画出该二叉树。
【答案】该二叉树如图所示：