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

单项选择（2010年3月二级考试）

对下列二叉树进行后序遍历的结果是【】

A、ZBTYCPXA

B、ATBZXCYP

C、ZBTACYXP

D、ATBZXCPY

答案解析

A

【解析】

按照二叉树后序遍历的方法：

在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后遍历右子树，最后访问根结点；并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。

对本题中的二叉树进行后序遍历的结果应是ZBTYCPXA。

讨论

数据结构与算法

支持子程序调用的数据结构是【】。

某二叉树有5个度为2的结点，则该二叉树中的叶子结点数是【】。

一棵二叉树有10个度为1的结点，7个度为2的结点，则该二叉树共有结点个数为【】。

某二叉树共有7个结点，其中叶子结点只有1个，则该二叉树的深度为（假设根结点在第1层）【】

深度为5的满二叉树有__________个叶子结点。

一棵二叉树的中序遍历结果为DBEAFC，前序遍历结果为ABDECF，则后序遍历结果为 __________。

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

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

对于正整数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); }

二叉树

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

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

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

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

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

什么是啥夫曼（Huffman）树？

在数据结构中，【】是与存储结构无关的术语。

在有 6 个字符组成的字符集 S 中，各个字符出现的频次分别为 3、4、5、6、8、10，为 S 构造的哈夫曼树的加权平均长度为【】

已知一棵二叉树的树形如图，若其后序遍历为 f、d、b、e、c、a，则其先序列为【】

某二叉树中度为2的结点有18个，则该二叉树中有__________个叶子结点。

树和二叉树

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

某二又树的先序遍历序列为 ABCDFGE，中序遍历序列为 BAFDGCE。以下关于该二又树的叙述中，正确的是【】。

对于一般的树结构，可以采用孩子-兄弟表示法，即每个结点设置两个指针域，一个指针(左指针)指示当前结点的第一个孩子结点，另一个指针(右指针)指示当前结点的下一个兄弟结点。某树的孩子-兄弟表示如下图所示。以下关于结点 D 与 E 的关系的叙述中，正确的是【】。

对下图所示的二叉树进行中序遍历(左子树、根结点、右子树)的结果是【】。

在深度为7的满二叉树中，叶子结点的个数为【】

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

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

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

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

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