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

一、算法设计题

1． 试将下列递归过程改写为非递归过程。

【答案】算法如下：

2． 请编写完整的程序。如果矩阵A 中存在这样的一个元素矩阵A 的所有马鞍点。

【答案】算法如下：

满足条件：

是第i 行中值

的

最小的元素，且又是第j 列中值最大的元素，则称之为该矩阵的一个马鞍点。请编程计算出

3． 元素集合己存入整型数组树T 的非递归算法

：

【答案】算法如下：

中，试写出依次取A 中各值构造一棵二叉排序

4． 已知深度为h 的二叉树, 以一维数组应的算法。

【答案】算法如下： int Leaves （int BT[]，int n）

//计算深度为h. 以一维数BT 作为其存储结构的二叉树的叶结点数，n 为数组长度{int num=0; //记叶结点数

for （i=0; i

2*i+l

BT （2*i+l】<0） num++; }//若结点无孩子，则是叶子else if

（BT[i]>0） num++； //存储在数组后一半的元素是叶结点 return num;

}//结束Leaves

5． 已知指针P 指向带表头的中根次序线索二叉树中的某结点，试写一算法FFA （P ，q ）, 该算法寻找结点 P 的父亲结点q ，设线索二叉树的结点结构、表头结点结构和空树结构分别为（LTAG , LLINK , INFO , RL1NK , RTAG ）, 且规定线索树的最左下结点的LLINK 域和最右下结点的RLINKt 域指向表头。

【答案】算法如下：

在中序线索树t 上，求结点p 的双亲结点q

{q=p; //暂存

//找P 的中序最右下的结点

//顺右线索找到q 的后继（P 的袓先结点）

作为其存储结构，试编写一算法，求该二叉

树中叶结点的个数，为简单起见，设二叉树中元素结点为非负整数，要求写出算法基本思想及相

//若后继是头结点，则转到根结点

根结点无双亲

}//找最右结点的过程中回找到

P

6． 假定用两个一维数组L 【N 】和R 【N 】作为有N 个结点1，2, ... ，N 的二叉树的存储结构L[i]和R[i] 分別指示结点i 的左儿子和右儿子L[i]=0 （R[i]=0）表示i 的左（右）儿子为空。试写一个算法，由L 和R 建立一个维数组T[n]，使T[i]存放结点i 的父亲：然后再写一个判别结点u 是否为结点V 的后代的算法。

【答案】算法如下：

int Generation （int U, V , N , L[], R[], T[]}

//L[ ]和R[ ]是含N 个元素且指示二叉树结点i 左儿子和右儿子的一维数组 //本算法据此建立结点i 的双亲数组T , 并判断结点U 是否是结点V 的后代 {for（i=l; i<=N; i++） T[i]=0; //T数组初始化

for （i=l; i<=N; i++） if （L[i]!=0） T[L[i]]=i; //若结点i 的左子女是L , 则结点的双亲是结点i for （i=l; i<=N; i++） if （R[i]!=0> T[R[i]]=i; //若结点i 的右子女是R , 则R 的双亲是i int parent=U; //判断U 是否是V 的后代 while （

parent!=V

parent!=0） parent=T[parent];

if （parent==V）{printf（“结点U 是结点V 的后代”）; return （l ）:} else{printf（“结点U 不是结点V 的后代”）; return （0）; } }结束 Generation

7． 假设在二叉链表的结点中增设两个域：parent 域指示其双亲结点：flag 域（取值为0. 2）区分在遍历过 程中到达该结点时应继续向左、向右或访问该结点。试以此存储结构编写不用栈进行后序遍历的递推形式的算法。

【答案】算法如下：

//在增加双亲指针parent 和标志域flag 的二叉树中，不用栈后序遍历二叉树

//

//准备到左子树中找

P

向

左