離散考試復(fù)習(xí)題 180題.doc

第一部分：數(shù)理邏輯1 下列語句是命題的是( ）：A.15能被3整除，3是偶數(shù)嗎？ B.明年5月1日是晴天C.2X+30 D.我在說謊. 2下列敘述中有( ）個(gè)命題(1)離散數(shù)學(xué)是計(jì)算機(jī)科學(xué)系的一門必修課 (2) 地球外的星球上也有人 (3) 我正在說謊. (4)請(qǐng)不要吸煙 A.1個(gè) B.2個(gè) C. 3個(gè) D. 4個(gè) 3 下列語句中不是命題的只有（ ）A這個(gè)語句是假的。B1+1=1.0C飛碟來自地球外的星球。D凡石頭都可練成金。4 設(shè)p：我很累，q：我去學(xué)習(xí)，命題：“除非我很累，否則我就去學(xué)習(xí)”的符號(hào)化正確的是ApqBpqCpqDpq5 令p：今天下雪了，q：路滑，則命題“雖然今天下雪了，但是路不滑”可符號(hào)化為（ ）A. pq BpqC. pq Dpq 6使用邏輯連接詞將下列復(fù)合命題符合化：（1） 如果天不下雪且我有時(shí)間，我就進(jìn)城；（2） 我進(jìn)城的必要條件是我有時(shí)間；（3） 天不下雪或我不進(jìn)城；（4） 我進(jìn)城當(dāng)且僅當(dāng)我有時(shí)間且天不下雪。7判斷下面一段論述是否為真：“是無理數(shù)。并且，如果3是無理數(shù)，則也是無理數(shù)。另外6能被2整除，6才能被4整除?！?1. 將下列命題符號(hào)化 (1)2或3是素?cái)?shù). (2)4或6是素?cái)?shù). (3)小元元只能拿一個(gè)蘋果或一個(gè)梨.(4)王曉紅生于1975年或1976年. 8命題公式q(pq)的成真賦值是 9命題公式p(p(q(qr)的成假賦值是 10 命題公式(p(qr)(p(qr)的成真賦值是 11 命題公式p(p(qr)的成假賦值是 12.下列命題公式中是重言式的為（ ）A. B. C. D. 13 命題公式“”，是_。（永真式、非永真式的可滿足式、矛盾式）14.命題公式“”，是_。（永真式、非永真式的可滿足式、矛盾式）15.命題公式“”，是（ ）A.永真式 B. 非永真式的可滿足式C.矛盾式 D. 不確定 16. 下列為永假式的是（ ）。A、 B、 C、 D、17. 設(shè)P，Q 的真值為0，R，S的真值為1，則的真值= 。18. 全體小項(xiàng)合取式為（ ）。A、可滿足式； B、永假式； C、永真式； D、A，B，C 都可能。19. 全體大項(xiàng)析取式為（ ）。A、可滿足式； B、永假式； C、永真式； D、A，B，C 都可能。20. 設(shè)命題公式，則公式G的主合取范式是_。21. 命題公式G= (P Q) (P Q) ，則其主合取范式為 。22. 已知命題公式含有三個(gè)命題變?cè)?，且其主析取范式為，則其主合取范式為( )。A、 B、 C、 D、 23. 證明下列恒等式：(1) (2) 24. 證明下列恒等式：(1) (2) 25.設(shè)公式A含命題變項(xiàng)，又已知A的主合取范式為,則A的主析取范式為 。 26.設(shè)公式A含命題變項(xiàng)，又已知A的主析取范式為,則A的主合取范式為 。27 一個(gè)命題公式A(P,Q,R)的成真指派為000，001，010，100，110，則其主析取范式為 .28 一個(gè)命題公式A(P,Q,R)的成假指派為000，001，010，100，110，則其主合取范式為 . 29在自然推理系統(tǒng)P中構(gòu)造下面推理的證明：前提：qp,qs,st,tr結(jié)論：pq30 構(gòu)造下面命題推理的證明如果我學(xué)習(xí)，那么我數(shù)學(xué)不會(huì)不及格；如果我不熱衷于玩游戲機(jī)，那么我將學(xué)習(xí)；但我數(shù)學(xué)不及格，因此我熱衷與玩游戲機(jī)。31 在自然推理系統(tǒng)中構(gòu)造下面推理的證明： 若數(shù)a 是實(shí)數(shù)，則它不是有理數(shù)就是無理數(shù)。若a 不能表示成分?jǐn)?shù)，則它不是有理數(shù)。a 是實(shí)數(shù)且它不能表示成分?jǐn)?shù)。所以a 是無理數(shù)。32證明下面推理： 前提： 結(jié)論: 33證明下面推理：前提： 結(jié)論: 34已知今天下雨或刮風(fēng)；如果今天下雨，那么我在家看書；如果今天刮風(fēng)，那么我去放風(fēng)箏；今天我沒有在家看書。所以今天刮風(fēng)并且我去放風(fēng)箏了。35 在自然推理系統(tǒng)中用歸謬法證明下面各推理：前提：pq,rq,rs結(jié)論：p36. 將命題“沒有人登上過木星” 用謂詞符合化 37.將命題“在美國(guó)留學(xué)的學(xué)生未必都是亞洲人” 用謂詞符合化 38.將命題“兔子比烏龜跑的快” 用謂詞符合化 39.將命題“有的兔子比所有的烏龜跑的快” 用謂詞符合化 答案：，其中，40.將命題“并不是所有的兔子都比烏龜跑的快” 用謂詞符合化 41 用謂詞公式將下列語句形式化： （1）發(fā)亮的東西不都是金子。 （2）不是所有的男人都至少比一個(gè)女人高，但至少有一個(gè)男人比所有的女人高。42論域D=1，2，指定謂詞PP (1,1)P (1,2)P (2,1)P (2,2)TTFF則公式真值為 。43 表達(dá)式中$x的轄域是( ) A B C D44 設(shè)謂詞的定義域是a,b,c,試將表達(dá)式R（x）S(x)中的量詞消除，寫成與之等價(jià)的命題公式答案: ( R(a) R(b) R(c) ( S(a) S(b) S(c)45 設(shè)謂詞的定義域是a,b,c,試將表達(dá)式中的量詞消除，寫成與之等價(jià)的命題公式 46 將（P(x) R(x,y)）Q(x,y)中的變量換名或替代，使其不含既是約束出現(xiàn)又是自由出現(xiàn)的個(gè)體變量 47將(P(x) (R(x) Q(x) R(x) 中的變量換名或替代，使其不含既是約束出現(xiàn)又是自由出現(xiàn)的個(gè)體變量 48 設(shè)B不含有x，等值于()A. B. C. D.49下列四個(gè)公式正確的是 A. B. C. D.50 量詞否定等值式 _。答案: 51. 謂詞合式公式的前束范式為 。52. 給出下面公式的前束合取范式。53 求的前束范式。54試將（ P(x，y) （Q(z) R(x)）化成等價(jià)的前束范式。55 試將(（P（x,y,z）Q(x,u)）Q(y,v)化成等價(jià)的前束范式56.構(gòu)造下面推理的證明 前提：，結(jié)論：57 前提： 結(jié)論: 58 構(gòu)造下面推理的證明:前提: ,結(jié)論: xR(x)59 構(gòu)造下面推理的證明 不存在能表示成分?jǐn)?shù)的無理數(shù)。有理數(shù)都能表示成分?jǐn)?shù)。因此，有理數(shù)都不是無理數(shù)。60 構(gòu)造下面推理的證明 人都喜歡吃蔬菜。但不是所有的人都喜歡吃魚。所以，存在喜歡吃蔬菜而不喜歡吃魚的人。61. 設(shè)A(x):x能被3整除；B(x):x能被6整除；個(gè)體域?yàn)椋?,2,6,7,12。則下列各式真值為F的是( )。A、 B、 C、 D、 第二部分：集合論1. 下列關(guān)于集合的表示中，正確的是（ ）。A、； B、；C、； D、。2. 下列關(guān)于集合的表示中，正確的是（ ）。A、 B、 C、 D、 3 集合A=1,2,3,4,B=a,b,c,則下列敘述正確的是（ ）A. 1A B. cBC. 2A D. a，b，cB4 集合A=1,2,3,4,B=a,b,c,則不正確的是（ ）A. 1，2，4A B. 2，3 C. D. 2A5 集合a，b的冪集是 設(shè)集合A=，則其冪集=_答案: 6 設(shè)S,T,M是集合，下列結(jié)論正確的是（ ）A如果ST=SM，則T=M B如果S-T=，則S=TC D7 設(shè)A,B,C是三個(gè)非空集合,則( )是正確的. A. B. C. D. 8 以下敘述正確的是（ ）A. 若,則AB=B B. 若aA,則aAB C. 若aAB,則aA D. 若,則AB=A9 設(shè)A，B，C為三個(gè)任意集合，試證明（1）若AA=BB，則A=B；（2）若AB=AC，且A,則B=C.10 設(shè)A,B,C是任意集合，證明(1)(A-B)-C=A- BC(2)(A-B)-C=(A-C)-(B-C)11若集合A的元素個(gè)數(shù)為10，則其冪集的元素個(gè)數(shù)為（ ） A1024 B10 C100 D112 已知A,B是集合A=15，B=10，AB=20，則AB=（ ）A10 B5 C20 D1313 對(duì)100學(xué)生的調(diào)查表明，有32人學(xué)日語，20人學(xué)法語，45人學(xué)英語7人既學(xué)日語又學(xué)法語，15人既學(xué)日語又學(xué)英語，10人既學(xué)法語又學(xué)英語30人不學(xué)這三門語言中的任何一種求(1) 3門語言都學(xué)的學(xué)生人數(shù)；(2) 只學(xué)日語，只學(xué)法語，只學(xué)英語的學(xué)生人數(shù)；(3) 至少學(xué)習(xí)兩門語言的學(xué)生人數(shù)14 某班有25個(gè)學(xué)生，其中14人會(huì)打籃球，12人會(huì)打排球，6人會(huì)打籃球和排球，5人會(huì)打籃球和網(wǎng)球，還有2人會(huì)打這三種球。已知6個(gè)會(huì)打網(wǎng)球的人都會(huì)打籃球或排球。求不會(huì)打球的人數(shù)。15、設(shè)，求 16、設(shè)A和B為有限集，|A|=m，|B|=n，則有 個(gè)從A到B的關(guān)系。17、設(shè)A為有限集，且|A|=m，則有 個(gè)從A上的關(guān)系。18、設(shè)，求A上的全域關(guān)系 19、設(shè)，求A上的小于等于關(guān)系 20、設(shè)，求A上的恒等關(guān)系 21、設(shè)，求A上的整除關(guān)系 22、設(shè)，試用元素法表示 23 集合A a , b ，寫出P(A)和P(A)上的包含關(guān)系的集合表達(dá)式是 24 已知集合Aa,b,c上的二元關(guān)系R的關(guān)系矩陣MR，那么R( ) A. , B. , C. , D. ,25 設(shè)集合，上的二元關(guān)系分別為： 試用定義求，并畫出其關(guān)系圖。26 設(shè)R=, 則R1= 27 設(shè)R=, 則R2,3 = 答案：,28 設(shè)R=, 則R1 = 答案：2,329 設(shè)R=, 則R3= 答案：2 30、設(shè)，求（1）的集合表達(dá)式，（2）求，（3）求，（4）求31 設(shè)R是集合A上的二元關(guān)系，IA是上的恒等關(guān)系，下面四個(gè)命題為真的是()A.R是自反的B.R是傳遞的C.R是對(duì)稱的D.R是反對(duì)稱的32、集合上的關(guān)系不具有的性質(zhì)是（ ）A.自反性 B.反自發(fā)性 C.對(duì)稱性 D.反對(duì)稱性33、集合上的關(guān)系不具有的性質(zhì)是（ ）A.自反性 B. 傳遞性 C.對(duì)稱性 D.反對(duì)稱性34、下面關(guān)系圖所描述的關(guān)系具有的性質(zhì)是（ ）A.對(duì)稱的 B.反對(duì)稱的 C.自反的 D.傳遞的35、設(shè)，舉出上關(guān)系的例子，使它具有下述性質(zhì)：（1）是對(duì)稱的又是反對(duì)稱的（2）既不是對(duì)稱的又不是反對(duì)稱的（3）R是可傳遞的36 設(shè)R是A=1，2，3，4上的二元關(guān)系,R=,則R的自反閉包是 。答案: ,，,37 設(shè)R是A=1，2，3，4上的二元關(guān)系,R=,則R的對(duì)稱閉包是 。答案: ,38 設(shè)R是A=1，2，3，4上的二元關(guān)系,R=,則R的傳遞閉包是 。39、下列關(guān)系是等價(jià)關(guān)系的是（ ） A. 三角形的全等關(guān)系 B.朋友關(guān)系 C.同事關(guān)系 D.父子關(guān)系40，是上的模3同余關(guān)系，則= 答案： 41 設(shè)A=1，2，3，4，在AA上定義二元關(guān)系R， ,AA ，u,v R u + y = x + v.(1)證明R 是AA上的等價(jià)關(guān)系.(2)確定由R 引起的對(duì)AA的劃分.42. ，是的一個(gè)劃分，則由所確定的等價(jià)關(guān)系為 43、，則在上可以定義 種不同的等價(jià)關(guān)系。44、為上的二元關(guān)系，證明：（1）為等價(jià)關(guān)系，（2）求導(dǎo)出的劃分。45、設(shè)是非空集合上的關(guān)系，如果是 ，則稱是上的偏序關(guān)系。46、下列關(guān)系不是偏序關(guān)系的是（ ） A. 集合的包含關(guān)系 B. 數(shù)集上的小于關(guān)系 C. 數(shù)集上的等于關(guān)系 D.數(shù)集上的小于等于關(guān)系47 設(shè)集合A=a，b，c，d，e，偏序關(guān)系R的哈斯圖下圖所示，則元素的關(guān)系不正確的是（ ）。A B C D48 設(shè)集合A=a，b，c，d，e，偏序關(guān)系R的哈斯圖下圖所示，則A上的極大元是 ，極小元是 ，最大元是 ，最小元是 。 49 設(shè)上的整除關(guān)系，是否為上的偏序關(guān)系？若是，則：（1）、畫出的哈斯圖；（2）、求的極大值和的極小值。50 設(shè)上的整除關(guān)系，是否為上的偏序關(guān)系？若是，則：（1）、畫出的哈斯圖；（2）、求。51 畫出下列偏序集的哈斯圖,并找出A的極大元極小元最大元和最小元.A=a,b,c,d,e，R=,IA.52 下圖是兩個(gè)偏序集的哈斯圖.分別寫出集合A和偏序關(guān)系R的集合表達(dá)式. 53、針對(duì)下面的哈斯圖，寫出集合以及偏序關(guān)系的表達(dá)式 答案：54. 設(shè)A=1，2，3，4，A上關(guān)系圖為則= 。55. 設(shè)R，S是集合A上的關(guān)系，則下列說法正確的是（ ）。 A、若R，S 是自反的， 則是自反的； B、若R，S 是反自反的， 則是反自反的； C、若R，S 是對(duì)稱的， 則是對(duì)稱的； D、若R，S 是傳遞的， 則是傳遞的。56. 設(shè),則為（ ）。A、自反的 B、反自反的 C、傳遞的 D、等價(jià)的57. 設(shè)A=1，2，3，則A上的二元關(guān)系有（ ）個(gè)。 A、 23 ； B、 32 ； C、 ； D、 。58. 設(shè)集合A=a，b，c，d上的關(guān)系R= , , , 用矩陣運(yùn)算求出R的傳遞閉包t (R)。59. 設(shè)A=a，b，c，d，其上偏序關(guān)系R的哈斯圖為則 R= 。60. 設(shè),且是上的等價(jià)關(guān)系,則= 。61. 設(shè),且是上的等價(jià)關(guān)系,則 。62. (1) 已知 A=1，2，3，4，5上的等價(jià)關(guān)系R，R=,寫出R對(duì)應(yīng)的劃分。(2) 已知 A=1，2，3，4，5上的一個(gè)劃分D=1，3，2，4，5寫出對(duì)應(yīng)的等價(jià)關(guān)系S。63. 設(shè)A和B為有限集，|A|=m，|B|=n，則有 個(gè)從A到B的二元關(guān)系。64. 設(shè)A=, R=，則R具有（ ）。A、 自反性 B、 傳遞性 C、 對(duì)稱性 D、 反對(duì)稱性65. 設(shè)S=1，2，3，4，R為S上的關(guān)系，其關(guān)系矩陣是，求(1) R的關(guān)系表達(dá)式（用列舉法寫出）；R的關(guān)系圖。 (2) ，。(3) r(R), s(R)，t(R)。第三部分：圖論1、非負(fù)整數(shù)列是可圖化的當(dāng)且僅當(dāng) 2、下列非負(fù)整數(shù)列（ ）是可簡(jiǎn)單圖化的？A.5,5,4,4,2,1 B.5,4,3,2,2 C.3,3,3,1 D.4,4,3,3,2,23、無向圖G有16條邊，3個(gè)4度頂點(diǎn)，4個(gè)3度頂點(diǎn)，其余頂點(diǎn)度數(shù)均小于3，問G的階數(shù)n為幾？4、已知無向圖中頂點(diǎn)數(shù)與邊數(shù)相等，2度與3度頂點(diǎn)各2個(gè)，其余頂點(diǎn)均為懸掛頂點(diǎn)，試求的邊數(shù)。5、設(shè)為個(gè)互不相等的正整數(shù)，證明不可簡(jiǎn)單圖化。6、下圖的點(diǎn)連通度是 ，邊連通度是 。 7寫出下圖中所有的點(diǎn)割集 8、下面無向圖的點(diǎn)連通度是 ，邊連通度是。 9 下面有向圖中有 個(gè)是強(qiáng)連通的？ 10、寫出下面無向圖的關(guān)聯(lián)矩陣 。 11、寫出下面有向圖的關(guān)聯(lián)矩陣 。 12、寫出下列有向圖的鄰接矩陣 13、寫出下面有向圖的可達(dá)矩陣 。 14、設(shè)圖G的鄰接矩陣為則G的邊數(shù)為( )A5 B6 C3 D415、已知圖G的鄰接矩陣為 ，則G有（ ） A5點(diǎn)，8邊 B6點(diǎn)，7邊 C6點(diǎn)，8邊 D5點(diǎn)，7邊16、下列（ ）是歐拉圖。17 下圖中,（ ）是歐拉圖。A B C D18、完全圖，當(dāng)為 時(shí)，是歐拉圖。19、命題“階有向完全圖是歐拉圖”的真值是 。20、命題“當(dāng)為正偶數(shù)時(shí)，完全二部圖是歐拉圖”的真值是 。21、在完全圖上至少加 條邊，才能使所得圖為歐拉圖。22、判斷下列圖是哈密頓圖、半哈密頓圖、還是都不是？23 下圖中既是歐拉圖又是哈密頓圖的是（ ） A B C D24、設(shè)完全二部圖為哈密頓圖，則應(yīng)滿足 。25 說明圖 G （如圖5所示）不是漢密爾頓圖 26、已知a,b,c,d,e,f,g七人中，會(huì)講的語言分別為：a:英語、德語,b：英語、漢語,c：英語、意大利語、俄語,d：漢語、日語,e：意大利語、德語,f：俄語、日語、法語,g：德語、法語問能否將他們的座位安排在圓桌旁，使得每個(gè)人都能與他身邊的人交談？27、求A到其余頂點(diǎn)的最短路徑。28用Dijdstra算法求右圖中u到v的最短路。29一公司在六個(gè)城市C1，C2，-，C6中每一個(gè)都有分公司，從CI到CJ的班機(jī)旅費(fèi)由下列矩陣中第I行第J列的元素給出（表示沒有直接班機(jī)）。 0 0 50 40 25 1050 0 15 20 25 15 0 10 20 40 20 10 0 10 2525 20 10 0 5510 25 25 55 0公司所關(guān)心的是計(jì)算兩城市間的費(fèi)用最低的路線，對(duì)上述六城市中任意一對(duì)城市，計(jì)算兩城市間費(fèi)用 最低的路線。30、 (1)求下圖的最小生成樹；(2)求該圖的點(diǎn)連通度和邊連通度；(3)求A到B的最短路徑的長(zhǎng)度。 A 31 關(guān)于無向樹的描述,不正確的是( ).無向樹是連通圖、沒有回路,每個(gè)邊都是橋；無向樹是連通圖、邊數(shù)比頂點(diǎn)數(shù)少,任意兩個(gè)頂點(diǎn)的路徑是惟一的；無向樹是連通圖、沒有回路,每個(gè)頂點(diǎn)都是割點(diǎn)；無向樹是連通圖、沒有回路，每條邊都是割邊。32 下面與“T是樹”不等價(jià)的是( ) AT是無圈圖，且e=n-1 BT是連通圖，且e=n-1 CT刪去任一邊后不連通 DT任意添加一條邊后有且僅有一個(gè)圈33、證明若T是n階非平凡的無向樹，則T 中至少有兩片樹葉.34、已知無向樹T中有1個(gè)3度頂點(diǎn)，2個(gè)2度頂點(diǎn)，其余頂點(diǎn)全是樹葉，試求樹葉數(shù)，并畫出滿足要求的非同構(gòu)的無向樹. 35、畫出所有有3片樹葉、1個(gè)3度頂點(diǎn)、其余頂點(diǎn)不等于1和3的7階非同構(gòu)的無向樹。36、一棵無向樹T有5片樹葉，3個(gè)2度分支點(diǎn)，其余的分支點(diǎn)都是3度頂點(diǎn)，問T有幾個(gè)頂點(diǎn)？37、求下圖的一棵最小生成樹.38 對(duì)于下圖，利用避圈法求一棵最小生成樹。39 關(guān)于含有n片樹葉的最優(yōu)二叉樹描述,不正確的是( ).A. 含有n片樹葉的最優(yōu)二叉樹每個(gè)分支點(diǎn)都有兩個(gè)孩子；B. 含有n片樹葉的最優(yōu)二叉樹分支點(diǎn)的個(gè)數(shù)是n-1；C.W(T)等于個(gè)分支點(diǎn)的權(quán)重（構(gòu)造最優(yōu)二叉樹時(shí)產(chǎn)生）之和；D. 在權(quán)重一定的前提下，含有n片樹葉的最優(yōu)二叉樹是惟一的。40、求帶權(quán)為1, 1, 2, 3, 4, 5的最優(yōu)樹. 41、在通信中，八進(jìn)制數(shù)字出現(xiàn)的頻率如下： 0：25% 1：20% 2：15% 3：10% 4：10% 5：10% 6：5% 7：5