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

一、算法设计题

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

【答案】算法如下:

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

否则返回-1表示失败

元素序号

结束

，查找失败的平均查找

期望值分析:在等概率情况下，则查找成功的平均查找长度为

长度为(n+2)/2(失败位置除小于每一个，还存在大于最后一个) 。若查找成功和不成功的概率也相等，则查找成功时和关键字比较的个数的期望值约为。

2． 写出算法，求出中序线索二叉树中给定值为X 的结点之后继结点，返回该后继结点的指针。线索树中结点结构为；

。其中，data 存放结点的值；lc 、rc 为指向左、

右孩子或该结点前驱、后继的指针，ltag 、rtag 为标志域，若值为0, 则lc 、rc 为指向左、右孩子的指针；若值为1，则lc 、rc 为指向其前驱、后继结点的指针。

【答案】算法如下:

先在带头结点的中序线索二叉树T 中査找给定值为x 的结点，假定值为x 的结点存在

设P 指向二叉树的根结点

结束

第 2 页，共 36 页

在中序线索二叉树T 中,, 求给定值为x 的结点的

后继结点

首先在T 树上査找给定值为x 的结点，由p 指向

' 若P 的右标志为1, 则P 的rc 指针指向其后继

结点P 的右子树中最左边的结点是结点P 的中序后继

结库

.

3． 已知L 为没有头结点的的单链表中第一个结点的指针，每个结点数据域存放一个字符，该字符可能是英文字母字符、数字字符或其他字符，编写算法构造三个以带头结点的单循环链表表示的线性表，使每个表中只含同一类字符(要求用最少的时间和最少的空间) 。

【答案】算法如下:

L 是不带头结点的单链表第一个结点的指针，链表中的数据域存放字符

//本算法将链表L 分解成含有英文字母字符、数字字符和其他幸符的带头结点的三个循环链表

//建立三个链表的头结点

//置三个循环链表为空表

//分解原链表

//L指向待处理结点的后继

//处理字母字符

//处理数字字符

//处理其他符号

//结束while(L!＝

null) //算法结束

4． 有二叉排序树采用二叉链表方式存放，树中结点值各不相同，欲得到一个由大到小的结点值递减序列，简述处理方法思路，用非递归形式写出算法。

【答案】算法如下:

按递减次序输出二叉排序树结点的值

是元素为二叉树结点指针的栈，容量足够大

沿右子树向下

第 3 页，共 36 页

结束

5． 假设在二叉链表的结点中增设两个域:parent 域指示其双亲结点:flag 域(取值为历的递推形式的算法。

【答案】算法如下:

在增加双亲指针

和标志域

的二叉树中，不用栈后序遍历二叉树

) 区分在遍

历过程中到达该结点时应继续向左、向右或访问该结点。试以此存储结构编写不用栈进行后序遍

向左

向右

访问根结点

找被访问结点的双亲

结束

二、应用题

6． 模式匹配算法是在主串中快速寻找模式的一种有效的方法，如果设主串的长度为m ，模式的长度为n ，则在主串中寻找模式的KMP 算法的时间复杂性是多少? 如果某一模式

，请给出它的next 函数值及next 函数的修正值nextval 之值。

【答案】KMP 算法的时间复杂性是O(m＋n) 。

p 的next 和nextval 值分别为01112212321和01102201320。

7． 在多关键字排序时，LSD 和MSD 两种方法的特点是什么？

【答案】(1)最高位优先(MSD)法

先对最高位关键字K 进行排序，将序列分成若干子序列，每个子序列中的记录都具有相同的

K 0值，然后，分别就每个子序列对关键字K 1进行排序，按K 1值不同再分成若干更小的子序列，依次重复，直至最后对最低位关键字排序完成，将所有子序列依次连接在一起，成为一个有序子序列。

(2)最低位优先(LSD)法 先对最低位关键字

进行排序，然后对高一级关键字

第 4 页，共 36 页

进行排序，依次重复，直至对最高