2017年西安电子科技大学数据结构复试实战预测五套卷
● 摘要
一、应用题
1． 阅读下面的算法，说明算法实现的功能。
【答案】本算法功能是将两个无头结点的循环链表合并为一个循环链表。Head1最后一个结点的链域指向head2, head2最后一个结点的链域指向headl ，headl 为结果循环链表的指针。
2． 为什么在倒排文件组织中，实际记录中的关键字域可删除以节约空间? 而在多重表结构中这样做为什么要牺牲性能？
【答案】因倒排文件组织中，倒排表有关键字值及同一关键字值的记录的所有物理记录号，可方便地查询具有同一关键字值的所有记录；而多重表文件中次关键字索引结构不同，删除关键字域后查询性能受到影响。
3． 画出同时满足下列两个条件的两棵不同的二叉树。
（1）按前序遍历二叉树的顺序为ABCDE 。
（2）高度为5其对应的树（森林）的高度最大为4。 【答案】（1）满足条件的二叉树如图1所示：
图1
（2）满足条件的二叉树如图2所示：
图2
4． 在改进了的（无回溯）字符串模式匹配中，要先求next 数组的值。下面是求nextval 值的算法。
{在模式P 中求nextval 数组的值
}
算法中第4行有【答案】第4行的
第六行中也有
两处比较语句相同。请分析说明此两处比较
语句的含义是什么? 分析此算法在最坏情况下的时间复杂度是多少？
语句是测试模式串的第J 个字符是否等于第K 个字符，如是，则
语句的意义是，当第J 个字符在模式匹配中失
指针J 和K 均増加1，继续比较。第6行的
配时，若第K 个字符和第J 个字符不等，则下个与主串匹配的字符是第K 个字符；否则，若第K 个字符和第J 个字符相等，则下个与主串匹配的字符是第K
个字符失配时的下一个（即
）。该算法在最坏情况下的时间复杂度
5． 试证明：同一棵二叉树的所有叶结点，在前序序列、对称序序列以及后序序列中都按相同的，例如前序后序运对称序。 相对位置出现（即先后顺序相同）
，中序遍历是“左根右”，后序遍历是“左右根”【答案】前序遍历是“根左右”。三种遍历中只是访问 " 根”结点的时机不同，对左右子树均是按左右顺序来遍历的，因此所有叶子都按相同的相对位罝出现。
6． 证明：在二叉树的三种遍历序列中，所有叶结点间的先后关系都是相同的。要求毎步论断都指出根据。
【答案】前序遍历是“根左右”. 中序遍历是“左根右”. 后序遍历是“左右根”。若将“根”去掉，三祌遍历就剩“左右”。三种遍历中的差别耽足访问根结点的时机不同。二叉树是递归定义的，对左右子树均是按左右顺序来遍历的，因此所有叶结点间的先后关系都是相同的。
7． 画出对算术表达式求值时操作数栈和运算符栈的变化过程。
【答案】设操作数栈是opnd ，运算符栈是optr ，对算术表达式表所示。
表 操作数栈和运算符找的变化过程
求值，过程如
8． 带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径，假设从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法：
①该最短路径初始时仅包含初始顶点，令当前顶点为初始顶点；
②选择离最近且尚未在最短路径中的顶点V ，加入到最短路径中，修改当前顶点请证明之；否则请举例说明。
【答案】题目中方法不一定能（或不能）求得最短路径。举例说明：
③重复步骤②，直到是目标顶点时为止。请问上述方法能否求得最短路径? 若该方法可行，