习题五参考答案
一、选择题
1.对一棵树进行后根遍历操作与对这棵树所对应的二叉树进行( B )遍历操作相同。
A. 先根 B. 中根 C. 后根 D. 层次
2.在哈夫曼树中,任何一个结点它的度都是( C )。
B. 0或1 B. 1或2 C. 0或2 D. 0或1或2
3.对一棵深度为h的二叉树,其结点的个数最多为( D )。
h-1hA. 2h B. 2h-1 C. 2 D. 2-1
4.一棵非空二叉树的先根遍历与中根遍历正好相同,则该二叉树满足( A )
A. 所有结点无左孩子 B. 所有结点无右孩子
C. 只有一个根结点 D. 任意一棵二叉树
5.一棵非空二叉树的先根遍历与中根遍历正好相反,则该二叉树满足( B )
B. 所有结点无左孩子 B. 所有结点无右孩子
C. 只有一个根结点 D. 任意一棵二叉树
6.假设一棵二叉树中度为1的结点个数为5,度为2的结点个数为3,则这棵二叉树的叶结点的个数是( C )
A.2 B. 3 C. 4 D. 5
7.若某棵二叉树的先根遍历序列为ABCDEF,中根遍历序列为CBDAEF,则这棵二叉树的后根遍历序列为( B )。
A.FEDCBA B. CDBFEA C. CDBEFA D. DCBEFA
8.若某棵二叉树的后根遍历序列为DBEFCA,中根遍历序列为DBAECF,则这棵二叉树的先根遍历序列为( B )。
A.ABCDEF B. ABDCEF C. ABCDFE D. ABDECF
9.根据以权值为{2,5,7,9,12}构造的哈夫曼树所构造的哈夫曼编码中最大的长度为( B )
A.2 B. 3 C. 4 D. 5
10.在有n个结点的二叉树的二叉链表存储结构中有( C )个空的指针域。
A.n-1 B. n C. n+1 D. 0
…… 此处隐藏0字 ……
二、填空题
1. 在一棵度为m的树中,若度为1的结点有n1个,度为2的结点有n2个,……,度为m
的结点有nm个,则这棵树中的叶结点的个数为 1+n2+2n3+3n4+…+(m-1)nm 。
2. 一棵具有n个结点的二叉树,其深度最多为 n ,最少为 [log2n]+1 。
3. 一棵具有100个结点的完全二叉树,其叶结点的个数为 50 。
4. 以{5,9,12,13,20,30}为叶结点的权值所构造的哈夫曼树的带权路径长度是 217 。
5. 有m个叶结点的哈夫曼树中,结点的总数是 2m-1 。
6. 若一棵完全二叉树的第4层(根结点在第0层)有7个结点,则这棵完全二叉树的结点总