一、填空题
1、含5个结点，4条边的无向连通图（不同构）有3个，它们是。
?0??1A??1??1?2、设图G =
101001001??1?0??0??，则v1的入度
deg?(v1)= 3，v4的出度deg?(v4)= 1，从v2到v4的长度2的路有1条。 3、n个结点的无向完全图Kn的边数为。n(n-1)/2
4、图的对偶图为。
5、一棵树有7片树叶，3个3度结点，其余全是4度结点，则该树有1 个4度结点。
二、选择题
1、图中从v1到v3长度为3 的通路有（D）条。
A．0
B．1
C．2
D． 3
2、下图中既不是Eular图，也不是Hamilton图的图是（B）。
1
3、在一棵树中有7片树叶，2个3度结点，其余都是4度结点则该树有（A） 个4度结点。 A．1
B．2
C．3
D．4
4、设G=
A、完全图 B、树 C、简单图 D、多重图
5、给定无向图G=
A、{?v1,v4?,?v3,v4?} B、{?v1,v5?,?v4,v6?} C、{?v4,v7?,?v4,v8?} D、{?v1,v2?,?v2,v3?}
6、有n个结点n≧3，m条边的连通简单图是平面图的必要条件（D）。 A、n?3m?6 B、n?3m?6 C、m?3n?6 D、m?3n?6 7、设V={a, b, c, d, e, f },
E?{?a,b?,?b,c?,?c,a?,?a,d?,?d,e?,?f,e?}，则有向图G= E>是（C）。 A、强连通的 B、单向连通的 C、弱连通的 D、不连通的 8、下面那一个图可一笔画出（A）。 9、在任何图中必定有偶数个（C）。 A、度数为偶数的结点 B、入度为奇数的结点 C、度数为奇数的结点D、出度为奇数的结点 10、给定下列序列，（B）可以构成无向简单图的结点次数序列。 A、（1，1，2，2，3） B、（1，1，2，2，2） C、（0，1，3，3，3） D、（1，3，4，4，5） 2 11、设G是简单有向图，可达矩阵P(G)刻划下列（C）关系。 A、点与边 B、边与点 C、点与点 D、边与边 12、一颗树有两个2度结点，1个3度结点和3个4度结点，则1度结点数为（C）。 A、5 B、7 C、9 D、8 三、 计算题 1. 权数1，4，9，16，25，36，49，64，81，100构造一棵最优二叉树。 2. 一棵树T中，有3个2度结点，一个3度结点，其余结点都是树叶。 （1）T中有几个结点； （2）画出具有上述度数的所有非同构的无向图。 解：（1）设该树树叶数为t，则树T的结点数为3+1+t，又边数=结点数-1， ?deg(v)?边数2倍，∴3?2?1?3?t?1?2(3?t?1?1) i即9?t?6?2t，∵t?3，∴ T中7个结点。 （2）具有3个两度结点，一个3度结点，3片树叶的树（非同构的）共有以下三种： 3、如图给出的赋权图表示六个城市a, b, c, d, e, f 及架起城市间直接通讯线路的预测造价。试给出一个设计方案使得各城市间能够通讯且总造价最小，并计算出最小总造价。 3 解：要设计一个方案使各城市间能够通讯且总造价最小，即要求该图连通、无回路、边权之和最小的子图即最小生成树，由避圈法或破圈法可得其最小生成树为： 其树权即最小造价为：1+2+3+5+7=18。 4. 设7个符号在通讯中使用的频率如下： a：35% ，b：20% ，c：15% ，d：10% ， e：10% ，f：5% ，g ：5% 编一个相应的二元前缀码，使通讯中出现的符号尽可能地减少，并画出对应的二叉树及求二叉树的过程。 解：用100乘各频率得权数： w1=35， w2=20， w3=15， w4=10， w5=10， w6=5， w7=5 将其由小到大排列用Huffman算法可求得最优树。 5 5 10 10 15 20 35 10 10 10 15 20 35 20 10 15 20 35 20 25 20 35 40 25 35 40 100 最优二叉树为: 编码树为： 前缀码：a：11； b：01； c：101； d：100； e：001；f：0000；g：0001 4 60 5、假设英文字母，a，e，h，n，p，r，w，y出现的频率分别为12%，8%，15%，7%，6%，10%，5%，10%，求传输它们的最佳前缀码，并给出happy new year的编码信息。 解：根据权数构造最优二叉树。传输它们的最佳前缀码如上图所示，happy new year的编码信息为：10 011 0101 0101 001 110 111 0100 001 111 011 000 5