数据结构1800例题与答案之树和二叉树(8)

下标 1 D -5 C 3 A 0 F 2 B -3 E -2 2 3 4 5 6

数据 父母

【北京邮电大学2002 五、4 （15分）】

22．设计算法返回二叉树T的先序序列的最后一个结点的指针，要求采用非递归形式，且不许用栈。

【合肥工业大学 1999 五、2 （8分）】

23．已知一棵高度为Ｋ具有ｎ个结点的二叉树，按顺序方式存储： （1）编写用先根遍历树中每个结点的递归算法；

（2）编写将树中最大序号叶子结点的祖先结点全部打印输出的算法。【东北大学 1997 六(20分)】。

24．对于二叉树的链接实现,完成非递归的中序遍历过程。 【中山大学 1999 五、 (15分)】

类似本题的另外叙述有：

（1）写出中序遍历二叉树的非递归算法及递推算法。【大连海事大学1996 六、2 （10分)】。

（2）设计一个中序遍历算法，应用栈来存储树结点，要求结点仅能进栈和出栈一次。（本题指中序遍历二叉树）【西安电子科技大学1999计应用 四 (10分)】 （3）用非递归方式写出二叉树中序遍历算法。【山东科技大学 2002 六、2 (9分)】 25．已知二叉树用下面的顺序存储结构，写出中序遍历该二叉树的算法。 TYPE ARRAY [1..maxn] OF RECORD data:char; //存储结点值 Lc,Rc;integer; END; //存左孩子右孩子的下标，0表示无左、右孩子。

1 2 3 4 5 6 7 8 9 data A Lc Rc 2 3 B 4 5 C 0 6 D 0 0 E 0 7 F 8 9 G 0 0 H 0 0 I 0 0 如树 T=A（B（D，E,(#,G)），C（#，F（H，I）））存储如上图。【北京邮电大学 1999 九 (10分)】

26．试给出二叉树的自下而上、自右而左的层次遍历算法。【吉林大学 2001 二 、2 （8分)】

27．在一棵以二叉链表表示的二叉树上，试写出用按层次顺序遍历二叉树的方法，统计树中具有度为1的结点数目的算法。二叉链表的类型定义为：

TYPE bitreptr=^bnodetp;

bnodetp=RECORD data:char; lchild,rchild:bitreptr END;

【同济大学 2000 三、2 （12分）】 类似本题的另外叙述有：

（1）请设计算法按层次顺序遍历二叉树。【北方交通大学 2001 四、 (20分)】 （2）试以二叉链表作存储结构，编写按层次顺序遍历二叉树的算法。【上海交通大学1999 三(12分)】

（3）已知一棵以二叉链表作存储结构的二叉树，编写按层次顺序（同一层自左至右）遍历二叉树的算法。

【燕山大学 1999 十、1 （8分)】

（4）设二叉树用二叉链表存储，试编写按层输出二叉树结点的算法。【北京理工大学2001九、2（8分)】

（5）写出按层次顺序打印任意二叉树T中结点的程序。二叉树采用双链结构，结点形式为（LSON，DATA，RSON）可采用任何你熟识的算法语言，设T 指向二叉树的根结点。【山东大学1993 二 (12分)】

28．设一棵二叉树以二叉链表为存贮结构，结点结构为(lchild, data,rchild)，设计一个算法将二叉树中所有结点的左，右子树相互交换。【福州大学 1998 四、2 (10分)】 类似本题的另外叙述有：

（1）设t为一棵二叉树的根结点地址指针，试设计一个非递归的算法完成把二叉树中每个结点的左右孩子位置交换。【东北大学 1996 五、 (14分)】 （2）写一个将二叉树中每个结点的左右孩子交换的算法。（统考生做）【南京航空航天大学1999九(10分)】 29．设T是一棵满二叉树，编写一个将T的先序遍历序列转换为后序遍历序列的递归算法。 【东北大学 2001 三 (15分)】

30．已知一棵二叉树的中序序列和后序序列，写一个建立该二叉树的二叉链表存储结构的算法。

