第一章測試下列哪個(gè)命題公式是重言式？()

A:，

B:，

C:，

D:，

答案:D設(shè)p：我有錢，q：我去看電影。命題“雖然我有錢，但是我不去看電影”符號化為____

答案:設(shè)p，q的真值為0，r，s的真值為1，則的真值為____。

答案:若解釋I使命題公式A為真，使公式A?B也為真，則解釋I使公式B為(

）。

A:可滿足，

B:與解釋I無關(guān)

C:真，

D:假，

答案:C任何兩個(gè)重言式的合取或析取，仍然是一個(gè)重言式。（）

A:錯(cuò)

B:對

答案:B命題公式等值于（）。

A:

B:,

C:，

D:，

答案:Bn個(gè)命題變項(xiàng)可以產(chǎn)生（）個(gè)互不等值的極小項(xiàng)。

A:,

B:2n，

C:，

D:n，

答案:A已知_是聯(lián)結(jié)詞的完備集，僅用聯(lián)結(jié)詞“”表達(dá)為_。

答案:求命題公式的主析取范式和主合取范式。

答案:判斷下列推理是否正確，并證明你的結(jié)論。如果他是計(jì)算機(jī)系本科生或者是計(jì)算機(jī)系研究生，那么他一定學(xué)過DELPHI語言而且學(xué)過C++語言。只要他學(xué)過DELPHI語言或者C++語言，那么他就會(huì)編程序。因此如果他是計(jì)算機(jī)系本科生，那么他就會(huì)編程序。

答案:第二章測試設(shè)L(x,y):x大于y，則L(x,y)是一個(gè)命題。（）

A:對

B:錯(cuò)

答案:B在一階邏輯中將命題符號化時(shí)，針對不同的個(gè)體域，同一個(gè)命題符號化之后的結(jié)果可能相同也可能不同。（）

A:錯(cuò)

B:對

答案:B給定解釋N如下：在解釋N下，下面公式中真命題有（）。

A:

B:

C:

D:

答案:BC下列公式中，邏輯有效式是（）。

A:

B:

C:

D:

答案:BD在一階邏輯中，任何合式公式都存在與之等值的前束范式，并且前束范式是唯一存在的。（）

A:錯(cuò)

B:對

答案:A每列火車都比某些汽車快。，則該命題符號化為（）

A:

B:

C:

D:

答案:C給定解釋I如下：下列公式為真的是（）

A:

B:

C:

D:

答案:ABD答案:答案:，請問哪幾個(gè)正確（）

A:

B:

C:

D:

答案:AB第三章測試為真。（）

A:錯(cuò)

B:對

答案:B為真。（）

A:對

B:錯(cuò)

答案:B為真。（）

A:對

B:錯(cuò)

答案:A為假。（）

A:對

B:錯(cuò)

答案:B=____。

答案:=____。

答案:=____。

答案:=____。

答案:證明。

答案:證明

答案:化簡。

答案:已知，證明。

答案:一個(gè)班有50個(gè)學(xué)生，在第一次考試中有26人得5分，在第二次考試中有21人得5分。如果兩次考試中都沒得到5分的有17人，則兩次考試都得5分的有多少人？分別用包含排斥原理和文氏圖求解。

答案:第四章測試集合A={1,2,…,10}上的關(guān)系R={＜x,y＞|x+y=10,x,y∈A}，則R的性質(zhì)為（）。

A:傳遞的

B:對稱的

C:對稱的、傳遞的

D:自反的

答案:B集合A上的偏序關(guān)系的三個(gè)性質(zhì)是（）。

A:反對稱性

B:傳遞性

C:自反性

D:對稱性

答案:ABC集合A上的等價(jià)關(guān)系的三個(gè)性質(zhì)是（）。

A:反對稱性

B:自反性

C:對稱性

D:傳遞性

答案:BCDA上的恒等關(guān)系既是等價(jià)關(guān)系又是偏序關(guān)系。（）

A:對

B:錯(cuò)

答案:A若R和S都是非空集A上的等價(jià)關(guān)系，則R?S是A上的等價(jià)關(guān)系。（）

A:對

B:錯(cuò)

答案:A設(shè)Ａ＝｛1,2,3,4,5,6｝，B=____，從Ａ到B的關(guān)系Ｒ＝｛＜x,y＞|x=y2｝，則R=（），____}

