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

一、算法设计题

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

【答案】算法如下:

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

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

记其长度

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

//上一个重复子串结束

//当前重复子串长

度大，则更新

max

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

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

.//算法结束

，在串中的位置

，max ，index) ；

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

2． 编写递归算法，从大到小输出给定二叉排序树中所有关踺字不小于X 的数据元素。要求你的算法的时间复杂度为

【答案】算法如下:

从大到小输出二叉排序树bst 中所有关键字不小于x 的数据元素

) 是大根堆。

) 调整为大根堆；

第 2 页，共 36 页

，其中，2为排序树中所含结点数，m 为输出的关键字个数。

3． 已知关键字序列(

试写出一算法将(

利用(1)的算法写一个建大根堆的算法。 【答案】(1)算法如下:

''

假设

是大堆，本算法把

(2)

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

【答案】算法如下:

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

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

//交换A[i]与

A[j]

//算法Arrange 结束

5． 给定(已生成) 一个带表头结点的单链表，设head 为头指针，结点的结构为(data，next) ，data 为整型元素，next 为指针，试写出算法:按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间(要求:不允许使用数组作辅助空间) 。

【答案】算法如下:

//head是带头结点的单链表的头指针

//本算法按递增顺序输出单链表各结点的值，并释放结点所占的存储空间

//循环到仅剩头结点

//pre为元素最小值结点的前驱结点的指针

//P为工作指针

//记住当前最小值结点的前驱

//输出元素最小值结点的数据

第 3 页，共 36 页

调成大堆

//删除元素值最小的结点，释放结点

空间

//释放头结点

二、应用题

6． 证明:在二叉树的三种遍历序列中，所有叶结点间的先后关系都是相同的。要求每步论断都指出根据。

【答案】前序遍历是“根左右”，中序遍历是“左根右”，后序遍历是“左右根”。若将“根”去掉，三种遍历就剩“左右”。三种遍历中的差别就是访问根结点的时机不同。二叉树是递归定义的，对左右子树均是按左右顺序来遍历的，因此所有叶结点间的先后关系都是相同的。

7． 三维数组的每个元素的长度为4个字节，试问该数组要占多少个字节0，的存储空间? 如果数组元素以行优先的顺序存储，设第一个元素的首地址是100，试求元素A[5，7]的存储首地址。

【答案】数组占的存储字节数＝10*9*7*4＝2520；A[5，0，7]的存储地址＝100＋[4*9*7＋2*7＋5]*4＝1184

8． 以归并算法为例，比较内部排序和外部排序的不同，说明外部排序如何提高操作效率。

【答案】(1)内部排序中的归并排序是在内存中进行的归并排序，辅助空间为O(n)。外部归并排序是将外存中的多个有序子文件合并成一个有序子文件，将每个子文件中记录读入内存后的排序方法可采用多种内排序方法。外部排序的效率主要取决于读写外存的次数，即归并的趟数。

(2)因为归并的趟数

，其中，m 是归并段个数，k 是归并路数。增大k 和减少m 都

可减少归并趟数。应用中通过败者树进行多(k)路平衡归并和置换一选择排序减少m ，来提高外部排序的效率。

9． 证明:具有n 个顶点和多于n －1条边的无向连通图G —定不是树。

【答案】证明:具有n 个顶点n －1条边的无向连通图是自由树，即没有确定根结点的树，每个结点均可当根。若边数多于n －1条，因一条边要连接两个结点，则必因加上这一条边而使两个结点多了一条通路，即形成回路。形成回路的连通图不再是树。

10．设二叉树BT 的存储结构如表:

表 二叉树BT 的存储结构

其中BT 为树根结点的指针，其值为6, Lchild 、Rchild 分别为结点的左、右孩子指针域data

第 4 页，共 36 页