文档库 最新最全的文档下载
当前位置:文档库 › 离散数学图论部分经典试题及答案

离散数学图论部分经典试题及答案

离散数学图论部分经典试题及答案
离散数学图论部分经典试题及答案

离散数学图论部分综合练习

一、单项选择题

1.设图G 的邻接矩阵为

???

????

?

?????

???0101

010*******

11100100110

则G 的边数为( ).

A .6

B .5

C .4

D .3

2.已知图G 的邻接矩阵为

, 则G 有( ).

A .5点,8边

B .6点,7边

C .6点,8边

D .5点,7边

3.设图G =,则下列结论成立的是 ( ).

A .deg(V )=2?E ?

B .deg(V )=?E ?

C .E v V

v 2)deg(=∑∈ D .E v V

v =∑∈)deg(

4.图G 如图一所示,以下说法正确的是 ( ) . A .{(a , d )}是割边 B .{(a , d )}是边割集 C .{(d , e )}是边割集 D .{(a, d ) ,(a, c )}是边割集

5.如图二所示,以下说法正确的是 ( ).

A .e 是割点

B .{a, e }是点割集

C .{b , e }是点割集

D .{d }是点割集

6.如图三所示,以下说法正确的是 ( ) .

A .{(a, e )}是割边

B .{(a, e )}是边割集

C .{(a, e ) ,(b, c )}是边割集

D .{(d , e )}是边割集

?

? ? ? ?

c

a

b

e

d

?

f

图一

图二

图三

7.设有向图(a )、(b )、(c )与(d )如图四所示,则下列结论成立的是 ( ).

图四

A .(a )是强连通的

B .(b )是强连通的

C .(c )是强连通的

D .(d )是强连通的 应该填写:D

8.设完全图K n 有n 个结点(n ≥2),m 条边,当( )时,K n 中存在欧拉回路.

A .m 为奇数

B .n 为偶数

C .n 为奇数

D .m 为偶数 9.设G 是连通平面图,有v 个结点,e 条边,r 个面,则r = ( ).

A .e -v +2

B .v +e -2

C .e -v -2

D .e +v +2 10.无向图G 存在欧拉通路,当且仅当( ). A .G 中所有结点的度数全为偶数 B .G 中至多有两个奇数度结点 C .G 连通且所有结点的度数全为偶数 D .G 连通且至多有两个奇数度结点

11.设G 是有n 个结点,m 条边的连通图,必须删去G 的( )条边,才能确定G 的一棵生成树.

A .1m n -+

B .m n -

C .1m n ++

D .1n m -+ 12.无向简单图G 是棵树,当且仅当( ).

A .G 连通且边数比结点数少1

B .G 连通且结点数比边数少1

C .G 的边数比结点数少1

D .G 中没有回路.

二、填空题

1.已知图G 中有1个1度结点,2个2度结点,3个3度结点,4个4度结

点,则G 的边数是 . 2.设给定图G (如图四所示),则图G 的点割

? ? ? ? ?

c a b e

d

? f 图四

集是 .

3.若图G=中具有一条汉密尔顿回路, 则对于结点集V 的每个非空子集S ,在G 中删除S 中的所有结点得到的连通分支数为W ,则S 中结点

数|S|与W 满足的关系式为 .

4.无向图G 存在欧拉回路,当且仅当G 连通 且 .

5.设有向图D 为欧拉图,则图D 中每个结点的入度 . 应该填写:等于出度

6.设完全图K n 有n 个结点(n ?2),m 条边,当 时,K n 中存在欧拉回路.

7.设G 是连通平面图,v , e , r 分别表示G 的结点数,边数和面数,则v ,e 和r 满足的关系式 .

8.设连通平面图G 的结点数为5,边数为6,则面数为 . 9.结点数v 与边数e 满足 关系的无向连通图就是树.

10.设图G 是有6个结点的连通图,结点的总度数为18,则可从G 中删去 条边后使之变成树.

11.已知一棵无向树T 中有8个结点,4度,3度,2度的分支点各一个,T 的树叶数为 .

12.设G =是有6个结点,8条边的连通图,则从G 中删去 条边,可以确定图G 的一棵生成树.

13.给定一个序列集合{000,001,01,10,0},若去掉其中的元素 ,则该序列集合构成前缀码.

三、判断说明题

1.如图六所示的图G 存在一条欧拉回路.

2.给定两个图G 1,G 2(如图七所示):

(1)试判断它们是否为欧拉图、汉密尔顿图?并说明理由. (2)若是欧拉图,请写出一条欧拉回路.

v 1

23v 4

图六

图七

3.判别图G (如图八所示)是不是平面图, 并说明理由.

4.设G 是一个有6个结点14条边的连 通图,则G 为平面图.

四、计算题

1.设图G ??V ,E ?,其中V ??a 1, a 2, a 3, a 4, a 5?,

E ???a 1, a 2?,?a 2, a 4?,?a 3, a 1?,?a 4, a 5?,?a 5, a 2??

(1)试给出G 的图形表示; (2)求G 的邻接矩阵;

(3)判断图G 是强连通图、单侧连通图还是弱连通图?

2.设图G =,V ={ v 1,v 2,v 3,v 4,v 5},E ={ (v 1, v 2),(v 1, v 3),(v 2, v 3),(v 2, v 4),(v 3, v 4),(v 3, v 5),(v 4, v 5) },试

(1)画出G 的图形表示; (2)写出其邻接矩阵;

(2)求出每个结点的度数; (4)画出图G 的补图的图形.

3.设G =,V ={ v 1,v 2,v 3,v 4,v 5},E ={ (v 1,v 3),(v 2,v 3),(v 2,v 4),(v 3,v 4),(v 3,v 5),(v 4,v 5) },试

(1)给出G 的图形表示; (2)写出其邻接矩阵; (3)求出每个结点的度数; (4)画出其补图的图形.

4.图G =,其中V ={ a , b , c , d , e },E ={ (a , b ), (a , c ), (a , e ), (b , d ), (b , e ), (c , e ), (c , d ), (d , e ) },对应边的权值依次为2、1、2、3、6、1、4及5,试

(1)画出G 的图形; (2)写出G 的邻接矩阵;

(3)求出G 权最小的生成树及其权值.

5.用Dijkstra 算法求右图中A 点到其它各点的最短路径。 6.设有一组权为2,3,5,7,11,13,17,19,23,29,31,试

(1)画出相应的最优二元树; (2)计算它们的权值. 7.给出右边所示二元有序树的

三种遍历结果.

v 1

v 2

v 3

v 4

v 5

v 6

?

?

? ? ?

v 5

v 1 v 2

v 4

v 6 ?

v 3

图八

a

b

d

c

e

g f i

h

五、证明题

1.若无向图G 中只有两个奇数度结点,则这两个结点一定是连通的. 2.设G 是一个n 阶无向简单图,n 是大于等于2的奇数.证明图G 与它的补图G 中的奇数度顶点个数相等.

3.设连通图G 有k 个奇数度的结点,证明在图G 中至少要添加2

k

条边才能使其成为欧拉图.

参考解答

一、单项选择题

1.B 2.D 3.C 4.C 5.A 6.D 7.D 8.C 9.A 10.D 11.A 12.A

二、填空题

1.15 2.{f },{c ,e } 3.W?|S| 4.所有结点的度数全为偶数 5.等于出度 6.n 为奇数 7.v -e +r =2 8.3 9.e=v -1 10.4 11.5

12.3 13.0

三、判断说明题

1.解:正确.

因为图G 为连通的,且其中每个顶点的度数为偶数. 2.解:(1)图G 1是欧拉图. 因为图G 1中每个结点的度数都是偶数.

图G 2是汉密尔顿图.

因为图G 2存在一条汉密尔顿回路(不惟一):

a (a ,

b )b (b , e ) e (e , f ) f (f , g ) g (g , d ) d (d ,

c ) c (c , a )a 问题:请大家想一想,为什么图G 1不是汉密尔顿图,图G 2不是欧拉图。

(2)图G 1的欧拉回路为:(不惟一):

v 1(v 1, v 2) v 2 (v 2, v 3) v 3 (v 3, v 4) v 4 (v 4, v 5)v 5 (v 5, v 2) v 2 (v 2, v 6)v 6 (v 6, v 4) v 4 (v 4, v 1)v 1 3.解:图G 是平面图.

?

?

?

? ?

v 5

v 1 v 2

v 4

v 6 ?

v 3

因为只要把结点v 2与v 6的连线(v 2, v 6)拽 到结点v 1的外面,把把结点v 3与v 6的连线 (v 3, v 6)拽到结点v 4, v 5的外面,就得到一个平 面图,如图九所示.

4.解:错误.

不满足“设G 是一个有v 个结点e 条边的连通简单平面图,若v ≥3,则e ≤3v -6.”

四、计算题

1.解:(1)图G 是有向图: (2)邻接矩阵如下:

,000101000000001

010*******

)(???

????

?

?????

???=D A

(3)图G 是单侧连通图,也是弱连通图.

2.解:(1)图G 如图十

(2)邻接矩阵为 图十

?????

??

?????????0110010110110110110100110

(3)deg(v 1)=2

deg(v 2)=3 deg(v 3)=4

deg(v 4)=3

deg(v 5)=2

(4)补图如图十一

图十一 3.解:(1)G 的图形如图十二

?

? ? ?

?

a 1

a 2

a 3

a 4 a

5

v 1

v 2 v 3

v 4 v 5

? ? ? ? ? v 1

v 2 v 3

v 4 v 5 ? ? ?

?

(2)邻接矩阵: 图十二

?????

??

?????????0110010110110110110000100 (3)v 1,v 2,v 3,v 4,v 5结点的度数依次为1,2,4,3,2 (4)补图如图十三:

图十三 4.解:(1)G 的图形表示如图十四:

图十四 (2)邻接矩阵:

?????

??

?????????0111110110110011100110110 (3)粗线表示最小的生成树,如图十五

如图十五 最小的生成树的权为1+1+2+3=7: 5. 解:注意算法执行过程的数据要完整的表示。 6.解:(1)最优二叉树如图十六所示: 方法(Huffman ):从2,3,5,7,11,13,17 ,19,23,29,31中选2,3为最低层结点,并 从权数中删去,再添上他们的和数,即 5,5,7,11,13,17,19,23,29,31;

再从5,5,7,11,13,17,19,23,29,31中选 5,5为倒数第2层结点,并从上述数列中

删去,再添上他们的和数,即7,10,11,13, 17,19,23,29,31; 然后,从7,10,11,13,17,19,23,29,31中 选7,10和11,13为倒数第3层结点,并从 如图十六 上述数列中删去,再添上他们的和数,即 17,17,24,19,23,29,31; ……

(2)权值为:2?6+3?6+5?5+7?4+11?4+13?4+17?3+19?3+23?3+29?3+31?2 =12+18+25+28+44+52+51+57+69+87+62=505

7.解:a)前根:a,b,d,g,e,h,i,c,f

