第一部分：数理逻辑
1 下列语句是命题的是( ）：
A.15能被3整除，3是偶数吗？ B.明年5月1日是晴天 C.2X+3>0 D.我在说谎. 2下列叙述中有( ）个命题
(1)离散数学是计算机科学系的一门必修课 (2) 地球外的星球上也有人 (3) 我正在说谎. (4)请不要吸烟 A.1个 B.2个 C. 3个 D. 4个 3 下列语句中不是命题的只有（ ） ．．A．这个语句是假的。 C．飞碟来自地球外的星球。
B．1+1=1.0
D．凡石头都可练成金。
4 设p：我很累，q：我去学习，命题：“除非我很累，否则我就去学习”的符号化正确的是 A．┐p∧q C．┐p→┐q
B．┐p→q D．p→┐q
5 令p：今天下雪了，q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（ ）
A. p∧┐q B．p∨┐q C. p∧q D．p→┐q 6使用逻辑连接词将下列复合命题符合化： （1） 如果天不下雪且我有时间，我就进城； （2） 我进城的必要条件是我有时间； （3） 天不下雪或我不进城；
（4） 我进城当且仅当我有时间且天不下雪。
7判断下面一段论述是否为真：“?是无理数。并且，如果3是无理数，则2也是无理数。另外6能被2整除，6才能被4整除。”
11. 将下列命题符号化 (1)2或3是素数. (2)4或6是素数.
1
(3)小元元只能拿一个苹果或一个梨.
(4)王晓红生于1975年或1976年.
8命题公式q∧(p∨┐q)的成真赋值是＿＿＿＿＿＿＿＿＿＿＿＿ 9命题公式p∨(┐p→(q∨(┐q→r)))的成假赋值是＿＿＿＿＿＿＿＿ 10 命题公式(p→(q∧r))∧(┐p→(┐q∧┐r))的成真赋值是＿＿＿ 11 命题公式p→(p∧(q→r))的成假赋值是＿＿＿＿＿＿＿＿＿＿＿＿ 12..下列命题公式中是重言式的为（ ）
A.?(p?q)?q B. (p?q)?r C.(p?q)?(p??q) D.((p?q)?p)?p
13 命题公式“(p?q)??p?q”，是__________。（永真式、非永真式的可满足式、矛盾式）
14.命题公式“(?p?q)?(p?(p?q))”，是__________。（永真式、非永真式的可满足式、矛盾式）
15.命题公式“(?p?q)??(q??r)??(r??p??q)”，是（ ） A.永真式 B. 非永真式的可满足式 C.矛盾式 D. 不确定 16. 下列为永假式的是（ ）。
A、 ?(P?Q)?Q B、(P?(P?Q))?Q C、 (P??P)?Q D、(P??P)??P 17. 设P，Q 的真值为0，R，S的真值为1，则
?(P?(Q?(R??P)))?(R??S)的真值= 。
18. 全体小项合取式为（ ）。
A、可满足式； B、永假式； C、永真式； D、A，B，C 都可能。 19. 全体大项析取式为（ ）。
A、可满足式； B、永假式； C、永真式； D、A，B，C 都可能。
20. 设命题公式G??P?(?Q?R)，则公式G的主合取范式是_____________________。 21. 命题公式G= (P ? Q) ? (?P ? Q) ，则其主合取范式为 。
2
22. 已知命题公式含有三个命题变元，且其主析取范式为m0?m1?m3，则其主合取范式为( )。
A、 m2?m4?m5?m6?m7 B、 M2 C、 M2?M4?M5?M6?M7 D、 m2 23. 证明下列恒等式：
(1)(P?Q)?(Q?R)?P?Q?R (2)(P?Q)?(?P?Q)?F 24. 证明下列恒等式：
(1) P?(Q?R)?(P?Q)?R (2) (P?Q)?(?P?Q)?T
25.设公式A含命题变项p、q、r，又已知A的主合取范式为M0?M2?M3?M5,则A的主析取范式为 。
26.设公式A含命题变项p、q、r，又已知A的主析取范式为m1?m4?m6?m7,则A的主合取范式为 。
27 一个命题公式A(P,Q,R)的成真指派为000，001，010，100，110，则其主析取范式为 .
28 一个命题公式A(P,Q,R)的成假指派为000，001，010，100，110，则其主合取范式为 .
29在自然推理系统P中构造下面推理的证明： 前提：q?p,q?s,s?t,t?r 结论：p?q
30 构造下面命题推理的证明
如果我学习，那么我数学不会不及格；如果我不热衷于玩游戏机，那么我将学习；但我数学不及格，因此我热衷与玩游戏机。
31 在自然推理系统中构造下面推理的证明：
若数a 是实数，则它不是有理数就是无理数。若a 不能表示成分数，则它不是有理数。a 是实数且它不能表示成分数。所以a 是无理数。 32证明下面推理：
前提： p?(q?r),q?(r?s)
3
结论: (p?q)?s 33证明下面推理：
前提： p?(q?s),q,p??r 结论: r?s
34已知今天下雨或刮风；如果今天下雨，那么我在家看书；如果今天刮风，那么我去放风筝；今天我没有在家看书。所以今天刮风并且我去放风筝了。 35 在自然推理系统中用归谬法证明下面各推理： 前提：p??q,?r?q,r??s 结论：?p
36. 将命题“没有人登上过木星” 用谓词符合化 37.将命题“在美国留学的学生未必都是亚洲人” 用谓词符合化 38.将命题“兔子比乌龟跑的快” 用谓词符合化
39.将命题“有的兔子比所有的乌龟跑的快” 用谓词符合化 答案：??x?y(F(x)?G(x)?H(x,y))，其中F(x):x是兔子，G(x):x是乌龟，
40.将命题“并不是所有的兔子都比乌龟跑的快” 用谓词符合化 41 用谓词公式将下列语句形式化： （1）发亮的东西不都是金子。
（2）不是所有的男人都至少比一个女人高，但至少有一个男人比所有的女人高。 42论域D={1，2}，指定谓词P
P (1,1) P (1,2) P (2,1) P (2,2) T T F F 则公式(?x)(?y)P(y,x)真值为 。
43 表达式?x(P(x,y)??zQ(y,x,z))??yR(y,z)?F(y)中?x的辖域是( )． A．Q(y,x,z) B．(P(x,y)??zQ(y,x,z)) C．R(y,z) D．(P(x,y)
44 设谓词的定义域是{a,b,c},试将表达式?xR（x）??xS(x)中的量词消除，写成与之等价的命题公式＿＿＿＿＿＿＿＿＿＿＿＿＿＿
答案: ( R(a) ?R(b) ?R(c)) ?( S(a) ?S(b) ?S(c))
4
45 设谓词的定义域是{a,b,c},试将表达式?x?yH(x,y)中的量词消除，写成与之等价的命题公式＿＿＿＿＿＿＿＿＿＿＿＿＿＿
46 将?x（P(x) ?R(x,y)）?Q(x,y)中的变量换名或替代，使其不含既是约束出现又是自由出现的个体变量
47将?x(P(x) ?(R(x) ?Q(x) ? ?xR(x)) ??zS(x,z)中的变量换名或替代，使其不含既是约束出现又是自由出现的个体变量 48 设B不含有x，?x(A(x)?B)等值于 ( )
A.?xA(x)?B B.?x(A(x)?B) C.?xA(x)?B D.?x(A(x)?B) 49下列四个公式正确的是
①?x(A(x)?B(x))??xA(x)??xB(x) ②?x(A(x)?B(x))??xA(x)??xB(x) ③?x(A(x)?B(x))??xA(x)??xB(x) ④?xA(x)??xB(x)??x(A(x)?B(x)) A.①③ B.①④ C.③④ D.②④ 50 量词否定等值式??xA(x)? ___________________。 答案: ?x?A(x)
51. 谓词合式公式(?x)P(x)?(?x)Q(x)的前束范式为 。
52. 给出下面公式的前束合取范式。
(?x)(P(x)?Q(x,y))?((?y)P(y)?(?z)Q(y,z))
53 求?xF(x)??y(G(x,y)?H(x,y))的前束范式。
54试将?x（??y P(x，y) ?（?zQ(z) ? R(x)））化成等价的前束范式。 55 试将?x?y(（?zP（x,y,z）??uQ(x,u)）??vQ(y,v))化成等价的前束范式 56.构造下面推理的证明
前提：?x(F(x)?G(x))，?xF(x)
结论：?xG(x)
57 前提： ?x(F(x)?G(x)?H(x)),?x(F(x)?R(x))
5
结论: ?x(F(x)?R(x)?G(x)) 58 构造下面推理的证明:
前提: ?xF(x)??y((F(y)?G(y))?R(y)),?xF(x)
结论: ?xR(x) 59 构造下面推理的证明
不存在能表示成分数的无理数。有理数都能表示成分数。因此，有理数都不是无理数。 60 构造下面推理的证明
人都喜欢吃蔬菜。但不是所有的人都喜欢吃鱼。所以，存在喜欢吃蔬菜而不喜欢吃鱼的人。
61. 设A(x):x能被3整除；B(x):x能被6整除；个体域为：{1,2,6,7,12}。则下列各式真值为F的是( )。
A、 (?x)A(x) B、 (?x)(A(x)?B(x)) C、 (?x)(A(x)?B(x)) D、 (?x)(A(x)?B(x))
第二部分：集合论
1. 下列关于集合的表示中，正确的是（ ）。 A、{a}?{{a}}； B、{{?}}?{?,{?}}； C、??{{?},?}； D、??{{?}}。 2. 下列关于集合的表示中，正确的是（ ）。 A、 C、
?a???a,b,c? B、 ?a???a,b,c?
???a,b,c? D、
?a,b???a,b,c,?a,b,c??
3 集合A={1,{2},3,4},B={a,b,{c}},则下列叙述正确的是（ ） A. {1}∈A B. {c}∈B
6
C. ??{{2}}?A D. {a，b，c}?B 4 集合A={1,{2},3,4},B={a,b,{c}},则不正确的是（ ）
A. {1，{2}，4}?A B. ?∈{{2}，3} C. ??A D. ??{{2}}?A 5 集合{a，{b}}的幂集是 设集合A=?，则其幂集2=______________答案: {Φ}
A
6 设S,T,M是集合，下列结论正确的是（ ） A．如果S∪T=S∪M，则T=M B．如果S-T=Φ，则S=T C．S?S?S D．S?T?S?(~T) 7 设A,B,C是三个非空集合,则( )是正确的.
A.A?B?A?C?B?C B.A?B?A?C?B?C C.A?B?A?C?B?C D. A?B?A?C?B?C 8 以下叙述正确的是（ ）
A. 若A?B,则A∩B=B B. 若a?A,则a∈A∪B C. 若a∈A∪B,则a∈A D. 若A?B,则A∩B=A 9 设A，B，C为三个任意集合，试证明 （1）若A×A=B×B，则A=B；
（2）若A×B=A×C，且A≠?,则B=C. 10 设A,B,C是任意集合，证明 (1)(A-B)-C=A- B?C (2)(A-B)-C=(A-C)-(B-C)
11若集合A的元素个数为10，则其幂集的元素个数为（ ）． A．1024 B．10 C．100 D．1 12 已知A,B是集合│A│=15，│B│=10，│A∪B│=20，则│A∩B│=（ ） A．10 B．5 C．20 D．13
13 对100学生的调查表明，有32人学日语，20人学法语，45人学英语．7人既学日语又学法语，15人既学日语又学英语，10人既学法语又学英语．30人不学这三门语言中的任何一种．求
7
(1) 3门语言都学的学生人数；
(2) 只学日语，只学法语，只学英语的学生人数； (3) 至少学习两门语言的学生人数．
14 某班有25个学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。已知6个会打网球的人都会打篮球或排球。求不会打球的人数。
15、设A?{0,1}，B?{1,2}，求B?A? 16、设A和B为有限集，|A|=m，|B|=n，则有 个从A到B的关系。 17、设A为有限集，且|A|=m，则有 个从A上的关系。
18、设A?{0,1}，，求A上的全域关系 19、设A?{0,1}，，求A上的小于等于关系
3，4，5，6，8，}，20、设A?{2，，求A上的恒等关系 3，4，5，6，8，}，21、设A?{2，，求A上的整除关系
22、设A?{1，2，3，4}，试用元素法表示R?{x,yx是y的倍数}
23 集合A＝{ a , b }，写出P(A)和P(A)上的包含关系?的集合表达式是
24 已知集合A＝{a,b,c}上的二元关系R的关系矩阵MR＝，那么R＝( )
A. {
?????????? R?{1,1,1,2,2,4,3,1,3,3} ???????? S?{1,3,2,2,3,2,4,4}
试用定义求R?S，S?R，R，R，S2?1?1，R?1?S?1，并画出其关系图。
26 设R={<1,2>,<1,3>,<2,2>,<2,4>,<3,2>}, 则R?{1}= 27 设R={<1,2>,<1,3>,<2,2>,<2,4>,<3,2>}, 则R?{2,3} =
8
答案：{<2,2>,<2,4>,<3,2>}
28 设R={<1,2>,<1,3>,<2,2>,<2,4>,<3,2>}, 则R[{1}] = 答案：{2,3}
29 设R={<1,2>,<1,3>,<2,2>,<2,4>,<3,2>}, 则R[{3}]= 答案：{2}
30、设R?(x,yx,y?N且x?3y?12，求（1）R的集合表达式，（2）求R?{2,3,4,6}，（3）求R?{3}?，（4）求R3
31 设R是集合A上的二元关系，IA是上的恒等关系，下面四个命题为真的是 ( ) A.R是自反的 B.R是传递的 C.R是对称的 D.R是反对称的 32、集合A?{1,2,3}上的关系
R?{1,1,2,2,3,3}不具有的性质是（ ）
A.自反性 B.反自发性 C.对称性 D.反对称性 33、集合A?{1,2,3}上的关系（ ）
A.自反性 B. 传递性 C.对称性 D.反对称性 34、下面关系图所描述的关系具有的性质是（ ）
R?{1,1,2,2,3,32,3,3,2}不具有的性质是
A.对称的 B.反对称的 C.自反的 D.传递的
35、设A?{1,2,3}，举出A上关系R的例子，使它具有下述性质： （1）R是对称的又是反对称的 （2）R既不是对称的又不是反对称的 （3）R是可传递的
36 设R是A={1，2，3，4}上的二元关系,R={<1,1>,<1,2>,<2,3>,<3,4>},则R的自反闭包是 。
答案: {<1,1>,<1,2>,<2,3>,<3,4>,<4,3>，<2,2>,<3,3>,<4,4>}
9
37 设R是A={1，2，3，4}上的二元关系,R={<1,1>,<1,2>,<2,3>,<3,4>},则R的对称闭包是 。
答案: {<1,1>,<1,2>,<2,1>,<2,3>,<3,2>,<3,4>,<4,3>}
38 设R是A={1，2，3，4}上的二元关系,R={<1,1>,<1,2>,<2,3>,<3,4>},则R的传递闭包是 。
39、下列关系是等价关系的是（ ）
A. 三角形的全等关系 B.朋友关系 C.同事关系 D.父子关系 40．A?{1,2,3,,8}，R是A上的模3同余关系，则A/R=
答案：{{1,4,7},{2,5,8},{3,6}}
41 设A={1，2，3，4}，在A?A上定义二元关系R，
?
42. A?{1,2,3}，??{{1},{2,3}}是A的一个划分，则由?所确定的等价关系为
43、A?{1,2,3}，则在A上可以定义 种不同的等价关系。 44、R为N?N上的二元关系，
?a,b,c,d?N?N,a,bRc,d?b?d，
证明：（1）R为等价关系，（2）求R导出的划分。
45、设R是非空集合A上的关系，如果R是 ，则称R是A上的偏序关系。
46、下列关系不是偏序关系的是（ ） A. 集合的包含关系 B. 数集上的小于关系
C. 数集上的等于关系 D.数集上的小于等于关系
47 设集合A={a，b，c，d，e}，偏序关系R的哈斯图下图所示，则元素的关系不正确的是（ ）。
10
ecabdg
fA．c?d B．a?e C．a?c D．d?e
48 设集合A={a，b，c，d，e}，偏序关系R的哈斯图下图所示，则A上的极大元是 ，极小元是 ，最大元是 ，最小元是 。
ecabdg
f49 设A??3,5,9,15?上的整除关系R?a1,a2a1,a2?A,a1整除a2，R是否为A上的偏序关系？若是，则：
（1）、画出R的哈斯图；（2）、求A的极大值和A的极小值。
50 设A??1,2,3,5,6,9,15,27,36,45?上的整除关系R?a1,a2a1,a2?A,a1整除a2，
????R是否为A上的偏序关系？若是，则：（1）、画出R的哈斯图； 的最小上界lub?2,9?和最大下界glb?2,9?。 （2）、求?2,9?51 画出下列偏序集 >的哈斯图,并找出A的极大元`极小元`最大元和最小 ={ >的哈斯图.分别写出集合A和偏序关系R 的集合表达式. 52 下图是两个偏序集 bcfdeg a 53、针对下面的哈斯图，写出集合以及偏序关系的表达式 11 答案： A={1,2,3,4,5}，R={1,3,1,5,2,4,2,5,3,54,5?IA 54. 设A={1，2，3，4}，A上关系图为 则R= 。 55. 设R，S是集合A上的关系，则下列说法正确的是（ ）。 A、若R，S 是自反的， 则R?S是自反的； B、若R，S 是反自反的， 则R?S是反自反的； C、若R，S 是对称的， 则R?S是对称的； D、若R，S 是传递的， 则R?S是传递的。 56. 设A?{1,2,3,4},R?{?1,2?,?2,2?},则R为（ ）。 A、自反的 B、反自反的 C、传递的 D、等价的 57. 设A={1，2，3}，则A上的二元关系有（ ）个。 A、 23 ； B、 32 ； C、 23?32； D、 32?2。 58. 设集合A={a，b，c，d}上的关系R={ ,< b , a > ,< b, c > , < c , d>}用矩阵运算求出R的传递闭包t (R)。 59. 设A={a，b，c，d}，其上偏序关系R的哈斯图为 12 则 R= 。 60. 设 A?{a,b,c,d,e,f},R?IA{?a,b?,?b,a?,?e,f?,?f,e?, ?a,e?,?e,a?,?a,f?,?f,a?,?b,f?,?f,b?,?b,e?,?e,b?},且R是A上 的等价关系,则61. 设 AR= 。 A?{a,b,c,d,e,f},R?IA{?a,b?,?b,a?,?e,f?,?f,e?, ?a,e?,?e,a?,?a,f?,?f,a?,?b,f?,?f,b?,?b,e?,?e,b?},且R是A上 的等价关系,则 ?a?R? 。 62. (1) 已知 A={1，2，3，4，5}上的等价关系R， R={<1,1>,<1,2>,<2,1>,<2,2>,<3,3>,<3,5>,<5,3>,<5,5>,<4,4>} 写出R对应的划分。 (2) 已知 A={1，2，3，4，5}上的一个划分D={{1，3}，{2}，{4}，{5}} 写出对应的等价关系S。 63. 设A和B为有限集，|A|=m，|B|=n，则有 个从A到B的二元关系。 64. 设A=?a,b,c?, R= ?a,a,a,b,b,b,b,a,b,c,c.c,c,a?，则R具有（ ） 。 001?000??101??000?， A、 自反性 B、 传递性 C、 对称性 D、 反对称性 ?1?1??0?165. 设S={1，2，3，4}，R为S上的关系，其关系矩阵是?求(1) R的关系表达式（用列举法写出）；R的关系图。 (2) R，R。 (3) r(R), s(R)，t(R)。 c 2第三部分：图论 1、非负整数列 d1,d2,,dn是可图化的当且仅当 2、下列非负整数列（ ）是可简单图化的？ A.5,5,4,4,2,1 B.5,4,3,2,2 C.3,3,3,1 D.4,4,3,3,2,2 3、无向图G有16条边，3个4度顶点，4个3度顶点，其余顶点度数均小于3，问G的阶 13 数n为几？ 4、已知无向图G中顶点数n与边数m相等，2度与3度顶点各2个，其余顶点均为悬挂顶点，试求G的边数m。 5、设 d1,d2,,dn为n个互不相等的正整数，证明 d1,d2,,dn不可简单图化。 6、下图的点连通度是 ，边连通度是 。 7写出下图中所有的点割集 8、下面无向图的点连通度是 ，边连通度是。 9 下面有向图中有 个是强连通的？ 10、写出下面无向图的关联矩阵 。 11、写出下面有向图的关联矩阵 。 14 12、写出下列有向图的邻接矩阵 13、写出下面有向图的可达矩阵 14、设图G的邻接矩阵为 ??00100??00011???10000???01001?? ??01010?? 则G的边数为( )． A．5 B．6 C．3 D．4 15、已知图G的邻接矩阵为 ， 则G有（ ）． A．5点，8边 B．6点，7边 C．6点，8边 D．5点，7边 16、下列（ ）是欧拉图。 。 15 17 下图中,（ ）是欧拉图。 A B C D 18、完全图 Kn(n?3)，当n为 时， Kn是欧拉图。 19、命题“n(n?2)阶有向完全图是欧拉图”的真值是 。 20、命题“当r,s为正偶数时，完全二部图Kr,s是欧拉图”的真值是 。 21、在完全图 K2k(k?2)上至少加 条边，才能使所得图为欧拉图。22、判断下列图是哈密顿图、半哈密顿图、还是都不是？ 23 下图中既是欧拉图又是哈密顿图的是（ ） A． K9 B． K10 C． K2,3 D． K3,3 24、设完全二部图 Kr,s为哈密顿图，则r,s应满足 。 25 说明图 G （如图5所示）不是汉密尔顿图． 16 26、已知a,b,c,d,e,f,g七人中，会讲的语言分别为： a:英语、德语,b：英语、汉语,c：英语、意大利语、俄语,d：汉语、日语,e：意大利语、德语,f：俄语、日语、法语,g：德语、法语 问能否将他们的座位安排在圆桌旁，使得每个人都能与他身边的人交谈？ 27、求A到其余顶点的最短路径。 B8A1C24226D5F1E 28用Dijdstra算法求右图中u到v的最短路。 29一公司在六个城市C1，C2，----，C6中每一个都有分公司，从CI到CJ的班机旅费由下列矩阵中第I行第J列的元素给出（∞表示没有直接班机）。 0 0 50 ∞ 40 25 10 50 0 15 20 ∞ 25 ∞ 15 0 10 20 ∞ 40 20 10 0 10 25 25 ∞ 20 10 0 55 10 25 ∞ 25 55 0 17 公司所关心的是计算两城市间的费用最低的路线，对上述六城市中任意一对城市，计算两城市间费用 最低的路线。 30、 (1)求下图的最小生成树； (2)求该图的点连通度和边连通度； (3)求A到B的最短路径的长度。 A 31 关于无向树的描述,不正确的是( ). 无向树是连通图、没有回路,每个边都是桥； 无向树是连通图、边数比顶点数少１,任意两个顶点的路径是惟一的； 无向树是连通图、没有回路,每个顶点都是割点； 无向树是连通图、没有回路，每条边都是割边。 32 下面与“T是树”不等价的是( ) A．T是无圈图，且e=n-1 B．T是连通图，且e=n-1 C．T删去任一边后不连通 D．T任意添加一条边后有且仅有一个圈 33、证明若T是n阶非平凡的无向树，则T 中至少有两片树叶. 34、已知无向树T中有1个3度顶点，2个2度顶点，其余顶点全是树叶，试求树叶数，并画出满足要求的非同构的无向树. 35、画出所有有3片树叶、1个3度顶点、其余顶点不等于1和3的7阶非同构的无向树。 36、一棵无向树T有5片树叶，3个2度分支点，其余的分支点都是3度顶点，问T有几个顶点？ 37、求下图的一棵最小生成树. 38 对于下图，利用避圈法求一棵最小生成树。 18 39 关于含有n片树叶的最优二叉树描述,不正确的是( ). A. 含有n片树叶的最优二叉树每个分支点都有两个孩子； B. 含有n片树叶的最优二叉树分支点的个数是n-1； C. W(T)等于个分支点的权重（构造最优二叉树时产生）之和； D. 在权重一定的前提下，含有n片树叶的最优二叉树是惟一的。 40、求带权为1, 1, 2, 3, 4, 5的最优树. 41、在通信中，八进制数字出现的频率如下： 0：25% 1：20% 2：15% 3：10% 4：10% 5：10% 6：5% 7：5% 求传输它们的最佳前缀码，并求传输10n（n?2）个按上述比例出现的八进制数字需要多少个二进制数字？若用等长的（长为3）的码字传输需要多少个二进制数字？ 42 最优二叉树有n片树叶，则它有 分支点。 43 求带权2、3、5、7、11、13的最优二叉树。 44 画一棵带权为1，1，1，3，3，5，8的最优二叉树T，并计算它的权W（T）。 45 下图所示的二叉树中序遍历的结果是 ，前序遍历的结果是 ，后序遍历的结果是 ， abdce 46 下列编码是前缀码的是( ). A.{1,11,101} B.{1,001,0011} C. {1,01,001,000} D.{0,00,000} 19 47、下列编码不是前缀码的是( ) A.{0，10，110，1111} B.{1，01，001，000} C. {1，11，101，001，0011} D.{0，10，111} 48.求下面2叉树所产生的二元前缀码 49. 设G是有n个结点的有向完全图，则G的边数为 。 50. 设有n个结点的无向图G有m条边,则G的补图G有 条边。 51. 一棵无向树T有7片树叶，3个3度结点，其余结点均为4度。则T有（ ）个4度结点。 A、1； B、2； C、3； D、4。 52. 如下图所示的赋权图表示某七个城市 v1,v2,?,v7及预先算出的它们之间的一些直接通 信线路造价（单位：百万元），试给出一个设计方案，使得各城市之间能够通信而且总造价最小，并计算最小总造价。 53. 下面四组数能构成无向图的度数列的有( )。 A、 2,3,4,5,6,7； B、 1,2,2,3,4； C、 2,1,1,1,2； D、 3,3,5,6,0。 54. 下图中既不是Euler图，也不是Hamilton图的图是（ ）。 20 55. 一棵无向树T有7片树叶，3个3度结点，其余结点均为4度。则T有（ ）个4度结点。 A、1 B、2 C、3 D、4 56. 对下图所示无向带权图G求一棵最小生成树T，并计算出T的权W(T)。 12341234533212833447456 21