【正文】 的通路是 通路 。 44. 設(shè) R1， R2 是集合 A＝ {1,2,3,4}上的二元關(guān)系 ,其中 R1＝ {1,1,1,2,2,4}, R2={1,4,2,3,2,4,3,2},則 R1?R2＝ 。 42. 設(shè) L 是一個(gè)集合， ?和 ?是 L 上兩個(gè)二元運(yùn)算，如果這兩個(gè)二元運(yùn)算滿足 律， 律和 律，則 (L,?,?)是格 。 40. 設(shè) G是由 6個(gè)元素構(gòu)成的循環(huán)群， a是 G的一個(gè)生成元素，則 G有 個(gè)子群，G的生成元是 。 38. 設(shè) A是非空集合，集合代數(shù) (P(A)， ?， ?)中， P(A)對(duì)運(yùn)算 ?的單位元是 ， P(A)對(duì)運(yùn)算 ?的單位元是 。 36. 一個(gè)有向樹 T 稱為根樹，若 ，其中 ，稱為樹根， 稱為樹葉 . 。 34. 設(shè) G 是有 n 個(gè)結(jié)點(diǎn)的簡單圖，若 G 中每對(duì)結(jié)點(diǎn)的度數(shù)之和 ，則 G 一定是哈密頓圖 . 。 32. 設(shè) G 是完全二叉樹， G有 15 個(gè)結(jié)點(diǎn)，其中有 8個(gè)是樹葉，則 G有 條邊， G 的總度數(shù)是 ， G 的分支點(diǎn)數(shù)是 ， G 中度數(shù)為 3的結(jié)點(diǎn)數(shù)是 . 。 30. 在無向圖中，結(jié)點(diǎn)間的連通關(guān)系具有 性， 性， 性，是 關(guān)系 . 。 28. 換名規(guī)則施于 變?cè)?，代入?guī)則施于 變?cè)?。 26. 謂詞邏輯公式 )()( xxQxxP ??? 的前束范式是 。 24. 已知命題公式為 G＝ (?P?Q)?R,則命題公式 G 的析取范式是 。（填“是”或“不是”） 。 21．設(shè)有向圖 D＝ V,E的鄰接矩陣為 A(D)=????????????1100100001000120，那么 ?E?＝ 。))=________________________________________ 。 18．一個(gè)樹林 G 有三棵樹， G 的頂點(diǎn)數(shù)是 20，則 G 的邊數(shù)為 _______________ 。（填“是”或“不是”） 。 15. p→ q 的主合取范式是 _________________________ 。 1設(shè) A，≤ 是分配格，若對(duì)任意的 a， c， c∈ A，如果有 a∧ b=a∧ c， a∨ b=a∨ c 成立，則 a______b。 1設(shè) A={a,b}， B={0,1,2}，那么可定義 ________種不同的從 A到 B 的單射 。 RPQPQ ??? , 的有效結(jié)論是 __________。 元素?cái)?shù)目不超過 ________的格一定是鏈 。 當(dāng) n 是 ____________值時(shí)，無向完全圖 Kn是歐拉圖 。 R 是實(shí)數(shù)集合， R 中的關(guān)系 g={x2， x} ________ 從 R 到 R的函數(shù)（填“是”或“不是”） 。 二、填空題 1. 代數(shù)格（ L， ?， ?）中的運(yùn)算 ?和 ?滿足的算律有 _______、 __________、 __________。 A. x? y = x+y－ 2xy ? y = x+y C. x? y = x? y ? y = |x|+|y| G 的相鄰矩陣為????????????0010000110010110，則 G 有（ ）。 A.｜Ｅ｜ (｜ E｜ — 1)／ 2 B.｜Ｖ｜ (｜Ｖ｜一 1)／ 2 C.｜Ｅ｜ (｜Ｅ｜－１ ) D.｜Ｖ｜ (｜Ｖ｜－１ ) 65．設(shè) G是有 n個(gè)結(jié)點(diǎn)， m條邊的連通阻，必須刪去 G的 ( )條邊，才能確定 G的一棵生成樹 。 A. ??aa? B.?? Aa? C. Aa? D.?? Aa? 63．設(shè)集合 A{1， 2， 3， 4}， B： {2， 4， 6， 9}，那么集合 A， B的對(duì)稱差 A⊕ B＝ ( )。 61．設(shè)命題公式 ? ?RQPG ???: ，則使公式 G取真值為 1 的 P， Q， R 賦值分別是 ( )。 59. 設(shè) G??x?yP(x,y)?Q(z,w)，下面三個(gè)命題為真的是 ( )。 ?S4 ? S3， ? S2 ? S3 G 是有 6 個(gè)元素的循環(huán)群， a 是生成元素，則 G 的子集（ ）是子群。 A.{a}?A B.{a}?A ?A D.??A 55. 設(shè) A, B, C都是集合，如果 A?C＝ B?C，則有 ( ) 。 y，使 P(y)都取真值 1 y0，使 P(y0)取真值 1 y，使 P(y)都取真值 1 y0，使 P(y0)取真值 0 a? f ? b? ? ? ?g c ? ?h 圖 d e 53. 設(shè) G 是群，當(dāng) G 有（ ）個(gè)元素時(shí)，不能肯定 G 是交換群。 A.{b,d} B.nhcuj7d3 C.{e} D.{f,h} 51． 謂詞公式 ? xA(x)? ?? xA(x)的類型是（ ） 。 A.?=0 B.??? C.??{a,b} D.??{?} ，行元素之和是對(duì)應(yīng)結(jié)點(diǎn)的 ( )，列元素之和是對(duì)應(yīng)結(jié)點(diǎn)的 ( ) 。 47. 設(shè)集合 ?},{},{ 3214321 bbbBaaaaA ?? 是從 A到 B 的函數(shù)， ,{ 21 ??? ba? }, 341322 ?????? bababa ，則 ?是 ( )。 A.{c,1,2,c} B.{1,c,2,c} C.{c,1,c,2} D.{1,c,c,2} 45. 設(shè) A＝ {0,a},B={1,a,3},則 A?B 的恒等關(guān)系是 ( )。 A. 0?ba B. 1??ba C. aba ?? D. 1??ba 43. 布爾代數(shù)式 )( cbcabab ??? =( )。 A. 21? B.?1?2 C. 22? D.?2?1 41. 下列圖表示的偏序集中，是格的為 ( )。 ?b=a－ b B. a?b=a+2b C. a?b=max{a,b} D. a?b=?a－ b? 39. 下列代數(shù)系統(tǒng) (G,*)中，其中 *是加法運(yùn)算 . ( )不是群 。 B. 哈密頓圖 ? ? ? ? ? ? 圖 37. 設(shè)集合 A＝ {1,2,3,… ,10},在集合 A上定義的運(yùn)算，不是封閉的為 ( )。 35. 由 5 個(gè)結(jié)點(diǎn)可構(gòu)成的根樹中，其叉數(shù) m 最多為 ( )。 的所有結(jié)點(diǎn)的度數(shù)全為偶數(shù) 的所有結(jié)點(diǎn)的度數(shù)全為奇數(shù) 連通且所有結(jié)點(diǎn)的度數(shù)全為偶數(shù) 連通且所有結(jié)點(diǎn)的度數(shù)全為奇數(shù) 33. 設(shè) mEnVEVG ????? , 為連通平面圖且有 r 個(gè)面，則 r＝ ( )。 A. },{ ??????????? cdbcdbabdaE B. },{ ??????????? cddbcbabdaE C. },{ ??????????? cdadcbabcaE D. },{ ??????????? dcdbdacabaE 31. 相鄰矩陣具有對(duì)稱性的圖一定是 ( )。 A. ?(G)n B.?(G)?n C. ?(G)n D. ?(G)?n 29. 圖 G 與 G?的結(jié)點(diǎn)和邊分別存在一一對(duì)應(yīng)關(guān)系，是 G≌ G?(同構(gòu) )的 ( )。 A. n(n－ 1) B. n(n+1) C. n(n－ 1)/2 D. n(n+1)/2 27. 僅有一個(gè)孤立結(jié)點(diǎn)的圖稱為 ( )。 25. 在圖 G＝ V,E中，結(jié)點(diǎn)總度數(shù)與邊數(shù)的關(guān)系是 ( )。 A. )0( ???? yxyx B. )0( ???? yxxy C. )0( ???? yxyx D. )0( ????? yxyx 23． 設(shè) L(x)： x 是演員， J(x)： x 是老師， A(x,y)： x 佩服 y. 那么命題“所有演員都佩服某些老師”符號(hào)化為 ( )。 A. HQ? B. GH? C. GH? D. HG? 21． 謂詞公式 )())()(( xQyyRxPx ???? 中量詞 ?x的轄域是 ( )。 A.(P?Q)?R B.(P?Q)?R C.(P?Q)?R D. P?(Q?R) 19. 命題公式 (P?Q)?P 是 ( )。 A. ppp ???? )( B. ppq ??? )( C. )()( pqqp ????? D. rqp ?? )( 17. 設(shè)命題公式 ?(P?(Q??P))，記作 G，則使 G 的真值指派為 0 的 P， Q的取值是 ( )。 A. ppp ???? )( B. ppq ??? )( C. )()( pqqp ????? D. rqp ?? )( 15. 下列各 Hasse 圖中，是格的有 （ ）。 ， 0 ， 1 ，不存在 ，不存在 13. 設(shè) NNNf ,: ? 為自然數(shù)，且 ?????? 為偶數(shù)若 為奇數(shù)若 xx xxf21)( 則 })0({)0( ff 和 分別是 （ ）。 A、 R 是對(duì)稱的 B、 R 是反對(duì)稱的 C、 R 是反自反的 D、 R 中有 7 個(gè)元素 11. 下列各組數(shù)中，哪 個(gè)可以構(gòu)成無向圖的度數(shù)列 （ ）。 ?A B.{{4,5}}?A C. {1,2,3}?A D.??A 在有界格中，若一個(gè)元素有補(bǔ)元，則補(bǔ)元 ( )。 A、所有可數(shù)集合都是等勢的 B、任何集合都有與其等勢的真子集 C、有些無限集合沒有可數(shù)子集 D、有理數(shù)集合是不可數(shù)集合 無向完全圖 K3的不同構(gòu)的生成子圖有（ ）個(gè) 。 A、中國將成功舉辦 2020 年奧運(yùn)會(huì) B、一億年前地球發(fā)生了大災(zāi)難 C、我說的不是真話 D、哈密頓圖是連通的 設(shè) R 是實(shí)數(shù)集合，在上定義二元運(yùn)算 *： a， b∈ R， a*b=a+bab，則下面的論斷中正確的是 （ ）。測 試 題 —— 離散數(shù)學(xué) 一、選擇題 G 是一棵根樹，則 （ ）。 A、 G 一定是連通的 B、 G 一定是強(qiáng)連通的 C、 G 只有一個(gè)頂點(diǎn)的出度為 0 D、 G 只有一個(gè)頂點(diǎn)的入度為 1 下面哪個(gè)語句不是命題 （ ）。 A、 0 是 *的零元 B、 1 是 *的幺元 C、 0 是 *的幺元 D、 *沒有等冪元 下面說法中正確的是 （ ）。 A. 6 C. 4 D. 3 下面哪一種圖不一定是無向樹 ? A、無回路的連通圖 B、有 n 個(gè)頂點(diǎn) n1 條邊的連 通圖 C、每對(duì)頂點(diǎn)間都有通路的圖 D、連通但刪去一條邊則不連通的圖 設(shè)集合 A＝ {{1,2,3},{4,5},{6,7,8}}，則下列各式為真的是 ( )。 A、必惟