【东北大学 1999 六、3 （12分）】 31．设二叉树采用二叉链表作为存储结构。试用类PASCAL语言实现按前序遍历顺序输出二叉树中结点的非递归算法。要求定义所用结构。设栈已经定义：inits(S)，empty（S） push（S，P），pop（S），top（S）分别为栈初始化，判栈空，入栈，出栈，看栈顶等操作。【北京工业大学1997二、1（10分）】

h

32．已知深度为h的二叉树以一维数组BT(1:2-1)作为其存储结构。请写一算法，求该二叉树中叶结点的个数。【北京航空航天大学 1996】 33．设某二叉树结点结构为: TYPE bitreptr=^bnodetp;

bnodetp=RECORD data:integer; lchild,rchild:bitreptr END; 试编写算法，计算每层中结点data域数值大于50的结点个数，并输出这些结点的data域的数值和序号。

【北京工业大学 1998 九(10分)】

34．编写递归程序将二叉树逆时针旋转90度打印出来。如右图：（要求用类PASCAL语言，并描述结构）。

【北京工业大学 1999 二 、 (6分)】 35．二叉树排序方法如下：

（1）将第一个数据放在树根。

（2）将随后读入的数据与树根中的数据相比较，若比树根大，则置于右子树，反之则置于左子树，建成一棵二叉树；

（3）利用中序遍历打印排序结果。

试用PASCAL或C语言编写二叉树的排序程序，并分析其算法复杂性。【浙江大学 1995 九 (15分)】

36．已知一二叉树中结点的左右孩子为left和right，p指向二叉树的某一结点。请用C或PASCAL编一个非递归函数postfirst(p),求p所对应子树的第一个后序遍历结点。【浙江大学1998 六(10分)】

37．已知二叉树T的结点在先根次序下的排列为A[1]，A[2]，?，A[n]，在中根次序

下的排列为B[1]，B[2]，?，B[n]，其中，A和B是一维数组，数组元素的值为T中相应的结点的INFO字段的值，并假定二叉树T中结点的INFO字段的值互不相同，n>=0。试解答：

（1）证明由A[1：n]和B[1：n]能唯一的确定二叉树T的结构；

（2）给出建造二叉树T的算法，要求所建造的二叉树以LLINK/RLINK链接结构表示，且该算法是非递归算法；

(3) 分析你所给算法的时间复杂性，该过程包括如何确定基本运算如何推导出期望复杂性和最坏复杂性。【吉林大学 1997 四 (20分) 1998 二】

38．已知一具有n个结点的二叉树的中序遍历序列与后序遍历序列分别存放于数组IN[1：n]和POST[1：n]中，（设该二叉树各结点的数据值均不相同）。请写一建立该二叉树的二叉链表结构的非递归算法。该二叉链表的链结点结构为(lchild,data,rchild)，其中data为数据域，lchild与rhild分别为指向该结点左、右孩子的指针域（当孩子结点不存在时，相应指针域为空，用nil表示）。

【北京航空航天大学 1998 六 (15分)】

39．试写出复制一棵二叉树的算法。二叉树采用标准链接结构。【山东大学 2000 二 (10

分)】。

类似本题的另外叙述有：

（1）已知二叉树T,试写出复制该二叉树的算法(t→T)

（1）（8分)递归算法（2）（12分)非递归算法【北方交通大学 1993 七(20分)】 （2）算法题（共20分，每题10分)

（1）试写出一递归函数，判别两棵树是否相等。 （2）试写出一递归函数，复制一棵二叉树。【山东工业大学 1997 八、 (20分)】 40．假设一维数组H[1：n]存放森林F的每个结点的地址，且序列H[1]，H[2]，?，H[n]正好是森林F在先根次序下结点地址的排列；E[1:n]是一维数组，且当1<=i<=n时，E[i]是H[i]所指结点的次数（即儿子结点的个数）。试给出一个算法，该算法计算森林F的树形个数，并计算森林F的最后一个树形的根结点地址。【吉林大学 1995 五(15分) …… 此处隐藏：5585字，全部文档内容请下载后查看。喜欢就下载吧 ……