b)中根:g,d,b,h,e,i,a,c,f c)后根:g,d,h,i,e,b,f,c,a

五、证明题

1.证明:用反证法.设G 中的两个奇数度结点分别为u 和v .假设u 和v 不连通,即它们之间无任何通路,则G 至少有两个连通分支G 1,G 2,且u 和v 分别属于G 1和G 2,于是G 1和G 2各含有一个奇数度结点.这与定理3.1.2的推论矛盾.因而u 和v 一定是连通的.

2.证明:设,G V E =<>,,G V E '=<>.则E '是由n 阶无向完全图n K 的边

? ? ? ? ? ? ? ? ? 3

2 7 1

3 5 5 11 17 3

4 ?

? 160

29 10 ? ? ? 23 19 42 ? ? 17 ? 24 ? 53

31

? ?

? 95

65

删去E 所得到的.所以对于任意结点u V ∈,u 在G 和G 中的度数之和等于u 在n K 中的度数.由于n 是大于等于2的奇数,从而n K 的每个结点都是偶数度的( 1 (2)n -≥度),于是若u V ∈在G 中是奇数度结点,则它在G 中也是奇数度结点.故图G 与它的补图G 中的奇数度结点个数相等.

3.证明:由定理3.1.2,任何图中度数为奇数的结点必是偶数,可知k 是偶数.

又根据定理4.1.1的推论,图G 是欧拉图的充分必要条件是图G 不含奇数度结点.因此只要在每对奇数度结点之间各加一条边,使图G 的所有结点的度数变为偶数,成为欧拉图.

故最少要加2

k

条边到图G 才能使其成为欧拉图.

各大学教材课后习题答案网址

各大学教材课后习题答案网址 《线性代数》(同济第四版)课后习题答案(完整版) 高等数学(同济第五版)课后答案(PDF格式,共527页) 中国近现代史纲要课后题答案 曼昆《经济学原理》课后习题解答 21世纪大学英语读写教程(第三册)参考答案 谢希仁《计算机网络教程》(第五版)习题参考答案(共48页) 《概率论与数理统计》习题答案 http:// 《模拟电子技术基础》详细习题答案(童诗白,华成英版,高教版) 《机械设计》课后习题答案(高教版,第八版,西北工业大学) 《大学物理》完整习题答案 .com/viewthread.php?tid=217&fromuid=164951 《管理学》课后答案(周三多) 机械设计基础(第五版)习题答案[杨可桢等主编] 程守洙、江之永主编《普通物理学》(第五版)详细解答及辅导 .php?tid=3&fromuid=164951 新视野大学英语课本详解(四册全) 21世纪大学英语读写教程(第四册)课后答案 新视野大学英语读写教程3册的课后习题答案 1

