單項(xiàng)選擇題第一章命題邏輯1．以下語句，哪一個(gè)是真命題：（B）A．我正在謊言B．若是1+1=0，那么雪是黑的C．9+5＞18D．存在最大的質(zhì)數(shù)2．下面哪一個(gè)命題是假命題（A）A．若是2是偶數(shù)，那么一個(gè)公式的析取范式唯一B．若是2是偶數(shù)，那么一個(gè)公式的析取范式不唯一C．若是2是奇數(shù)，那么一個(gè)公式的析取范式唯一D．若是2是奇數(shù)，那么一個(gè)公式的析取范式不唯一3．下面哪個(gè)聯(lián)系詞運(yùn)算不能交換（B）A．；B．C．D．4．設(shè)P：天下大雨，Q：他乘公共汽車上班。命題“只有天下大雨，他才乘公共汽車上班”符號(hào)化為（B）A．PQB．QPC．PQD．PQ5．設(shè)P：天下釘子，Q：我去B城。命題“除非天下釘子，否則我去B城”符號(hào)化為：（CA．PQB．QPC．PQD．Q┐P6．設(shè)P：我們劃船，Q：我們跳舞，命題“我們不能夠既劃船又跳舞”符號(hào)化為（B）A．PVQ2）┐（P∧Q）C．┐P∧┐QD．┐P∧Q7．令P：今天下雪了，Q：路滑，則命題“誠然今天下雪了，但是路不滑”可符號(hào)化為（DA．P┐QB．P∨┐QC．P∧QD．P∧┐Q8．設(shè)P：我將去鎮(zhèn)上，Q：我有時(shí)間，命題“我將去鎮(zhèn)上，僅當(dāng)我有時(shí)間”，符號(hào)化為（AA．PQB、QPC、PQD、┐P∨┐Q9．下面哪一個(gè)命題公式是重言式（D）A．（P∨R）∧（PQ）B．P（Q∨R）C．（P∨Q）（Q∨R）D．（P（QR））（PQ）（PR）

）））。10．下面哪一組命題公式不是等價(jià)的（A．（PQ）（QP），PQC．P（Q∨R），┐P∧（Q∨R）

C）B．（PQ），（P∧┐Q）∨（┐P∧Q）D．P（Q∨R），（P∧┐Q）R11．下面哪個(gè)命題公式是重言式（B）A．（PQ）（QP）B．（PQ）PC．（┐P∨Q）∧┐（┐P∧Q）D．（PQ）P12．以下公式哪一個(gè)是兩個(gè)命題變?cè)狿，Q的小項(xiàng)（C）A．P∧┐P∧QB．┐P∨QC．┐P∧QD．┐P∨P∨Q13．一個(gè)公式在等價(jià)意義下，下面哪個(gè)寫法是唯一的。（C）ABCD14．命題公式(PQ)的主析取范式編碼為(D)A．m00m01m11B．m00∨m11C．m01D．m10命題公式(PQ)的主合取范為(a)A．M01M10B.M00M11C.M00M01D.M10M11命題公式的任意兩個(gè)不相同極小項(xiàng)的合取式必然為(b)A.永真式B.永假式C.可滿足式D.不能確定17．下面聯(lián)系詞集中，哪一個(gè)不是聯(lián)系詞的極小全功能集（A．{，}B．{↓}C．{}D．{，，

}

d）第二章一階邏輯1．設(shè)S(x):x是三好學(xué)生

,a:

張三,b:

李四,

命題“張三是三好學(xué)生而李四不是”符號(hào)化為（）DA．S（a），S（b）B．S（a）∨S（b）C．S（a）∨S（b）D．S（a）∧S（b）令F(x):x是有理數(shù)，G(x):x是實(shí)數(shù)。將命題“所有的有理數(shù)都是實(shí)數(shù)，但有的有實(shí)數(shù)不是有理數(shù)”符號(hào)化為（）BA.x(F(x)∧G(x))∧x(G(x)F(x))B.x(F(x)

G(x))

∧

x(G(x)

∧

F(x))C.x(F(x)

∧G(x))

∧

x(G(x)

∧

F(x))D.x(F(x)

G(x))

∧

