数据结构复习题-第6章答案2014-6-16

1、第6章树和二叉树一、选择题（每小题 1分，共10分）1以下数据结构中，（A ）是非线性数据结构。A.树B.线性表C.队列D.栈2在一棵二叉树中第五层上的结点数最多为（B ）。A.8B.15C.16D.323. 已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为 CBAEDF,则后序遍历的结果为（A ）oA. CBEFDAB. FEDCBAC. CBEDFAD.不定4若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（B ）。A.9B.11C.15D.不确定5. 给定二叉树如图所示。设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。若遍历后的结点序列

2、为3,7,5,6,1,2,4,则其遍历方式是（ D ）oA. LRNB. NRLC. RLND. RNL6. 在下列存储形式中，哪一个不是树的存储形式？（D ）A.双亲表示法B.孩子表示法C.孩子兄弟表示法D.顺序存储表示法7. 有n个叶子的哈夫曼树的结点总数为（ D ）oA .不确定B. 2nC. 2n+1D . 2n-18. 设i为n个结点的完全二叉树结点编号，i=1 , 2, 3.n ;若i （ n-1 ） /2时，结点i的 右孩子为（B ）A.2i B.2i+1C.2i-1D.i+19. 由分别带权为9、2、5、7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为（C ）oA.23B

3、.37C.44D.4610. 一棵具有n个结点的完全二叉树的树高度（深度）是（A ）oA.+1B. log 2 n+1C.D. log 2 n-111. 由权值分别为7,9,4,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（B ）oA.36B.60C.48D.5312. 由权值分别为11, 8, 6, 2, 5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（B ） oA. 24 B. 71 C. 48 D. 5313. 具有35个结点的完全二叉树的深度为（B ）。A. 5 B. 6 C. 7 D. 814. 由权值分别为3, 8 , 6 , 2 , 5的叶子结点生成一棵哈夫曼树，它的带

4、权路径长度为（D ）.A. 24B . 55C . 72D. 5315. 任何一棵二叉树的叶子结点在前序、中序和后序遍历序列中的相对次序（A ）。A 不发生改变B 发生改变 C 不能确定 D以上都不对16具有10个叶子结点的二叉树中有（B ） 个度为2的结点。A . 8 B . 9 C . 10 D . 11二、判断题（每小题 1分，共10分）1完全二叉树中，若一个结点没有左孩子，则它必是树叶。（对 ）2二叉树的遍历结果不是唯一的。（对 ）3二叉树中序线索化后，不存在空指针域。（对 ）4. 在二叉树的第i层上至少有2i-1个结点（i>=1）。（错 ）5设T为哈夫曼树，具有 5个叶结点，树

5、T的高度最高可以是 4。（错）因为不知道树的根结点6已知二叉树的前序遍历和后序遍历序列并不能唯一地确定这棵树, 是哪一个。（错 ）7有n个叶子结点的哈夫曼树所具有的结点数为2n。（错）。8用树的前序遍历和中序遍历可以导出树的后序遍历。（错）9. 二叉树的后序遍历序列中，任意一个结点均处在其孩子结点的后面。（V ）10. 度为2的有序树是二叉树。（X ）11. 二叉树的前序遍历序列中，任意一个结点均处在其孩子结点的前面。（V ）12用一维数组存储二叉树时，总是以前序遍历顺序存储结点。（X）13若已知一棵二叉树的前序遍历序列和后序遍历序列，则可以恢复该二叉树。（X ）14.在哈夫曼树中，权值最小的

6、结点离根结点最近。（X ）三、填空题（每空1分，共10分）1具有n个结点的完全二叉树的深度为 。血疽+12设只含根结点的二叉树的高度为1,则高度为k的二叉树的最大结点数为 ，最小结点数为。2k-1、k3将一棵树转化为二叉树时，此二叉树的根节点的右子树为 。 空树 四、简答题（共10 分）1. 满二叉树和完全二叉树有什么区别?答：满二叉树是叶子一个也不少的树，而完全二叉树虽然前n-1层是满的，但最底层却允许在右边缺少连续若干个叶子结点，满二叉树是完全二叉树的一个特例。2. 画出二叉树的五种基本形态。答：二叉树的五种基本形态为:3. 在结点个数为 n（n>1）的各棵树中，高度最小的树的高度是

7、多少？它有多少个叶结点？多 少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？答：结点个数为n时，高度最小的树的高度为1,有2层；它有n-1个叶结点，1个分支结点；高度最大的树的高度为 n-1，有n层；它有1个叶结点，n-1个分支结点。4. 什么是哈夫曼（Huffman）树？答：设有n个权值W1,w2,w，构造一棵有n个叶子结点的二叉树，每个叶子的权值为 w,则带权路径长度 WPL最小的二叉树叫哈夫曼树或最优二叉树。或者：又称最优二叉树，它是n个带权叶子结点构成的所有二叉树中，带权路径长度WPL最小的二叉树。五、应用题（共40分）1. （ 8 分）已知一棵树的边的集合表

8、示为：（L,N）,（G,K）,（G,L）,（G,M）,（B,E）,（B,F）,（D,G）,（D,H）,（D,I）,（D,J）,（A,B）,（A,C）,（A,D）画出这棵树，并回答下列问题：（1）树根是哪个结点？哪些是叶子结点？哪些是非终端结点？（2）树的度是多少？各个结点的度是多少？（3）树的深度是多少？各个结点的层数是多少？以结点G为根的子树的深度是多少？2. 用一维数组存放的一棵完全二叉树如下表所示ABCDEFGHIJKL写出先序、中序、后序、层次遍历该二叉树时访问结点的顺序。3. （ 5分）对任何一棵二叉树 T,如果其终端结点数为 n°,度为2的结点数为n2,证明：n°

