数据结构与算法-等级考试试题(二级考试 2007年4月二叉树)

单项选择（2007年4月二级考试）

已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为【】

A、GEDHFBCA

B、DGEBHFCA

C、ABCDEFGH

D、ACBFEDHG

答案解析

B二叉树的遍历有3种：前序、中序和后序。前序遍历首先访问根结点，然后遍历左子树或左子结点，最后遍历右子树或右子结点；中序遍历首先遍历左子树或左子结点，然后访问根结点，最后遍历右子树或右子结点；后序遍历...

查看完整答案

讨论

数据结构与算法

树是结点的集合，它的根结点数目是【】

对于正整数n ，输出其和等于n且满足以下限制条件的所有正整数的和式，组成和式的数字自左至右构成一个非递增的序列。如 n = 4 ，程序输出为：4 = 44 = 3 + 14 = 2 + 24 = 2 ＋ 1 ＋ 1 4 = 1 ＋ 1 ＋ 1 ＋ 1test 是实现该功能的 C 程序段，请将未完成的部分补足，使之完整。test 函数为一递归函数，参数 n 为被分解和式的数， k 为当前的分解深度。算法思想是对 n 的所有合理的和式分解，将分解出的数（称为和数）存于二数组 a[]中。当其中一个分解己不再需要进一步进行时，即找到一个解，将存于 a[] 中的一个完整和式的和数输出。当还需要进一部分解时，以要进一部分解的数及分解深度为参数，递归调用 test 函数。#define MAXN 100 int a[MAXN]; test(int n,int k){ int i,j; for (j=__________；j>=1；j--）{ a[k]=j; if (__________）{ printf ( "%d = %d" , a[0]，a[l]); for (i = 2 ; i < = k ; i + + ) printf ( " + % d " , a[i]); printf ( " n " ); }else test(__________，k + l ); } }

写出和下列递归过程等价的非递归过程。void test(int sum){ int a; scanf("%d",&a); if(a==0) sum=1; else{ test(sum); sum=sum*a; } pritf("%d",sum); }

一般情况下，将递归转换成等价的非递归算法应该设置【】

用数组 Q（其下标在 0 . . n-1 中，共有n个元素）表示一个环形队列， f 为当前队头元素的前一位置， r 为队尾元素的位置。假定队列中元素个数总小于 n ,求队列中元素个数的公式是__________。

设栈 S 和队列 Q 的初始状态为空，元素 a 、 b 、 c 、 d 、e、 f 依次通过栈 S ，一个元素出栈后即进入队列 Q 。若这 6 个元素出队列的顺序是 b 、 d 、 c 、f、 e 、 a ，则栈 S 的容量至少应该是__________。

顺序队列一般应该组织成为环状队列的形式，而且一般队列头或尾其中之一应该特殊处理。例如，队列为 listarray [ 0 ... n-1] ，队列头指针为front ，队列尾指针为 rear ，则 listarray[rear]表示下一个可以插入队列的位置。请解释其原因。

设一单项链表的头指针为head，链表的记录中包含整数类型的key域，试设计算法，将此链表的记录按照key递增的顺序进行就地排序。

中缀表达式 A-(B + c/d) * E的后缀形式是【】

用数组表示的循环队列的队首和队尾位置分别为1和 max_size，试给出判断队列为空和为满的边界条件。

二叉树

具有7个结点的互不相识的二叉树共有__________棵。

一个深度为 h 的满 m 叉树有如下性质：第 h 层上的结点都是叶结点，其各层上每个结点有 m 棵非空子树。问：（1）第 k 层最多有多少个结点？（k≤h )（2）整棵树最多有多少个结点？（3）若按层次从上到下，每层从左到右的顺序从1开始对全部结点编号，编号为 i 的结汽的双亲结点的编号是什么？编号为 i 的结点的第 j 个孩子结点（若存在）的编号是什么？

证明，由一棵二叉树的前序序列和中序序列可唯一地确定这棵二叉树。设一棵二叉树的前序序列为ABDGECFH，中序序列为DGBEAFHC，试画出该二叉树。

已知一棵二叉树的前序遍历结果是ADCEBFIHGJ，中序遍历结果是CDEBAFHGIJ，试画出这棵二叉树。

用一维数组存放的一棵完全二叉树如下：A、B、C、D、E、F、G、H、I、J、K、L写出后序遍历该二叉树时访问结点的顺序。

一棵二叉树按中序遍历时各结点被访问的次序和这棵二叉树按后序遍历时各结点被访问的次序能否唯一确定这棵二叉树的结构？为什么？若已知一棵二叉树按先序遍历时各结点被访问的次序和这棵二叉树按后序遍历时各结点被访问的次序，能否唯一确定这棵二叉树的结构？为什么？

对于二叉树T 的两个结点 n1 和 n2 ，我们应该选择树 T 结点的前序、中序和后序中哪两个序列来判断结点 n1 必定是结点 n2的祖先，并给出判断的方法。不需证明判断方法的正确性。

证明一棵二叉树无论进行先序、中序、后序遍历，其叶子结点的相对次序不发生改变。

对二叉排序树进行【】遍历，可以得到该二叉树所有结点构成的排序序列。

若二叉树采用二叉链表存储结构，要交换其所有分支结点左右子树的位置，利用【】遍历方法最合适。

树和二叉树

有n个数顺序（依次）进栈，则出栈顺序有Cn种。Cn=×

已知一棵度为m的树中有N1个度为1的结点，N2个度为2的结点，...，Nm个度为m的结点。试问该树中有多少个叶子结点？

已知一棵二叉树，如果先序遍历的顺序是ADCEFGHB，中序遍历的顺序是CDFEGHAB，则后序遍历的结果为【】。

具有n个叶子的二叉树，每个叶子的权值为wi（1≤i≤n），其中带权路径长度最小的二叉树称为__________。

啥夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。

什么是啥夫曼（Huffman）树？

在叶子数目和权值相同的所有二叉树中，最优二叉树一定是完全二叉树，该说法【】。

线索二叉树是一种【】结构。

二叉树在线索化后，仍不能有效求解的问题是【】。

二叉树中，具有两个子女的结点的中序后继结点最多只能有一个子女。