x(G(x)

F(x))3．設(shè)F(x)：x是火車，G(x)：x是汽車，H(x,y)：x比y快。“每列火車都比某些汽車快”符號(hào)化為（）CA．(x)(y)(F(x)G(y)H(x,y))；B．(x)(y)(F(x)G(y)H(x,y))；C．(x)(F(x)(y)(G(y)H(x,y)))；D．(x)F(x)H(x,y)4．設(shè)C(x)：x是國家選手，G(x)：x是強(qiáng)壯的。命題“沒有一個(gè)國家選手不是強(qiáng)壯的”可符號(hào)化為（

）

CA．C．5．設(shè)個(gè)體域

(x)(C(x)G(x))；(x)(C(x)G(x))；A={a、b}，公式(x)P(x)

B．(x)(C(x)G(x))D．(x)(C(x)G(x))xS(x)在A上消去量詞應(yīng)為（

；；

）

DA．P(x)∧S(x)C．P(a)∧S(b)6．一階公式?x(P(x)

BD∨?yR(y))

．P(a)∧P(b)∧S(a)∨S(b)．P(a)∧P(b)∧(S(a)∨S(b))→Q(x)中量詞?x的轄域是( )AA.(P(x)

∨?yR(y))

B.P(x)C.x(P(x)

∨?yR(y))

D.(P(x)

∨?yR(y))

→Q(x)7、設(shè)論域?yàn)檎麛?shù)集，以下公式中哪個(gè)值為真（A．xy(xy0)B.yx(xy0)

C.

xy(x

）y

A

0)D．

xy(x

y

0)8．下面給出的一階邏輯等價(jià)式中，哪一個(gè)是錯(cuò)的。（

）

BA．AxB（x）x（AB（x））B．x（A（x）B（x））xA（x）xB（x）C．x（A（x）B（x））xA（x）xB（x）D．xA（x）x（A（x））9．在謂詞演算中，以下各式中，哪式是正確的（A．xyA(x,y)yxA(x,y)B．xyA(x,y)C．xyA(x,y)xyA(x,y)D．xyA(x,y)

）。BxA(x,y)yxB(x,y)10．設(shè)論域?yàn)檎麛?shù)集，以下公式中哪個(gè)值為假（）DA．y(xy0)B．yx(xy2)C．xyz(xyz)D．xy((xy)1)11．設(shè)I是以下一個(gè)講解：D＝{a,b},P(a,a)P(a,b)P(b,a)P(b,b)1010則在講解I下取真值為1的公式是().DAxyP(x,y)BxyP(x,y)CxP(x,x)DxyP(x,y).12．謂詞公式(x)P(x,y)∧(x)(Q(x,z)(x)(y)R(x,y,z))中量詞x的轄域是（）AA．（Q(x,z)(x)(y)R(x,y,z)）B．Q(x,z)，R(x,y,z)C．Q(x,z)(y)R(x,y,z)D．Q(x,z)13.謂詞公式x(p(x)yR(y)Q(x)中變?cè)质?)DA．自由變?cè)狟．既不是自由變?cè)膊皇蔷惺冊(cè)狢．拘束變?cè)狣．既是自由變?cè)质蔷惺冊(cè)?4.一階邏輯公式x(F(x,y)∧G(y,z))→zF(z,y)是（）CA.前束范式B.封閉公式C.永真式D.永假式15．一階邏輯公式xP(x)xP(x)是()AA.永真的B.永假的C.可滿足的D.前束范式.16.一階邏輯公式xP(x)yQ(y)的前束范式是（d）A.xy(P(x)Q(y))B.xP(x)∨yQ(y)C.xyP(x)∨Q(y)D.xy(P(x)Q(y))第三章會(huì)集的基本看法和運(yùn)算1．以下式子中正確的選項(xiàng)是（）．DA．＝0；B．；C．＝{}；D．｛｝2．以下各式中哪個(gè)是錯(cuò)的（B）A、；B、；C、｛｝；D、{}。3．以下命題正確的選項(xiàng)是（）。AA．{}=B．{}=C．{a}{a，b，c}D．{a，b，c}4．以下各命題哪一個(gè)是假命題（）BA．{a,b}{a,b,c,{a,b,c}}B．{a,b}{a,b,c,{a,b,c}}C．{a,b}{a,b,{a,b}}D．{a,b}{{a,b}}5．設(shè)A={{1,2,3},{4,5},{6,7,8}}，以下哪個(gè)式子為真（）CA．1∈AB．{1,2,3}?AC．{{4,5}}?AD．A6．設(shè)A＝{}，B=P（P（A）），下式中錯(cuò)的是（A．B；B．{}B；C．{{}}B；7．設(shè)A=，B={,{}}，則B－A是（）CA．{{}}；B．{}；C．{,{}}；