9、;=n2+1。4. 叙述并证明二叉树的性质3。5. （ 8分）已知一棵二叉树如下，（1）请分别写出按前序、中序、后序和层次遍历时得到的结点序列。（2 ）如果此二叉树由森林转换得到，请画出原森林中的各棵树。6. （8分）画出由下列序列得到的二叉树以及由此二叉树转化的森林：先序：EBADCFHGIKJ中序：ABCDEFGHIJK7. 有二叉树中序序列为：ABCEFGHD后序序列为：ABFHGEDC请画出此二叉树，并写出二叉树的先序遍历序列和层次遍历序列。8. （ 8分）二叉树 T的前序遍历序列和中次遍历序列分别是ABCDEF和CBEDAF,试画出该二叉树，并写出二叉树的后序遍历序列和层次遍历序列。

10、9. （ 6分）二叉树的先序序列为EBADCFHGIK；二叉树的中序序列为ABCDEFGHIJ,请画出该二叉树，并写出二叉树的后序遍历序列和层次遍历序列。10. （8分）设一棵二叉树的先序、中序遍历序列分别为先序遍历序列：A B D F C E G H中序遍历序列：B F D A G E H C请画出该二叉树，并将这棵二叉树转换成对应的树（或森林）。11. （ 8分）设一棵二叉树的前序序列为ABDGECF,中序序列为：DGBEAFHC试画出该二叉树。并写出后序和层次遍历序列。12. （6分）设给定一个权值集合W=（3 , 5, 7, 9, 11）,要求根据给定的权值集合构造一棵哈夫曼树并计算哈

11、夫曼树的带权路径长度WPL。13. （ 8 分）假设字符 a,b,c,d,e,f,g,h的使用频度分别是 0.15,0.19,0.07,0.08,0.04,0.23,0.13 , 0.11画出哈夫曼树并写出 a,b,c,d,e,f,g,h 的Huffman （哈夫曼）编码。14. （8 分）假设字符 a,b,c,d,e,f 的使用频度分 0.07,0.09,0.12,0.22,0.23,0.27，写出a,b,c,d,e,f 的 Huffman （哈夫曼）编码。15. （8 分）假设字符 a,b,c,d,e,f的使用频度分别是 0.07,0.10,0.12,0.16,0.25,0.30,构造哈夫

12、曼树并写出 a,b,c,d,e,f的哈夫曼编码。16. （6分）试分别画出具有三个结点的树和三个结点的二叉树的不同形态。17. 请画出下图所示的树所对应的二叉树。答案:18. （6分）请画出与下列二叉树对应的森林。19. 已知一棵树边的集合为<I,M>,<I,N>,<E,I>,<B,E>,<B,D>,<A,B>,<G,J>,<G,K>, <C,G>, <C,F>,<H,L>,<C,H>,<A,C>，请回答下列问题：（1）哪个是根结点？（ 2

13、）哪些是叶子结点？哪些是分支结点？ （3）哪个是结点G的双亲结点？ （ 4）哪些是结点G的祖先？（ 5）哪些是结点G的孩子？（6） 哪些是结点 E的子孙？（ 7）哪些是结点 E的兄弟？哪些是结点 F的兄弟？（8） 结点B和N的层次号分别是多少？（9）树的深度是多少？（10）以结点C为根的子树的深度是多少？20. 假设在树中，结点 x是结点y的双亲时，用（x，y）来表示树边。已知一棵树边的集合为：（ i，m），（ i，n） ,（ e，i ），（ b，e），（ b，d），（ a，b ），（ g，j ），（ g，k）, （ c，g），（ c, f），（h，l ），（c，h），（a，c） 。用树形表示

14、法画出此树，并回答下列问题：（1）哪个是根结点：（2）哪些是叶结点？（ 3）哪个是g的双亲？（4）哪些是g的祖先？（ 5）哪些是g的孩子？（ 6）哪些是e的子孙？（7）哪些是e的兄弟？哪些是f的兄弟？（ 8）结点b和n的层次各是多少？（9）树的深度是多少？ （10）以结点c为根的子树的深度是多少？（11）树的度数是多少？21. 已知一棵树边的结点为（I,M ），（I，N）,（E，l）,（B ，E），（B，D）,（C，B）,（G，L），（G，K），（A，G），（A，F）,（H，J），（A，H），（C，A），试画出这棵树，并回答下列问题:（1）哪个是根结点？（2）哪些是叶子结点？（3）树的深度是多

15、少？六、算法题（共12分）1. 编写计算二叉树深度的算法（二叉树的深度也叫二叉树的高度）。答: int Depth （BiTree T ） /返回二叉树的深度if （T ） depthLeft = Depth（ T->lchild ）;/求左子树的深度depthRight= Depth（ T->rchild ）; /求右子树的深度depthval = 1 + （depthLeft > depthRight ? depthLeft : depthRight）;/ 深度的最大值 +1else depthval = 0;return depthval;2. 编写算法：统计一个二叉树中所有叶子结点的数目。答： void CountLeaf (BiTree T, int& count)/ 在实际使用时， count 作为全局变量