2017年兰州大学数据结构复试仿真模拟三套题
● 摘要
一、应用题
1． 对给定文件（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
2． 设哈希（Hash ）表的地址范围为0～17，哈希函数为：造出哈希表，试回答下列问题：
（1）画出哈希表示意图；
（2）若查找关键字63，需要依次与哪些关键字比较？ （3）若查找关键字60，需要依次与哪些关键字比较？
（4）假定每个关键字的查找概率相等，求查找成功时的平均查找长度。 【答案】（1）哈希表示意图如表所示：
表 哈希示意图
（2）查找关键字63时，由于63比较。
（3）查找关键字60时，由于（4）
为关键字，用
线性探测再散列法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49）
所以需要依次与31，46，47，32，17，哈希地址12内为空，查找失败。
3． 设输入序列为2, 3, 4, 5, 6, 利用一个栈能得到序列2, 5, 3, 4, 6吗? 栈可以用单链表实现吗？
【答案】不能得到序列2, 5, 3, 4, 6。因为根据输入序列，2进栈之后，2出找，3, 4, 5依次进栈。5出栈，此时栈中剩下3, 4。因为4在栈顶，所以4应该比3先出栈，不能得到提供的序列。栈可以用单链表实现，这就是链栈。由于栈只在栈顶操作，所以链栈通常不设头结点。 4． 假设以S 和X 分别表示入栈和出栈操作，则对初态和终态均为空的栈操作可由S 和X 生成的序列表示（如SXSX ）。
（1）试指出判别给定序列是否合法的一般规则；
（2）两个不同合法序列（对同一输入序列）能否得到相同的输出元素序列? 如能得到，请举列说明。
【答案】（1）通常有两条规则。第一是给定序列中S 的个数和X 的个数相等；第二是从给定序列的开始，到给定序列中的任一位置，S 的个数要大于或等于X 的个数。
（2）可以得到相同的输出元素序列。例如，输入元素为A , B , C , 则两个输入的合法序列ABC 和BAC 均可得到输出元素序列ABC 。对于合法序列ABC ，使用SXSXSX 操作序列；对于合法序列BAC ，使用SSXXSX 操作序列。
5． 带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径，假设从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法：
①该最短路径初始时仅包含初始顶点，令当前顶点为初始顶点；
②选择离最近且尚未在最短路径中的顶点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。
6． 对下面的关键字集
若查找表的装填因子为0.8，采用线性探
测再哈希方法解决冲突，做：（1）设计哈希函数；（2）画出哈希表；（3）计算查找成功和查找失败的平均查找长度；（4）写出将哈希表中某个数据元素删除的算法。
【答案】（1）由于装填因子为0.8，关键字有8个，所以表长为哈希函数，哈希函数为
（2）哈希表如表所示：
表 哈希表
（3）计算查找失败时的平均查找长度，必须计算不在表中的关键字，
当其哈希地址为
时的查找次数。本例中
（4）算法如下：
7． 画出对算术表达式表所示。
表 操作数栈和运算符找的变化过程
求值时操作数栈和运算符栈的变化过程。
求值，过程如
故查找失败和查找成功时的平均查找长度分别为：
用除留余数法设计
【答案】设操作数栈是opnd ，运算符栈是optr ，对算术表达式