）DD．{，{}}D．

P（A）。8．會(huì)集{0}的所有子集是（）BA．；B．,{0}；C．{}；D．{,{0}}9．設(shè)A＝{a,b}，則A的冪集P（A）為（）DA．{a,b}B．{,{a},}C．{,{a,}}D．{,{a},,{a,b}}10．設(shè)X，Y，Z是會(huì)集，“一”是會(huì)集相對(duì)補(bǔ)運(yùn)算，以低等式不正確的選項(xiàng)是（A．(X－Y)－Z＝X－(Y∩Z)

）ＡB．(X－Y)－Z＝(X－Z)－YC．(X－Y)－Z＝(X－Z)－(Y－Z)D．(X－Y)－Z＝X－(Y∪Z)11.設(shè)會(huì)集

A={2,{a},3,4}

，B={1,{a},3,4}

，E為全集，則以下命題正確的選項(xiàng)是

(

)CA{2}

A

B{a}

AC

{{a}}

B

D{{a},1,3,4}

B.設(shè)A,B為會(huì)集,A∩B=A∪B成立的充分必要條件是(D)A.A=B=B.A=C.B=D.A=B第四章二元關(guān)系與函數(shù)1．設(shè)A＝{1，2}，B＝{a,b,c}，C＝{c,d}，則A×（B∩C）為（B）A．c,1,2,cB．1,c,2,cC．c,1,c,2D．1,c,c,22．設(shè)會(huì)集A={1，2，3}，A上的關(guān)系R={<1，1>，<1，2>，<2，2>，<3，3>，<3，2>}，則R不具備()BA．傳達(dá)性B．對(duì)稱性C．自反性D．反對(duì)稱性3．設(shè)R是會(huì)集A={a,b,c,d}上的二元關(guān)系，R={<a,a>,<a,b>,<a,c>,<a,d>,<c,b>,<d,b>,<d,c>}，則R具有關(guān)系的哪些性質(zhì)（）DA.自反性、反對(duì)稱性B.反自反性、傳達(dá)性C.自反性、對(duì)稱性D.反對(duì)稱性、傳達(dá)性4．設(shè)會(huì)集A＝{1,2,3,4}，A上的關(guān)系R＝{<1,1>,<2,2>,<1,3>}，則R具有關(guān)系的哪些性質(zhì)（）．AA．傳達(dá)性；B．自反性；C．對(duì)稱性；D．以上答案都不對(duì)5．設(shè)A={0,b}，B={1,b,3}，則A∪B的恒等關(guān)系為（）AA．{<0,0>,<1,1>,<b,b>,<3,3>}；B．{<0,0>,<1,1>,<3,3>}；C．{<1,1>,<b,b>,<3,3>}；D．{<0,1>,<1,b>,<b,3>,<3,0>}6．設(shè)A＝{1，2，4，6，8},會(huì)集A上的二元關(guān)系Ra,bab2，則和分別domRranR為（）BA．1,2和1,4B．1,4和1,2C．1,4和2,1D．1,1,4,2和2,17．若會(huì)集A上的關(guān)系R為等價(jià)關(guān)系，則R的必要條件是（）DA．對(duì)稱的和傳達(dá)的B．反自反的C．反對(duì)稱的D．自反的，對(duì)稱的和傳達(dá)的8．設(shè)會(huì)集

A={a,b,c}

，A上所有互不相同的等價(jià)關(guān)系的數(shù)目為

( )CA.3

B.4

C.5

D.69．設(shè)

A={a,b,c,d}

，A上的等價(jià)關(guān)系

R={<a,b>,<b,a>,<c,d>,<d,c>}

∪IA，則對(duì)應(yīng)于