答案:設(shè)S=____，Ａ上的關(guān)系Ｒ＝｛，，，｝，則RR=（），____}

答案:R是A=____上的等價(jià)關(guān)系，R=IA∪____則由R誘導(dǎo)的劃分為（）。____,____,____}

答案:設(shè)RíA×A，證明R自反?IAíR。

答案:設(shè)A={1,2,…,10}。B、C、D是否為A的劃分？若是，則求出由它誘導(dǎo)的等價(jià)關(guān)系.（1）B={{1,3,6},{2,8,10},{4,5,7}};（2）C={{1,5,7},{2,4,8,9},{3,5,6,10}};（3）D={{1,2,7},{3,5,10},{4,6,8},{9}}

答案:第五章測試給定下列各圖，為簡單圖的是（）。

A:

B:

C:

D:

答案:C下面各序列中，可以構(gòu)成無向簡單圖的是（）。

A:（1,1,2,2,2）

B:（1,3,4,4,3）

C:（1,1,2,2,3）

D:（3,3,4,2,3）

答案:A下面給出的無向圖中，為多重圖的是（）。

A:G=＜V，E＞,其中V={a,b,c,d,e}，E={（a,b）,（b,c）,（c,d）,（a,e）}

B:G=＜V，E＞,其中V={a,b,c,d,e}，E={（a,c）,（b,e）,（a,e）,（d,e）}

C:G=＜V，E＞,其中V={a,b,c,d,e}，E={（a,b）,（b,e）,（e,d）,（c,c）}

D:G=＜V，E＞,其中V={a,b,c,d,e}，E={（a,b）,（b,e）,（e,b）,（a,e）,（d,e）}

答案:D下列各組數(shù)中，能夠構(gòu)成無向圖的度數(shù)列的是（）。

A:2,2,4,2,2

B:1,1,1,2,4

C:3,3,2,3

D:1,2,3,4,5

答案:A一個(gè)無向圖有16條邊，每個(gè)頂點(diǎn)都是2度的，則這個(gè)無向圖中有幾個(gè)頂點(diǎn)（）。

A:10

B:4

C:16

D:8

答案:C下面圖中強(qiáng)連通圖為（）。

A:

B:

C:

D:

答案:C對如下無向圖下面選項(xiàng)中哪一個(gè)不是該無向圖的點(diǎn)割集。（）

A:{v2}

B:{v3，v5}

C:{v2，v4}

D:{v6}

答案:C不含平行邊的圖稱為簡單圖。（）

A:錯(cuò)

B:對

答案:A任何圖（無向圖或有向圖）中，度數(shù)為奇數(shù)的頂點(diǎn)個(gè)數(shù)為偶數(shù)。（）

A:錯(cuò)

B:對

答案:B頂點(diǎn)數(shù)相同，邊數(shù)相同，度數(shù)序列也相同的兩個(gè)圖一定同構(gòu)。（）

A:錯(cuò)

B:對

答案:A給圖著色時(shí)，若圖為圈，長度為偶數(shù)的圈要用2種顏色，長度為奇數(shù)的圈要用3種顏色。（）

A:對

B:錯(cuò)

答案:A給圖著色時(shí)，奇階輪圖要用3種顏色，偶階輪圖要用4種顏色。（）

A:錯(cuò)

B:對

答案:B項(xiàng)目網(wǎng)絡(luò)圖有一個(gè)始點(diǎn)和一個(gè)終點(diǎn)，始點(diǎn)的出度為0，終點(diǎn)的入度為0。（）

A:對

B:錯(cuò)

答案:B無向圖的關(guān)聯(lián)矩陣中每一列都恰好有兩個(gè)1或一個(gè)2。（）

A:錯(cuò)

B:對

答案:B有向圖的鄰接矩陣中所有元素之和等于對應(yīng)圖中邊數(shù)的兩倍。（）

A:對

B:錯(cuò)

答案:B完全圖K4的所有非同構(gòu)的生成子圖中，2條邊的有（）個(gè)。____。

