有n（n>1）个顶的树T，下面说法不正确的是 A．T是二分图? B．T是可平面图? C．T中存在完美匹配? D．T中任意两点间有唯一轨道相连接
设G是有n个结点，m条边的连通图，为了得到G的一棵生成树，必须从G中删去的边数是
A．m?n+1 B．m?n C．m+n+1 D．n?m+1
无向简单图G是棵树，当且仅当
A．G连通且边数比顶点数少1 B．G连通且顶点数比边数少1 C．G的边数比顶点数少1 D．G中没有圈
下面给出的集合中，哪一个是前缀码 A．{0，10，110，101111} B．{01，001，000，1} C．{b，c，aa，ab，aba} D．{1，11，101，001，0011}
给定一个序列集合{1，01，10，11，001，000}，若去掉其中的元素 ?，则该序列集合构成前缀码。
若一棵典型有序二元树有2n?1个顶点，则它的树叶数是 A．n B．2n C．n?1 D．2
下面那种描述的单图不一定是树。 A．无回路的连通图 B．有n个顶点，n?1条边的图 C．每对顶点都有通路的图 D．连通但删去一条边则不连通的图
下列无向图一定是树的是 A．连通图? B．无圈但添加一条边后有圈的图? C．每对顶点间都有路的图? D．连通且E(G)?V(G)?1
求生成树个数时，将一个树对应一个Prufer序列，如果树T的对应Prufer序列为(2,3,2,3)，则标号为2的顶点的次数是 A．1 B．2 C．3 D．4
右图是二分图。
一个有13个顶的简单图G中有3个顶的次数是4，4个顶的次数是3，6个顶的次数是1，则图G一定是树。
设树T中有2个3度顶点和3个4度顶点，其余的顶点都是树叶，则T中有 片树叶。 10
若T是图G的生成树，则 A．T必唯一 B．G不一定是连通图 C．T中必不含圈 D．G中不含圈
若G是一个含p个顶点，q条边的图，若q≥p，则G中必有圈。
有4个连通片组成的17个顶的森林的边数为 A．16 B．15 C．14 D．13
设G是一个满足|E(G)|≥|V(G)|的图，则G中必有圈。
在下图中，用Kruskal算法构造最小生成树，写出边添加到生成树的边序列，并画出生成树。
f2e 5867 1gad
6563
b4c
f2e答：
5
1ga d 53 b4c
求下图的最优树T（不要求中间过程，只要求画出最小生成树, 并给出T的权和）。
16 46234 7255 13
答： 14 242
13
权和为17。
求下图的最小生成树，并给出权值(只给结果，不要过程)
47 466139 512 1054125169 答：
权和为28。
求下图的最小生成树，并给出权值。
v2v42 1344 7535v1v6 v1v7683234
4v3v5 v2v42 143v1v6权和为16。 v81v7 32 v3v5
假设用于通信的电文仅由8个字母 {a, b, c, d, e, f, g, h} 构成，它们在电文中出现的概率分别为{ 0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10}，试为这8个字母设计哈夫曼编码。 解：a, 1100；b, 00；c, 11110；d, 1110；e,10；f, 11111；g, 01；h,1101
1.00 0.40.6
0.190.210.320.28
0.110.17
0.070.100.060.05
画出带权0,2，0.17，0.13，0.1，0.1，0.08，0.06，0.06，
0.020.030.07，0.03的Huffman树。
1.00
0.400.60 0.200.200.260.34 0.100.100.130.130.170.17画出带权0.1，0.1，0.1，0.1，0.15，0.2，0.25
0.060.070.080.09的Huffman树。
0.030.061.000.40.20.60.20.250.10.10.350.150.20.10.1
假定通信中出现的字母为a, b, c, d, e, f, g, h，其出现的频率如下表。试画出这组字母（权）的Huffman树，要求给出求解过程。 字母 频率 a 25% b 20% c 15% d 15% e 10% f 5% g 5% h 5%
1
0.550.45
ab0.25 0.3
c0.1d0.15
ghef
设T是树叶权为1，2，3，4，5的Huffman树，那么树T的带权路径长为 。33
有99个顶点的典型有序二元树的叶子数是 。
一个出城汽车队行驶时不得超车，但每车都可以进入路过的一个胡同里去加油，再在某时刻退出胡同插队继续开行，共有5辆不同的汽车。则开出城的不同车队种数是 。
行餐后姊妹去洗碗，洗前已把5个不同花色的碗摞成一摞。妹妹把姐姐洗过的碗每次拿一个放入消毒柜，也摞成一摞。由于小妹贪玩，碗被放入消毒柜可能不及时，姐姐则把洗过的碗摞在旁边，则小妹摞起的碗摞可能的种数是 。 答：42
对一个括号序列进行检测，从左向右数到第99个括号时，记录了右括号 个，因此得出结论为坏括号序列。 50
对一个好括号序列进行检测，从左向右至少数到第 个括号时，会记录下50个右括号。 100
画出所有不同构的5顶点树。
以下说法错误的是
A. 同构的图具有相同的顶点数和边数 B. 同胚的图边数相同，但顶点数不同 C. 如果一个图是可平面的，那么与它同构的图也是可平面的 D. 如果一个图是可平面的，那么与它同胚的图也是可平面的
如果一个3－正则简单平面图的每个面都有3条边，则这个图的边数是 A．3 B．4 C．5 D．6
图H是下面平面图G的一个平面嵌入，则图H的面数是 A．5 B．6 C．7 D．8
如果平面图G有v个顶点，e条边和f个平面，则 A．v?e?f?2 B．e?v?f?2 C．v?e?f?2 D．e?v?f?2
具有6 个顶点，12条边的连通简单平面图中，每个面的边数是 A．2 B．3 C．4 D．5
设G为一个连通的平面图，G有5个顶点和9条边，则G有 个面。6
n(n≥3)阶极大平面图的面数等于 。 2n?4
n(n≥3)阶极大平面图的边数等于 。 3n?6
100个顶点的极大连通平面图中最多有? 个面。 196 100个面的极大连通平面图中最多有 个顶点。 52
画出面数最多的5顶点连通平面图的平面嵌入，并指出它有几个面。
6个面。
如果单图G是平面图，那么它一定有一个次数不超过5的顶。 不妨设G是连通的，否则考虑它的每一个连通分支。
设G有n个顶，m条边，f个面。因为G是单图，每个面至少有三条边，所以3f≤2m。 如果每个顶的次数都不小于6，那么有6n≤2m。
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库2013四川师范大学 图论期末考试复习题(2)在线全文阅读。
相关推荐：