R的

A的劃分是（）DA．{{a},{b,c},flpdjfr}C．{{a},,{c},ljxxfvh}

BD

．{{a,b},{c},hzhdrpj}．{{a,b},{c,d}}10．P={a、b、c、d}的最大劃分是（）（即集中元素?cái)?shù)目最多的劃分）CA．{{a}，{b，c}zlzlzvj}；B．{a，{b，c}}；C．{{a}、，{c}，jjnbfxl}D．{{a，b，c，d}}11．會(huì)集A上的關(guān)系R是偏序關(guān)系的必要條件是（）AA．自反的，反對(duì)稱的和傳達(dá)的；B．自反的和對(duì)稱的；C．傳達(dá)和和對(duì)稱的；D．傳達(dá)的和反對(duì)稱的。12．會(huì)集A＝{1,2,3，4，5，6，7，8，9，10}，A上的整除關(guān)系是一個(gè)偏序關(guān)系，則元素是會(huì)集A的（）．C

10以下關(guān)系中哪一個(gè)是會(huì)集A={a,b,c,d,e,f}上偏序關(guān)系？（）BA.{<a,c>,<b,c>,<c,b>}∪IAB.{<a,e>,<c,d>,<b,f>}∪IAC.{<a,b>,<b,f>,<f,c>}∪IAD.{<b,d>,<e,f>,<d,b>,<f,e>}∪IA14.會(huì)集

A=a,b,c,d

，A

上的一個(gè)劃分

1

a,b,c,d

，則對(duì)應(yīng)的等價(jià)關(guān)系

R

1（

A）。A．{a,b

,

b,a

}

IA

B．{

a,b

,

b,a

,

c,c

,

d,d

}C．{

a,a

,

b,b

,

c,c

,

d,d

}

D．{

a,b

,

b,a

}設(shè)A={a,b,c,d}，A上的等價(jià)關(guān)系R={<a,b>,<b,a>,<c,d>,<d,c>}∪IA，則對(duì)應(yīng)于R的A的劃分是（D）A．{{a},{b,c},njpzndj}B．{{a,b},{c},xlpbphl}C．{{a},,{c},zznrvvp}D．{{a,b},{c,d}}16．設(shè)R為實(shí)數(shù)集，照射f：RR，f（x）＝-x2+2x-1，則f是（）。DA．單射而非滿射B．滿射而非單射C．雙射D．既不是單射，也不是滿射17．設(shè)f和g都是A到A的雙射函數(shù)，則（fog）-1為（D）A．f-1og-1B.f-og-1C.（gof）-1D.g-1of-1設(shè)會(huì)集A={a,b,c},B={β,ε,θ},則從A到B最多能夠定義多少個(gè)雙射函數(shù)( )DA.27

B.9

C.8

D.6第七章

圖的基本看法1．僅由一個(gè)孤立點(diǎn)組成的圖稱為（A．零圖B．平凡圖C

）B．多重圖

D．子圖2．給予下序列，哪一個(gè)可組成無向簡(jiǎn)單圖的極點(diǎn)度數(shù)序列（

B

）（1）（1，1，2，2，3）（2）（1，1，2，2，2）（3）（1，2，3，4，5）（4）（1，3，4，4，5）3．下面所給的數(shù)值序列，能成為簡(jiǎn)單圖的度數(shù)序列的是（）CA．(1,2,2,3,4,5)B．(1,2,3,4,5,5)C．(1,1,1,2,3)D．(2,3,3,4,5,6)4．在任何圖G=＜V，E＞中，極點(diǎn)總度數(shù)和邊數(shù)的關(guān)系為（）Cdeg(v)2Edeg(v)Edeg(v)2Edeg(v)EA．vVB．vVC．vVD．vV5．設(shè)G為有n個(gè)結(jié)點(diǎn)的無向完好圖，則G的邊數(shù)為（）AA．n(n1)2B．(n1)2C．n(n－1)D．n(n+1)6．有向圖G=<V，E>，其中V={a,b,c,d,e,f}，E={<a,b>,<b,c>,<a,d>,<d,e>,<f,e>}是( )AA．弱連通圖B．單向連通圖C．強(qiáng)連通圖D．不連通圖7．圖G=<V,E>以以下列圖所示，從a到d有多少條簡(jiǎn)單通路（）CA．5B．6C．7D．88．毗鄰矩陣擁有對(duì)稱性的圖必然是（）BA．有向圖B．無向圖C．混雜圖D．簡(jiǎn)單圖9．G=<V,E>是簡(jiǎn)單有向圖，可達(dá)矩陣P（G）刻劃以下哪一種關(guān)系（）AA．點(diǎn)與點(diǎn)B．點(diǎn)與邊C．邊與點(diǎn)D．邊與邊0111110．設(shè)圖G的毗鄰矩陣為10100，則G的極點(diǎn)數(shù)與邊數(shù)分別為( )D110111010110110A．4,511．在完好圖