新视野大学英语第四册答案(第二版) 《中国近现代史》选择题全集(共含250道题目和答案) 《电工学》课后习题答案(第六版,上册,秦曾煌主编) 完整的英文原版曼昆宏观、微观经济学答案 《数字电子技术基础》习题答案(阎石,第五版) 《电路》习题答案上(邱关源,第五版) 《电工学》习题答案(第六版,秦曾煌) https://www.wendangku.net/doc/579959736.html,/viewthread.php?tid=112&fromuid=164951 21世纪大学英语读写教程(第三册)课文翻译 《生物化学》复习资料大全(3套试卷及答案+各章习题集) 《模拟电子技术基础》课后习题答案(共10章)ewthread.php?tid=21&fromuid=164951 《概率论与数理统计及其应用》课后答案(浙江大学盛骤谢式千编著)《理论力学》课后习题答案(赫桐生,高教版) 《全新版大学英语综合教程》(第四册)练习答案及课文译文viewthread.php?tid=78&fromuid=164951 《化工原理答案》课后习题答案(高教出版社,王志魁主编,第三版)《国际贸易》课后习题答案(海闻P.林德特王新奎) 大学英语综合教程1-4册练习答案 read.php?tid=1282&fromuid=164951 《流体力学》习题答案 《传热学》课后习题答案(第四版) 高等数学习题答案及提示

(完整版)离散数学试卷及答案

离散数学试题(A卷答案) 一、(10分)求(P↓Q)→(P∧?(Q∨?R))的主析取范式 解:(P↓Q)→(P∧?(Q∨?R))??(?( P∨Q))∨(P∧?Q∧R)) ?(P∨Q)∨(P∧?Q∧R)) ?(P∨Q∨P)∧(P∨Q∨?Q)∧(P∨Q∨R) ?(P∨Q)∧(P∨Q∨R) ?(P∨Q∨(R∧?R))∧(P∨Q∨R) ?(P∨Q∨R)∧(P∨Q∨?R)∧(P∨Q∨R) ? M∧1M ? m∨3m∨4m∨5m∨6m∨7m 2 二、(10分)在某次研讨会的休息时间,3名与会者根据王教授的口音分别作出下述判断: 甲说:王教授不是苏州人,是上海人。 乙说:王教授不是上海人,是苏州人。 丙说:王教授既不是上海人,也不是杭州人。 王教授听后说:你们3人中有一个全说对了,有一人全说错了,还有一个人对错各一半。试判断王教授是哪里人? 解设设P:王教授是苏州人;Q:王教授是上海人;R:王教授是杭州人。则根据题意应有: 甲:?P∧Q 乙:?Q∧P 丙:?Q∧?R 王教授只可能是其中一个城市的人或者3个城市都不是。所以,丙至少说对了一半。因此,可得甲或乙必有一人全错了。又因为,若甲全错了,则有?Q ∧P,因此,乙全对。同理,乙全错则甲全对。所以丙必是一对一错。故王教授的话符号化为:

