习题树和二叉树

1、习题6树和二叉树说明：本文档中，凡红色字标出的题请提交纸质作业，只写题号和答案即可。6.1 单项选择题1 .由于二叉树中每个结点的度最大为2,所以二叉树是一种特殊的树，这种说法_B_OA.正确B.错误2 .假定在一棵二叉树中，双分支结点数为15,单分支结点数为 30个，则叶子结点数为B 个。A. 15 B. 16 C. 17 D. 473 .按照二叉树的定义，具有3个结点的不同形状的二叉树有_C_种。A. 3B. 4 C. 5 D. 64 .按照二叉树的定义，具有3个不同数据结点的不同的二叉树有_C_种。A. 5B. 6 C. 30 D. 325 .深度为5的二叉树至多有_C_个结点。A. 1

2、6 B. 32 C. 31 D. 106 .设高度为h的二叉树上只有度为 0和度为2的结点，则此类二叉树中所包含的结点数至少为BOA. 2hB. 2h-1 C. 2h+1 D. h+17 .对一个满二叉树，m个树叶，n个结点，深度为h,则_A_ 。A. n=h+mB. h+m=2n C. m=h-1D. n=2 h-18 .任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序_A_OA.不发生改变B.发生改变C.不能确定D.以上都不对9 .如果某二叉树的前根次序遍历结果为stuwv,中序遍历为uwtvs,那么该二叉树的后序为 _C_OA. uwvtsB. vwutsC. wuvts D

3、. wutsv10 .二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法_A_。 A.正确B.错误11 .某二叉树的前序遍历结点访问顺序是 遍历的结点访问顺序是_D_。A. bdgcefha B. gdbecfha12 .在一非空二叉树的中序遍历序列中， A.只有右子树上的所有结点 C.只有左子树上的部分结点abdgcefh,中序遍历的结点访问顺序是dgbaechf,C. bdgaechf 根结点的右边D. gdbehfca _A_O则其后序13.如图6.1所示二叉树的中序遍历序列是B.只有右子树上的部分结点D.只有左子树上的所有结点_B_O历时,A.abcdgefab列为d

4、gA. gdbehfca 15.设 a,b a在b前的条图6.114. 一棵B 。16.A. acbedB. dfebagcD. defbagcC. dbaefcgabg图6.2二叉树如图6.2所示，其中序遍历的序. a在b的右方C. a是b的祖先 已知某二叉树的后序遍历序列是B.decab C.deabcabdgcefh B. dgbaechfD. abcdefgh为一棵二叉树上的两个结点, 件是 B 。B. a在b的左方C.在中序遍D. a是b的子孙 dabec,中序遍历序列是 D.cedbadebac,它的前序遍历序列是_D_O_C_存储结17 .实现任意二叉树的后序遍历的非递归算法而不

5、使用栈结构，最佳方案是二叉树采用 构。A.二叉链表B.广义表存储结构C.三叉链表 D.顺序存储结构18 .如图6.3所示的4棵二叉树，_C_不是完全二叉树。图6.324.树的基本遍 历策略可分为先根 遍历和后根遍历；二 叉树的基本遍历策 略可分为先序遍历、 中序遍历和后序遍 历。这里，我们把由 树转化得到的二叉树叫做这棵数对应的二叉树。结论_A_是正确的。A.树的先根遍历序列与其对应的二叉树的先序遍历序列相同B.树的后根遍历序列与其对应的二叉树的后序遍历序列相同 C.树的先根遍历序列与其对应的二叉树的中序遍历序列相同 D.以上都不对25.树最适合用来表示 _C_。A.有序数据元素C.元素之间具

6、有分支层次关系的数据B.无序数据元素D.元素之间无联系的数据6.2 填空题(将正确的答案填在相应的空中)1.有一棵树如图6.5所示，回答下面的问题：这棵树的卞B吉点是_k0_;这棵树的叶子结点是； 结点k3的度是_2_; 这棵树白度是_3_; 这棵树的深度是_4_;(6)结点k3的子女是_k5,k6_;结点k3的父结点是_k1_;2.指出树和二叉树的三个主要差别：树的结点个数至少为1,而二叉树的结点个数可以树中结点的最大度数没有限制，而二叉树结点的最大度数为2树的结点无左、右之分，而二叉树的结点有左、右之分3.从概念上讲，树与二叉树是两种不同的数据结构，将树转化为二叉树的基本目的是 叉树的存储

7、结构并利用二叉树的已有算法解决树的有关问题。为0树可采用4. 一棵二叉树的结点数据采用顺序存储结构，存储于数组t中，如图6.6所示,则该二叉树的链接表示形式为图6.6 一棵二叉树的顺序存储数组 t5 .深度为k的完全二叉树至少有 _2k-1_个结点。至多有 _2k-1_个结点，若按自上而下，从左到 右次序给结点编号(从1开始)，则编号最小的叶子结点的编号是_1k-2+1。6 .在一棵二叉树中，度为零的结点的个数为n 0,度为2的结点的个数为 n 2,则有no=_n2+1_7 . 一棵二叉树的第i (i>1)层最多有_2i-1_个结点；一棵有 n (n>0)个结点的满二叉树共有_(n

8、+1)/2_个叶子和_(n-1)/2个非终端结点。8 .结点最少的树为只有一个结点的树结点最少的二叉树为空的二叉树_。9 .现有按中序遍历二叉树的结果为abc,问有_5_种不同形态的二叉树可以得到这一遍历结果，这些二叉树分别是。10 .由如图6.7所示的二叉树，回答以下问题:其中序遍历序列为_dgbaechif_;其前序遍历序列为_abdgcefhi_ ;其后序遍历序列为gdbeihfca;6.3 简答题1 .根据二叉树的定义，具有三个结点的二叉树有5种不同的形态，请将它们分别画出。2 .假设一棵二叉树的先序序列为 EBADCFHGIKJ中序序列为ABCDEFGHIJK 请画出该树。3.由如图

9、6.7所示的二叉树，请画出该二叉树对应的森林。图6.7 一棵二叉树图6.8 一棵树4. 已知一棵树如图 6.8所示，转化为一棵二叉树，表示为 。5. 以数据集 4 ， 5， 6， 7， 10 ， 12， 18为结点权值，画出构造Huffman 树的每一步图示，计算其带权路径长度为。6. 一棵含有N个结点的k叉树，可能达到的最大深度和最小深度各为多少？最大深度： h=N-k+1, 最小深度： logkN+17. 证明：一棵满k叉树上的叶子结点数 n0和非叶子结点数n1之间满足以下关系：n 0=(k-1)n 1 +16.4 算法设计题1 . 编写按层次顺序(同一层自左至右)遍历二叉树的算法。2 试编写算法，对一棵二叉树, 统计叶子的个数。3 试编写算法，对一棵二叉树根结点不变，将左、右子树进行交换，树中每个结点的左、右子树进 行交换。7. 假设用于通讯的电文仅有八个字母(a,b,c,d,e,f,g,h) 组成，字母在电文中出现的频率分别为0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.