2017年兰州财经大学算法与数据结构(同等学力加试)复试实战预测五套卷
● 摘要
一、应用题
1． 设依以下次序给出关键字：34，16，19，21，5，49，24，62，3，17，45，8，构造3阶树。要求从空树开始，每插入一个关键字，画出一棵树。
【答案】如图所示：
图
2． 试举一例，说明对相同的逻辑结构，同一种运算在不同的存储方式下实现，其运算效率不同。
【答案】线性表中的插入、删除操作，在顺序存储方式下平均移动近一半的元素，时间复杂度为O （n ）; 而在链式存储方式下，插入和删除时间复杂度都是0（1）。
3． KMP 算法（字符串匹配算法）较Brute （朴素的字符串匹配）算法有哪些改进？
【答案】朴素的模式匹配度达到
时间复杂度是
KMP 算法有一定改进，时间复杂
主要优点是主串指针不回溯。当主串很大不能一次读入内存且经常发生部分匹配
时，KMP 算法的优点更为突出。
4． （1）如果G1是一个具有n 个顶点的连通无向图，那么G1最多有多少条边?G1最少有多少条边？
（2）如果G2是一个具有n 个顶点的强连通有向图，那么G2最多有多少条边?G2最少有多少条边？
（3）如果G3是一个具有n 个顶点的弱连通有向图，那么G3最多有多少条边?G3最少有多少条边？
1）G1最多n （n-l ）/2条边，最少n-1条边。 【答案】（（2）G2最多n （n-l ）条边，最少n 条边。 （3）G3最多n （n-l ）条边，最少n-1条边。
5． 设某文件经内排序后得到100个初始归并段（初始顺串），若使用多路归并排序算法，并要求三趟归并完成排序，问归并路数最少为多少？
【答案】设归并路数为k ，归并趟数为s ，则
因
且k 为整数，故k=5，即
最少5-路归并完成排序。
6． 证明若二叉排序树中的一个结点存在两个孩子，则它的中序后继结点没有左孩子，则它的中序前驱结点没有右孩子。
【答案】根据中序遍历的定义，该结点的中序后继是其右子树上按中序遍历的第一个结点：叶结点或仅有右子树的结点；而其中序前驱是其左子树上按中序遍历的最后个结点：叶结点或仅有左子树的结点。命题得证。
7． 快速排序的最大递归深度是多少? 最小递归深度是多少？
【答案】设待排序记录的个数为n ，则快速排序的最小递归深度为
最大递归深度n 。
8． 模式匹配算法是在主串中快速寻找模式的一种有效的方法，如果设主串的长度为m , 模式的长度为n ，则在主串中寻找模式的KMP 算法的时间复杂性是多少? 如果某一模式给出它的next 函数值及next 函数的修正值nextval 之值。
【答案】KMP 算法的时间复杂性是01102201320。
p 的next 和nextval 值分别为01112212321和
请
二、算法设计题
9． 设有两个栈操作算法。
【答案】栈的定义：
都采用顺序栈方式，并且共享一个存储区为了尽量利用空
间，减少溢出的可能，可采用栈顶相向，迎面增长的存储方式。试设计81, 82有关入栈和出栈的
（1）入栈操作：
（2）出栈操作
10．编写算法打印出由指针Hm 指向总表头的以十字链表形式存储的稀疏矩阵中每一行的非零元的个数。注意：行、列及总表头结点的形式为：
它们已用
域链接成循环链表。非零元的结点形式也同上，每一行（列）的非零元由
域把它们链接成循环链表，该行（列）的表头结点即为该行（列）循环链表的表头。
【答案】算法如下：