文档介绍：This model paper was revised by the Standardization Office on December 10, 2020
树和二叉树****题数据结构<br****题六 树和二叉树
一、00} D．{b,c,aa,ac,aba,abb,abc}
22. 一棵有n个结点的二叉树，按层次从上到下，同一层从左到右顺序存储在一维数组A[1..n]中，则二叉树中第i个结点（i从1开始用上述方法编号）的右孩子在数组A中的位置是（ ）
A．A[2i](2i<=n) B．A[2i+1](2i+1<=n)
C．A[i-2] D．条件不充分，无法确定
23、以下说法错误的是 ( )
A．哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。
B．若一个二叉树的树叶是某子树的中序遍历序列中的第一个结点，则它必是该子树的后序遍历序列中的第一个结点。
C．已知二叉树的前序遍历和后序遍历序列并不能惟一地确定这棵树，因为不知道树的根结点是哪一个。
D．在前序遍历二叉树的序列中，任何结点的子树的所有结点都是直接跟在该结点的之后。
二、判断题（在各题后填写“√”或“×”）
1. 完全二叉树一定存在度为1的结点。( )
2．对于有N个结点的二叉树，其高度为log2n。( )
3. 二叉树的遍历只是为了在应用中找到一种线性次序。( )
4. 一棵一般树的结点的前序遍历和后序遍历分别与它相应二叉树的结点前序遍历和后序遍历是一致的。( )
5. 用一维数组存储二叉树时，总是以前序遍历顺序存储结点。( )
6．中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。 ( )
7．完全二叉树中，若一个结点没有左孩子，则它必是树叶。( )
8. 二叉树只能用二叉链表表示。( )
9. 给定一棵树，可以找到唯一的一棵二叉树与之对应。( )
10. 用链表(llink-rlink)存储包含n个结点的二叉树，结点的2n个指针区域中有n-1个空指针。( )
11．树形结构中元素之间存在一个对多个的关系。( )
12．将一棵树转成二叉树，根结点没有左子树。( )
13．度为二的树就是二叉树。( )
14. 二叉树中序线索化后，不存在空指针域。( )
15．霍夫曼树的结点个数不能是偶数。( )
16．哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。( )
三、填空题
1．在二叉树中，指针p所指结点为叶子结点的条件是___ ___。
2．深度为k的完全二叉树至少有___ ____个结点，至多有___ ____个结点。
3．高度为8的完全二叉树至少有______个叶子结点。
,一共有________个指针域,其中只有________个用来指向结点的左右孩子，其余的________个指针域为NULL。
5．树的主要遍历方法有________、________、________等三种。
6．一个深度为k的，具有最少结点数的完全二叉树按层次，（同层次从左到右）用自然数依此对结点编号，则编号最小的叶子的序号是__ _；编号是i的结点所在的层次号是_ __（根所在的层次号规定为1层）。
7．如果结点A有 3个兄弟，而且B是A的双亲，则B的度是______。
8．二叉树的先序序列和中序序列相同的条件是___ ___。
9．一个无序序列可以通过构造一棵___ ___树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。
10．若一个二叉树的叶子结点是某子树的中序遍历序列中的最后一个结点，则它必是该子树的____ __序列中的最后一个结点。
11．若以{4，5，6，7，8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度是______。
12．以下程序段采用先根遍历方法求二叉树的叶子数，请在横线处填充适当的语句。
Void countleaf(bitreptr t,int *count)/*根指针为t，假定叶子数count的初值为0*/
{if(t!=NULL)
{if((t->lchild==NULL)&&(t->rchild==NULL))________;
countleaf(t->lchild,&count);
________