软件基础习题答案 第三章习题 1.试分别画出具有3个结点的树和具有3个结点的二叉树的所有不同形态。 解答: 具有3个结点的树只有两种不同形态:(1)和(2);具有3个结点的二叉树有下列 五种形态:(a)、(b)、(c)、(d)、(e)。 (a) (b) (c) (d) (e) 2.若一棵树有n个度为1的结点,n2个度为2的结点,…,n个度为m的结点,则这棵 树中的叶子结点有多少个? 解答: 这棵树中的叶子结点个数no=1+∑(1-1)n;=1+n2+(m-1)nm 3.给出题图3.1中所示的二叉树的先序、中序和后序遍历序列,并画出其顺序和链式存储 结构 题图3.1 解答: 先序: ABDGHCEIFJ中序: GDHBAEICFJ后序: GHDBIEJFCA 顺序存储结构: 巴凹" 链式存储结构:
软件基础习题答案 第三章习题 1．试分别画出具有 3 个结点的树和具有 3 个结点的二叉树的所有不同形态。 解答： 具有 3 个结点的树只有两种不同形态：（1）和（2）；具有 3 个结点的二叉树有下列 五种形态：（a）、（b）、（c）、（d）、（e）。 A B C （a） A B C A B C A B C A B C (1) (2) （b） （c） （d） （e） 2．若一棵树有 n1 个度为 1 的结点，n2 个度为 2 的结点，…，nm个度为 m 的结点，则这棵 树中的叶子结点有多少个？ 解答： 这棵树中的叶子结点个数 = = + − m i 1 i n0 1 (i 1)n =1 + n2+（m - 1）nm 3．给出题图 3.1 中所示的二叉树的先序、中序和后序遍历序列，并画出其顺序和链式存储 结构。 题图 3.1 解答： 先序：ABDGHCEIFJ 中序：GDHBAEICFJ 后序：GHDBIEJFCA 顺序存储结构： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 A B C D E F G H I J 链式存储结构： B C D D B E H F B J B A G B I B
G人[H[AI 4.已知一棵二叉树的中序遍历序列为 BDCEAFHG,其后序遍历序列为 DECBHGFA,试画 出这棵二叉树并写出其先序遍历序列 解答: 这棵二叉树形状为:如右图: 其先序遍历序列为 ABCDEFGH ⑥国 5.编写计算链式存储结构的二叉树中叶子结点的递归算法。 解答: 算法6.3 void CountLeaf (bstree p, int* count) //先序遍历二叉树,以 count返回二叉树中叶子结点的数目 p!=NULL if ((p->lchild!=NULL)&&(p->rchild! =NULL)) (=*count)++ /对叶子结点计数 CountLeaf( p->lchild, count) CountLeaf( p->rchild, count
4．已知一棵二叉树的中序遍历序列为 BDCEAFHG，其后序遍历序列为 DECBHGFA，试画 出这棵二叉树并写出其先序遍历序列。 解答： 这棵二叉树形状为：如右图： 其先序遍历序列为： ABCDEFGH 5．编写计算链式存储结构的二叉树中叶子结点的递归算法。 解答： 算法 6.3 void CountLeaf (bstree p, int* count) { // 先序遍历二叉树，以 count 返回二叉树中叶子结点的数目 if ( p!=NULL ) { if ((p->lchild!=NULL)&& (p->rchild!=NULL)) (*count)++; // 对叶子结点计数 CountLeaf( p->lchild, count); CountLeaf( p->rchild, count); } // if A B ^ C D ^ G ^ ^ H ^ ^ E ^ I ^ ^ F ^ J ^ H C G D F E A B
1// CountLeaf 6.现有一组关键字{50,28,73,91,56,18,34,86},画出生成的二叉排序树,并写出 对该树进行中序遍历得到的关键字序列 解答 生成的二叉排序树为:如右图: 其中序遍历得到的序列为 (18,28,34,50,56,73,86,91) 7.写出题图3,2所示的树的先序和后序遍历序列,并将此树转换成对应的二叉树 题图3 解答:先序遍历序列 ABEFHUJCDGKL 后序遍历序列 EHIJFBCKLGDA 转换成对应的二叉树:如右图 ( 8.将题图33所示的森林转换成对应的二叉树 ①① 题图3.3
} // CountLeaf 6．现有一组关键字{50，28，73，91，56，18，34，86}，画出生成的二叉排序树，并写出 对该树进行中序遍历得到的关键字序列。 解答： 生成的二叉排序树为：如右图： 其中序遍历得到的序列为： （18 ，28 ，34 ，50 ，56 ，73 ，86 ，91） 7．写出题图 3.2 所示的树的先序和后序遍历序列，并将此树转换成对应的二叉树。 题图 3. 解答：先序遍历序列： ABEFHIJCDGKL 后序遍历序列： EHIJFBCKLGDA 转换成对应的二叉树：如右图： 8．将题图 3.3 所示的森林转换成对应的二叉树。 题图 3.3 B C D D B E G B F B A J B I B H B K B L B C D D B E H B F B A G B I B L B M N B O B K B J B 18 34 56 91 73 86 50 28 G C L E D K A B F H I J
解答: 对应的二叉树为:如右图 9.假设用于通讯的电文仅有8个字母{A,B,C,D,E,F,G,H}组成,各字母在电文中 的出现频率分别为:7,19,2,6,32,3,21,10。试为这8个字母设计哈夫曼编码 解答:其哈夫曼树为:如右图 哈夫曼编码为: C:1l010 D:1100 E:10 F:1101 H:111l 10.给出题图34所示的无向图的邻接矩阵和邻接链表,并写出其深度优先搜索和广度优先 搜索序列。 题图3.4
解答： 对应的二叉树为：如右图： 9．假设用于通讯的电文仅有 8 个字母{A，B，C，D，E，F，G，H}组成，各字母在电文中 的出现频率分别为：7，19，2，6，32，3，21，10。试为这 8 个字母设计哈夫曼编码。 解答：其哈夫曼树为：如右图 哈夫曼编码为： A ：1110 B ：00 C ：11010 D ：1100 E ：10 F ：11011 G ：01 H ：1111 10．给出题图 3.4 所示的无向图的邻接矩阵和邻接链表，并写出其深度优先搜索和广度优先 搜索序列。 题图 3.4 1 2 4 3 5 6 B C D E H F A G I L M N O K J C F D A H B G E 0 0 0 0 0 0 0 1 1 1 1 1 1 1
解答: 邻接矩阵为(下图) 邻接链表存储为(下图) 1 2v2 1101 03v3 4 101011 v4 3 101101 5|v5 4 0001106[64 从Ⅵ出发顺序存储) 深度优先搜索序列:v1,v2,v3,4,v5,V6 广度优先搜索序列:v1,V2,v3,v4,v5,v6 从v1出发链式存储): 深度优先搜索序列:v,v2,v3,ⅴ5,v6,4 广度优先搜索序列:v1,v2,v3,v5,v4,v6
解答： 邻接矩阵为（下图）： 邻接链表存储为（下图）： 从 v1 出发(顺序存储) ： 深度优先搜索序列：v1, v2, v3, v4, v5, v6 广度优先搜索序列：v1, v2, v3, v4, v5, v6 从 v1 出发(链式存储) ： 深度优先搜索序列：v1, v2, v3, v5, v6, v4 广度优先搜索序列：v1, v2, v3, v5, v4, v6