離散數(shù)學(xué)復(fù)習(xí)題參考帶答案

本文格式為Word版，下載可任意編輯——離散數(shù)學(xué)復(fù)習(xí)題參考帶答案一、選擇題：（每題2’）

1、以下語(yǔ)句中不是命題的有（）。

A．離散數(shù)學(xué)是計(jì)算機(jī)專業(yè)的一門(mén)必修課。C．太陽(yáng)系以外的星球上有生物。

B．雞有三只腳。

D．你計(jì)劃考碩士研究生嗎?

2、命題公式A與B是等價(jià)的，是指（）。

A．A與B有一致的原子變?cè)?/p>

B．A與B都是可滿足的D．A與B有一致的真值）。

C．當(dāng)A的真值為真時(shí)，B的真值也為真

3、所有使命題公式P∨(Q∧?R)為真的賦值為（

A．010，100，101，110，111C．全體賦值

B．010，100，101，111D．不存在

4、合式公式?(P∧Q)?R的主析取范式中含微小項(xiàng)的個(gè)數(shù)為（）。

A．2

B．3

C．5

D．0

5、一個(gè)公式在等價(jià)意義下，下面哪個(gè)寫(xiě)法是唯一的（）。

A．析取范式B．合取范式

C．主析取范式D．以上答案都不對(duì)

6、下述公式中是重言式的有（）。

A．(P∧Q)?(P∨Q)C．?(P?Q)∧Q

B．(P?Q)?((P?Q)∧(Q?P))D．P?(P∧Q)

7、命題公式(?P?Q)?(?Q∨P)中微小項(xiàng)的個(gè)數(shù)為（），成真賦值的個(gè)數(shù)為（）。

A．0

B．1

C．2

D．3

8、若公式(P∧Q)∨(?P∧R)的主析取范式為m001∨m011∨m110∨m111則它的主合取范式為（）。

A．m001∧m011∧m110∧m111C．M001∧M011∧M110∧M111

B．M000∧M010∧M100∧M101

D．m000∧m010∧m100∧m101

B．(?x)(?y)A(x,y)?(?y)(?x)A(x,y)D．(?x)(A(x)∧B(x))?(?x)A(x)∨(?x)B(x)

9、以下公式中正確的等價(jià)式是（）。

A．?(?x)A(x)?(?x)?A(x)C．?(?x)A(x)?(?x)?A(x)

10、以下等價(jià)關(guān)系正確的是（）。

A．?x(P(x)∨Q(x))??xP(x)∨?xQ(x)C．?x(P(x)?Q)??xP(x)?Q

B．?x(P(x)∨Q(x))??xP(x)∨?xQ(x)D．?x(P(x)?Q)??xP(x)?Q

）。

C．?x?y（x·y=y）

D．?x?y（x+y=2y）

11、設(shè)個(gè)體域?yàn)檎麛?shù)集，以下真值為真的公式是（

A．?x?y（x·y=1）

B．?x?y（x·y=0）

12、設(shè)S={?,{1},{1,2}}，則有（）?S。

A．{{1,2}}

B．{1,2}

C．{1}

D．{2}

13、以下是真命題的有（）。

A．{a}?{{a}}

B．{{?}}?{?,{?}}C．??{?,{?}}

S

D．{?}?{?,{?}}

14、設(shè)S={?,{1},{1,2}}，則2有（）個(gè)元素。

A．3

B．6

C．7

D．8

15、已知冪集的基數(shù)|?(A)|=2048，則集合A的基數(shù)|A|為（）。

A．11

B．12

C．10

D．9

16、設(shè)A={1，2，3}，則A上的二元關(guān)系有（）個(gè)。

A．2

3

B．3

2

C．2

3?3

D．3

2?2

17、設(shè)A={a,b,c,d}，A上的等價(jià)關(guān)系R={,,,}∪IA，則對(duì)應(yīng)于R的A的劃分是（）。

A．{{a},{b,c},qyghmyg}B．{{a,b},{c},vweungz}

C．{{a},,{c},pjkhiin}D．{{a,b},{c,d}}

18、設(shè)R，S是集合A上的關(guān)系，則以下說(shuō)法正確的是（）。

A．若R、S是自反的，則R?S是自反的B．若R、S是反自反的，則R?S是反自反的C．若R、S是對(duì)稱的，則R?S是對(duì)稱的

D．若R、S是傳遞的，則R?S是傳遞的

19、集合A上的相容關(guān)系R的關(guān)系矩陣M(R)的對(duì)角線元素（

）。A．全是1

B．全是0

C．有的是1，有的是0

D．有的是2

20、設(shè)集合A={1，2，3}，A上的關(guān)系R={，，，，}，則R不具備（A．自反性

B．傳遞性

C．對(duì)稱性

D．反對(duì)稱性

21、設(shè)S?{1,2,3}，S上關(guān)系R的關(guān)系圖為（如下圖），

則R具有（）性質(zhì)。

A．自反性、對(duì)稱性、傳遞性B．反自反性、反對(duì)稱性C．反自反性、反對(duì)稱性、傳遞性

D．自反性

22、設(shè)S={1，2，3}，R為S上的關(guān)系，其關(guān)系圖為

則R具有（）的性質(zhì)。A．自反、對(duì)稱、傳遞

B．什么性質(zhì)也沒(méi)有

C．反自反、反對(duì)稱、傳遞

D．自反、對(duì)稱、反對(duì)稱、傳遞

23、設(shè)A={1,2,3}，B={a,b}，以下各二元關(guān)系中是A到B的函數(shù)的是（

）。

A．R={,,}B．R={,,,}C．R={,}

D．R={,}

24、設(shè)R為實(shí)數(shù)集，映射f：R?R，f(x)=-x2+2x-1，則f是（）。

