数据结构第六章复习题

第六章复习题第六章复习题 1. 列出图所示二叉树的叶结点、分支结点和每个结点的层次。 【解答】 二叉树的叶结点有、。分支结点（度不为 0 的结点）有、 、。结点的层次为 1；结点、的层次为 2； 结点、的层次为 3；结点、的层次为 4；结点的层次 为 5。 2. 使用 (1)顺序表示和 (2)二叉链表表示法，分别画出上图所示二叉 树的存储表示。 【解答】 1 2 3 4 0 5 6 0 7 0 0 0 8 0 0 0 0 9 3. 如果一棵树有 n1个度为 1 的结点, 有 n2个度为 2 的结点, , nm个 度为 m 的结点, 试问有多少个度为 0 的结点? 试推导之。 顺序表示 二叉链表表示 【解答】 总结点数 n = n0 + n1 + n2 + + nm 总分支数 e = n-1 = n0 + n1 + n2 + + nm-1 = m*nm + (m-1)*nm-1 + + 2*n2 + n1 则有 1) 1( 2 0 + = = m i i nin 4. 试分别找出满足以下条件的所有二叉树: (1) 二叉树的前序序列与中序序列相同; (2) 二叉树的中序序列与后序序列相同; (3) 二叉树的前序序列与后序序列相同。 【解答】 (1)二叉树的前序序列与中序序列相同：空树或缺左子树的单支树； (2)二叉树的中序序列与后序序列相同：空树或缺右子树的单支树； (3)二叉树的前序序列与后序序列相同：空树或只有根结点的二叉树。 5. 请画出右图所示的树所对应的二叉树。 【解答】 6. 已知一棵二叉树的先序遍历的结果是 ABECDFGHIJ, 中序遍历的 结果是 EBCDAFHIGJ, 试画出这棵二叉树。 【解答】 1 对应二叉树 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 当前序序列为 ABECDFGHIJ，中序序列为 EBCDAFHIGJ 时，逐 步形成二叉树的过程如下图所示： 7. 已知一棵树的先根次序遍历的结果与其对应二叉树表示(孩子-兄 弟表示)的前序遍历结果相同, 树的后根次序遍历结果与其对应二 叉树表示的中序遍历结果相同。试问利用树的先根次序遍历结果 和后根次序遍历结果能否唯一确定一棵树? 举例说明。 【解答】 因为给出二叉树的前序遍历序列和中序遍历序列能够唯一地确定 这棵二叉树，因此，根据题目给出的条件，利用树的先根次序遍历结 果和后根次序遍历结果能够唯一地确定一棵树。 例如， 对应二叉树的先序序列为 1, 2, 3, 4, 5, 6, 8, 7；中序序列为 3, 4, 8, 6, 7, 5, 2, 1。 树的先根遍历序列为 1, 2, 3, 4, 5, 6, 8, 7； 后根遍历序列为 3, 4, 8, 6, 7, 5, 2, 1。 8. 给定权值集合15, 03, 14, 02, 06, 09, 16, 17, 构造相应的赫夫曼树, EBCD FHIGJ A A B E F CD HIGJ A B E F C D G J HI A B E F C D G J H I 1 2 3 4 5 6 7 8 对应二叉树 1 2 3 4 5 6 7 8 并计算它的带权外部路径长度。 【解答】 此树的带权路径长度 WPL = 229。 9. 假定用于通信的电文仅由8个字母c1, c2, c3, c4, c5, c6, c7, c8组成, 各字母在电文中出现的频率分别为 5, 25, 3, 6, 10, 11, 36, 4。 试为这 8 个字母设计不等长 Huffman 编码, 并给出该电文的总码数。 【解答】 已知字母集 c1, c2, c3, c4, c5, c6, c7, c8 ，频率 5, 25, 3, 6, 10, 11, 36, 4 ，则 Huffman 编码为 c1 c2 c3 c4 c5 c6 c7 c8 0110 10 0000 0111 001 010 11 0001 15 03 14 02 06 09 1617 02 03 151406091617 05 02 03 15 14 06 09 16 17 05 11 () () () 02 03 1514 09 1617 05 11 06 20 () 02 03 14 15 09 16 17 05 11 06 20 29 0203 1415091617 05 11 06 202933 () 02 03 14 1509 05 11 06 20 29 16 17 33 49 () 0203 15 09 05 11 06 2029 1617 33 49 14 82 () 电文总码数为 4 * 3 + 4 * 4 + 3 * 10 + 3 * 11+ 4 * 5 + 4 * 6+ 2 * 25 + 2 * 36= 257 10. 填空题 (1) 对于一棵具有 n 个结点的树，该树中所有结点的度数之和为 _n-1_。（度数和就是树的分支数，因此为 n-1） (2) 假定一棵三叉树的结点个数为 50，则它的最小高度为 _5_，最大高度为_50_。(最小高度是满三叉树，最大高度为单支树) (3) 在一棵二叉树中，假定度为 2 的结点有 5 个，度为 1 的结点 有 6 个，则叶子结点数有_6_个。 （n0=n2+1） (4) 对于一棵具有 n 个结点的二叉树，对应二叉链表中指针总数 为_2n_个， 其中_ n-1_个用于指向子女结点， _ n+1_个指针空闲着。 (见教材 p126) (5) 在一个小顶堆中，堆顶结点的值是所有结点中的_最小者_， 在一个大顶堆中，堆顶结点的值是所有结点中的_最大者_。 (6) 当从一个小顶堆中删除一个元素时，需要把_最后_元素填补 到_堆顶_位置，然后再按条件把它逐层调整。 (7) 在赫夫曼编码中，若编码长度只允许小于等于 4，则除了已 100 61 39 36 25 22 17 7 10 11 11 4 3 6 5 C3C8 C5 C6 C1C4 C2 C7 0 0 0 0 0 0 0 1 1 1 1 1 1 1 对两个字符编码为 0 和 10 外，还可以最多对_4_个字符编码。 (8) 设二叉树有 n 个结点且根结点处于第 1 层，则其高度为（不 确定） 。 (9) 设高度为 h 二叉树只有度为 2 和度为 0 的结点，则该二叉树 中所含结点至少有（ 2h -1 ）个。 (除第一层之外，每层都有 2 个结点) (10) 设森林 F 中有 4 棵树，第 1、2、3、4 棵树的结点个数分别 为 n1、n2、n3、n4，当把森林 F 转换成一棵二叉树后，其根结点的右 子树中有（ n2+n3+n4 ）个结点。 (11) 设森林 F 中有 4 棵树，第 1、2、3、4 棵树的结点个数分别 为 n1、n2、n3、n4，当把森林 F 转换成一棵二叉树后，其根结点的左 子树中有（ n1-1 ）个结点。 (12) 将含有 82 个结点的完全二叉树从根结点开始顺序编号， 根结 点为第 0 号，其他结点自上向下，同一层自左向右连续编号。则 第 40 号结点的双亲结点的编号为（ 19 ） 。（编号为 i 的结点，左孩 子编号 2i+1，右孩子 2i+2） （13）高度为 h 的完全二叉树最少有 2h-1 个结点。（第 h 层只有一 个结点） （14）某二叉树结点的中序序列为 A、B、C、D、E、F、G，后序 序列为 B、D、C、A、F、G、E，则其左子树中结点数目为： （ C ） A）3 B）2 C）4 D）5 11. n 个结点可构造出多少种不同形态的二叉树? 【解答】见教材 p155 有 种。 12. 判断下列叙述的对错。如果正确，在题前打“” ，否则打“” 。 (1) 若有一个结点是二叉树中某个子树的中序遍历结果序列的最 后一个结点，则它一定是该子树的先序遍历结果序列的最后一个结 点。 （最右下结点有左孩子无右孩子） (2) 若有一个结点是二叉树中某个子树的先序遍历结果序列的最 后一个结点，则它一定是该子树的中序遍历结果序列的最后一个结 点。 （最右下结点有左孩子无右孩子） (3) 若有一个叶子结点叶子结点是二叉树中某个子树的中序遍历结果序列 的最后一个结点， 则它一定是该子树的先序遍历结果序列的最后一个 结点。 （4）在哈夫曼树中，权值最小的结点离根结点最近。( ) （5）将一棵树转换为二叉树表示后,该二叉树的根结点一定没有右 子树。( ) 13. 阅读理解题 说明下列递归过程的功能 void unknown ( BinTreeNode * T, int a , int i ) /指针 T 是完全二叉树的根指针。 if ( T != NULL ) ai = T-data; unknown ( T-leftChild, a, 2*i+1 ); unknown ( T-rightChild, a, 2*i+2 ); ) 1/(n C n 2n + 主程序调用方式 unknown ( BT.root, a, 0 ); /将完全二叉树所有结点从根开始，自顶向下，同一层自左向 右连续编号，根结点的编号为 0。 答案 将用二叉链表表示的完全二叉树转换为二叉树的顺序（数组）表 示。 14. 下面是一个使用栈stack实现对二叉树进行非递归先根遍历的函数, 请在标号处填写合适的语句。 程序: Void preorder(bitree *T) bitree *stackm; int top; if(T!=NUL