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

一、算法设计题

1． 给定一个整数数组求出b 中最长平台的长度。

【答案】算法如下:

//求具有N 个元素的整型数组b 中最长平台的长度。

//局部最长平台

//新平台起点

(“最长平台长度

2． 编写一算法，利用叶结点中的空指针域将所有叶结点链接为一个带有头结点的双链表，算法返回头结点的地址。

【答案】算法如下:

全局变量链表头指针

将

若bt 不空

中序遍历左子树

叶结点

第一个叶结点

生成头结点

头结点的左链空，右链指向第一个结点

第一个叶结点左链指向头结点，pre 指向当前叶结点

中序遍历右子树

第 2 页，共 39 页

b 中连续的相等元素构成的子序列称为平台。试设计算法，

在b 数组中起始下标为”，1，

k)

树中的所有叶结点链成带头结点的双链表

当前叶结点链入双链表

最后一个叶结点的右链置空(链表结束标记

)

结束

3． 编写算法，求二叉树的宽度。

【答案】算法如下:

求二叉树bt 的最大宽度

空二叉树宽度为

Q 是队列，元素为二叉树结点指针，容量

足够大

front 为队头指针，rear 为队尾指针

last 为同层最右结点在队列中的位置

temp 记当前层宽度，maxw 记最大宽度

根结点入队

同层元素数加

1

左子女入队

右子女入队

一层结束

指向下层最右元素

更新当前最大宽度

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

。

设有向图有n 个顶点

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

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

人队

第 3 页，共 39 页

；

【答案】算法如下:

到顶点

不存在路径

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

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

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

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

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

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

输入顶点信息

二、应用题

6． 我们知道，对于n 个元素组成的线性表进行快速排序时，所需进行的比较次数与这n 个元素的初始排序有关。问:

当n=7时，在最好情况下需进行多少次比较? 请说明理由。 当n=7时，给出一个最好情况的初始排序的实例。 当n=7时，在最坏情况下需进行多少次比较? 请说明理由。 当n=7时，给出一个最坏情况的初始排序的实例。

【答案】(1)在最好情况下，每次划分能得到两个长度相等的子文件。假设文件的长度那么第一趟划分得到两个长度均为以此类推，总共进行共10次即可。

(2)在最好情况下快速排序的原始序列实例:4，1，3，2，6，5，7。

(3)在最坏情况下，若每次用来划分的记录的关键字具有最大(或最小) 值，那么只能得到左(或右) 子文件，其长度比原长度少1。因此，若原文件中的记录按关键字递减次序排列，而要求排序后按递增次序排列时，快速排序的效率与起泡排序相同，其时间复杂度为

第 4 页，共 39 页

，

的子文件，第二趟划分得到4个长度均为的子文件，

(n+1)趟划分，各子文件的长度均为1，排序完毕。当n=7时，k=3，在

最好情况下，第一需比较6次，第二趟分别对两个子文件(长度均为3，k=2)进行排序，各需2次，

。所以当n=7时，