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

一、算法设计题

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

【答案】算法如下:

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

树

数组存放生成树

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

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

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

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

循环n －1次

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

算法结束

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

的二叉树的存储结构。

和

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

，使

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

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

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

【答案】算法如下:

和

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

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

T 数组初始化

若结点i 的左子女是则结点L 的

双亲是结点

i

若结点i 的右子女是R , 则R 的

双亲是

i

判断U 是否是V 的后代

3． 串以静态存储结构存储，结构如下所述，试实现串操作equal 算法。

串被确认的最大长度

【答案】算法如下:

//本算法判断字符串S 和字符串t 是否相等，如相等返回1，否则返回

//在类C 中，一维数组下标从零开始

//两串相等

//算法结束

4． 编程:假设以数组Q[m]存放循环队列中的元素，同时以rear 和length 分别指示环形队列中的队尾位置和队列中所含元素的个数。试给出该循环队列的队空条件和队满条件，并写出相应的初始化(initqueue)，插入(enqueue)和删除(dequeue)元素的操作。

【答案】定义队列:

//循环队列占m 个存储单元

//rear指向队尾元素，length 为元素个数

(1)设cq 是seQueue 类型变量，则当(2)队列的初始化:

//cq为循环队列，本算法进行队列初始化

时队列空，当 时队列满。

//算法结束 (3)队列的插入:

//cq是已如上定义的循环队列，本算法将元素x 入队

//队满

.

//计算插入元素位置

//将元素x 入队列

//修改队列长度

//算法结束

//cq是已如上定义的循环队列，本算法是出队算法，且返回出队元素

//队空

；//出队元素位置

//修改队列长度

//返回队头元素

//算法结束

5． 设计算法将一棵以二叉链表存储的二叉树按顺序方式存储到一维数组中(注:按层从上到下，由左到右) 。

【答案】算法如下:

是结点在一维数组中的编

号

队列，容量足够大

本算法将二叉树的二叉链表存储结构转换为顺序存储结构

seq

初始化，#代表虚结点

根结点入队

存入顺

序存储结构

左

子女入队

(4)队列的删除: