习题6
1.判断图1中哪些是欧拉图？对不是欧拉图的至少要加多少条边才能成为欧拉图？
图1
解答：是。否，1条。否，2条。
2.画一个无向欧拉图，使它具有：
(1)偶数个顶点，偶数条边。
(2)奇数个顶点，奇数条边。
(3)偶数个顶点，奇数条边。
(4)奇数个顶点，偶数条边。
解答：(1)C4（4圈）
(2)C3（3圈）
(3)
(4)
3.判断彼得松图是否为欧拉图，是否为哈密顿图。若不是，至少加几条新边才能使它成为欧拉图？又至
少加几条新边才能使它变成哈密顿图?
解答：不是欧拉图，也不是哈密顿图。加5条新边可以成为欧拉图，加1条边可以成为哈密顿图。
4.判断图2所示的四个图是否能一笔画出。
图2
解答：否。是。是。
5.(1)画一个欧拉回路和哈密顿回路的图；
(2)画一个欧拉回路，但没有哈密顿回路的图；
(3)画一个没有欧拉回路，但有哈密顿回路的图；
(4)画一个既没有欧拉回路，也没有哈密顿回路的图。
解答：(1)C 3（3圈）
(2)
(3)
(4)
6.设有a ,b ,c ,d ,e ,f ,g 七个人，他们分别会讲如下各种语言：a 会讲英语；b 会讲汉语和英语；c 会讲英语、西班牙语和俄语；d 会讲汉语和日语；e 会讲德语和西班牙语；f 会讲法语、日语和俄语；g 会讲法语和德语。能否将七个人的座位安排在圆桌旁，使得每个人均能与他身边的人交谈。
解答：分别用a ,b ,c ,d ,e ,f ,g 七个结点表示七个人，若两人能够交谈（使用同一种语言），则在代表他们的结点之间连一条无向边，如下图a 所示。将七个人的座位安排在圆桌旁，使得每个人均能与他身边的人交谈，只需出一条哈密顿回路，如abdfgeca 。
7.国际象棋中的马走日字，即在()y x ，格子的马可以走到()1,2±±y x ，()2,1±±y x 中的任何一个，只要棋盘中有这个格子。马从某个格子开始，走遍所有的格子且每个格子只走一次称作马的周游。证明：
(1)在43⨯的棋盘上存在马的周游。
(2)在33⨯的棋盘上不存在马的周游。
证明：每个格子看成一个顶点，两个顶点之间相邻当且仅当马可以从对应的一个格子跳到另一个格子。因此，马的周游问题等价于图中的哈密顿通路存在问题。
(1)对于43⨯的棋盘，可以使用以下走法（格子中数字代表走的步数）：
1
471012
92536118
(2)对于33⨯的棋盘，不可能存在哈密顿通路，因此中心格子对应的顶点是孤立点。
8.一棵无向树T 有5片树叶，3个2度分支点，其余的分支点都是3度结点，问T 有几个结点？
解答：假设T 有n 个结点，根据握手定理，有5323(53)2(1)n n +⨯+⨯--=⨯-得n =11。9.无向树T 有8片树叶，2个3度分支点，其余的分支点都是4度顶点，问T 有几个顶点？解答：假设T 有n 个顶点，根据握手定理，有
，得n =12
10.一棵无向树T 有),,3,2(k i n i  =个i 度分支点，其余顶点都是树叶，问T 有几片树叶？解答：假设T 有n 个顶点，x 片树叶。那么23k n x n n n =++++ 。另外，根据握手定理，有232(1)23k n x n n kn -=++++ ，从而得33(2)22(2)k k i i x n k n i n
==++-+=+-∑ 。
11.若)3(≥n n 阶无向树T 的最大度()T ∆至少为几，最多为几？
解答：至少为2，至多为n -1。
12.根树T 如图3所示。回答以下问题：
(1)T 是几叉树？
(2)T 的树高为几？
(3)T 有几个内点？
(4)T 有几个分支点？
图3
解答：(1)
T 是4叉树。(2)T
的树高为4。(3)T
有8个内点。
(4)T 有7个分支点。
13.画一棵权为9,8,7,6,5,4,3的最优二叉树，并计算出它的权。解答：（最优二叉树不唯一）
权：(34)4(567)3(89)2116+⨯+++⨯++⨯=。
14.下面给出的各符号串集合哪些是前缀码？
{}
1111,110,10,01=A {}
000,001,01,12=A {}
0011,001,101,11,13=A {}
abc abb aba dc dd c b A ,,,,,,4={}
aba abb abc ac aa a c b A ,,,,,,,5=解答：A 1：是；A 2：是；A 3：否；A 4：是；A 5：否。
15.用图4中的二叉树产生一个二元前缀码。
图4
解答：{000,001,1000,101,11}。
16.设7个字母在通信中出现的频率如下：
%35:a %20:b %15:c %10:d %10:e %5:f %5:g 构造一组表示它们的二元前缀码，使得传送的二进制位最少。解答：（答案不唯一）
二元前缀码为{0000,0001,001,01,100,101,11}。
17.图5中的二叉树表示一个算式。
(1)用中序遍历法还原算式。
(2)用前序遍历法写出该算式的波兰符号法表达式。
(3)用后序遍历法写出该算式的逆波兰符号法表达式。
图5
解答：(1)
(2)
二叉树公式
(3)
18.用二叉有序正则树表示代数表达式
解答：