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

一、算法设计题

1． 在输入数据无序的情况下，建立一个数据值为整型的递增有序的顺序存储线性表L ，且要求当输入相同数据值时，线性表中不能存在数据值相同的数据元素，试写出其算法。

顺序存储结构的线性表描述为:

线性表可能达到的最大长度}；

【答案】算法如下:

//在顺序表a 中査找值为x 的元素，査找成功返回0值，否则返回查找失败时的较大下标值

//当査找失败时，low ＝high ＋

1

//结束对分査找函数

//本过程生成顺序表

L

//顺序表L 初始化

//设x ＝9999时退出输入

//去查找x 元素

//不同元素才插入

//插入元素x ，线性表长度增

1

//结束过程creat

2． 以顺序存储结构表示串，设计算法。求串S 中出现的第一个最长重复子串及其位置并分析算法的时间复杂度。

【答案】算法如下:

//串用一维数组s 存储，本算法求最长重复子串，返回其长度

//index记最长的串在s 串中的开始位置，max

记其长度

//length记局部重复子串长度，i 为字符数组下标

//上一个重复子串结束

//当前重复子串长

度大，则更新

max

//初始化下一重复子串的起始位置和长度

(”最长重复子串的长度为

.//算法结束

，在串中的位置

，max ，index) ；

时间复杂度:算法的时间复杂度为O(n)，每个字符与其后继比较一次。

3． 已知一具有n

个结点的二叉树的中序遍历序列与后序遍历序列分别存放于数组

和

中(设该二叉树各结点的数据值均不相同) 。请写一建立该二叉树的二叉链表结构的非递

归算法。该二叉链表的链结点结构为(lchild, data , rchild) ，其中data 为数据域，lchild 与rhild 分别为指向该结点左、右孩子的指针域(当孩子结点不存在时，相应指针域为空，用nil 表示) 。

【答案】算法如下:

由二叉树的中序序列IN[ ]和后序序列POST[ ]建立二叉树

和

为栈，容量足够大

分別是中序序列和后序序列第一和最后元素的下标，初始调用时

，

初始化

取出栈顶数据

在中序序列中査等于

.

根结点的值

无左子树

的结点

将建立左子树的数据入栈

无右子树

右子树数据入

结束

:

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

【答案】算法如下:

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

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

沿右子树向下

结束

5． 试为二叉树写出一个建立三叉链表的算法，并在此三叉链表中删去每一个元素值为x 的结点，以及以它为根的子树，且释放相应存储空间。二叉树的三叉链表的描述为:

{二叉树根结点的指针}

【答案】算法如下:

生成三叉链表的二叉树(题目给出PASCAL 定义，下面用类C 语言书写

)

是二叉树结点指针的一维数组，容量足够大

一维数组最后元素的下标

元素或虚结点

根结点

双亲结点和子女结点用指针链上