一个递归的定义可以用递归过程求解，也可以用非递归过程求解，但单从运行空间效率来看，通常递归过程比非递归过程（）

一个递归的定义可以用递归过程求解，也可以用非递归过程求解，但单从运行时间来看，通常递归过程比非递归过程()。

A.较快

B.较慢

C.相同

D.无法确定

已知Ackerman函数的定义如下：

(1)写出递归算法;

(2)写出非递归算法;

(3)根据非递归算法， 画出求akm(2，1)时栈的变化过程。

将一个非负十进制整数转换成八进制数，使用非递归算法实现。

  算法分析：十进制转换成八进制的过程是将十进制整数除8得余数，直到商是0为止，然后倒排余数。为了得到倒排的余数，可以利用栈来实现，每次运算后将余数压入栈中，直到商为0，将栈中数据输出即是。使用顺序栈，将顺序栈的定义及其基本操作的实现写在头文件“seqstack.h”中。

已知Ackermann函数定义如下：

(1)写出Ack(2，1)的计算过程。 (2)写出计算Ack(m，n)的非递归算法。【北京师范大学2005六、2(15分)】【北京航空航天大学1999六(15分)】

某语言允许过程嵌套定义和递归调用(如Pascal)语言，若在栈式动态存储分配中采用嵌套层次显示表display解决对非局部变量的引用问题，试给出下列程序执行到语句“b：=10;时运行栈及display表的示意图。”

设G是含有n个顶点(设顶点编号为1，2，…，n)的有向无环图。将G用如下定义的邻接表存储(编者略)。请编写一个非递归算法求G的每个顶点出发的最长路径的长度(每条弧的长度均为1)并存入mpl域中。要求：首先写出算法思想，然后写算法过程。

阅读下列说明和c函数代码，将应填入 (n) 处的字句写在答题纸的对应栏内。

【说明】

对二叉树进行遍历是二叉树的一个基本运算。遍历是指按某种策略访问二叉树的每个结点，且每个结点仅访问一次的过程。函数InOrder。()借助栈实现二叉树的非递归中序遍历运算。

设二叉树采用二叉链表存储，结点类型定义如下：

typedef struct BtNode{

ElemTypedata； ／*结点的数据域，ElemType的具体定义省略*／

struct BtNode*ichiid，*rchild； ／*结点的左、右弦子指针域*／

)BtNode，*BTree；

在函数InOrder()中，用栈暂存二叉树中各个结点的指针，并将栈表示为不含头结点

的单向链表(简称链栈)，其结点类型定义如下：

typedef struct StNode{ ／*链栈的结点类型*／

BTree elem； ／*栈中的元素是指向二叉链表结点的指针*／

struct StNode*link；

}S％Node；

假设从栈顶到栈底的元素为en、en-1、…、e1，则不含头结点的链栈示意图如图5—5

所示。

【C函数】

int InOrder(BTree root) ／*实现二叉树的非递归中序遍历*／

{

BTree ptr； ／*ptr用于指向二又树中的结点*／

StNode*q； ／*q暂存链栈中新创建或待删除的结点指针+／

StNode*stacktop=NULL； ／*初始化空栈的栈顶指针stacktop*／

ptr=root； ／*ptr指向二叉树的根结点*／

while( (1 ) I I stacktop!=NULL){

while(ptr!=NULL){

q=(StNode*)malloc(sizeof(StNode))；

if(q==NULL)

return-1；

q->elem=ptr；(2) ；

stacktop=q； ／*stacktop指向新的栈顶*／

ptr=(3 ) ； ／*进入左子树*／

}

q=stacktop； (4) ； ／*栈顶元素出栈*／

visit(q)； ／*visit是访问结点的函数，其具体定义省略*／

ptr= (5) ； ／*进入右子树*／

free(q)； ／*释放原栈顶元素的结点空间*／

}

return 0；

}／*InOrder*／

阅读以下预备知识、函数说明和C代码，将应填入(n)处的字句填写完整。

[说明]

(1)对给定的字符集合及相应的权值，采用哈夫曼算法构造最优二叉树，并用结构数组存储最优二叉树。例如，给定字符集合{a,b,c,d)及其权值2、7、4、5，可构造如图3-26所示的最优二叉树，以及相应的结构数组Ht(如表3-12所示，其中数组元素Ht[0]不用)。

结构数组Ht的类型定义如下：

(2)用“0”或“1”标识最优二叉树中分支的规则是：从一个结点进入其左(右)孩子结点，就用“0”(或“1”)标识该分支(示例见图3-26)。

(3)若用上述规则标识最优二叉树的每条分支后，从根结点开始到叶子结点为止，按经过分支的次序将相应标识依次排列，可得到由“0”、“1”组成的一个序列，称此序列为该叶子结点的前缀编码。例如图3-26所示的叶子结点a、b、c、d的前缀编码分别是110、0、111、10。

[函数说明1]

函数void LeafCode (int root，int n)的功能是：采用非递归方法，遍历最优二叉树的全部叶子结点，为所有的叶子结点构造前缀编码。其中，形参root为最优二叉树的根结点下标；形参n为叶子结点个数。

在函数void LeafCode (int root，int n)构造过程中，将Ht[p].weight域用做被遍历结点的遍历状态标志。

[函数4.1]

[函数说明2]

函数void Decode (char (作图)buff，int root)的功能是：将前缀编码序列翻译成叶子结点的字符序列，并输出。其中，形参root为最优二叉树的根结点下标；形参buff指向前缀编码序列。

[函数4.2]

A、较快

B、较慢

C、相同

D、无法比较