((?P ∧Q )∧((Q ∧?R )∨(?Q ∧R )))∨((?Q ∧P )∧(?Q ∧R )) ?(?P ∧Q ∧Q ∧?R )∨(?P ∧Q ∧?Q ∧R )∨(?Q ∧P ∧?Q ∧R ) ?(?P ∧Q ∧?R )∨(P ∧?Q ∧R ) ??P ∧Q ∧?R ?T 因此,王教授是上海人。 三、(10分)证明tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。 证明 设R 是非空集合A 上的二元关系,则由定理4.19知,tsr (R )是包含R 的且具有自反性、对称性和传递性的关系。 若'R 是包含R 的且具有自反性、对称性和传递性的任意关系,则由闭包的定义知r (R )?'R 。由定理4.15和由定理4.16得sr (R )?s ('R )='R ,进而有tsr (R )?t ('R )='R 。 综上可知,tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。 四、(15分)集合A ={a ,b ,c ,d ,e }上的二元关系R 为R ={}, (1)写出R 的关系矩阵。 (2)判断R 是不是偏序关系,为什么? 解 (1) R 的关系矩阵为: ??? ??? ? ? ? ?=100001100010100 10110 11111 )(R M (2)由关系矩阵可知,对角线上所有元素全为1,故R 是自反的;ij r +ji r ≤1,故R 是反对称的;可计算对应的关系矩阵为:

离散数学图论与系中有图题目

离散数学图论与系中有图题目

————————————————————————————————作者:————————————————————————————————日期:

图论中有图题目 一、 没有一个简单的办法能确定图的色数以及用尽可能少的颜色给图的节点着色。Welch-Powell 给出了一个使颜色数尽可能少(不一定最少)的结点着色方法,在实际使用中比较有效: 第1步、 将图的结点按度数的非增顺序排列;第2步、用第1种颜色给第1个结点着色,并按照结点排列顺序,用同一种颜色给每个与前面已着色的结点不邻接的结点着色;第3步、换一种颜色对尚未着色的结点按上述方法着色,如此下去,直到所有结点全部着色为止。 例1 分别求右面两图的色数 (1)由于(1)中图G 中无奇数长的基本回路,由定理可知()2G χ=。 (2)由于(2)中图G 含子图轮图4W ,由于()44W χ=,故()4G χ≥。又因 为此图的最大度()4G ?=,G 不是完全图,也不是奇数长的基本回路,由定理可知()()4G G χ≤?=,因而()4G χ=。 (对n 阶轮图n W ,n 为奇数时有()3n W χ=,n 为偶数时有()4n W χ=;对n 阶零图n N ,有()1n N χ=;完全图n K ,有()n K n χ=;对于二部图12,,,G V V E E =<>=Φ时即()1n N χ=,E ≠Φ时即()2G χ=;在彼得森图G 中,存在奇数长的基本回路,因而()3G χ≥,又彼得森图既不是完全图也不是长度为奇数的基本回路,且()3G ?=,由定理()3G χ≤,故()3G χ=) 例 2 给右边三个图的顶点正常着 色,每个图至少需要几种颜色。 答案:(1) ()2G χ=;(2) ()3G χ=; (3)()4G χ= 例3 有8种化学品A,B,C,D,P,R,S,T 要放进贮藏室保管。出于安全原因, 下列各组药品不能贮在同一个室内:A-R, A-C, A-T, R-P, P-S, S-T, T-B, B-D, D-C, R-S, R-B, 4个结点、6个结点和8个结点的三次正则图 (2) (1) (3) (2)(1)

离散数学期末试题

离散数学考试试题(A 卷及答案) 一、(10分)求(P ↓Q )→(P ∧?(Q ∨?R ))的主析取范式 解:(P ↓Q )→(P ∧?(Q ∨?R ))??(?( P ∨Q ))∨(P ∧?Q ∧R )) ?(P ∨Q )∨(P ∧?Q ∧R )) ?(P ∨Q ∨P )∧(P ∨Q ∨?Q )∧(P ∨Q ∨R ) ?(P ∨Q )∧(P ∨Q ∨R ) ?(P ∨Q ∨(R ∧?R ))∧(P ∨Q ∨R ) ?(P ∨Q ∨R )∧(P ∨Q ∨?R )∧(P ∨Q ∨R ) ?0M ∧1M ?2m ∨3m ∨4m ∨5m ∨6m ∨7m 二、(10分)在某次研讨会的休息时间,3名与会者根据王教授的口音分别作出下述判断: 甲说:王教授不是苏州人,是上海人。 乙说:王教授不是上海人,是苏州人。 丙说:王教授既不是上海人,也不是杭州人。 王教授听后说:你们3人中有一个全说对了,有一人全说错了,还有一个人对错各一半。试判断王教授是哪里人? 解 设设P :王教授是苏州人;Q :王教授是上海人;R :王教授是杭州人。则根据题意应有: 甲:?P ∧Q 乙:?Q ∧P 丙:?Q ∧?R 王教授只可能是其中一个城市的人或者3个城市都不是。所以,丙至少说对了一半。因此,可得甲或乙必有一人全错了。又因为,若甲全错了,则有?Q ∧P ,因此,乙全对。同理,乙全错则甲全对。所以丙必是一对一错。故王教授的话符号化为: ((?P ∧Q )∧((Q ∧?R )∨(?Q ∧R )))∨((?Q ∧P )∧(?Q ∧R )) ?(?P ∧Q ∧Q ∧?R )∨(?P ∧Q ∧?Q ∧R )∨(?Q ∧P ∧?Q ∧R ) ?(?P ∧Q ∧?R )∨(P ∧?Q ∧R ) ??P ∧Q ∧?R ?T 因此,王教授是上海人。 三、(10分)证明tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。 证明 设R 是非空集合A 上的二元关系,则tsr (R )是包含R 的且具有自反性、对称性和传递性的关系。 若'R 是包含R 的且具有自反性、对称性和传递性的任意关系,则由闭包的定义知r (R )?' R 。则sr (R )?s ('R )='R ,进而有tsr (R )?t ('R )='R 。

离散数学试题与答案

试卷二试题与参考答案 一、填空 1、 P:您努力,Q:您失败。 2、 “除非您努力,否则您将失败”符号化为 ; “虽然您努力了,但还就是失败了”符号化为 。 2、论域D={1,2},指定谓词P P (1,1) P (1,2) P (2,1) P (2,2) T T F F 则公式x ??真值为 。 3设A={2,3,4,5,6}上的二元关系}|,{是质数x y x y x R ∨<><=,则 R= (列举法)。 R 的关系矩阵M R = 。 4、设A={1,2,3},则A 上既不就是对称的又不就是反对称的关系 R= ;A 上既就是对称的又就是反对称的关系R= 。 5、设代数系统,其中A={a,b,c}, 则幺元就是 ;就是否有幂等 性 ;就是否有对称性 。 6、4阶群必就是 群或 群。 7、下面偏序格就是分配格的就是 。 8、n 个结点的无向完全图K n 的边数为 ,欧拉图的充要条件就是 。 * a b c a b c a b c b b c c c b

二、选择 1、在下述公式中就是重言式为( ) A.)()(Q P Q P ∨→∧; B.))()(()(P Q Q P Q P →∧→??; C.Q Q P ∧→?)(; D.)(Q P P ∨→。 2、命题公式 )()(P Q Q P ∨?→→? 中极小项的个数为( ),成真赋值的个数为 ( )。 A.0; B.1; C.2; D.3 。 3、设}}2,1{},1{,{Φ=S ,则 S 2 有( )个元素。 A.3; B.6; C.7; D.8 。 4、设} 3 ,2 ,1 {=S ,定义S S ?上的等价关系 },,,, | ,,,{c b d a S S d c S S b a d c b a R +=+?>∈∈<><><<=则由 R 产 生的S S ?上一个划分共有( )个分块。 A.4; B.5; C.6; D.9 。 5、设} 3 ,2 ,1 {=S ,S 上关系R 的关系图为 则R 具有( )性质。 A.自反性、对称性、传递性; B.反自反性、反对称性; C.反自反性、反对称性、传递性; D.自反性 。 6、设 ο,+ 为普通加法与乘法,则( )>+<ο,,S 就是域。 A.},,3|{Q b a b a x x S ∈+== B.},,2|{Z b a n x x S ∈== C.},12|{Z n n x x S ∈+== D.}0|{≥∧∈=x Z x x S = N 。 7、下面偏序集( )能构成格。

离散数学期末试题及答案完整版

离散数学期末试题及答 案 HEN system office room 【HEN16H-HENS2AHENS8Q8-HENH1688】

326《离散数学》期末考试题(B ) 一、填空题(每小题3分,共15分) 1.设,,},,{{b a b a A =?},则-A ? = ( ),-A {?} = ( ), )(A P 中的元素个数=|)(|A P ( ). 2.设集合A 中有3个元素,则A 上的二元关系有( )个,其中有( )个是A 到A 的函数. 3.谓词公式))()(())()((y P y Q y x Q x P x ?∧?∧→?中量词x ?的辖域为( ), 量词y ?的辖域为( ). 4.设}24,12,8,6,4,3,2,1{24=D ,对于其上的整除关系“|”,元素( )不存在补元. 5.当n ( )时,n 阶完全无向图n K 是平面图,当当n 为( )时,n K 是欧拉图. 二.1. 若n B m A ==||,||,则=?||B A ( ),A 到B 的2元关系共有( )个,A 上的2元关系共有( )个. 2. 设A = {1, 2, 3}, f = {(1,1), (2,1), (3, 1)}, g = {(1, 1), (2, 3), (3, 2)}和h = {(1, 3), (2, 1), (3, 1)},则( )是单射,( )是满射,( )是双射. 3. 下列5个命题公式中,是永真式的有( )(选择正确答案的番号). (1)q q p p →→∧)(; (2))(q p p ∨→; (3))(q p p ∧→; (4)q q p p →∨∧?)(; (5)q q p →→)(. 4. 设D 24是24的所有正因数组成的集合,“|”是其上的整除关系,则3的补元( ),4的补元( ),6的补元( ).

离散数学测验题--图论部分(优选.)

离散数学图论单元测验题 一、单项选择题(本大题共10小题,每小题2分,共20分) 1、在图G =中,结点总度数与边数的关系是( ) (A) deg(v i )=2∣E ∣ (B) deg(v i )=∣E ∣ (C)∑∈=V v E v 2)deg( (D) ∑∈=V v E v )deg( 2、设D 是n 个结点的无向简单完全图,则图D 的边数为( ) (A) n (n -1) (B) n (n +1) (C) n (n -1)/2 (D) n (n +1)/2 3、 设G =为无向简单图,∣V ∣=n ,?(G )为G 的最大度数,则有 (A) ?(G )n (D) ?(G )≥n 4、图G 与G '的结点和边分别存在一一对应关系,是G ≌G '(同构)的( ) (A) 充分条件 (B) 必要条件 (C)充分必要条件 (D)既非充分也非必要条件 5、设},,,{d c b a V =,则与V 能构成强连通图的边集合是( ) (A) },,,,,,,,,{><><><><><=c d b c d b a b d a E (B) },,,,,,,,,{><><><><><=c d d b c b a b d a E (C) },,,,,,,,,{><><><><><=c d a d c b a b c a E 6、有向图的邻接矩阵中,行元素之和是对应结点的( ),列元素之和是对应结点的( ) (A)度数 (B) 出度 (C)最大度数 (D) 入度 7、设图G 的邻接矩阵为 ?? ?? ?? ? ? ????????0101010010000011100000100 则G 的边数为( ). A .5 B .6 C .3 D .4 8、设m E n V E V G ==>=<,,,为连通平面图且有r 个面,则r =( ) (A) m -n +2 (B) n -m -2 (C) n +m -2 (D) m +n +2 9、在5个结点的二元完全树中,若有4条边,则有 ( )片树叶。 (A) 2 (B) 3 (C) 5 (D) 4 10、图2是( ) (A) 完全图 (B)欧拉图 (C) 平面图 (D) 哈密顿图

各科书的下载地址

[Word格式]《成本会计》习题及答案(自学推荐,23页) [Word格式]《成本会计》配套习题集参考答案 [Word格式]《实用成本会计》习题答案 [Word格式]《会计电算化》教材习题答案(09年) [JPG格式]会计从业《基础会计》课后答案 [Word格式]《现代西方经济学(微观经济学)》笔记与课后习题详解(第3版,宋承先)[Word格式]《宏观经济学》习题答案(第七版,多恩布什) [Word格式]《国际贸易》课后习题答案(海闻 P.林德特王新奎) [PDF格式]《西方经济学》习题答案(第三版,高鸿业)可直接打印 [Word格式]《金融工程》课后题答案(郑振龙版) [Word格式]《宏观经济学》课后答案(布兰查德版) [JPG格式]《投资学》课后习题答案(英文版,牛逼版) [PDF格式]《投资学》课后习题答案(博迪,第四版) [Word格式]《微观经济学》课后答案(高鸿业版) [Word格式]《公司理财》课后答案(英文版,第六版) [Word格式]《国际经济学》教师手册及课后习题答案(克鲁格曼,第六版) [Word格式]《金融市场学》课后习题答案(张亦春,郑振龙,第二版) [PDF格式]《金融市场学》电子书(张亦春,郑振龙,第二版) [Word格式]《微观经济学》课后答案(平狄克版) [Word格式]《中级财务会计》习题答案(第二版,刘永泽) [PDF格式]《国际经济学》习题答案(萨尔瓦多,英文版) [JPG格式]《宏观经济学》课后答案(曼昆,中文版) [PDF格式]《宏观经济学》答案(曼昆,第五版,英文版)pdf格式 [Word格式]《技术经济学概论》(第二版)习题答案 [Word格式]曼昆《经济学原理》课后习题解答 [PDF格式]西方经济学(高鸿业版)教材详细答案 [Word格式]完整的英文原版曼昆宏观、微观经济学答案 [Word格式]《金融市场学》课后答案(郑振龙版) 化学物理 [Word格式]《固体物理》习题解答(方俊鑫版) [Word格式]《简明结构化学》课后习题答案(第三版,夏少武) [Word格式]《生物化学》复习资料大全(3套试卷及答案+各章习题集) [PDF格式]《光学教程》习题答案(第四版,姚启钧原著) [Word格式]《流体力学》实验分析答案(浙工大版) [Word格式]《高分子化学》课后习题答案(第四版,潘祖仁主编) [PDF格式]《化工热力学》习题与习题答案(含各种版本) [Word格式]《材料力学》习题答案 [Word格式]《量子力学导论》习题答案(曾谨言版,北京大学) [PDF格式]《理论力学》习题答案(动力学和静力学)

【浙江工商大学】《离散数学》期末考试题(B)

《离散数学》期末考试题(B) 一、填空题(每小题3分,共15分) 1.设,,},,{{b a b a A =?},则-A ? = ( ),-A {?} = ( ),)(A P 中的元素个数=|)(|A P ( ). 2.设集合A 中有3个元素,则A 上的二元关系有( )个,其中有( )个是A 到A 的函数. 3.谓词公式))()(())()((y P y Q y x Q x P x ?∧?∧→?中量词x ?的辖域为 ( ), 量词y ?的辖域为( ). 4.设}24,12,8,6,4,3,2,1{24=D ,对于其上的整除关系“|”,元素( )不存在补元. 5.当n ( )时,n 阶完全无向图n K 是平面图,当当n 为( )时,n K 是欧拉图. 二、单选题(每小题3分,共15分) 1.设R 是集合A 上的偏序关系,1-R 是R 的逆关系,则1 -?R R 是A 上的 (A)偏序关系 (B)等价关系 (C)相容关系 (D)以上结论都不成立 2.由2个命题变元p 和q 组成的不等值的命题公式的个数有 (A)2 (B)4 (C)8 (D)16 3.设p 是素数且n 是正整数,则任意有限域的元素个数为 (A)n p + (B)pn (C)n p (D)p n 4.设R 是实数集合,≤是其上的小于等于关系,则(R, ≤)是 (A)有界格 (B)分配格 (C)有补格 (D)布尔格 5.3阶完全无向图3K 的不同构的生成子图有 (A)2 (B)3 (C)4 (D)5 三、判断题(每小题3分,共15分): 正确打“√”,错误打“×”. 1.若一个元素a 既存在左逆元l a ,又存在右逆元r a ,则r l a a =. ( ) 2.命题联结词→不满足结合律. ( ) 3.在Z 8 = {0,1,2,3,4,5,6,7}中,2关于“?8”的逆元为 4. ( ) 4.整环不一定是域. ( )

离散数学期末试卷及答案

一.判断题(共10小题,每题1分,共10分) 在各题末尾的括号内画 表示正确,画 表示错误: 1.设p、q为任意命题公式,则(p∧q)∨p ? p ( ) 2.?x(F(y)→G(x)) ? F(y)→?xG(x)。( ) 3.初级回路一定是简单回路。( ) 4.自然映射是双射。( ) 5.对于给定的集合及其上的二元运算,可逆元素的逆元是唯一的。( ) 6.群的运算是可交换的。( ) 7.自然数集关于数的加法和乘法构成环。( ) 8.若无向连通图G中有桥,则G的点连通度和边连通度皆为1。( ) 9.设A={a,b,c},则A上的关系R={,}是传递的。( ) 10.设A、B、C为任意集合,则A?(B?C)=(A?B)?C。( ) 二、填空题(共10题,每题3分,共30分) 11.设p:天气热。q:他去游泳。则命题“只有天气热,他才去游泳”可符号 化为。 12.设M(x):x是人。S(x):x到过月球。则命题“有人到过月球”可符号 化为。 13.p?q的主合取范式是。 14.完全二部图K r,s(r < s)的边连通度等于。 15.设A={a,b},,则A上共有个不同的偏序关系。 16.模6加群中,4是阶元。 17.设A={1,2,3,4,5}上的关系R={<1,3>,<1,5>,<2,5>,<3,3>,<4,5>},则R的传递闭包t(R) = 。. 18.已知有向图D的度数列为(2,3,2,3),出度列为(1,2,1,1),则有向图D的入度

列为。 19.n阶无向简单连通图G的生成树有条边。 20.7阶圈的点色数是。 三、运算题(共5小题,每小题8分,共40分) 21.求?xF(x)→?yG(x,y)的前束范式。 22.已知无向图G有11条边,2度和3度顶点各两个,其余为4度顶点,求G 的顶点数。 23.设A={a,b,c,d,e,f},R=I A?{,},则R是A上的等价关系。求等价类[a]R、[c]R及商集A/R。 24.求图示带权图中的最小生成树,并计算最小生成树的权。 25.设R*为正实数集,代数系统< R*,+>、< R*,·>、< R*,/>中的运算依次为普通加法、乘法和除法运算。试确定这三个代数系统是否为群?是群者,求其单位元及每个元素的逆元。 四、证明题(共3小题,共20分) 26 (8分)在自然推理系统P中构造下述推理的证明: 前题:p→(q∨r),?s→?q,p∧?s 结论:r 27 (6分)设是群,H={a| a∈G∧?g∈G,a*g=g*a},则是G的子群 28.(6分)设G是n(≥3)阶m条边、r个面的极大平面图,则r=2n-4。

离散数学期末考试试题及答案

离散数学试题(B卷答案1) 一、证明题(10分) 1)(P∧(Q∧R))∨(Q∧R)∨(P∧R)R 证明: 左端(P∧Q∧R)∨((Q∨P)∧R) ((P∧Q)∧R))∨((Q∨P)∧R) ((P∨Q)∧R)∨((Q∨P)∧R) ((P∨Q)∨(Q∨P))∧R ((P∨Q)∨(P∨Q))∧R T∧R(置换)R 2) x (A(x)B(x))xA(x)xB(x) 证明:x(A(x)B(x))x(A(x)∨B(x)) x A(x)∨xB(x) xA(x)∨xB(x) xA(x)xB(x) 二、求命题公式(P∨(Q∧R))(P∧Q∧R)的主析取范式和主合取范式(10分)。 证明:(P∨(Q∧R))(P∧Q∧R)(P∨(Q∧R))∨(P∧Q∧R)) (P∧(Q∨R))∨(P∧Q∧R) (P∧Q)∨(P∧R))∨(P∧Q∧R) (P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R))∨(P∧Q∧R))∨(P∧Q∧R) m0∨m1∨m2∨m7 M3∨M4∨M5∨M6 三、推理证明题(10分) 1)C∨D,(C∨D)E, E(A∧B),(A∧B)(R∨S)R∨S证明:(1) (C∨D) E ?P (2) E(A∧B) ??P (3) (C∨D)(A∧B) T(1)(2),I (4) (A∧B)(R∨S)??P (5) (C∨D)(R∨S) ? T(3)(4),I (6) C∨D P (7) R∨S T(5),I 2) x(P(x)Q(y)∧R(x)),xP(x)Q(y)∧x(P(x)∧R(x)) 证明(1)xP(x) P

