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

一、算法设计题

1． 图G 有n 个点，利用从某个源点到其余各点最短路径算法思想，设计一产生G 的最小生成树的算法。

【答案】算法如下:

利用从源点v0到其余各点的最短路径的思想，产生以邻接矩阵表示的图G 的最小生成

树

数组存放生成树

数组存放顶点是否找到最短路径

初始化, 设顶点信息就是编号

从v0开始，求其最小生成树

是尚未到最小生成树的顶点的集合

循环n －1次

顶点u 已找到最短路径下，下面修改相关顶点的最短路径

算法结束

2． 试将下列递归过程改写为非递归过程。

【答案】算法如下:

3． 元素集合已存入整型数组树T 的非递归算法:CSBT(r，A)

【答案】算法如下:

以存储在数组K 中的n 个关键字，建立一棵初始为空的二叉排序

树

在调用时，

T=null

f 是P 的双亲

申请结点空间

根结点

左子女

右子树根结点的值大于等于根

结点的值

算法结束

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

【答案】算法如下:

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

//算法结束

中，试写出依次取A 中各值

构造一棵二叉排序

5． 请用流程图或高级语言表示算法。已知有向图有n 个顶点，请写算法，根据用户输入的数对建立该有向图的邻接表。即接受用户输入的

(以其中之一为0标志结束) ，对于每条这样的

边，申请一个结点，并插入到的单链表中，如此反复，直到将图中所有边处理完毕。

提示:先产生邻接表的n 个头结点(其结点数值域从1到n) 。 【答案】算法如下:

建立有向图的邻接表存储结构

输入顶点信息

题目要求两顶点之一为0表示结束

二、应用题

6． 设a ，b ，c ，d ，e 五个字符的编码分别为1，2，3，4，5，并设标识符依以下次序出现:ac ，Bd ，aa ，be ，ab ，ad ，cd ，be ，ae ，ce 。要求用哈希(Hash)方法将它们存入具有10个位置的表中。

(1)将上述关键字(标识符) 构造一个哈希函数，使得发生冲突尽可能地少； (2)线性探测再散列法解决冲突。写出上述各关键字在表中位置。

【答案】(1)构造的哈希函数为:哈希函数H(key)=(关键字各字符编码之和)MOD7。 (2)关键字在表中的位置如表所示:

表 关键字在表中的位置