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

一、算法设计题

1． 线性表中元素存放在向量A(1，... ，，1) 中，元素是整型数。试写出递归算法求出A 中的最大和最小元素。

【答案】算法如下:

//一维数组A 中存放有n 个整型数，本算法递归的求出其中的最小数和最大数

//算法结束

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

【答案】算法如下:

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

否则返回-1表示失败

元素序号

结束

，查找失败的平均查找

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

。

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

3． 已知顺序表中有m 个记录，表中记录不依关键字有序排列，编写算法为该顺序表建立一个有序的索引表，索引表中的每一项含记录的关键字和该记录在顺序表中的序号，要求算法的时间复杂度在最好的情况下能达到O(m)。

【答案】算法如下:

顺序表中记录个数

关键字

该关键字在顺序表中的下标

索引表的一项

关键字

记录中的其他数据

给有m 个记录的顺序表seq 建立索引表

index

监视哨

关键字放入正确位置

第i 个记录的下标

4． 已知二叉树T ，试写出复制该二叉树的算法(t→T) 。

【答案】算法如下:

复制二叉树t 的非递归算法

是二叉树的结点指针的队列，容量足够大

结束本题

5． 按图的宽度优先搜索法写一算法判别以邻接矩阵存储的有向图中是否存在由顶点到顶点的路径

。

设有向图有n 个顶点

判断以邻接矩阵方式存储的有向图中是否存在由顶点到顶点的路径

是队列，容量足够大，元素是顶点编号

人队

到顶点

不存在路径

【答案】算法如下:

二、应用题

6． 一个ISAM 文件除了主索引外，还包括哪两级索引？

【答案】ISAM 文件有三级索引:磁盘组、柱面和磁盘，柱面索引存放在某个柱面上，若柱面索引较大，占多个磁道时，可建立柱面索引的索引——主索引。故还包括的两级索引是盘组和磁道。

7． 已知图的邻接矩阵为:

当用邻接表作为图的存储结构，且邻接点都按序号从大到小排列时，试写出: (1)以顶点VI 为出发点的唯一的深度优先遍历序列； (2)以顶点VI 为出发点的唯一的广度优先遍历序列； (3)该图唯一的拓扑有序序列。 【答案】(1)