《数据结构》期末复习题及参考答案 - 第6章 树和二叉树
一、 选择题
1、在二叉树的第I层(I≥1)上最多含有结点数为（ ）
A. 2I B. 2I-1-1 C. 2I-1 D. 2I -1
2、深度为6的二叉树最多有( )个结点 A．64 B.63 C.32 D.31
3、一棵树高为K的完全二叉树至少有( )个结点 A.2k –1 B.2k-1 –1 C.2k-1 D.2 k
4、有关二叉树下列说法正确的是（ ）
A. 二叉树的度为2 B. 一棵二叉树的度可以小于2 C. 二叉树中至少有一个结点的度为2 D. 二叉树中任何一个结点的度都为2
5、n个结点的线索二叉树上含有的线索数为（ ） A. 2n B. n－l C. n＋l D. n
6、线性表和树的结构区别在于（ ） A．前驱数量不同，后继数量相同 B．前驱数量相同，后继数量不同 C．前驱和后继的数量都相同 D．前驱和后继的数量都不同
7、已知一算术表达式的中缀形式为 A+B*C-D/E，后缀形式为ABC*+DE/-，则其前缀形式为( )
A．-A+B*C/DE B. -A+B*CD/E C．-+*ABC/DE D. -+A*BC/DE
8、设有一表示算术表达式的二叉树（见下图），
/
+ + * C * - D E F G B A
它所表示的算术表达式是（ ）
A. A*B+C/(D*E)+(F-G) B. (A*B+C)/(D*E)+(F-G) C. (A*B+C)/(D*E+（F-G）) D. A*B+C/D*E+F-G 9、一棵具有 n个结点的完全二叉树的树高度（深度）(符号?x?表示取不大于x的最大整数)是（ ）
A. ?log2n? B. ?log2n??1 C. ?log2(n?1)? D.?log2n??1 1
10、利用二叉链表存储树，则根结点的右指针是（ ）。
A．指向最左孩子 B．指向最右孩子 C．空 D．非空 11、已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历
的结果为（ ）。
A．CBEFDA B． FEDCBA C． CBEDFA D．不定 12、某二叉树中序序列为A,B,C,D,E,F,G，后序序列为B,D,C,A,F,G,E 则前序序列是：
A．E,G,F,A,C,D,B B．E,A,C,B,D,G,F C．E,A,G,C,F,B,D D．上面的都不对
13、若前序遍历二叉树的结果为序列A、B、C，则有_________棵不同的二叉树可以得到这一结果。 A. 3 B. 4 C. 5 D. 6
14、已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac , 则它的前序遍历是（ ）。
A. acbed B. decab C. deabc D. cedba
15、线索二叉树是一种（ ）结构。
A．逻辑 B．逻辑和存储 C．物理 D．线性
二、填空题
1、对于任意一棵二叉树，如果其叶子结点数为N0，度为1的结点数为N1，度为2的结点数为N2，则N0=___ N2 + 1_________。
2、具有256个结点的完全二叉树的深度为___9___。 3、一个深度为4的二叉树，其结点至少有 4 个，至多有 15 个： 4、深度为H 的完全二叉树至少有_ 2H-1__个结点；至多有 2H-1_个结点；H和结点总数N之间的关系是 H=?log2N?+1。 5、若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，N个结点的二叉树共有__2N__个指针域，其中有_N-1__个指针域是存放了地址，有__N+1_____个指针是空指针。 6、设一棵赫夫曼树有6个叶子结点，权值分别为3、4、7、14、15、20，则根结点的权值是__63____ 7、已知二叉树的先序遍历次序是 abdcef，中序遍历次序是 bdaecf，则它的后序遍历次序是： dbefca 。 2
8、对一棵完全二叉树，设一个结点的编号为i，若它的左孩子结点存在，则其编号为 2i ；若右孩子结点存在，则其编号为 2i+1 ；而双亲结点的编号为 ??i/2? ? 。 9、赫夫曼树是带权路径长度 最小的 二叉树，又称最优二叉树，路径上权值较大的结点离根较近。 10、下面程序段的功能是建立二叉树的算法，请在下划线处填上正确的内容。
typedef struct node { int data;
struct node *lchild;_
struct node *rchild __; } BiTNode, *BiTree;
void createBitree(BiTree &T) { scanf(―%c‖, &ch);
if(ch=='#') T=NULL ; else
{ T=( BiTNode *)malloc(sizeof(BiTNode)); T->data=ch;
createBitree(T->lchild)；___ createBitree(T->rchild); } }
11、二叉树由_根结点__，__左子树_，_右子树__三个基本单元组成。 12、树的链表存储结构常用的有三种，其中，双亲 表示法——以一组连续空间存储树的结点，在每个结点中设一个指示器指示双亲结点的位置。孩子 表示法——每个结点的孩子以单链表的形式存储，n个结点有n个孩子链表，n个头指针又组成一个线性表，并以顺序存储结构存储。孩子兄弟 表示法——以二叉链表作为树的存储结构，链表中的结点的两个指针分别指向该结点的第一个孩子结点和下一个兄弟结点。//P135-136
13、利用树的孩子兄弟表示法存储，可以将一棵树转换为__二叉树____。 14、在二叉树中，指针p所指结点为叶子结点的条件是_ p->lchild==NULL && p->rchlid==NULL _____。 15、树的孩子兄弟表示法和二叉树的二叉链表表示法，本质是一样的，只是解释不同，也就是说树（树是森林的特例，即森林中只有一棵树的特殊情况）可用二叉树唯一表示，并可使用二叉树的一些算法去解决树和森林中的问题。
16、树和二叉树逻辑上都是树形结构，但是二叉树不是树的特例，二叉树与树是两个不同的概念。二叉树的度 至多为2，树无此限制；二叉树有左右子树之分，即使在只有一个分枝
3
的情况下， 也必须指出是 左子树还是右子树，树无此限制。
三、简答题
1、已知一棵二叉树的前序遍历的结果是ABKCDFGHIJ，中序遍历的结果是KBCDAFHIGJ, 试画出这棵二叉树，并写出后序遍历结果。 答案：
当前序序列为ABKCDFGHIJ，中序序列为KBCDAFHIGJ时，逐步形成二叉树的过程如下图所示：
这棵二叉树的后序遍历结果是：K D C B I H J G F A
2、某通信电文由A、B、C、D、E、F六个字符组成，它们在电文中出现的次数（权值）分别是16，5，7，3，8，1。试画出其哈夫曼树，确定其对应的哈夫曼编码，并计算其带权路径长度。为使结果唯一，请将权值较小的结点作为其双亲的左孩子，而将权值较大的结点作为其双亲的右孩子。 答案：
哈夫曼树如下：
对应的哈夫曼编码如下： A: 0 B: 101 C: 110 D: 1001 E: 111 F: 1000
带权路径长度为: WPL=(1+3)*4+(5+7+8)*3+16*1=92
3、对下图所示二叉树分别按前序﹑中序﹑后序遍历，给出相应的结点序列，同时给二叉树
4
加上中序线索。
答案：
nullBC（1）前序序列：ABDEHCFG null（2）中序序列：DHEBAFCG
GDF（3）后序序列：HEDBFGCA
（4）中序线索见图中虚线箭头所示。
E
H
四、算法分析题
1、已知二叉树的存储结构为二叉链表，阅读下面算法，之后，对于如下所示的二叉树： （1）画出执行下面算法后所建立的结构； （2）说明该算法的功能。
typedef struct node {
DateType data； Struct node * next； }ListNode；
typedef ListNode * LinkList； LinkList Leafhead = NULL；
void Inorder ( BinTree T ) {
LinkList s；
If(T) { Inorder(T－>lchild)；
If ((!T－>lchild)&&(!T－>rchild))
{ s=(ListNode*)malloc(sizeof(ListNode))； s－>data=T－>data； s－>next=Leafhead；
5
A