当前位置：问答库＞考研试题

一、算法设计题

1． 设计将数组A[n]中所有的偶数移到奇数之前的算法。要求不增加存储空间，且时间复杂性为〇(n)。

【答案】算法如下:

//n个整数存于数组A 中，本算法将数组中所有偶数排在奇数之前

//用类C 语言编写，数组下标从0开始

//交换A[i]与

A[j]

//算法Arrange 结束

2． 已知一棵二叉树的前序遍历序列和中序遍历序列分别存于两个一维数组中，试编写算法建立该二叉树的二叉链表。

【答案】算法如下:

根据二叉树前序序列pre 和中序序列in 建立二叉树。元素下标

申请结点

是根

在中序序列中，根结点将树分成左右

子树

无左子树

递归建立左子树

无右子树

递归建立右子树

结束:

和

是两个序列首、尾

3． 请运用快速排序思想，设计递归算法实现求n(n>1)个不同元素集合中的第f(

【答案】算法如下:

在后半部分继续进行划分

在前半部分继续进行划分

) 小元素。

4． 请编写一个判别给定二叉树是否为二叉排序树的算法，设二叉树用llink —rlink 法存储。

【答案】算法如下:

判断二叉树是否是二叉排序树，本算法结束后，在调用程序中由flag 得出结论

中序遍历左子树

中序遍历的第一个结点不必判断

前驱指针指向当前结点

不是完全二叉树

中序遍历右子树

算法结束

判断二叉树t 是否是二叉排序树，若是，返回true ，否则，返回

false

若左右子树均为二叉

排序树

左子树中的最大值和右子树中

的最小值

不是二叉排序树

结束

求二叉树左子树的最大值

返回机器最小整数

求二叉树右子树的最小值

返回机器最大整数

5． 编写对有序表进行顺序查找的算法，并画出对有序表进行顺序查找的判定树。假设每次查找时的给定值为随机值，又查找成功和不成功的概率也相等，试求进行每一次查找时和给定值进行比较的关键字个数的期望值。

【答案】算法如下:

在具有个元素的有序表R 中，顺序査找值为K 的结点，査找成功返回其位置

否则返回-1表示失败

元素序号

结束

，查找失败的平均查找

期望值分析:在等概率情况下，则查找成功的平均查找长度为等，则查找成功时和关键字比较的个数的期望值约为

。

长度为(n+2)/2(失败位置除小于每一个，还存在大于最后一个) 。若查找成功和不成功的概率也相

二、应用题

6． KMP 算法(字符串匹配算法) 较Brute(朴素的字符串匹配) 算法有哪些改进？

【答案】朴素的模式匹配(Brute.Force)时间复杂度是匹配时，KMP 算法的优点更为突出。

7． 将算术表达式

，KMP 算法有一定改进，时间复

杂度达到O(m＋n) 。主要优点是主串指针不回溯。当主串很大不能一次读入内存且经常发生部分

转化为二叉树。

【答案】该算术表达式转化的二叉树如图所示。