B．5,6C．4,10DK4的所有非同構(gòu)的生成子圖中，有幾個(gè)是

．5,83條邊的？(

)BA.1

B.2

C.3

D.412．圖G和G’的結(jié)點(diǎn)和邊分別存在——對(duì)應(yīng)關(guān)系是GG'（同構(gòu)）的（）A．充分條件B．充分必要條件C．必要條件D．既不充分也不用要條件設(shè)圖G=<V,E>為無向圖，|V|=6，|E|=22，則G必然是DA.完好圖B.正則圖C.簡(jiǎn)單圖D.多重圖14．設(shè)A（G）是有向圖G=（V，E）的毗鄰矩接，其中第i行中值為1的元素?cái)?shù)目為（A．結(jié)點(diǎn)Vi的入度B.結(jié)點(diǎn)Vi的出度C．結(jié)點(diǎn)Vi的度數(shù)D.結(jié)點(diǎn)Vj的度數(shù)15.有3條邊的互不相同構(gòu)的4階無向簡(jiǎn)單圖的個(gè)數(shù)為（）A

）

BA.2

B.3

C.4

D.5有向圖G是強(qiáng)連通圖，當(dāng)且僅當(dāng)DA.圖G中最少有一條通路B.圖G中有經(jīng)過每個(gè)極點(diǎn)最少一次的通路C.圖G中最少有一條回路D.圖G中有經(jīng)過每個(gè)極點(diǎn)最少一次的回路17.有向圖G是單向連通圖，當(dāng)且僅當(dāng)( )BA.圖G中最少有一條通路B.圖G中有經(jīng)過每個(gè)極點(diǎn)最少一次的通路C.圖G的連通分枝數(shù)為一.D.圖G中有經(jīng)過每個(gè)極點(diǎn)最少一次的回路.第八章一些特其他圖1．一個(gè)連通的無向圖G，若是它的所有結(jié)點(diǎn)的度數(shù)都是偶數(shù)，那么它擁有一條( )BA．哈密爾頓回路B．歐拉回路C．哈密爾頓通路D．初級(jí)回路2．無向圖G是歐拉圖，當(dāng)且僅當(dāng)（）DA．G的所有結(jié)點(diǎn)的度數(shù)全為偶數(shù)。B．G中所有結(jié)點(diǎn)的度數(shù)全為奇數(shù)。C．G連通且所有結(jié)點(diǎn)度數(shù)全為奇數(shù)。D．G連通且所有結(jié)點(diǎn)度數(shù)全為偶數(shù)。3．設(shè)G是連通平面圖，有5個(gè)極點(diǎn)，6個(gè)面，則G的邊數(shù)是( )AA．9條B．5條C．6條D．11條4．設(shè)G是連通平面圖，G中有6個(gè)極點(diǎn)8條邊，則G的面的數(shù)目是（）CA．2個(gè)面B．3個(gè)面C．4個(gè)面D．5個(gè)面5．二部圖

K3,3是( )

BA.歐拉圖B.哈密頓圖6.以下列圖形哪一個(gè)能夠一筆畫出？

C.

平面圖（）D

D.完好圖7．在下面的無向圖中，哪一個(gè)是哈密頓圖？。（8．以下列圖屬于什么圖？（）DA．二部圖B．歐拉圖C．哈密爾頓圖

）BD．是二部圖也是哈密爾頓圖以下列圖的最大般配是( )aA.{e1,e2,e5,e7,e11}B.{e2