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

一、算法设计题

1． 设在4地(A, B , C , D) 之间架设有6座桥，如图所示。

要求从某一地出发，经过每座桥恰巧一次，最后仍回到原地。 (1)试就以上图形说明:此问题有解的条件是什么？

(2)设图中的顶点数为n ，试用C 或PASCAL 语言描述与求解此问题有关的数据结构并编写一个算法，找出满足要求的一条回路。

【答案】(1)只有所有的顶点的度都是偶数，才能有解。 (2)算法如下:

图中顶点的最大个数

弧(边) 结点

是邻接点在顶点向量中的下标，num 是边的编号

指向下一邻接点的指针

与弧(或边) 相关的信息指针

顶点结点

顶点信息及指向第一邻接点

的指针

邻接表

修改常规访问标志数组visited 的含义:当元素值为1时表示该边已访问；当元素值为0时表示该边尚未访问。

用邻接表作为存储结构的深度优先遍历算法

第一邻接点

结束dfs （ ）

求顶点的度

若顶点度为0, 或顶点的度不是偶

数，无解

无解

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

。

设有向图有n 个顶点

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

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

人队

到顶点

不存在路径

【答案】算法如下:

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

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

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

【答案】算法如下:

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

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

1

//结束对分査找函数

//本过程生成顺序表

L

//顺序表L 初始化

//设x ＝9999时退出输入

//去查找x 元素

//不同元素才插入

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

1

//结束过程creat

4． 假定用两个一维数组L 【N 】和R 【N 】作为有N 个结点1，2，…，N

的二叉树的存储结构。

和

分别指示结点i 的左儿子和右儿子，

，使

) 表示i 的左(右) 儿子为空。试写一个

存放结点i 的父亲；然后再写一个判别结点u 是否

算法，由L 和R 建立一个一维数组为结点V 的后代的算法。

【答案】算法如下:

和

是含有N 个元素且指示二叉树结点i 左儿子和右儿子的一维数组

T 数组初始化

本算法据此建立结点i 的双亲数组T , 并判断结点U 是否是结点V 的后代