软件基础习题答案
第三章习题
试分别画出具有3个结点的树和具有3个结点的二叉树的所有不同形态。
解答：
具有3个结点的树只有两种不同形态：（1）和（2）；具有3个结点的二叉树有下列五种形态：（a）、（b）、（c）、（d）、（e）。
若一棵树有n1个度为1的结点，n2个度为2的结点，…，nm个度为m的结点，则这棵树中的叶子结点有多少个？
解答：
这棵树中的叶子结点个数 =1 + n2 +（m - 1）nm
给出题图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
链式存储结构：
已知一棵二叉树的中序遍历序列为BDCEAFHG，其后序遍历序列为DECBHGFA，试画出这棵二叉树并写出其先序遍历序列。
解答：
这棵二叉树形状为：如右图,
其先序遍历序列为：
ABCDEFGH
编写计算链式存储结构的二叉树中叶子结点的递归算法。
解答：
算法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
} // CountLeaf
现有一组关键字{50，28，73，91，56，18，34，86}，画出生成的二叉排序树，并写出对该树进行中序遍历得到的关键字序列。
解答：
生成的二叉排序树为：如右图：
其中序遍历得到的序列为：
（18,28,34,50,56,73,86,91）
写出题图3.2所示的树的先序和后序遍历序列，并将此树转换成对应的二叉树。
题图3.
解答：先序遍历序列：
ABEFHIJCDGKL
后序遍历序列：
EHIJFBCKLGDA
转换成对应的二叉树：如右图：
将题图3.3所示的森林转换成对应的二叉树。
题图3.3
解答：
对应的二叉树为：如右图：
假设用于通讯的电文仅有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
解答,
邻接矩阵为（下图）,邻接链表存储为（下图）：
从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
第三章习题
试分别画出具有3个结点的树和具有3个结点的二叉树的所有不同形态。
解答：
具有3个结点的树只有两种不同形态：（1）和（2）；具有3个结点的二叉树有下列五种形态：（a）、（b）、（c）、（d）、（e）。
若一棵树有n1个度为1的结点，n2个度为2的结点，…，nm个度为m的结点，则这棵树中的叶子结点有多少个？
解答：
这棵树中的叶子结点个数 =1 + n2 +（m - 1）nm
给出题图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
链式存储结构：
已知一棵二叉树的中序遍历序列为BDCEAFHG，其后序遍历序列为DECBHGFA，试画出这棵二叉树并写出其先序遍历序列。
解答：
这棵二叉树形状为：如右图,
其先序遍历序列为：
ABCDEFGH
编写计算链式存储结构的二叉树中叶子结点的递归算法。
解答：
算法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
} // CountLeaf
现有一组关键字{50，28，73，91，56，18，34，86}，画出生成的二叉排序树，并写出对该树进行中序遍历得到的关键字序列。
解答：
生成的二叉排序树为：如右图：
其中序遍历得到的序列为：
（18,28,34,50,56,73,86,91）
写出题图3.2所示的树的先序和后序遍历序列，并将此树转换成对应的二叉树。
题图3.
解答：先序遍历序列：
ABEFHIJCDGKL
后序遍历序列：
EHIJFBCKLGDA
转换成对应的二叉树：如右图：
将题图3.3所示的森林转换成对应的二叉树。
题图3.3
解答：
对应的二叉树为：如右图：
假设用于通讯的电文仅有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
解答,
邻接矩阵为（下图）,邻接链表存储为（下图）：
从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
