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

一、算法设计题

1． 已知无向图采用邻接表存储方式，试写出删除边(i, j) 的算法。

【答案】算法如下:

在用邻接表方式存储的无向图g 中，删除边(i,

j)

删顶点i 的边结点(i, j) , pre 是前驱指针

释放空间

沿链表继续査找

删顶点j 的边结点(j,

i)

释放空间

沿链表继续査找

2． 给定一个整数数组

【答案】算法如下:

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

//局部最长平台

//新平台起点

(“最长平台长度

第 2 页，共 38 页

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

求出b 中最长平台的长度。

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

k)

3． 设线性表存于A[l..size]的前mun 各分量中，且递增有序。请设计一个算法，将x 插入到线性表的适当位置上，以保持线性表的有序性，并在设计前说明设计思想，最后说明所设计算法的时间复杂度。

【答案】算法如下:

//A是Size 个元素空间但目前仅有num(num＜size}个元素的线性表 //本算法将元素x 插入到线性表中，并保持线性表的有序性

//题目要求下标从1开始

//对分査找元素x 的插入位置

//元素后移

//将元素x 插人

算法结束

设计思想:算法中当查找失败(即线性表中无元素X) 时，变量low 在变量high 的右面(low＝high ＋l) 。移动元素从位置low 开始，直到num 为止。

时间复杂度:查找的复杂度为O (logn)，插入的时间复杂度为O (n)，若用顺序查找，则查找的时间复杂度亦为O(n)。

4． 设T 是一棵满二叉树，写一个把T 的后序遍历序列转换为前序遍历序列的递归算法。

【答案】算法如下:

将满二叉树的后序序列转为前序序列，

标。

根结点

左子树或右子树的结点数

将左子树前序序列转

为后序序列

将右子树前序序列转为

后序序列

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

【答案】算法如下:

第 3 页，共 38 页

是序列初始和最后结点的下

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

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

结束本题

二、应用题

6． 已知一棵二叉树的后序遍历序列为EICBGAHDF , 同时知道该二叉树的中序遍历序列为CEIFGBADH , 试画出该二叉树。

【答案】该二叉树如图所示:

图

7． (1)对于有向无环图，叙述求拓扑有序序列的步骤；

(2)对于图1, 写出它的四个不同的拓扑有序序列。

图1

【答案】(1)对有向图，求拓扑序列步骤为:

1) 在有向图中选一个没有前驱(即入度为0) 的顶点并输出。

第 4 页，共 38 页