(2)P(a) T(1),ES (3)x(P(x)Q(y)∧R(x)) P (4)P(a)Q(y)∧R(a) T(3),US (5)Q(y)∧R(a) T(2)(4),I (6)Q(y) T(5),I (7)R(a) T(5),I (8)P(a)∧R(a) T(2)(7),I (9)x(P(x)∧R(x)) T(8),EG (10)Q(y)∧x(P(x)∧R(x)) T(6)(9),I 四、某班有25名学生,其中14人会打篮球,12人会打排球,6人会打篮球和排球,5人会打篮球和网球,还有2人会打这三种球。而6个会打网球的人都会打另外一种球,求不会打这三种球的人数(10分)。 解:A,B,C分别表示会打排球、网球和篮球的学生集合。则|A|=12,|B|=6,|C|=14,|A∩C|=6,|B∩C|=5,|A∩B∩C|=2。 先求|A∩B|。 ∵6=|(A∪C)∩B|=|(A∩B)∪(B∩C)|=|(A∩B)|+|(B∩C)|-|A∩B∩C|=|(A∩B)|+5-2,∴|(A∩B)|=3。 于是|A∪B∪C|=12+6+14-6-5-3+2=20。不会打这三种球的人数25-20=5。五、已知A、B、C是三个集合,证明A-(B∪C)=(A-B)∩(A-C)(10分)。 证明:∵x A-(B∪C) x A∧x(B∪C) xA∧(xB∧x C) (x A∧x B)∧(x A∧xC) x(A-B)∧x(A-C) x(A-B)∩(A-C) ∴A-(B∪C)=(A-B)∩(A-C) 六、已知R、S是N上的关系,其定义如下:R={| x,yN∧y=x2} R*S={| x,y N∧y=x2+1} S*R={<x,y>| x,yN∧y=(x+1)2},R{1,2}={<1,1>,<2,4>},S[{1,2}]={1,4}。 七、设R={<a,b>,,<c,a>},求r(R)、s(R)和t(R) (15分)。 解:r(R)={,,,<b,b>,

离散数学试卷及答案

填空10% (每小题 2 分) 1、若P,Q,为二命题,P Q 真值为0 当且仅当。 2、命题“对于任意给定的正实数,都存在比它大的实数” 令F(x):x 为实数,L(x, y) : x y 则命题的逻辑谓词公式为。 3、谓词合式公式xP(x) xQ(x)的前束范式为。 4、将量词辖域中出现的和指导变元交换为另一变元符号,公式其余的部分不变,这种方法称为 换名规则。 5、设x 是谓词合式公式A的一个客体变元,A的论域为D,A(x)关于y 是自由的,则被称为存 在量词消去规则,记为ES。 选择25% (每小题分) 1、下列语句是命题的有()。 A、明年中秋节的晚上是晴天; C、xy 0 当且仅当x 和y 都大于0; D 、我正在说谎。 2、下列各命题中真值为真的命题有()。 A、2+2=4当且仅当3是奇数; B、2+2=4当且仅当 3 不是奇数; C、2+2≠4 当且仅当3是奇数; D、2+2≠4当且仅当 3 不是奇数; 3、下列符号串是合式公式的有() A、P Q ; B、P P Q; C、( P Q) (P Q); D、(P Q) 。 4、下列等价式成立的有( )。 A、P QQ P ; B、P(P R) R; C、P (P Q) Q; D 、P (Q R) (P Q) R。 5、若A1,A2 A n和B为 wff ,且A1 A2 A n B 则 ( )。 A、称A1 A2 A n 为 B 的前 件; B 、称 B 为A1,A2 A n 的有效结论

C 、 x(M (x) Mortal (x)) ; D 、 x(M(x) Mortal (x)) 8、公式 A x(P(x) Q(x))的解释 I 为:个体域 D={2} ,P(x) :x>3, Q(x) :x=4则 A 的 真 值为( ) 。 A 、 1; B 、 0; C 、 可满足式; D 、无法判定。 9、 下列等价关系正确的是( )。 A 、 x(P(x) Q(x)) xP(x) xQ(x); B 、 x(P(x) Q(x)) xP(x) xQ(x); C 、 x(P(x) Q) xP(x) Q ; D 、 x(P(x) Q) xP(x) Q 。 10 、 下列推理步骤错在( )。 ① x(F(x) G(x)) P ② F(y) G(y) US ① ③ xF(x) P ④ F(y) ES ③ ⑤G(y) T ②④I ⑥ xG(x) EG ⑤ A 、②; B 、④; C 、⑤; D 、⑥ 逻辑判断 30% 1、 用等值演算法和真值表法判断公式 A ((P Q) (Q P)) (P Q) 的类型。 C 、当且仅当 A 1 A 2 A n D 、当且仅当 A 1 A 2 A n B F 。 6、 A ,B 为二合式公式,且 B ,则( )。 7、 A 、 A C 、 A B 为重言式; B 、 B ; E 、 A B 为重言式。 人总是要死的”谓词公式表示为( )。 论域为全总个体域) M (x ) : x 是人; Mortal(x) x 是要死的。 A 、 M (x) Mortal (x) ; B M (x) Mortal (x)

