《第五章树练习答案》由会员分享，可在线阅读，更多相关《第五章树练习答案（6页珍藏版）》请在金锄头文库上搜索。
1、第五章树练习答案一、 单项选择题（每题2分，共26分）1) 树最适合用来表示（ C ）A有序数据元素 B.无序数据元素C. 元素之间具有分支层次关系的数据 D.元素之间无联系的数据2) 如图所示的4棵二叉树中，（ C ）不是完全二叉树。（a）（b）（d）3) 二叉树按某种顺序线索化后，任一结点均有指向其前驱和后续的线索，这种说法（ B ）A. 正确 B.错误4) 如图1-1所示二叉树的中序遍历序列是（ B ）。A. abdgcefh B. dgbaechf C. gdbehfca D. abcdefghacbdgehf图1-15) 如果是T2是由有序树T1转换而来的二叉树，那么T1中结点的先序
2、就是T2中结点的（ A ）。A. 先序 B. 中序 C. 后序 D. 层次序6) 某二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定是（ D ）。A. 空或只有一个结点 B. 完全二叉树C. 二叉排序树 D. 高度等于其结点数7) 树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵树对应的二叉树。结论（ A ）是正确的。A. 树的先根遍历序列与其对应的二叉树的先序遍历序列相同。B. 树的后根遍历序列与其对应的二叉树的后序遍历序列相同。C. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同。D.
3、以上都不对8) 如图所示的T2是由森林T1转换而来的二叉树，那么森里T1有（ C ）个叶子结点。A. 4 B. 5 C. 6 D. 7aebcdfihjg9) 深度为5的二叉树至多有（ C ）个结点。A. 16 B. 32 C. 31 D. 1010) 在一非空二叉树的中序遍历序列中，根结点的右边（ A ）。A. 只有右子树上的所有结点 B. 只有右子树的部分结点C. 只有左子树上的部分结点 D. 只有左子树上的所有结点11) 设n，m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是（ C ）。A. n在m右方 B. n是m是祖先 C. n在m左方 D. n是m子孙12) 线索二叉树是
4、一种（ C ）结构。A. 逻辑 B. 逻辑和存储 C. 物理 D. 线性（说明：线索二叉树是二叉树的一种存储（物理）结构）13) 根据使用频率为5个字符设计的哈夫曼编码不可能是（ C ）。A. 111,110,10,01,00 B. 000,001,010,011,1C. 100,11,10,1,0 D. 001,000,01,11,10k1k2k3k4k5k6k7二、 填空题1) 有一棵树如图所示，回答下面的问题（7分）：(1) 这棵树的根节点（k1）；(2) 这棵树的叶子结点是（k2,k5,k7,k4）；(3) 结点k3的度是（2）；(4) 这棵树的度是（3）；(5) 这棵树的深度是（4）
5、；(6) 结点k3的孩子结点是（k5,k6）；(7) 结点k3的双亲结点是（k1）2) 指出树和二叉树的三个主要差别（树的结点个数至少为1，而二叉树的结点个数可以为0），树中结点的最大度数没有限制，而二叉树结点的最大度数为2），（树的结点无左、右之分，而二叉树的结点有左右之分）。（3分）3) 一棵二叉树的结点数据采用顺序存储结构，存储于数组t中，如图所示，则该二叉树的链式存储表示形式为（ ）。（5分）123456789101112131415161718192021eafdgcjihb4) 在一棵二叉树中，度为零的结点的个数为n0，度为2的结点的个数为n2，则有 n0=（n2+1）（2分）5)
6、 现有按中序遍历二叉树的结果为abc，问有（5）种不同形态的二叉树可以得到这一遍历结果，这些二叉树分别是（ ）。（6分）acbdgehfi6) 由如图所示的二叉树，回答以下问题。（1） 其中序遍历序列为（dgbaechif）；（2分）（2） 其先序遍历序列为（Abdgcefhi）；（2分）（3） 其后序遍历序列为（gdbeihfca）；（2分）（4） 该二叉树的中序线索二叉树为（）；（5分）NULLNULLabdcefhig（5） 该二叉树的后序线索二叉链表为（）；（5分）0a00b10c00f11e11d01h01g11i1NULL（6） 该二叉树对应的森林是（）。（3分）abdgcefhi
7、三、 简答题1) 假设二叉树采用顺序存储结构，如图所示1234567891011121314151617181920eafdgcjhib（1） 画出二叉树表示；（5分）（2） 写出先序遍历，中序遍历和后序遍历的结果； 解：先序遍历序列：eadcbjfghi（3分） 中序遍历序列：abcdjefhgi（3分） 后序遍历序列：bcjdahigfe（3分）（3） 写出结点值c的双亲结点，其左、右孩子；（3分）解：c的双亲结点为d，左孩子为b，没有右孩子。（4） 画出把此二叉树还原成森林的图（4分）2) 已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，给出它的先序遍历序列。（5分）解：该二叉树的先序遍历序列为cedba3) 有一份电文中共使用5个字符：a、b、c、d、e，它们的出现频率依次为4、7、5、2、9，试画出对应的哈夫曼树（请按左子树根结点的权小于等于右子树根结点的权次序构造），并求出每个字符的哈夫曼编码。（6分）271116c6beda00001111解：a：011b：10c：00d：010e：114) 设给定权集w=2,3,4,7,8,9,试构造关于w的一棵哈夫曼树，并求其加权路径长度WPL。93387151832549解：WPL7*2+8*2+4*3+2*4+3*4+9*2=806 / 6
