数据结构第四到第六章的练习题
一、单项选择题
1、设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为_______。
A、2h
B、2h-1
C、2h+1
D、h+1
2、已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是_______。
A、acbed
B、decab
C、deabc
D、cedba
3、如果T2是由有序树T转换而来的二叉树，那么T中结点的后序就是T2中结点的_______。
A、前序
B、中序
C、后序
D、层次序
4、按照二叉树的定义，具有3个结点的二叉树有_______种。
A、3
B、4
C、5
D、6
5、对一个满二叉树,m个树叶,n个结点，深度为h，则_______。
A、n=h+m
B、h+m=2n
C、m=h-1
D、n=2m-1
二、填空题
1、已知完全二叉树的第7层有8个结点，则其叶子结点数是_______。
2、在有n个叶子结点的哈夫曼树中，总结点数是_______。
3、一棵二叉树的第i（i>=1）层最多有_______个结点；一棵有n（n>0）个结点的满二叉树共有_______个叶子和_______个非终端结点。
三、综合设计题
1、指出树和二叉树的主要差别，深度为k的二叉树，以顺序结构存储，最坏情况下浪费的空间为多少？并以k=4为例，画出最坏情况下的二叉树结构。
2、画出以数据集{4，5，6，7，10，12，18}为结点权值所构造的Huffman树，其带权路径长度WPL为多少？
四、算法设计
1、二叉树采用链接存储结构，试设计一个按层次顺序（同一层次自左至右）遍历二叉树的算法（非递归算法）
2、二叉树采用链接存储结构，设计一个算法计算一棵给定二叉树的所有结点数。
提示：递归模型如下：
f（b）=0 若b=NULL
f（b）=1 若b->left=NULL且b->right=NULL
f（b）=f（b->left）+f ( b->right)+1 其他
树和二叉树单元练习
一、判断题（下列各题，正确的请在后面的括号内打√；错误的打Χ）
_____1．树结构中每个结点最多只有一个直接前驱，但是可以有多个直接后继。
_____2．满二叉树一定是完全二叉树。
_____3．在中序线索二叉树中，右线索若不为空，则一定指向其双亲。
_____4．二叉树的前序遍历中，任意一个结点均处于其孩子结点的前面。
_____5．由二叉树的前序遍历序列和中序遍历序列，可以推导出后序遍历的序列。
_____6．在完全二叉树中，若一个结点没有左孩子，则它必然是叶子结点。
_____7．在哈夫曼编码中，当两个字符出现的频率相同，其编码也相同，对于这种情况应该做特殊处理。
_____8．含多于两棵树的森林转换的二叉树，其根结点一定无右孩子。
_____9．具有n个叶子结点的哈夫曼树共有2n-1个结点。
_____10．一棵完全二叉树中序遍历序列的最后一个结点，必定是该二叉树前序遍历的最后一个结点。
二、填空题
1．在树中，一个结点所拥有的子树数称为该结点的(1)__________，度为零的结点称为(2)__________结点，树中结点的最大层次称为树的(3)__________。
2．对于二叉树来说，第i层上至多有(4)__________个结点，深度为h的二叉树至多有(5)__________个结点。
3．有20个结点的完全二叉树，编号为10的结点的父结点的编号是(6)__________。
4．某二叉树的中序遍历序列为：ABDECFGH，中序遍历序列为：DEBAFCHG，则二叉树的后序遍历序列为：(7)__________。
5．由树转换成二叉树时，其根结点无(8)__________。
6．三个结点可以组成(9)__________种不同形态的树。
7．采用二叉链表存储的n个结点的二叉树，一共有(10)__________个指针域。
三、选择题
1．树最适合用来表示_____。
A）有序数据元素B）无序数据元素
C）元素之间无联系的数据 D）元素之间有分支的层次关系2．前序为ABC的二叉树共有_____种。
A）2 B）3 C）4 D）5
3．A、B为一棵二叉树上的两个结点，在中序遍历时，A在B前的条件是_____。
A）A在B后方B）A是B祖先C）A在B下方D）A是B子孙
4．具有n（n>1）个结点的完全二叉树中，结点i（2i>n）的左孩子结点是_____。
A）2i B）2i+1 C）2i-1 D）不存在5．把一棵树转换为二叉树后，这棵二叉树的形态是_____。
A）唯一的B）有多种
C）有多种，但根结点都没有左孩子D）有多种，但根结点都没有右孩子6．二叉树按某种是顺序线索后，任一结点均有指向其前驱和后继的线索，这种说法_____。
A）正确 B）错误C）不确定 D）都有可能7．下列陈述正确的是_____。
A）二叉树是度为2的有序树
B）二叉树中结点只有一个孩子时无左右之分
C）二叉树中必有度为2的结点
D）二叉树中最多只有两棵子树，且有左右子树之分
8．用5个权值{3,2,4,5,1}构造的哈夫曼树的带权路径长度是_____。
A）32 B）33 C）34 D）35
9．在树结构中，若结点B有4个兄弟，A是B的父结点，则A的度为_____。
A）3 B）4 C）5 D）6
10．二叉树的叶子结点个数比度为2的结点的个数_____。
A）无关B）相等C）多一个D）少一个
四、综合题
1．已知一棵树边的集合如下，请画出此树，并回答问题。
{(L,M0,(L,N),(E,L),(B,E),(B,D),(A,B),(G,J),(G,K),(C,G),(C,F),( H,I),(C,H),(A,C)}
（1）根结点：__________ （2）叶子结点：__________
（3）G的双亲：__________ （4）G的祖先：__________
（5）G的孩子：__________ （6）E的子孙：__________
（7）E的兄弟：__________，F的兄弟：__________
（8）B的层次：__________，N的层次：__________
（9）树的深度：__________，以结点C为根的子树的深度：__________
（10）树的度：__________
2．假设用于通信的电文仅由A、B、C、D、E、F、G、H这8个字母组成，字母在电文中出现的频率分别为7、1、2、6、32、3、21、10。
试为这8个字母设计哈夫曼编码。
单元练习五图结构
一、单项选择题
1、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的_______倍。
A、1/2
B、1
C、2
D、4
2、具有4个顶点的无向完全图有_______条边。
A、6
B、12
C、16
D、20
3、具有6个顶点的无向图至少应有_______条边才能确保是一个连通图。
A、5
B、6
C、7
D、8
4、采用邻接表存储的图的深度优先遍历算法类似于二叉树的_______。
A、先序遍历
B、中序遍历
C、后序遍历
D、按层遍历
二、填空题
1、在无权图G的邻接矩阵A中，若（vi，vj）或<vi,vj>属于图G的边集合，则对应元素A[i][j]等于_______，否则等于_______。
2、已知一个图的邻接矩阵表示，计算第i个结点的入度的方法是_______。
3、在有n个结点的无向图中，其边数最多为_______。
4、有n个顶点的连通图至少有_______个结点。
三、综合设计题
1、用宽度优先搜索和深度优先搜索对下图G进行遍历（从顶点1出发），给出遍历序列。