离散数学题(3) 求解 20+5

来源：百度知道 编辑：UC知道 时间：2024/06/01 05:57:00
第四章 图
4-1 10 个顶点的简单图 G 中有 4 个奇度顶点，问 G 的补图中有几个奇度顶点 ？

4-2 是非判断：无向图G中有10条边,4个3度顶点,其余顶点度数全是2,共有 8 个顶点. [ ]

4-3 填空补缺：1条边的图 G 中，所有顶点的度数之和为 [ ]

第五章 树
5-1 握手定理的应用（指无向树）
（1）在一棵树中有 7 片树叶，3 个 3 度顶点，其余都是 4 度顶点，问有( )个？
（2）一棵树有两个 4 度顶点，3 个 3 度顶点，其余都是树叶，问有( )片？

5-2 一棵树中有 i 个顶点的度数为 i（=2，…k），其余顶点都是树叶，问树叶多少片？
设有x片,则x=

5-3 求最优 2 元树：用 Huffman 算法求带权为 1，2，3，5，7，8 的最优 2 元树 T。试问：（1） T 的权 W（T）？ （2）树高几层 ？

5-4 以下给出的符号串集合中，那些是前缀码？将结果填入[ ]内.
B1 = {0，10，110，1111} [ ]
B2 = {1，01，001，000} [ ]
B3 = {a，b，c，aa，ac，aba，abb，abc} [ ]
B4 = {1，11，101，001，0011} [ ]

5-5(是非判断题)11阶无向连通图G中17条边，其任一棵生成树 T 中必有6条树枝 [ ]

5-6(是非判断题)二元正则树有奇数个顶点。材

4-1 10 个顶点的简单图 G 中有4个奇度顶点，问G的补图中有几个奇度顶点？

答案：6个奇度顶点。

4-2 是非判断：无向图G中有10条边,4个3度顶点,其余顶点度数全是2,共有8个顶点. 

答案：[对，是]

4-3 填空补缺：1条边的图 G 中，所有顶点的度数之和为 [2]

答案：所有顶点的度数之和为2。

5-1  握手定理的应用（指无向树）

（1）在一棵树中有7片树叶，3个3 度顶点，其余都是4度顶点，问有( 1 )个？

（2）一棵树有两个4度顶点，3个3度顶点，其余都是树叶，问有( 7 )片？

5-2 一棵树中有i个顶点的度数为ai（i=2，…,k），其余顶点都是树叶，问树叶多少片？

 设有x片,则x=3*a3+4*a4+…+k*ak-2(a3+a4+…+ak)+2

5-3 求最优 2 元树：用 Huffman 算法求带权为 1，2，3，5，7，8 的最优 2 元树 T。试问：（1）T 的权W（T）=61，（2）树高5层。 

5-4  以下给出的符号串集合中，那些是前缀码？将结果填入[    ]内.

         B1 = {0，10，110，1111}