离散数学期末考试试题及答案

离散数学试题(B卷答案1) 一、证明题(10分) 1)(?P∧(?Q∧R))∨(Q∧R)∨(P∧R)?R 证明: 左端?(?P∧?Q∧R)∨((Q∨P)∧R) ?((?P∧?Q)∧R))∨((Q∨P)∧R) ?(?(P∨Q)∧R)∨((Q∨P)∧R) ?(?(P∨Q)∨(Q∨P))∧R ?(?(P∨Q)∨(P∨Q))∧R ?T∧R(置换)?R 2) ?x (A(x)→B(x))??xA(x)→?xB(x) 证明:?x(A(x)→B(x))??x(?A(x)∨B(x)) ??x?A(x)∨?xB(x) ???xA(x)∨?xB(x) ??xA(x)→?xB(x) 二、求命题公式(P∨(Q∧R))→(P∧Q∧R)的主析取范式和主合取范式(10分)。 证明:(P∨(Q∧R))→(P∧Q∧R)??(P∨(Q∧R))∨(P∧Q∧R)) ?(?P∧(?Q∨?R))∨(P∧Q∧R) ?(?P∧?Q)∨(?P∧?R))∨(P∧Q∧R) ?(?P∧?Q∧R)∨(?P∧?Q∧?R)∨(?P∧Q∧?R))∨(?P∧?Q∧?R))∨(P∧Q∧R) ?m0∨m1∨m2∨m7 ?M3∨M4∨M5∨M6 三、推理证明题(10分) 1)C∨D, (C∨D)→?E,?E→(A∧?B), (A∧?B)→(R∨S)?R∨S 证明:(1) (C∨D)→?E P (2) ?E→(A∧?B) P (3) (C∨D)→(A∧?B) T(1)(2),I (4) (A∧?B)→(R∨S) P (5) (C∨D)→(R∨S) T(3)(4), I (6) C∨D P (7) R∨S T(5),I 2) ?x(P(x)→Q(y)∧R(x)),?xP(x)?Q(y)∧?x(P(x)∧R(x)) 证明(1)?xP(x) P