A．單射而非滿射

B．滿射而非單射

C．雙射

D．既不是單射，也不是滿射

。

）25、設(shè)A={?，{1}，{1，3}，{1，2，3}}則A上包含關(guān)系“?〞的哈斯圖為（）。

A．B．C．D．

26、N是自然數(shù)集合，定義f：N?N，f(x)=xmod3（即x除以3的余數(shù)），則f是（）。

A．滿射不是單射C．雙射

B．單射不是滿射D．不是單射也不是滿射

27、設(shè)S={?,{1},{1,2}}，則有（）?S。

A．{{1,2}}

B．{1,2}

C．{1}

D．{2}

28、集合A={x|x=2n∧n?N}對(duì)（）運(yùn)算封閉。

A．加法

B．減法

C．乘法

D．|x－y|

29、設(shè)*是集合A上的二元運(yùn)算，稱Z是A上關(guān)于運(yùn)算*的零元，若（）。

A．?x?A，有x*Z=Z*x=Z

B．Z?A，且?x?A有x*Z=Z*x=ZD．Z?A，且?x?A有x*Z=Z*x=Z

C．Z?A，且?x?A有x*Z=Z*x=x30、下面偏序集（）能構(gòu)成格。

31、在（）中，補(bǔ)元是唯一的。

A．有界格

B．有補(bǔ)格

C．分派格

D．有補(bǔ)分派格。

32、下面四組數(shù)能構(gòu)成無(wú)向簡(jiǎn)單圖的度數(shù)序列的有（）。

A．(2,2,2,2,2)

B．(1,1,2,2,3)

C．(1,1,2,2,2)

）。

D．函數(shù)關(guān)系

D．(1,1,3,3,3)

33、無(wú)向圖結(jié)點(diǎn)之間的連通性，是結(jié)點(diǎn)集之間的一個(gè)（

A．連通關(guān)系

B．偏序關(guān)系

C．等價(jià)關(guān)系

34、已知圖G的相鄰矩陣為：

A．5點(diǎn)，8邊

則G有（）。B．6點(diǎn)，7邊

C．5點(diǎn)，7邊

D．6點(diǎn)，8邊

35、以下四組數(shù)為結(jié)點(diǎn)度序列，能構(gòu)成無(wú)向圖的是（）。

A．2,3,4,5,6,7

B．1,2,2,3,4

C．2,1,1,1,2D．3,3,5,6,0

36、以下幾個(gè)圖是簡(jiǎn)單圖的有（）。

A．G1=(V1,E1)，其中V1={a,b,c,d,e}，E1={(a,b),(b,e),(e,b),(a,e),(d,e)}B．G2=(V2,E2)，其中V2=V1，E2={,,,,,}C．G3=(V3,E3)，其中V3=V1，E3={(a,b),(b,e),(e,d),(c,c)}

D．G4=(V4,E4)，其中V4=V1，E4={,,,,}

37、在一棵樹(shù)中有7片樹(shù)葉，3個(gè)3度結(jié)點(diǎn)，其余都是4度結(jié)點(diǎn)則該樹(shù)有（）個(gè)4度結(jié)點(diǎn)。

A．1

B．2

C．3

D．4

38、一棵樹(shù)有2個(gè)4度結(jié)點(diǎn)，3個(gè)3數(shù)度結(jié)點(diǎn)，其余是樹(shù)葉，則該樹(shù)中樹(shù)葉的個(gè)數(shù)是（）。

A．8

B．9

C．10

D．11

39、設(shè)圖G是有6個(gè)頂點(diǎn)的連通圖，總度數(shù)為20，則從G中刪去（）邊后使之變成樹(shù)。

A．10

B．5

C．3

D．2

40、下面那一個(gè)圖可一筆畫(huà)出（）。

41、在如下各圖中（）歐拉圖。

42、下圖中既不是歐拉圖，也不是哈密爾頓圖的是（）。

43、在如下的有向圖中，從V1到V4長(zhǎng)度為3的道路有（）條。

A．1

B．2

C．3

D．4

44、圖中從v1到v3長(zhǎng)度為3的通路有（）條。

A．0

B．1

C．2

D．3

二、判斷題（每題1分）

1．?x(A(x)?B(x))??xA(x)??xB(x)。（Y）2．設(shè)A，B，C是任意三個(gè)集合。

（1）若A?B且B?C，則A?C。（Y）（2）若A?B且B?C，則A?C。（3）若A?B且B?C，則A?C。（N）（4）(A?B)?C=(A×C)?(B×C)。（5）A?∪(B?C)=(A∪B)?(A∪C)。（N）3．A，B，C為任意集合，若A∪B=A∪C，則B=C。（N）4．可能有某種關(guān)系，既不是自反的，也不是反自反的。（Y）5．可能有某種關(guān)系，既是對(duì)稱的，又是反對(duì)稱的。

（Y）

6．設(shè)R是實(shí)數(shù)集，R上的關(guān)系S={||x-y|＜2∧x,y?R}，S是相容關(guān)系。（Y）7．若集合A上的關(guān)系R是對(duì)稱的，則Rc

也是對(duì)稱的。（Y）8．?dāng)?shù)集合上的不等關(guān)系（≠）可確定A的一個(gè)劃分

（N）

9．設(shè)集合A、B、C為任意集合，若A×B=A×C，則B=C。（N）10．函數(shù)的復(fù)合運(yùn)算“?〞滿足結(jié)合律。

（Y）11．集合A上的恒等關(guān)系是一個(gè)雙射函數(shù)。（Y）12．任何一個(gè)循環(huán)群必定是阿貝爾群。

（Y）13．任何循環(huán)群必定是阿貝爾群，反之亦真。