答案:一個(gè)無向圖有21條邊，3個(gè)4度頂點(diǎn)，其余都是3度頂點(diǎn)，則該圖有（）個(gè)頂點(diǎn)。____。

答案:任何圖（無向圖或有向圖）中所有頂點(diǎn)的度數(shù)之和等于邊數(shù)的（）倍。____。

答案:在一個(gè)n階圖中，若從頂點(diǎn)u到v(uv)存在通路，則從u到v存在長度小于等于（）的通路。____。

答案:下圖至少要用（）種顏色著色。____。

答案:35條邊，每個(gè)頂點(diǎn)的度數(shù)至少為3的圖最多有（）個(gè)頂點(diǎn)。____。

答案:求圖中從頂點(diǎn)b頂點(diǎn)到g的最短路徑為（）。____。

答案:畫出4階3條邊的所有非同構(gòu)的無向簡單圖。

答案:設(shè)有向圖D的度數(shù)列為2,2,3,3，入度列為0,0,2,3，試求出D的出度列。

答案:設(shè)G為9階無向圖，每個(gè)頂點(diǎn)的度數(shù)不是5就是6，證明G中至少有5個(gè)6度頂點(diǎn)或至少有6個(gè)5度頂點(diǎn)。

答案:設(shè)G1與G2均為無向簡單圖，證明：G1@G2當(dāng)且僅當(dāng)，其中分別為G1與G2的補(bǔ)圖。

答案:已知n階無向圖G中有m條邊，各頂點(diǎn)的度數(shù)均為3，又已知2n-3=m，問在同構(gòu)的意義下，G是唯一的嗎？若G為簡單圖，是否唯一？請說明為什么。

答案:有向圖D如下圖所示，求D中在定義意義下長度為4的通路總數(shù)，并指出其中有多少條是回路？又有幾條是v3到v4的通路。

答案:計(jì)算機(jī)系期末要安排7門公共課的考試，課程編號為1到7。下列每一對課程有學(xué)生同時(shí)選修：1和2，1和3，1和4，1和7，2和3，2和4，2和5，2和7，3和4，3和6，3和7，4和5，4和6，5和6，5和7，6和7。這7門課的考試至少要安排在幾個(gè)不同的時(shí)間段？給出一個(gè)安排方案。

答案:第六章測試下列無向圖中哪些是二部圖（）。

A:

B:

C:

D:

答案:BCD下列圖中哪些是歐拉圖（）。

A:

B:

C:

D:

答案:AB下列圖中哪些是哈密爾頓圖（）。

A:

B:

C:

D:

答案:AC下列圖中哪些是不平面圖（）。

A:

B:

C:

D:

答案:BCD圖存在完美匹配。（）

A:對

B:錯(cuò)

答案:A圖存在完美匹配。（）

A:對

B:錯(cuò)

答案:B任何地圖都是4-可著色的。（）

A:對

B:錯(cuò)

答案:A圖中，____是匹配，____是極大匹配，____是最大匹配，匹配數(shù)是____。

答案:圖中，____為最大匹配，____完備匹配，____完美匹配。

答案:圖中，____為完備匹配，____完美匹配。

答案:第七章測試具有2個(gè)頂點(diǎn)的非同構(gòu)無向樹有幾棵（）。

A:4

B:2

C:3

D:1

答案:D具有4個(gè)頂點(diǎn)的非同構(gòu)無向樹有幾棵（）。

A:4

B:3

C:1

D:2

答案:D具有6個(gè)頂點(diǎn)的非同構(gòu)無向樹有幾棵（）。

A:6

B:5

C:3

D:4

答案:A一棵樹有7片樹葉、3個(gè)3度頂點(diǎn)、其余都是4度頂點(diǎn)，則該樹有1個(gè)4度頂點(diǎn)。（）

A:對

B:錯(cuò)

答案:A一棵樹有2個(gè)4度頂點(diǎn)、3個(gè)3度頂點(diǎn)、其余都是樹葉，則該樹有10片樹葉。（）

A:錯(cuò)

B:對

答案:A對圖所示的根樹中序行遍法訪問的次序是_，前序行遍法