大学几乎所有学科的课本答案

大学几乎所有学科的课本答案 ! 任明嘉的日志 经济金融 [PDF格式]《会计学原理》同步练习题答案 [Word格式]《成本会计》习题及答案(自学推荐,23页) [Word格式]《成本会计》配套习题集参考答案 [Word格式]《实用成本会计》习题答案 [Word格式]《会计电算化》教材习题答案(09年) [JPG格式]会计从业《基础会计》课后答案 [Word格式]《现代西方经济学(微观经济学)》笔记与课后习题详解(第3版,宋承先)[Word格式]《宏观经济学》习题答案(第七版,多恩布什) [Word格式]《国际贸易》课后习题答案(海闻P.林德特王新奎) [PDF格式]《西方经济学》习题答案(第三版,高鸿业)可直接打印 [Word格式]《金融工程》课后题答案(郑振龙版) [Word格式]《宏观经济学》课后答案(布兰查德版) [JPG格式]《投资学》课后习题答案(英文版,牛逼版) [PDF格式]《投资学》课后习题答案(博迪,第四版) [Word格式]《微观经济学》课后答案(高鸿业版) [Word格式]《公司理财》课后答案(英文版,第六版)

[Word格式]《国际经济学》教师手册及课后习题答案(克鲁格曼,第六版) [Word格式]《金融市场学》课后习题答案(张亦春,郑振龙,第二版)[PDF格式]《金融市场学》电子书(张亦春,郑振龙,第二版) [Word格式]《微观经济学》课后答案(平狄克版) [Word格式]《中级财务会计》习题答案(第二版,刘永泽) [PDF格式]《国际经济学》习题答案(萨尔瓦多,英文版) [JPG格式]《宏观经济学》课后答案(曼昆,中文版) [PDF格式]《宏观经济学》答案(曼昆,第五版,英文版)pdf格式 [Word格式]《技术经济学概论》(第二版)习题答案 [Word格式]曼昆《经济学原理》课后习题解答 [PDF格式]西方经济学(高鸿业版)教材详细答案 [Word格式]完整的英文原版曼昆宏观、微观经济学答案 [Word格式]《金融市场学》课后答案(郑振龙版) 化学物理 [Word格式]《固体物理》习题解答(方俊鑫版) [Word格式]《简明结构化学》课后习题答案(第三版,夏少武) [Word格式]《生物化学》复习资料大全(3套试卷及答案+各章习题集)[PDF格式]《光学教程》习题答案(第四版,姚启钧原著) [Word格式]《流体力学》实验分析答案(浙工大版) [Word格式]《高分子化学》课后习题答案(第四版,潘祖仁主编)

离散数学试卷及答案(1)

