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

一、算法设计题

1． 已知二叉树T ，试写出复制该二叉树的算法（t →T ）。

【答案】算法如下：

BiTree Copy（BiTree t）//复制二叉树t 的非递归算法

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

else

}//结束本题

2． 设线性表存于时间复杂度。

【答案】算法如下：

设计思想：算法中当查找失败（即线性表中无元素X ）时，变量low 在变量high 的右面

第 2 页，共 44 页

的前num 各分量中，且递增有序。请设计一个算法，将x 插入到线

性表的适当位置上，以保持线性表的有序性，并在设计前说明设计思想，最后说明所设计算法的

移动元素从位置low 开始，直到num 为止。

时间复杂度：查找的复杂度为

插入的时间复杂度为O （n ）, 若用顺序查找，则查找

的时间复杂度亦为O （n ）。

3． 若x 和y 是两个采用顺序结构存储的串，编写一个比较两个串是否相等的函数。

【答案】算法如下：

4． 已知递增有序的单链表A , B 分别存储了一个集合，请设计算法以求出两个集合A 和B 的差，并以同样的形式存储，同时集A-B （即仅由在A 中出现而不在B 中出现的元素所构成的集合）返回该集合的元素个数。

【答案】算法如下：

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

【答案】算法如下：

typedef struc {DiTree data ; int num ; }tnode // num 是结点在一维数组中的编号tnodc Q[maxsize]; //队列，容量足够大

void BiToSeqt{BiTree t, ELemType seq[]}

//本算法将二叉树的二叉链表存储结构转换为顺序存储结构seq {int front=0, rear:=0; tnode q; Bitree p; if （!t ） exit （0）;

for （i=1; i

{tq=Q[++front]; p=tq.data; l=tq.num; seq[i]=p->data; //存入顺序存储结构

第 3 页，共 44 页

if （p->lchild）{tq.data=p->lchild; tq.num=2*i; Q[++rear}//左子女入队 if （p->rchild）{tq.data=p->rchild; tq.num=2*i+1; Q[++rear]=tq; }//右子女入队 } }

6． 令G=（V , E）为一个有向无环图，编写一个给图G 中每一个顶点赋以一个整数序号的算法，并满足以下 条件：若从顶点i 至顶点j 有一条弧，则应使i

【答案】算法如下：

//对以邻接表存储的DAG 图g 重新编号, 使若有

i< j

//求各顶点的入度

//记录结点的逆序序号

7． 给定next ）, data （已生成）一个带表头结点的单链表，设head 为头指针，结点的结构为（data ，为整型元素，next 为指针，试写出算法：按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间（要求：不允许使用数组作辅助空间）。

【答案】算法如下：

第 4 页，共 44 页