11009試題庫（363）[筆試+11009《離散數(shù)學（本）》國家開放大學期末考試題庫（363）[筆試+一平臺機考]

適筆試+一平臺機考】【試卷號：11009】【課50501363(135)判斷(122)計算題(60)邏輯公式翻譯單選(135)--

）1、5階無向完全圖K5,的邊數(shù)為（）A.10

2、G是連通平面圖,有v個結點,e條邊,r個面,則r=（）答案：e－v＋2

3、n階無向完全圖K,的邊數(shù)及每個結點的度數(shù)分別是（）4、n階無向完全圖Kn中的邊數(shù)5、π階無向完全圖K,每個結點的度數(shù)是C.n-16、表達式中 7、集合A={1,2,3,4,5,6,7,上的關系R={<x,y>|x+y=10且x,yA}則R的性質為（）對稱的8、集合A={1,2,3,4}上的關系R={<x,y>|x=y且x,yA},則R質為（）．傳遞的9、集合為A={x|x為小于10的自然數(shù)}答案：B.對稱的10、命題公式(P∨Q)→Q為（）答：可滿足式11、命題公式(P∨Q)→R的析取范式是（）．答：(┐P∧┐Q)∨R12、命題公式P→Q的主合取范式是（）．答：┐P∨Q13、命題公式P的合取范式是（）。A.P14、命題公式┐(p→Q)的主析取范式是（）．答：P∧┐Q15、前提條件P→┐Q2P的有效結論是（）．┐Q

16、如果R1和R2是A上的自反關系,則R1∪R2,R1∩R2,R1-R2自反關系有（）個．217、如圖二所示,以下說法正確的是（）．答案：e是割點

18、如圖一所示,以下說法正確的是（）.答：A.e是割點

19、如圖一所示,以下說法正確的答案：{（d,e）}是邊割集20、若a是圖G的割點,則以下說法正確的是（）。D.刪除a點，則G不聯(lián)通

21、若G是一個漢密爾頓圖,則G一定是（）．答案：連通圖

22、若R1和R2是A上的對稱關系,則R1UR2,R∩R2,R1-R22-R1中對稱關系有（）個。D.4

23、若集合A={1,2,3,4},B=,3,5},則下列表述正確的是（）24、若集合A={1,2,3,4},則下列表述不正確的是25、若集合A={1,2,3,4},則下列表述不正確的是（）。26、若集合A={1,2,3},則下列表述不正確的是（）。27、若集合A={1,2,3},則下列表述正確的是（）28、若集合A={1,2},B={1,2,{1,2}},則下列表述正確的是（）29、若集合A={2,3,4,5},則下列表述不正確的是（）.30、若集合A={2,a,{a},4},則下列表述正確的是（）。{a}A31、若集合A={a,b,c,d},則下列表述正確的是（）32、若集合A={a,b,c},則下列表述不正確的是（）。33、若集合A={a,b,c},則下列表述正確的是（）34、若集合A={a,b,c},則下列表述正確的是（）1/

11009試題庫（363）[筆試+35、若集合A={a,b,c},則下列表述正確的是（）。36、若集合A={a,b},B={a,}則（）。37、若集合A={a,b},則下列表述正確的是（）38、若集合A={a,{a},{1,2}則下列表述正確的是（）。{a}A39、若集合A={b,c,d},則下列表述正確的是（）40、若集合A={{a}},則下列表述正確的是（）41、若集合A的元素個數(shù)為10,則其冪集的元素個數(shù)為（）

A．1024

42、若集合A的元素個數(shù)為5,則其冪集的元素個數(shù)為（）

答：C.32

43、若圖G=<V,E>,其中V={a,b,c,d},E={(a,b),(b,c),(b,d則該圖中的割點為（）．B.b44、若無向圖G的結點度數(shù)之和為10,則G的邊數(shù)為（）.A.545、若無向圖G的結點度數(shù)之和為20,則G的邊數(shù)為A.10

46、設A(x):x是金屬,B(x):x是金子,則命題“有的金屬是金子可符號化為（）47、設A(x):x是人,B(x):x是工人,則命題“有人是工人”可符號化為（）。48、設A(x):x是人,B(x):x是教師,則命題“有人是教師”可符號化為（）．49、設A(x):x是人,B(x):x是學生,則命題“不是所有人都生”可符號化為（）.D.?(?

50、設A(x):x是書,B(x):x是數(shù)學書,則命題“不是所有書數(shù)學書”可符號化為（）．51、設A(x):x是水果,B(x):x是草莓,則命題“不是所有的都是草莓”可符號化為（）D.（Vx）（A（x）→B（x））

52、設A(x):x是水果,B(x):x是草莓,則命題“不是所有的都是草莓”可符號化為（）.D.()(A(x)→B(x))

53、設A(x):x是學生,B(x):x去跑步,則命題“所有學生都步”可符號化為（）.54、設A(x):是人,B(x):x是學生,則不是所有人都是學生可符號化為（）55、設A={1,2,3,4,5,6,7,8},R是A上的整除關系,B={2,4}則集合B的最大元、最小元、上界、下界依次為（）

B．無、2、無、2

56、設A={1,2,3,4,5,6},B={1,2,3}A到B的關系則R=57、設A={1,2,3,4},B={2,3,4},A到B的關系R={<x,y>x∈A,y∈B,且x+y=5},則R=（）.-->B.{<1,4>,<2,3>,<3,2>}

58、設A={1,2,3},B={1,2,3,4},A到B的關系R=[<x,y>x大于y)則R=（）59、設A={1,2,3},B={2,4,6},A到B的關系則R=（）。60、設A={1,2},B={1,2,3,4,5},A到B的關系R={<x,y>|x∈A,y∈B,x++1=y},則R=（）.61、設A={1,3,5,7,9},B={2,6},A到B的關系R={<X,y>|x-y=1則R=（）。62、設A={1,6,7},B={2,4,8,10},A到B的關系R={<z,y>|x∈A,∈B,且x=y},則R=（）。A.?

63、設A={a,b,c},B={1,2},作f:A→B,則不同的函數(shù)個864、設A={a,b},B={1,2},R1,R2,R3是A到B的二元關系,且R1={<a,2>,<b,2>},R2={<a,1<a,2>,<b,1>},R3={<a,1>,<b>則（）不是從A到B的函數(shù)．B．R265、設A、B是兩個任意集合,則A-B=（）．AB

66、設G是連通平面圖,v,e,r分別表示G的結點數(shù)、邊數(shù)和面數(shù)則v,e和r滿足關系式（）67、設G是歐拉圖,則G的奇數(shù)度數(shù)的結點數(shù)為（）個.A.O

68、設G是有8個結點的連通圖,結點的度數(shù)之和為28,則可從中刪去（）條邊后使之變成樹B.7

69、設G是有n個結點,m條邊的連通圖,必須刪去G才能確定G的一棵生成樹．答案：m-n+1

70、設G為連通無向圖,則（）時,G中存在歐拉回路.

A.G不存在奇數(shù)度數(shù)的結點2/11009試題庫（363）[筆試+71、設P:我將去打球,Q:我有時“我將去打球,僅當我有時間時”符號化為（）．答：P→Q

72、設個體域D={1,2},則謂詞公式(Vx)p(x)V(Зx)Q(x)量詞后的等值式為B.(P(1)AP(2))V(Q(1)VQ(2))

73、設個體域D={a,b,c},那么謂詞公式消去量詞后的等74、設個體域D是整數(shù)集合,則命題的真值是（）C.T

75、設個體域為集合{1,2,3,4}時,、B.對任一整數(shù)x存在整數(shù)y滿足x十y=576、設個體域為整數(shù)集,則公式77、設個體域為整數(shù)集,則78、設函數(shù)f:N→N,f(n)=n+1,下列表述正確的是（）．f是單射函數(shù)

79、設集合A={1,2,3,4,5,6B={1,2,3},A到B的關系R={<x,y>lxEA,yEB且x=y2則R=（）B.{<1，1>，<4，2>}

80、設集合A={1,2,3,4,5},偏序關系是A上的整除關系,則偏序集<A,>上的元素5是集合A的（）．極大元

81、設集合A={1,2,3,4,5}上的偏序關系的哈斯圖如圖所示,若的子集B={3,4,5},則元素3為B的（）．最小上界82、設集合A={1,2,3,4}上的二元關系

R={<1,1>,<2,2>,<2,3>,<4,4,S={<1,1>,<2,2>,<2,3>,<3,,<4,4>},則S是R的（）閉包．對稱

83、設集合A={1,2,3},B={3,5},C={5,6,7},則A∪B–C=（）{1,2,3,4}84、設集合A={1,2,3}上的函數(shù)分別為:

f={<1,2>，<2,1>，<3,3>}，g={<1,3>，<2,2>，<3,2>}，h={<1,3>，<2,1>，<3,1>}，則h=（）．答案是：f?g

85、設集合A={1,3,5,7,9},B={2,4,6},A到B的關系R={＜x,y>|∈A,y∈B,且x一y+1},則R=（）A.{<3,2>,<5,4>,<7,6>}86、設集合A={1,a},則P(A)=（）．{,{1},{a},{1,a}}

87、設集合A={2},B={3,4,5},A到B的關系R={<z,y>|x∈A,y∈且x=y+1},則R=（）.A.?88、設集合A={a},則A的冪集為（）．{，{a}}89、設連通平面圖G有v個結點,e條邊,r個面,則（）90、設命題公式G:G:┐p→(Q∧R),則使公式G取真值為1的P,Q,賦值分別是（）．答：1,0,091、設圖G=<V,E>,v∈V,則下列結論成立的是（）．92、設圖G的鄰接矩則G的邊數(shù)為（B．593、設無向圖G的鄰接矩陣為[01111，則G答案：7

94、設無向完全圖有K有n個結點(n≥2),m條邊,,中Kn存在歐拉回路。C.n為奇數(shù)

95、設有向圖(a)(b)(c)與(d)如圖一所示,則下列結論成立C.（c）僅為弱連通的

96、設有向圖(a)、(b)、(c)與(d)如圖六所示,則下列結論成立是（）．答d）只是弱連通的

97、設有向圖(a)、(b)、(c)與(d)如圖五所示,則下列結論成立是（）．答a）是強連通的

98、設有向圖(a)、(b)、(c)與(d)如圖一所示,則下列結論成立是（）．D．（d）是強連通的

99、圖G如圖三所示,以下說法正確的是（）．答案：{b,c}是點割集

100、圖G如圖四所示,以下說法正確的是3/

11009試題庫（363）[筆試+答案：{（a,d）,（b,d）}是邊割集

101、謂詞公式(?x)(A(x)→B(x)∨C(x,y))中的()。答：x是約束變元，y都是自由變元

102、無向簡單圖G是棵樹,當且僅當（）

A．G連通且邊數(shù)比結點數(shù)少1

103、無向樹T有5條邊,則T的結點數(shù)為（）C.6104、無向樹T有8個結點,則T的邊數(shù)為（）．答案：7105、無向圖G存在歐拉回路,當且僅當（）．

答案：G連通且所有結點的度數(shù)全為偶數(shù)

106、無向圖G的邊數(shù)是10,則圖G的結氓宵數(shù)之和為（）.答：B.20

107、無向圖G的邊數(shù)為12,則圖G的結點的度數(shù)之和是A.24108、無向圖G的鄰接矩陣為[01122]，則G答：5109、無向圖G是個棵樹,邊數(shù)為12,則G的結點數(shù)是（）A.9

110、無向圖G是棵樹,邊數(shù)是10,則G的結點度數(shù)之和是（）。A.20

111、無向圖G是棵樹,邊數(shù)是12,則G的結點度數(shù)之和是（）.C.24112、無向圖G是棵樹,邊數(shù)為10,則G的結點數(shù)是（）D.11113、無向圖G是棵樹,邊數(shù)為12,則G的結點數(shù)是（）D.13114、無向圖G是棵樹,結點數(shù)為10,則G的邊數(shù)是（）C.9115、無向圖G是樹,邊數(shù)是10,則G的結點度數(shù)之和是（）C.20116、無向完全圖K3的不同構的生成子圖的個數(shù)為（）（C）4117、無向完全圖K4是（）．答案：漢密爾頓圖118、下列等價公式成立的為（）．

答：P→(┐Q→P)＜＝＞┐P→(P→Q)119、下列等價公式成立的為（）．

答：┐P∧P＜＝＞┐Q∧Q120、下列公式（）為永真式。121、下列公式（）為重言式．

C．（P?（?Q?P?（?P?（P?Q））122、下列公式（）為重言式．

答：Q→(P∨(P∧Q))?Q→P123、下列公式成立的為（）．答：┐P∧(P∨Q)＝＞Q

124、下列公式成立的為（）。125、下列公式中（）為永真式．答：┐A∧┐B?┐(A∨B)126、下面的推理正確的是（）127、下面的推理正確的是（）.128、已知圖G的鄰接矩陣則G有（D．57邊）．129、已知無向圖G的結點度數(shù)之和為10,則G的邊數(shù)為（D.5130、已知無向圖G的鄰接矩陣為[01011]，則G有（）．答案：5點，7邊

131、已知無向圖G有10條邊,則G的結點度數(shù)之和為（）B.20

132、已知一棵無向樹T中有8個頂點,43度、2度的分支各一個,T的樹葉數(shù)為（）．答案：5133、以下結論正確的是（）．

答案：樹的每條邊都是割邊

134、元向圖G是棵樹,邊數(shù)為20,則G的結點數(shù)為（）.B.21

135、在圖G=<V,E>中,度數(shù)與邊數(shù)的關系是（）判斷(122)--

）1、(?x)P(x)ΛQ(y)→R(x)中量詞?的轄域為P(x)ΛQ(y).錯誤

2、(Vx)(P(x)Q(y))→R(x)中量詞v的?域為(P(x)AQ(y))(4/

11009試題庫（363）[筆試+3、(vx)(P(x)∧Q(y))→R(x)中量詞v的轄域為(P(x)∧Q(y)).對轄域為緊接量詞V(P(x)∧Q(y)).

4、邊數(shù)相等與度數(shù)相同的結點數(shù)相等是兩個圖同構的必要條件.(對5、不存在集合A與B,使得AEB與ACB同時成立.()錯

6、不存在集合A與B,使得A∈B錯7、不存在集合A與B,使得A∈B與A?B同時成立。

8、不存在集合A與B,使得A∈B與A~B同時成立．解：錯誤9、含有三個命題變項P,Q,R的命題公式P∧Q的主析取范式(P∧∧R)∨(P∧Q∧┐R)．對10、漢密爾頓圖一定是歐拉圖．錯

11、結點數(shù)v與邊數(shù)e滿足e=v的無向連通圖就是樹．錯12、結點數(shù)相等與邊數(shù)相等是兩個圖同構的必要條件.對

13、空集的冪集是空集。錯14、兩個圖同構的必要條件是結點數(shù)相等、邊數(shù)相等、度數(shù)相同的結點數(shù)相等對15、命題公式(PQ)P為永真式．解：正確因為，由真值表16、命題公式P→(Q∨P)的真值是T．對

17、命題公式┐(P→Q)的主析取范式是P∨┐Q．錯

18、命題公式┐P∧(P∨Q)=>Q成立．對

19、命題公式┐P∧(P→┐Q)∨P為永真式．對

20、命題公式┐P∧P的真值是T．錯

21、任一無向圖中,度數(shù)為奇數(shù)的結點的個數(shù)為偶數(shù)．()對

22、如果R1和R2是A上的自反關系,判斷結論:“R-11、R1∪R2R1∩R2是自反的”是否成立？并說明理由．答：成立因為任意 ，有所以 R-11R1∪R2、R1∩R2是自反的

23、如果R1和R2是A上的自反關系,則R1nR2是自反的.()對

24、如果R1和R2是A上的自反關系,則、R1∪R2、R1∩R2是自反的．對

25、如果圖G是無向圖,且其結點度數(shù)均為偶數(shù),則圖G存在一條歐拉回路．

答：錯誤如果圖G圖G是連通的，同時結點度數(shù)都是偶26、如圖二所示的圖G存在一條歐拉回路．解：正確．

因為圖G為連通的，且其中每個頂點的度數(shù)均為偶數(shù)，如果具體指出一條歐拉回路也同樣給分，

27、如圖九所示的圖G不是歐拉圖而是漢密爾頓圖．對

28、若集合A={1,2,3}上的二元關系R={<1,1>,<1,2>,<3,3>},R是對稱的關系．錯

29、若集合A={1,2,3}上的二元關系R={<1,1>,<2,2>,<1,2>},（1）R是自反的關系；（2）R是對稱的關答：（1）錯誤因為 ，所以R（2）錯誤因為 ，但是 ，所以R不是對稱的30、若集合A={1,2,3}上的二元關系R={<1,1>,<2,2>,<1,2>},則R是自反的關系．錯

31、若偏序集<A,R>的哈斯圖如圖二所示,則集合A的最大元為a極小元不存在．錯

32、若偏序集<A,R>的哈斯圖如圖一所示,則集合A的最大元為a最小元不存在．答：錯誤，集合A沒有最大元，也沒有最小元其中a是極大元33、若偏序集<A,R>的哈斯圖如圖一所示,則集合A的最大元為a最小元不存在．解：正確

對于集合A的任意元素x<x,a>?R（或xRa），所以a是集合A合A34、若圖G=<V,E>,其中

V={a,b,c,d},E={(a,b),(a,d(b,c),(b,d)},則該圖中的割邊為(b,c)．對

35、若圖G=<V,E>中具有一條漢密爾頓回路,則對于結點集V的個非空子集S,在G中刪除S中的所有結點得到的連通分支數(shù)為W,則S中結點數(shù)|S|與W滿足的關系式為W|S|．對

36、若圖G中存在漢密爾路,則圖G是一個漢密爾頓圖.5/

11009試題庫（363）[筆試+37、若圖G中存在歐拉路,則圖G是一個歐拉圖．()

B．錯誤

38、若為偏序集的最大元,則a一定不為偏序集的最小元39、若無向圖G的邊數(shù)比結點數(shù)少1,則G是樹。40、若無向圖G的結點數(shù)比邊數(shù)多1,則G是樹。錯誤41、設A={1,2,3},則R是等價關系.42、設A={1,2,3},R={<1,11,2>,<2,1>,<3,3>},則R是等價關系．錯

43、設A={1,2},B={a,b,c},則A×B的元素個數(shù)為8．()錯

44、設A={1,2},B={a,b,c},作f:A→B,則不同的函數(shù)個數(shù)為9.(對

45、設A={1,2},B={a,b,c},作f:A→B,則共有6個不同的函數(shù)。

()錯

46、設A={1,2}上的二元關系為R={<x,y>|xA,yA,x+y=10則R的自反閉包為{<1,1>,<2,2>}．對

47、設A={2,3},B={1,2},C={3,4},從A到B的函數(shù)

f={<2,2>,<3,1>},從B到C的函數(shù)g={<1,3>,<2,4>},則Dog°f)={2,3}．對

48、設A={a,b,c,d},R={<a,b>,<b,a>,<a,a>,<b,b>,<c,c>},則R是等價關系.答：錯誤。

R不是等價關系，因R中不含<d,d>，故不滿足自反性.49、設

A={a,b,c},R={<a,a>,<b,b>,,c>,<a,b>,<b,a>,<b,c>,<c,},則R是等價關系.答案：錯誤。

R不是等價關系，因R中包含<a，b>與<b，c><a，c>故不滿足傳遞性.

50、設A={a,b},B={1,2,3},則AxB的元素個數(shù)為6()對

51、設A={a,b},B={1,2},C={a,b},從A到B的函數(shù)

f={<a,1>,<b,2>},從B到C的函數(shù)g={<1,b>,<2,a>},則g°

f={<1,2>,<2,1>}．錯

52、設G=<V,E>是具有n個結點的簡單圖,若在G中每一對結點度

數(shù)之和小于n-1,則在G中存在一條漢密爾頓路．錯

53、設G是漢密爾頓圖,S是其結點集的一個子集,若S的元素個

數(shù)為4,則在G-S中的連通分支數(shù)不超過4。對

54、設G是具有n個結點m條邊k個面的連通平面圖,則有關系

式:n+k-2=m.()對

55、設G是具有n個結點m條邊k個面的連通平面圖,則有關系

式:n+k一m=2.()對

56、設G是具有扎個結點m條邊五個面的連通平面圖,則n-m-k.

對

57、設G是具有扎個結點m條邊五個面的連通平面圖,則n-m-k.

對

58、設G是一個連通平面圖,且有6個結點11條邊,則G有7個面．答案：正確

定理，連通平面圖G為v，邊數(shù)是e，面數(shù)為r，則歐拉

公式v-e+r=2成立所以r=2-v+e=2-6+11=7則G存在一條歐拉回路

59、設G是一個連通平面圖,且有6個結點11條邊,則G有7個面．對60、設G是一個圖,結點集合為V,邊集合為E,則答案：對

61、設G是一個無向圖,結點集合為v,邊集合為E,則G的結點度數(shù)之和為|E|.()錯

62、設G是一個有6個結點13條邊的連通圖,則G為平面圖.()

錯63、設G是一個有6個結點14條邊的連通圖,則G為平面圖．解：錯誤，不滿足“設G有v個結點e條邊的連通簡單平面圖，若v≥3，則e≤3v-6．”

64、設G是一個有7個結點16條邊的連通圖,則G為平面圖．錯65、設G是有8個結點的連通圖,結點的度數(shù)之和為28,則可從G中刪去6條邊后使之變成樹.()錯

66、設N、R分別為自然數(shù)集與實數(shù)集,f:N→R,f(x)=x+6,則f單射．()對

67、設P(x):x是人,Q(x):x去上課,那么命題“有人去上課．”為(?x)(P(x)→Q(x))．錯68、設P(x):x是人,Q(x):x學習努力,那么命題“所有的人都學習努力．”為(?x)(P(x)∧Q(x))．錯

69、設P:他生病了,Q:他出差了,R:我同意他不參加學習．那么果他生病或出差了,我就同意他不參加學習”符號化的結為(P∨Q)→┐R．錯

70、設P:我們下午2點去禮堂看電影,Q:我們下午2點去教室看書．那我們下午2點或者去禮堂看電影或者去教室看書符號化的結果為P∨Q．錯

71、設P:小王來學校,Q:他會參加比賽．那么命題“如果小王來學校,則他會參加比賽”符號化的結果為P→Q．對

72、設P:昨天下雨,Q:今天下雨．那天下雨,今天仍下雨”符號化的結果為P∧Q．對

73、設R是集合A上的等價關系,且1,2,3是A中的元素,則R中至少包含<1,1>,<2,2>,<3,3>等元素．對

74、設個體域D={1,2,3,4},A(x)為“x大于5”,則謂詞公式(?x)A(的真值為T．錯

75、設個體域D={1,2,3,4},A(x)為“x等于3”,則謂詞公式(x)A(x的真值為F錯

76、設個體域D={1,2,3},A(x)為“x小于3”,則謂詞公式(?x)A(x的真值為T．對

77、設個體域D={1,2,3},則謂詞公式(Vx)A(x)消去量詞后的等式為A(1)∧A(2)∧A(3).()對

78、設個體域D={1,2},則謂詞公式(?x)P(x)∨(?x)Q(x)量后的等值式為(P(1)∧P(2))∨(Q(1)∨Q(2)).()對

79、設個體域D={1,2},則謂詞公式(Vx)P(x)v(3x)Q(x)消去量詞后的等值式為(P(1)AP(2))v(Q(1)vQ(2))()對

80、設個體域D={a,b,c},則謂詞公式錯

81、設個體域D={a,b},那么謂詞公式(?x)A(x)∨(?y)B(y)消去詞后的等值式為A(a)∨B(b)．錯

82、設個體域D={a,b},則謂詞公式(?x)(A(x)∧B(x))消去量詞的等值式為(A(a)∧B(a))∧(b)∧B(b))．對

83、設集合A={0,1,2,3},B=,3,4,5},R是A到B的二元關系,

則R的有序對集合為{<2,2>,<2,3>,<3,2>,<3,3>}．對

84、設集合A={1,2,3,4},B={2,4,6,8},判斷下列關系f是否構函數(shù)f:,并說明理由．（1）f={<1,4>,<2,2,>,<4,6>,<1,8>}；

（2）f={<1,6>,<3,4>,<2,2；

（3）f={<1,8>,<2,6>,<3,4>,<4,2,>}．

1）不構成函數(shù)因為，但沒有定義，所以不構成函數(shù)

（2）不構成函數(shù)因為，但沒有定義，所以不構成函數(shù)

（3）滿足。因為任意，都有且結果唯一。

85、設集合A={1,2,3,4},B=,4,6,8},下列關系

f={<1,4>,<2,2,>,<4,6>,<1,可以構成函數(shù)f:．錯

86、設集合A={1,2,3,4},B=,4,6,8},下列關系

f={<1,8>,<2,6>,<3,4>,<4,2可以構成函數(shù)f:．()對

87、設集合A={1,2,3,4},B={8,12},A到B的二元關系R=那么R－1={<6,3>,<8,4>}．對6/11009試題庫（363）[筆試+88、設集合A={1,2,3},B={1},則A×

B={<1,1>,<1,2>,<2,1>,<2,2<3,1>,<3,2>}．對

89、設集合A={1,2,3},B={1},則

P(A)-P(B)={{3},{1,3},{2,3{1,2,3}}．對

90、設集合A={1,2,3},B={2,4},C={3,4,5},則A∩

(C-B)={1,2,3,5}．錯

91、設集合A={1,2},B={2,3C={3,4},則AUB-C={1,2}。對

92、設集合A={1,2},B={2,3C={3,4},則AUB-C={1,3}。錯

93、設集合A={1,2},B={a,b},則A×B的元素個數(shù)為6.對

94、設集合A={2},B={3,4,5A到B的關系R=(<r,y>xEA,yEB且r=y+1),則R=()對95、設集合A={a,b,c,d},A上的二元關系

R={<a,a>,<b,b>,<b,c>,<c,d若在R中再增加兩個元素

<c,b>,<d,c>,則新得到的關系就具有反自反性質．錯

96、設集合A={a,b,c,d},A上的二元關系

R={<a,b>,<b,a>,<b,c>,<c,d>},則R具有反自反性質．對

97、設集合A={a,b,c},B={1,3},作f:A→B,則不同的函數(shù)個數(shù)為9錯

98、設集合A={a,b,c},R={<a,a>,<b,b>,<c,c>,<b,a>},則R是價關系.B.錯99、設集合A={a,b},B={1,2C={4,5},從A到B的函數(shù)f={<a,1>,<b,2>},從B到C的函數(shù)g={<1,5>,<2,4>},則gof={<a,5>,<b,4>}.對

100、設集合A={a,b},B={1,2},C={4,5},從A到B的函數(shù)f={,1>,<b,2>},人B到C數(shù)g=(<1,5>,<2,4>),則

gof=(<a,5>,<6,4>)()對

101、設集合A={a,b},B={1,2},C={a,b},從A到B的函數(shù)f=｛<a,1>,<b,2>},從B到C的函數(shù)g={<1,b>,<2,a>},則g0f={<1,2>,<2,l>}.()B．錯誤

102、設連通平面圖G的結點數(shù)為5,邊數(shù)為6,則面數(shù)為4．錯

103、設圖G如圖七所示,則圖G的點割集是{f}．錯

104、設圖G是有5個結點的連通圖,結點度數(shù)總和為10,則可從G中刪去6條邊后使之變成樹．錯

105、設圖G是有6個結點的連通圖,結點的總度數(shù)為18,則可從G中刪去4條邊后使之變成樹．對

106、設完全圖K有n個結點(n2),m條邊,當n為奇數(shù)時,Kn中存在歐拉回路．對107、完全圖K4不是平面圖.錯

完全圖K4如K.可以如下圖示嵌入平面.108、完全圖K4是平面圖.109、完全圖K5是平面圖.110、謂詞公118、下面的推理是否正確,試予119、下面的()(1)(?x)A(x)→B(x)前提引入(2)A(→B(y)US(1)錯

120、已知圖G中有1個1度結點,2個2度結點,3個3度結點,4個4度結點,則G的邊數(shù)是15．對

121、有6個結點的無向完全圖K,的邊數(shù)為30.錯

122、有n個結點的無向完全圖民的邊數(shù)為n(n-1).()錯

計算題(60)--）

1、畫一棵帶權為1,2,2,3,6的最優(yōu)二叉樹,計算它...2、求(PVQ)VR的析取范式與主合取范式．...

3、求(PVQ)→R的析取范式與合取范式....

4、求(PVQ)→R的析取范式與合取范式....

5、求(P∧Q)→(R∨S)的分析范式,合取范式。...

6、求(P∨Q)→(R∨Q)的析取范式,合取范式．...

7、求(P∨Q)→R的析取范式與主合取范式....

8、求P∨(Q∧R)的合取范式與主合取范式....

9、求P→(Q∧R)的合取范式與主合取范式....

10、求P→(Q∧R)的合取范式與主析取范式....

11、求出如圖一所示賦權圖中的最小生成樹(要求...

12、求命題公式(PQ)(RQ)的主析取范式、主合取范...13、設A={0,1,2,3,4,5,6},R={<x,y>|x∈A,Y∈A且...

14、設A={1,2,3,4,5},R={<x,y>|x∈A,y∈A且x-y=...

15、設A={1,2,3,4,5}，R={<x,y>|x∈A,y∈A且x-y=3...

16、設A={1,2,3,4},R={<x,y>｜x∈A,y∈A且x-y=2},...

17、設A={1,2,3},R={<x,y>|x∈A,y∈A且x+y=4},5...

18、設A={2,3,6,24,36},B為A的子集,其中B={6,12...

19、設G=<V,E>,V=(v1,v2,v3,v4,v5),E={(v1,v3),...

20、設G=<V,E>,V={v1,v2,v3,v4},E={(v1,v2),(v1...

21、設G=<V,E>,V=（v1,v2,v3,v4,v5）,E={(v1,v3）,（v1,...111、謂詞公式(Vr)(P(z)AQ(y))→R(x)中量詞V的轄域為

(P(x)AQ(y))→R(x).()錯

112、謂詞公式┐(?x)P(x)(x)┐P(x)成立．對

113、謂詞命題公式(?x)((A(x)∧B(x))∨C(y))中的自由變元為

x．錯

114、謂詞命題公式(?x)(P(x)→Q(x)∨R(x,y))中的約束變元為

x．對

115、無向圖G存在歐拉回路,當且僅當G連通且結點度數(shù)都是數(shù)．對116、無向圖G的結點數(shù)比邊數(shù)多1,則G是樹.117、無向圖G是樹當且僅當無向圖G是連通圖.7/11009試題庫（363）[筆試+22、設關系R的關系圖如下,試

23、設關系R的關系圖如下,試

24、設集合A={1,2,3,4},R=x,y>|x,yA;|xy|=1或...25、設集合A={1,2,3,4}上的關系:26、設集合A={1,2,3}

27、設集合A={1,2,3},A上的關系R={<x,y>lxEA,yE...28、設集合A={1,2,3},B={2,4},C={2,{3}},試計...

29、設集合A={1,2,3},B=｛2,{3}},C={{3},4},試計...30、設集合A={1,2,3},R={<1>,<2,1>,<3,1>},S=...

31、設集合A={2,3,6,12,246},B為A的子集,其中...32、設集合A={a,b,c,d},B=,b},試計算,

33、設集合A={a,b,c},B={{,b),試計算(1)AUB;(...

34、設集合A={a,,c},B=a},c}試計算:

35、設集合A={{1},1},B={{},試計算

36、設集合A={{a},a,b},B=,},試計算(1)AΛ...

37、設偏序集<A,R>的哈斯圖如圖一所示,B為A的子...38、設偏序集<A,R>的哈斯圖如下,B為A的子集,其...

39、設偏序集<A,R>的哈斯圖如下,B為A的子集,其...

40、設圖G=<V,E>,41、設圖G=<V,E>,V=

42、設圖G=<V,E>,V={v1,v2,v3,v4,v5},E={(v1,v2...43、設圖G=<V,E>,V={V1,V2,V3,V4},E={(V1,V2),(...44、設圖G=<V,E>,其中,結點集V={a,b,c,d,e),邊...

45、設圖G=<V,E>,其中V=(a,b,c,d,e),E=((a,b),(...46、設圖G=<V,E>,其中V={a,b,c,d,e},E={(a,b),(...47、設圖G=<V,E>,其中V={a,b,c,d},

48、設圖G=<V,E>,其中V={a,b,c,d},E={(a,b),(a,...49、設圖G=<V,E>,其中V={a,b,c,d},E={(a,b),(a,...50、設圖G=<V,E>,V=[V1,V2,V3,V4,V5),E={(v1,v2...51、設謂詞公式

52、設謂詞公式(x)(A(x,y)A(Vz)B(x,y,z))A(Vy)C...

53、設謂詞公式,54、設有如圖一所示的有向圖

55、試畫一棵帶權為1,2,3,3,4的最優(yōu)二叉樹,并計...

56、試畫一棵帶權為2,3,3,4,5,的最優(yōu)二叉樹,并...

57、試利用Kruskal算法(避圈法)求出如下所示賦...

58、試利用Kruskal算法求出如下所示賦權圖中的...

59、試求出如圖一所示賦權圖中的最小生成樹(要...

60、試求出如下所示賦權圖中的最小生成樹(要求...

1、畫一棵帶權為1,2,2,3,6的最優(yōu)二叉樹,計算它們的權.答案：2、求(PVQ)VR的析取范式與主合3、求(PVQ)→R的析取范式與合取范式.4、求(PVQ)→R的析取范式與合取范式.解：5、求(P∧Q)→(R∨S)的分析范式,合取范式答案：6、求(P∨Q)→(R∨Q)的析取范式,合取范式7、求(P∨Q)→R的析取范式與主合取范式.答案：8、求P∨(Q∧R)的合取范式與主合取范式.9、求P→(Q∧R)的合取范式與主合取范式.答案：8/

11009試題庫（363）[筆試+10、求P→(Q∧R)的合取范式與主析取范式.11、求出如圖一所示賦權圖中的最小生成樹(要求寫出求解步驟)并求此最小生成樹的權．12、求命題公式(PQ)(RQ)的主析取范式、主合取范式．解：13、設A={0,1,2,3,4,5,6},R={<x,y>|x∈A,Y∈A且x+y<1}14、設A={1,2,3,4,5},R={<x,y>|x∈A,y∈Ax-y=3},S={<x,y>|x∈A且x+y=3}試求 答案：15、設A={1,2,3,4,5}，R={|x∈A,y∈A且x-y=3}，S={|x∈A,∈A且x+y=3}試求R,S*R-S,r(S).9/

11009試題庫（363）[筆試+16、設A={1,2,3,4},R={<x,y>｜x∈A,y∈A且x-y=2},S={<x,y>

x∈A,y∈A且x+y=3},試求R,S,R.S,r(S).17、設A={1,2,3},R={<x,y>|x∈A,y∈A且x+y=4},5={<x,y>|xA,y∈A且x=y},試求R,S,R-1,r(S).18、設A={2,3,6,24,36},B為A的子集,其中B={6,12},R是A的整除關系,試:(1)寫出R的關系表達式;（2）說明R為偏差關系表達式；（3）畫出關系R的哈斯圖；

（4）求出B的最大元素、極大元素、上確界。19、設

G=<V,E>,V=(v1,v2,v3,v4,v5E={(v1,v3),(v1,v5),(v2,v3(3,v4),(v4,v5)},試:（1）給出G的圖形表示；（2）求出每個結點的度數(shù)；（3）畫出其補圖的圖形。解：20、設

G=<V,E>,V={v1,v2,v3,v4},E(v1,v2),(v1,v3),(v1,v4),(,v3),(v3,v2)},試

(1)給出G;(2);(3)數(shù);(4)畫出其補圖的圖形.

答：(1)給出G;(2)(3)deg(v1)=3,deg(v2)=2,deg(v3)=3,deg(v4)=2,

(4)10/

11009試題庫（363）[筆試+21、設G=<V,E>,V=（v1,v2,v3,v4,v5）,E={(v1,v3,（v1,v5）（v2,v3）,（v2,v5）,（v3,v）}，試：

（1）給出G的圖形表示；（2）寫出其鄰接矩陣；（3）求出每個結點的度數(shù)；（4）畫出其補圖的圖形.1）G的圖形表示如圖二所示：（422、設關系R的關系圖如下,23、設關系R的關系圖如下,(1)寫出R;

(2)判斷R.解：(2)不是等價關系因為該關系不滿足自反性注:答"不滿足傳遞性".

24、設集合A={1,2,3,4},R=x,y>|x,yA;|xy|=1或xy=0},試（1）寫出R的有序對表示；（2）畫出R的關系圖；

（3）說明R滿足自反性，不滿足傳遞性．解:

（ 1 R={<1,1>,<2,2>,<3,3>,<4,4>,<1,2>,<2,1>,<2,3>,<3,2>,<3,4,<4,3>}（3分）25、設集合A={1,2,3,4}上的關系26、設集合A={1,2,3試計算:27、設集合A={1,2,3},A上的關系R={<x,y>lxEA,yEAx+y>4),S={<x,y>|xEA,yEA且x<y),試求R,S,R-1,s(S).13.R={<2,3>,<3,2>,<3,3>)S={<1,2>,<1,3>,<2,3>)R1=(<2,3>,3,2>,<3,3>)11/

11009試題庫（363）[筆試+5(S)={<1,2>,<1,3>,<2,3>,<2,1>,<31>,<3,2>)

28、設集合A={1,2,3},B={2,4},C={2,{3}},試計算:29、設集合A={1,2,3},B=｛2,{3}},C={{3},4},試計算:(1)B∪C;B∪C={2,{3},4};(2)A一B;A一B={1,3};(3A一B)×C.(A一B)×C=｛<1,{3}>,<l,4>,<3,{3}>,<3,4>}

30、設集合A={1,2,3},R={<1,1>,<2,1>,<3,1>},S={<1,2>,,2>試計算31、設集合A={2,3,6,12,24,36},B為A的子集,其中B={6,},是A上的整除關系,試:(1）寫出R的關系表達式；

集合A=｛2,3,6,12,24,36系R為：

R={<2,2>,<3,3>,<6,6>,<12,12>,<24,24>,<36,36>,<2,6>,

<3,6>,<2,12>,<3,12>,<6,12>,<2,24>,<3,24>,<6,24>,<12,24>,<2,36>,<3,36>,<6,36>,<12,36>}.(2）畫出關系R的哈斯圖；關系R的哈斯圖如圖一所示：(3）求出B的最大元、極大元、最小上界．

集合B的最大元為12為12、最小上界為1232、設集合A={a,b,c,d},B=,b},試計算,

(1)AUB;(2)A-B;(3)A×B.答案：(1)AUB={a,b,c,d}(2)A-B={c,d};(3)A×B={<a,a>，

<a,b>,<b,a>,<b,b>,<c,a>,<c,b>,<d,a>,<d,b>}

33、設集合A={a,b,c},B={{,b),試計算

(1)AUB;(2)A-B;(3)AXB.解：（1）A∪B={a,b,c,{c}}；（2）A-B={a,c}；

（3）A×B={<a,{c}>,<a,b>,<b,{c}>,<b,b>,<c,{c}>,<c,b

34、設集合A={a,,c},B=a},c}試計算:35、設集合A={{1},1},B={{},36、設集合A={{a},a,b},B=,},試計算(1)AB:(2)AUB:(3)A-(AnB)37、設偏序集<A,R>的哈斯圖如圖一所示,B為A的子集,其B={a,b,c},試:（1）寫出R的關系表達式；

（2）畫出關系R的關系圖；

（3）求出B解：(2)（3）集合B為m最小上界為d.

38、設偏序集<A,R>的哈斯圖如下,B為A的子集,其中B=(b,c),

試寫出R的關系表達式;(2)畫出關系R的關系圖;(3)求出B的大元、極大元、上界,12/

11009試題庫（363）[筆試+39、設偏序集<A,R>的哈斯圖如下,B為A的子集,其中B={b,c試40、設圖G=<V,E>(1)畫出G;(2)寫出其鄰接矩陣;(3}的度數(shù);(4)畫出圖G.41、設圖G=<V,E>,(1)畫出G;

(2);

(3);(4)圖G解：(1)關系圖13/

11009試題庫（363）[筆試+(2)(4)42、設圖G=<V,E>,V={v1,v2,v3,v4,v5E={(v1,v2),(v1,v3),(v2,v3(2,v4),(v3,v4),(v3,v5),(v45)},試(1)畫出G的圖形表示；(2)求出每個結點的度數(shù)；（3)畫出圖G的補圖的圖形．43、設圖G=<V,E>,V={V1,V2,V3,V4},E(V1,V2),(V1,V4),(V2,V4)},（1）畫出G的圖形表示；（2）寫出其鄰接矩陣；（3）求出每個結點的度數(shù)；（4）畫出圖G的補圖的圖形．解：(1)(2)44、設圖G=<V,E>,其中,結點集V={a,b,c,d,e),邊集

E={(a,c),(a,e),(b,d),(b,(c,e),(d,e)),對應邊的權值依次為2、3、3、4、1及5,試:(1)畫出G的圖形;(2)求出G權最小生成樹及其權值.14/

11009試題庫（363）[筆試+45、設圖G=<V,E>,其中

V=(a,b,c,d,e),E=((a,b),(a),(a,e),(b,d),(b,e),(c,d)ce),(d,e)),對應邊的權值依次為2、1、2、3、6、4、1及5,試:（1）畫出G的圖形；（2）求出G權最小的生成樹及其權值．1）G的圖形如圖三所示：最小生成樹的權C（T）=1+1+2+3=7.46、設圖G=<V,E>,其中

V={a,b,c,d,e},E={(a,b),(a),(a,e),(b,d),(b,e),(c,e)cd),(d,e)},對應邊的權值依次為2、1、2、3、6、1、4及5,試（1）畫出G的圖形；（2）寫出G的鄰接矩陣；

（3）求出G權最小的生成樹及其權值．解：（1）G的圖形表示為：（2（3權為7：47、設圖G=<V,E>,其中V={a,b,c,d}15/

11009試題庫（363）[筆試+48、設圖G=<V,E>,其中

V={a,b,c,d},E={(a,b),(a,c(a,d),(b,c),(c,d)},對應邊的權值依次為6、5、2、3及8,試(1)畫出G的圖形；(2)寫出G的鄰接矩陣；(3)求出G.解：(1)G的圖形表示如圖一所示：(2)(3)權值為10.49、設圖G=<V,E>,其中

V={a,b,c,d},E={(a,b),(a,cα,d),(b,c),(b,d),(c,d)對應邊的權值依次為2、34、5、6及7，試

（1）畫出G的圖形；（2）寫出G的鄰接矩陣；

（3）求出G.解：（1）G:（2）鄰接矩陣（3權值為9.50、設圖G=,V=[V1,V2,V3,V4,V5),E={1,v2),(V1,V3),(v1,V5),(V23,(V3,V4),(V3,V5),(v4,v5)],試(1）畫出G關系圖如圖二所示：(2(2)deg(v1)=3deg(v2)=4deg(v3)=4

deg(v4)=3

deg(v5)=4

(3）畫出圖G51、設謂詞公52、設謂詞公式(x)(A(x,y)A(Vz)B(x,y,z))A(Vy)C(y,z),試:(1寫出量詞的轄域;(2)指出該公式的自由變元和約束變元16/

11009試題庫（363）[筆試+53、設謂詞公式54、設有如圖一所示的55、試畫一棵帶權為1,2,3,3,4的最優(yōu)二叉樹,并計算該最優(yōu)二樹的權.56、試畫一棵帶權為2,3,3,4,5,的最優(yōu)二叉樹,并計算該叉樹的權．解：最優(yōu)二叉樹如圖二所示．57、試利用Kruskal算法(避圈法)求出如下所示賦權圖中的生成樹(要求寫出求w解步驟),并求此最小生成樹的權.17/

11009試題庫（363）[筆試+58、試利用Kruskal算法求出如下所示賦權圖中的最小生成樹(求寫出求解步驟),并求此最小生成樹的權.答：用Kruskal:w(v1，v7)=1選e1=v1v7w(v7，v4)=1選e2=v7v4w(v1，v6)=2選e3=v1v6w(v3，v4)=3選e4=v3v4w(v2，v7)=4選e5=v2v7w(v5，v7)=5選e6=v5v7最小生成樹如圖三所示:最小生成樹的權W(T)=1+1+2+3+4+5=16.

說明:用其他方法，結果正確參照給分.

59、試求出如圖一所示賦權圖中的最小生成樹(要求寫出求驟),并求此最小生成樹的權.60、試求出如下所示賦權圖中的最小生成樹(要求寫出求解步驟)并求此最小生成樹的權.18/

11009試題庫（363）[筆試+邏輯公式翻譯(46)--）

1、將語句"51次列車每天上午10點發(fā)車或者11點...2、將語句“3大于2或1加1等于2"翻譯成命題公式...

3、將語句“41次列車下午五點開或者六點開。”...

4、將語句“a是偶數(shù)當且僅當a能被2整除?！狈?..

5、將語句“A選項是蘋果，B選項是桃子?！狈g成...

6、將語句“A選項是汽車，B選項是大樹?！狈g成...

7、將語句“除非小王來，否則小李不去?！狈g成...

8、將語句“當大家都進人教室后，討論會開始進行...

9、將語句“地球是圓的，太陽也是圓的?！狈g成...

10、將語句“今天沒有下雪?！狈g成命題公式。...

11、將語句“前天下雨，昨天還是下雨。”翻譯成命...

12、將語句“如果今天是周三，則昨天是周二?！狈?..

13、將語句“如果今天天晴，則后天上課?！狈瓭沙?..

14、將語句“如果今天下雨，那么明天的比賽就要延...

15、將語句“如果明天天晴，則我們?nèi)ソ加?，”翻譯成...

16、將語句“如果明天下雪，我們就去旅游?！狈g...

17、將語句“如果明天下雨，我們就放假。”翻譯成...

18、將語句“如果明天下雨，我們就去圖書館?！狈?..

19、將語句“如果所有人今天都去參加活動，則明天...

20、將語句“如果他接受了這個任務，他一定能完成...

21、將語句“如果他掌握了計算機的用法，那么他就...

22、將語句“如果他掌握了計算機的用法，那么他就...

23、將語句“如果小王來學校，則他會參加比賽．”翻...

24、將語句“若不下雨，我們就去參加比賽?！狈g...

25、將語句“所有的人都學習努力．”翻譯成命題公...

26、將語句“他不去學校．”翻譯成命題公式．...

27、將語句“他們明天去旅游，僅當明天天晴?！狈?..

28、將語句“他去旅游，僅當他有時間．”翻譯成命題...

29、將語句“他上午去教室上課，下午去體育館參加...

30、將語句“我會唱歌，并且會跳舞?！狈g成命題...

31、將語句“我會英語，并且會德語?！狈g成命題...

32、將語句“我會英語，并且會德語。”翻譯成命題...

33、將語句“我們下午2點或者去禮堂看電影或者...

34、將語句“我學英語，并且學法語?！狈g成命題...

35、將語句“小明是個學生?！狈g成命題公式...

36、將語句“小明是學生，小張是飛行員。”翻譯成...

37、將語句“小王今天上午或者去看電影或者去打...

38、將語句“小王是個學生，小李是個職員，而小張是...

39、將語句“小張和小李都可以完成這項工作”翻...

40、將語句“小張學習努力，小王取得好成績．”翻譯...

4