一、填空 20% (每小题2分) 1.设 }7|{)},5()(|{<∈=<∈=+x E x x B x N x x A 且且(N :自然数集,E + 正偶数) 则 =?B A 。 2.A ,B ,C 表示三个集合,文图中阴影部分的集合表达式为 。 3.设P ,Q 的真值为0,R ,S 的真值为1,则 )()))(((S R P R Q P ?∨→?∧→∨?的真值= 。 4.公式P R S R P ?∨∧∨∧)()(的主合取范式为 。 5.若解释I 的论域D 仅包含一个元素,则 )()(x xP x xP ?→? 在I 下真值为 。 6.设A={1,2,3,4},A 上关系图为 则 R 2 = 。 7.设A={a ,b ,c ,d},其上偏序关系R 的哈斯图为 则 R= 。

8.图的补图为 。 9.设A={a ,b ,c ,d} ,A 上二元运算如下: 那么代数系统的幺元是 ,有逆元的元素为 ,它们的逆元分别为 。 10.下图所示的偏序集中,是格的为 。 二、选择 20% (每小题 2分) 1、下列是真命题的有( ) A . }}{{}{a a ? ; B .}}{,{}}{{ΦΦ∈Φ; C . }},{{ΦΦ∈Φ; D . }}{{}{Φ∈Φ。 2、下列集合中相等的有( ) A .{4,3}Φ?; B .{Φ,3,4}; C .{4,Φ,3,3}; D . {3,4}。 3、设A={1,2,3},则A 上的二元关系有( )个。

A.23 ;B.32 ;C.332?;D.223?。 4、设R,S是集合A上的关系,则下列说法正确的是() R 是自反的; A.若R,S 是自反的,则S R 是反自反的; B.若R,S 是反自反的,则S R 是对称的; C.若R,S 是对称的,则S R 是传递的。 D.若R,S 是传递的,则S 5、设A={1,2,3,4},P(A)(A的幂集)上规定二元系如下 t s p R= t s ∈ =则P(A)/ R=() < > ∧ A ) (| || |} ( , {t , | s A.A ;B.P(A) ;C.{{{1}},{{1,2}},{{1,2,3}},{{1,2,3,4}}};D.{{Φ},{2},{2,3},{{2,3,4}},{A}} 6、设A={Φ,{1},{1,3},{1,2,3}}则A上包含关系“?”的哈斯图为() 7、下列函数是双射的为() A.f : I→E , f (x) = 2x ;B.f : N→N?N, f (n) = ; C.f : R→I , f (x) = [x] ;D.f :I→N, f (x) = | x | 。 (注:I—整数集,E—偶数集,N—自然数集,R—实数集) 8、图中从v1到v3长度为3 的通路有()条。 A.0;B.1;C.2;D.3。 9、下图中既不是Eular图,也不是Hamilton图的图是()

《离散数学》期末考试试题

《离散数学》期末考试试题 一、 填空题(每空2分,合计20分) 1. 设个体域为{2,3,6}D =-, ():3F x x ≤,():0G x x >。则在此解释下公式 ()(()())x F x G x ?∧的真值为______。 2. 设:p 我是大学生,:q 我喜欢数学。命题“我是喜欢数学的大学生”为可符合化 为 。 3. 设{1,2,3,4}A =,{2,4,6}B =,则A B -=________,A B ⊕=________。 4. 合式公式()Q P P ?→∧是永______式。 5. 给定集合{1,2,3,4,5}A =,在集合A 上定义两种关系: {1,3,3,4,2,2}R =<><><>, {4,2,3,1,2,3}S =<><><>, 则_______________S R =ο,_______________R S =ο。 6. 设e 是群G 上的幺元,若a G ∈且2a e =,则1a -=____ , 2a -=__________。 7. 公式))(()(S Q P Q P ?∧?∨∧∨?的对偶公式为 。 8. 设{2,3,6,12}A =, p 是A 上的整除关系,则偏序集,A <>p 的最大元是________,极小元是_ _。 9. 一棵有6个叶结点的完全二叉树,有_____个内点;而若一棵树有2个结点度数为2,一 个结点度数为3,3个结点度数为4,其余是叶结点,则该树有_____个叶结点。 10. 设图,G V E =<>, 1234{v ,v ,v ,v }V =,若G 的邻接矩阵????????????=0001001111011010A ,则1()deg v -=________, 4()deg v +=____________。 二、选择题(每题2分,合计20分) 1.下列各式中哪个不成立( )。 A 、)()())()((x xQ x xP x Q x P x ?∨??∨? ; B 、)()())()((x xQ x xP x Q x P x ?∨??∨?; C 、)()())()((x xQ x xP x Q x P x ?∧??∧?; D 、Q x xP Q x P x ∧??∧?)())((。

离散数学图论练习题

图论练习题 一.选择题 1、设G是一个哈密尔顿图,则G一定是( )。 (1) 欧拉图(2) 树(3) 平面图(4)连通图 2、下面给出的集合中,哪一个是前缀码?() (1) {0,10,110,101111}(2) {01,001,000,1} (3) {b,c,aa,ab,aba}(4) {1,11,101,001,0011} 3、一个图的哈密尔顿路是一条通过图中()的路。 4、设G是一棵树,则G 的生成树有( )棵。 (1) 0(2) 1(3) 2(4) 不能确定 5、n阶无向完全图Kn 的边数是( ),每个结点的度数是( )。 6、一棵无向树的顶点数n与边数m关系是()。 7、一个图的欧拉回路是一条通过图中( )的回路。 8、有n个结点的树,其结点度数之和是()。 9、下面给出的集合中,哪一个不是前缀码( )。 (1) {a,ab,110,a1b11} (2) {01,001,000,1} (3) {1,2,00,01,0210} (4) {12,11,101,002,0011} 10、n个结点的有向完全图边数是( ),每个结点的度数是( )。 11、一个无向图有生成树的充分必要条件是( )。 12、设G是一棵树,n,m分别表示顶点数和边数,则 (1) n=m (2) m=n+1 (3) n=m+1 (4) 不能确定。 13、设T=〈V,E〉是一棵树,若|V|>1,则T中至少存在( )片树叶。 14、任何连通无向图G至少有( )棵生成树,当且仅当G 是( ),G的生成树只有一棵。 15、设G是有n个结点m条边的连通平面图,且有k个面,则k等于: (1) m-n+2 (2) n-m-2 (3) n+m-2 (4) m+n+2。 16、设T是一棵树,则T是一个连通且( )图。 17、设无向图G有16条边且每个顶点的度数都是2,则图G有( )个顶点。 (1) 10 (2) 4 (3) 8 (4) 16 18、设无向图G有18条边且每个顶点的度数都是3,则图G有( )个顶点。 (1) 10 (2) 4 (3) 8 (4) 12

胡寿松第六版答案

胡寿松第六版答案 【篇一:大学课后习题答案】 /p> 《新视野大学英语读写教程(第二版)第三册》课后答案 /viewthread.php?tid=16fromuid=191597 新视野大学英语读写教程(第二版)第一册》课后答案 /viewthread.php?tid=14fromuid=191597 /viewthread.php?tid=37fromuid=191597 21世纪大学实用英语综合教程(第一册)课后答案及课文翻译 /viewthread.php?tid=4fromuid=191597 西方经济学(高鸿业版)教材详细答案 /viewthread.php?tid=60fromuid=191597 《新视野大学英语读写教程(第二版)第二册》课后答案 /viewthread.php?tid=15fromuid=191597 思想道德修养和法律基础课后习题答案 /viewthread.php?tid=63fromuid=191597 《中国近代史纲要》完整课后答案(高教版) /viewthread.php?tid=81fromuid=191597 《全新版大学英语综合教程》(第三册)练习答案及课文译文 /viewthread.php?tid=77fromuid=191597 《全新版大学英语综合教程》(第一册)练习答案及课文译文 /viewthread.php?tid=75fromuid=191597 《会计学原理》同步练习题答案

/viewthread.php?tid=305fromuid=191597 《微观经济学》课后答案(高鸿业版) /viewthread.php?tid=283fromuid=191597 《统计学》课后答案(第二版,贾俊平版) /viewthread.php?tid=29fromuid=191597 《西方经济学》习题答案(第三版,高鸿业)可直接打印 /viewthread.php?tid=289fromuid=191597 毛邓三全部课后思考题答案(高教版)/毛邓三课后答案 /viewthread.php?tid=514fromuid=191597 新视野大学英语听说教程1听力原文及答案下载 /viewthread.php?tid=2531fromuid=191597 西方宏观经济高鸿业第四版课后答案 /viewthread.php?tid=2006fromuid=191597 《管理学》经典笔记(周三多,第二版) /viewthread.php?tid=280fromuid=191597 《中国近代史纲要》课后习题答案 /viewthread.php?tid=186fromuid=191597 《理论力学》课后习题答案 /viewthread.php?tid=55fromuid=191597 《线性代数》(同济第四版)课后习题答案(完整版) 高等数学(同济第五版)课后答案(pdf格式,共527页) /viewthread.php?tid=18fromuid=191597