1、離散數(shù)學(xué)同步練習(xí)冊(cè) 學(xué)號(hào)姓名專(zhuān)業(yè)教學(xué)中心華南理工大學(xué)二O一O年九月第一章命題邏輯一填空題（1）設(shè)：p：派小王去開(kāi)會(huì)。q：派小李去開(kāi)會(huì)。則命題：“派小王或小李中的一人去開(kāi)會(huì)” 可符號(hào)化為： pq 。（2）設(shè)A，B都是命題公式，AB，則AB的真值是 T 。（3）設(shè)：p：劉平聰明。q：劉平用功。在命題邏輯中，命題：“劉平不但不聰明，而且不用功” 可符號(hào)化為： pq 。（4）設(shè)A , B 代表任意的命題公式，則蘊(yùn)涵等值式為A B PQ 。（5）設(shè)，p：徑一事；q：長(zhǎng)一智。在命題邏輯中，命題：“不徑一事，不長(zhǎng)一智。” 可符號(hào)化為： pq 。（6）設(shè)A , B 代表任意的命題公式，則德 摩根律為（A B）

2、 AB 。（7）設(shè)，p：選小王當(dāng)班長(zhǎng)；q：選小李當(dāng)班長(zhǎng)。則命題：“選小王或小李中的一人當(dāng)班長(zhǎng)。” 可符號(hào)化為： (AB) (AB) 。（8）設(shè)，P：他聰明；Q：他用功。在命題邏輯中，命題：“他既聰明又用功。” 可符號(hào)化為： PQ 。（9）對(duì)于命題公式A，B，當(dāng)且僅當(dāng) AB 是重言式時(shí)，稱(chēng)“A蘊(yùn)含B”，并記為AB。（10）設(shè)：P：我們劃船。Q：我們跑步。在命題邏輯中，命題：“我們不能既劃船又跑步。” 可符號(hào)化為： (PQ) 。（11）設(shè)P , Q 是命題公式，德摩根律為：（P Q） PQ 。（12）設(shè) P：你努力。Q：你失敗。在命題邏輯中，命題：“除非你努力，否則你將失敗。” 可符號(hào)化為： PQ

3、 。（13）設(shè) p：小王是100米賽跑冠軍。q：小王是400米賽跑冠軍。在命題邏輯中，命題：“小王是100米或400米賽跑冠軍。” 可符號(hào)化為： pq 。（4）設(shè)A，C為兩個(gè)命題公式，當(dāng)且僅當(dāng) A C 為一重言式時(shí)，稱(chēng)C可由A邏輯地推出。二判斷題1. 設(shè)A，B是命題公式，則蘊(yùn)涵等值式為ABAB。 （ F ）2. 命題公式pqr是析取范式。 （ T ）3. 陳述句“x + y 5” 是命題。 （ T ）4. 110 (p=1,q=1, r=0)是命題公式 (pq)r)q 的成真賦值。 （ T ）5. 命題公式 p(pq) 是重言式。 （ F ）6. 設(shè)A，B都是合式公式，則ABB也是合式公式。

4、（ F ）7. A(BC)( AB)(AC)。 （ F ）8. 陳述句“我學(xué)英語(yǔ)，或者我學(xué)法語(yǔ)” 是命題。 （ T ）9. 命題“如果雪是黑的，那么太陽(yáng)從西方出”是假命題。 （ T ）10. “請(qǐng)不要隨地吐痰！” 是命題。 （ F ）11. P Q P Q 。 （ F ）12. 陳述句“如果天下雨，那么我在家看電視” 是命題。 （ T ）13. 命題公式（PQ）（RT）是析取范式。 （ T ）14. 命題公式 (PQ) R (PQ) 是析取范式。 （ T ）三、選擇題：在每小題的備選答案中只有一個(gè)正確答案，將正確答案序號(hào)填入下列敘述中的 內(nèi)。1 設(shè)：P：天下雪。Q：他走路上班。則命題“只有天下

5、雪，他才走路上班。”可符號(hào)化為 （1） 。 （1）PQ （2）Q P （3） Q P （4）Q P2 (1 ) 明年國(guó)慶節(jié)是晴天。(2 ) 在實(shí)數(shù)范圍內(nèi)，x+y3。 (3 ) 請(qǐng)回答這個(gè)問(wèn)題！(4 ) 明天下午有課嗎？在上面句子中，是命題的只有 (2 ) 。3 命題公式A與B是等值的，是指 (4 ) 。（1） A與B有相同的命題變?cè)?） AB是可滿足式（3） AB為重言式（4） AB為重言式4 (1 ) 雪是黑色的。(2 ) 這朵花多好看呀！。 (3 ) 請(qǐng)回答這個(gè)問(wèn)題！(4 ) 明天下午有會(huì)嗎？在上面句子中，是命題的是 (1 ) 。5 設(shè)：P：天下大雨。Q：他乘公共汽車(chē)上班。則命題“只要天

6、下大雨，他就乘公共汽車(chē)上班。”可符號(hào)化為 （2） 。 （1）QP （2）P Q （3） Q P （4）Q P6 設(shè)：P：你努力；Q：你失敗。則命題“除非你努力，否則你將失敗。”在命題邏輯中可符號(hào)化為 （3） 。 （1）QP （2）P Q （3） P Q （4）Q P7 (1 ) 現(xiàn)在開(kāi)會(huì)嗎？(2 ) 在實(shí)數(shù)范圍內(nèi)，x+y 5。 (3 ) 這朵花多好看呀！(4 ) 離散數(shù)學(xué)是計(jì)算機(jī)科學(xué)專(zhuān)業(yè)的一門(mén)必修課。在上面語(yǔ)句中，是命題的只有 (2 ) 。8 設(shè)：P：天氣好。Q：他去郊游。則命題“如果天氣好，他就去郊游。”可符號(hào)化為 （1） （1）PQ （2）Q P （3） Q P （4）Q P9 下列式子是

7、合式公式的是 （4） 。（1）（P Q） （2） （P （Q R）（3）（P Q） （4） Q R10 （1）1101110 （2） 中國(guó)人民是偉大的。 （3） 全體起立！ （4） 計(jì)算機(jī)機(jī)房有空位嗎？在上面句子中，是命題的是 （1） 。11 設(shè)：P：他聰明；Q：他用功。則命題“他雖聰明但不用功。”在命題邏輯中可符號(hào)化為 （4） 。 （1）P Q （2）P Q （3）P Q （4）P Q12 (1 ) 如果天氣好，那么我去散步。 (2 ) 天氣多好呀！ (3 ) x=3。 (4 ) 明天下午有會(huì)嗎？在上面句子中 (1 ) 是命題。13 設(shè)：P：王強(qiáng)身體很好；Q：王強(qiáng)成績(jī)很好。命題“王強(qiáng)身體很好

8、，成績(jī)也很好。”在命題邏輯中可符號(hào)化為 （4） 。 （1）P Q （2）P Q （3）P Q （4）P Q四、解答題1設(shè)命題公式為（pq）（qp）。 （1）求此命題公式的真值表；（2）給出它的析取范式；（3）判斷該公式的類(lèi)型。（1）Pqpqpqqp（pq）（qp）TTFFTFFTFFTTTTFTTFTTTFFTTFTT（2）（p q）p q（3）可滿足式2設(shè)命題公式為（p q）（p r）。 （1）求此命題公式的真值表；（2）給出它的析取范式；（3）判斷該公式的類(lèi)型。（1）pqrpqp r（p q）（p r）TTTTTTTTFTTTTFTFTFTFFFTFFTTTTTFTFTTTFFTTTTFF

9、FTFF(2)(pq) ( p r) (pr)(3) 可滿足式3設(shè)命題公式為 Q （P Q） P。 （1）求此命題公式的真值表；（2）求此命題公式的析取范式；（3）判斷該命題公式的類(lèi)型。（1）PQ P QP Q（P Q） P Q （P Q） PTTFFTTFTFFTFTTFTTFTTFFFTTTFF(2) P（P Q）(3) 可滿足式4完成下列問(wèn)題 （1）求此命題公式 Q （P Q） P 的真值表；（2）求命題公式（P（QR）S的析取范式。（1）同上表（2） P(Q R) S5設(shè)命題公式為（P （P Q） Q。（1）求此命題公式的真值表；（2）判斷該公式的類(lèi)型。（1）PQP QP （P Q）（

10、P （P Q） QTTTTTTFFFTFTTFFFFTFF(2) 可滿足式6設(shè)命題公式為（P Q）P） Q。 （1）求此命題公式的真值表；（2）給出它的析取范式；（3）判斷該公式的類(lèi)型。(1)PQPP Q（P Q）P（P Q）P） QTTFTFTTFFTFTFTTTTTFFTFFT(2) P Q(P Q)(3)重言式7用直接證法證明 前提：P Q，P R，Q S結(jié)論：S R證明：8用直接證法證明 前提：P (Q R)，S Q，P，S。結(jié)論：R證明：S Q，S推出 Q（假言推論）P (Q R)，P推出Q R （假言推論） Q，Q R推出R（析取三段論）第二章謂詞邏輯一填空題（1）若個(gè)體域是含三個(gè)

11、元素的有限域a，b，c，則A(x) A(a)A(b)A(c) （2）取全總個(gè)體域，令F(x)：x為人,G(x)：x愛(ài)看電影。則命題“沒(méi)有不愛(ài)看電影的人。”可符號(hào)化為_(kāi)($x_(F(x)_ G(x)_。（3）若個(gè)體域是含三個(gè)元素的有限域a，b，c，則xA(x) A(a) A(b) A(c) 。（4）取全總個(gè)體域，令M(x)：x是人,G(y)：y是花, H(x,y)：x喜歡y。則命題“有些人喜歡所有的花。”可符號(hào)化為_(kāi)$x$y (_M(x) H(x,y) G(y)_。（5）取個(gè)體域?yàn)槿w人的集合。令F(x)：x在廣州工作,G(x)：x是廣州人。在一階邏輯中，命題“在廣州工作的人未必都是廣州人。”可

12、符號(hào)化為_(kāi)$x (F(x) G(x)_。（6）P(x)：x是學(xué)生，Q(x)：x要參加考試。在謂詞邏輯中，命題：“每個(gè)學(xué)生都要參加考試” 可符號(hào)化為：x(P(x) Q(x) ) 。（7）M(x)：x是人，B(x)：x勇敢。則命題“有人勇敢，但不是所有的人都勇敢”謂詞符號(hào)化為 _$x (M(x) B(x) (x(M(x) B(x)_。（8）P(x)：x是人，M(x)：x聰明。則命題“盡管有人聰明，但不是一切人都聰明”謂詞符號(hào)化為 _$x (P(x) M(x) (x(P(x) M(x)_。（9）I(x)：x是實(shí)數(shù)，R(x)：x是正數(shù)，N(x)：x是負(fù)數(shù)。在謂詞邏輯中，命題：“任何實(shí)數(shù)或是正的或是負(fù)的

13、” 可符號(hào)化為：x(I(x) R(x) R(x) 。（10）P(x)：x是學(xué)生，Q(x)：x要參加考試。在謂詞邏輯中，命題：“每個(gè)學(xué)生都要參加考試” 可符號(hào)化為：x(P(x) Q(x) ) 。（11）令M(x)：x是大學(xué)生,P(y)：y是運(yùn)動(dòng)員, H(x, y)：x欽佩y。則命題“有些大學(xué)生不欽佩所有運(yùn)動(dòng)員。”可符號(hào)化為 _$xy(M(x) P(y) H(x, y) _ _。二判斷題1. 設(shè)A，B都是謂詞公式，則x AB也是謂詞公式。 （ T ）2. 設(shè)c是個(gè)體域中某個(gè)元素，A是謂詞公式，則A(c) xA(x)。 （ F ）3. xyA(x,y) yxA(x,y) 。 （ T ）4. x$yA

14、(x,y) $yxA(x,y) 。 （ F ）5. 取個(gè)體域?yàn)檎麛?shù)集，則謂詞公式xy(x y = y ) 是假命題。 （T ）6. (x)（P(x)Q(x)） (x)（P(x) Q(x)）。 （T ）7. 命題公式 (PQ R) (PQ) 是析取范式。 （ F ）8. 謂詞公式(x)(A (x) B(x, y) R(x) 的自由變?cè)獮閤, y。 （ F ）9. （x）A（x） B）（$x）（A（x） B）。 （F ）10. R(x)：“x是大學(xué)生。” 是命題。 （T ）三、選擇題：在每小題的備選答案中只有一個(gè)正確答案，將正確答案序號(hào)填入下列敘述中的 內(nèi)。1設(shè)F（x）：x是火車(chē)，G（x）：x是汽

15、車(chē)，H（x，y）：x比y快。命題“某些汽車(chē)比所有火車(chē)慢”的符號(hào)化公式是 (2) 。（1） $y（G（y）x（F（x）H（x，y）（2） $y（G（y）x（F（x）H（x，y）（3） x $y（G（y）（F（x）H（x，y）（4） $y（G（y）x（F（x）H（x，y）2設(shè)個(gè)體域?yàn)檎麛?shù)集，下列真值為真的公式是 (3) 。（1）$yx (x y =2)（2）xy(x y =2)（3）x$y(x y =2)（4）$xy(x y =2)3設(shè)F（x）：x是人，G（x）：x早晨吃面包。命題“有些人早晨吃面包”在謂詞邏輯中的符號(hào)化公式是 (4) 。（1） （x）（F（x） G（x）（2） （x）（F（x）

16、G（x）（3） （$x）（F（x） G（x）（4） （$ x）（F（x） G（x）5下列式子中正確的是 (4) 。（1）（x）P（x）（$x）P（x） （2）（x）P（x）（x） P（x）（3）（$x）P（x）（$x） P（x） （4）（$x）P（x）（x） P（x）6下面謂詞公式是永真式的是(d) 。a) P（x） Q（x）b) （x）P（x）（$x）P（x）c) P（a）（x）P（x）d) P（a）（$x）P（x）5 設(shè)S（x）：x是運(yùn)動(dòng)員，J（y）：y是教練員，L（x，y）：x欽佩y。命題“所有運(yùn)動(dòng)員都?xì)J佩一些教練員”的符號(hào)化公式是 (c) 。a) x（S（x） y（J（y） L（x，y

17、）b) x $y（S（x）（J（y） L（x，y）c) x（S（x） $y（J（y） L（x，y）d) $yx（S（x）（J（y） L（x，y）6 下列式子是合式公式的是 (2) 。（1）（P Q） （2） （P （Q R）（3）（P Q） （4） Q R7 下列式子中正確的是 (4) 。（1）（x）P（x）（$x）P（x） （2）（x）P（x）（x） P（x）（3）（$x）P（x）（$x） P（x） （4）（$x）P（x）（x） P（x）四、解答題1構(gòu)造下面推理的證明：前提：$ x F（x）y（F（y） G（y） R（y），$ x F（x）。結(jié)論：$ x R（x）。2在一階邏輯中構(gòu)造下面推理

18、的證明 每個(gè)喜歡步行的人都不喜歡坐汽車(chē)。每個(gè)人或者喜歡坐汽車(chē)或者喜歡騎自行車(chē)。有的人不喜歡騎自行車(chē)。因而有的人不喜歡步行。令F(x)：x喜歡步行。G(x)：x喜歡坐汽車(chē)。H(x)：x喜歡騎自行車(chē)。x( F(x) G(x), x(G(x) H(x), $ x H(x) $ x F(x)3在命題邏輯中構(gòu)造下面推理的證明： 如果他是理科學(xué)生，他必須學(xué)好數(shù)學(xué)。如果他不是文科學(xué)生，他必是理科學(xué)生。他沒(méi)學(xué)好數(shù)學(xué)，所以他是文科學(xué)生。4用直接證法證明：前提：（x）（C（x） W（x）R（x），（$x）（C（x）Q（x）結(jié)論：（$x）（Q（x）R（x）。第三章集合與關(guān)系一填空題（1）如果|A|n，那么|AA|n

19、*n。A上的二元關(guān)系有_2_個(gè)。（2）集合A上關(guān)系R的自反閉包r（R）=_。（3）設(shè)集合A上的關(guān)系R和S，R=（1，2），（1，3），（3，2），S=（1, 3），（2，1），（3，2），則SR= (2,2),(1，2) 。（4）如果|A|n，那么|P(A)|。（5）設(shè)集合A上的關(guān)系R和S，R=，S=，則RS= , 。（6）設(shè)集合E=a, b, c，E的冪集P(E) ,a,b,c,a,b,a,c,b,c,a,b,c_。（7）設(shè)R是定義在集合X上的二元關(guān)系，如果對(duì)于每個(gè)x, yX， _ _ _ ，則稱(chēng)集合X上的關(guān)系R是對(duì)稱(chēng)的。（8）設(shè)關(guān)系R和S為，R=，S=，則RS =_ _ _ _。（9）設(shè)R

20、是定義在集合X上的二元關(guān)系，如果對(duì)于每個(gè)x, yX， _ _ _ ，則稱(chēng)集合X上的關(guān)系R是自反的。二判斷題1設(shè)A、B、C為任意的三個(gè)集合，則A(BC)=A(BC)。 （ ）2設(shè)S，T是任意集合，如果S -T = ，則S = T。 （ ）3集合A=1,2,3,4上的關(guān)系,是一個(gè)函數(shù)。 （ ）4集合A=1，2，3，4上的整除關(guān)系是等價(jià)關(guān)系。 （ ）5集合A 的冪集P(A)上的包含關(guān)系是偏序關(guān)系。 （ ）6設(shè)A=a, b, c, R AA且R=, 則R是傳遞的。 （ ）6設(shè)A，B是任意集合，如果B ，則A B A。 （ ）7集合A=1,2,3上的關(guān)系,是傳遞的。 （ ）8集合A=1，2，3，4上的小

21、于關(guān)系是等價(jià)關(guān)系。 （ ）9關(guān)系x1, x2N, x1+x26能構(gòu)成一個(gè)函數(shù)。 （ ）10集合A 上的恒等關(guān)系是偏序關(guān)系。 （ ）11集合A=1,2,3上的關(guān)系S=,是自反的。 （ ）12設(shè)X=1, 2, 3, Y=a, b, c。函數(shù)F=,是雙射。 （ ）13集合A上的關(guān)系R的自反閉包r(R)=RIA。 （ ）14集合A上的偏序關(guān)系R是自反的、對(duì)稱(chēng)的、傳遞的。 （ ）15. 設(shè)A，B是任意集合，則A B (A-B) (B-A)。 （ ）三、選擇題：在每小題的備選答案中只有一個(gè)正確答案，將正確答案序號(hào)填入下列敘述中的 內(nèi)。1 設(shè)A=a，b，c，B=a，b，則下列命題不正確的是 。a) AB=a

22、，bb) AB= a，b c) AB=cd) BA2 設(shè) A = a, b, c, d, A 上的關(guān)系R = , , , ，則它的對(duì)稱(chēng)閉包為。a) R = , , , , , , ，b) R = , , , , ，c) R = , , , , , ，d) R = , , , , , ，3 對(duì)于集合1, 2, 3, 4上的關(guān)系是偏序關(guān)系的是 。a) R=, ,b) R=, ,c) R=, ,d) R=, ,4 設(shè)A=1，2，3，4，5，B=6，7，8，9，10，以下哪個(gè)關(guān)系是從A到B的單射函數(shù) 。a) f =，b) f =，c) f =，d) f =，5設(shè) A = a, b, c，要使關(guān)系, ,

23、 , R 具有對(duì)稱(chēng)性，則 。a) R = , b) R = , c) R = , d) R = , 6設(shè)S=F，1，1，2，則S的冪集P（S）有 個(gè)元素 （1）3 （2）6 （3）7 （4）87設(shè)R為定義在集合A上的一個(gè)關(guān)系，若R是 ，則R為等價(jià)關(guān)系 。（1）反自反的，對(duì)稱(chēng)的和傳遞的 （2）自反的，對(duì)稱(chēng)的和傳遞的（3） 自反的，反對(duì)稱(chēng)的和傳遞的 （4）對(duì)稱(chēng)的，反對(duì)稱(chēng)的和傳遞的8設(shè)S，T，M為任意集合，下列命題正確的是 。a) 如果ST = SM，則T = Mb) 如果S-T = F，則S = Tc) S-T Sd) S S = S9 設(shè) A = a, b, c，要使關(guān)系, , , R 具有對(duì)

24、性，則 。（1）R = , （2）R = , （3） R = , （4）R = , 10設(shè)A=1，2，3，4，5，B=a，b，c，d，e，以下哪個(gè)函數(shù)是從A到B的入射函數(shù) 。a) F =，b) F=，c) F =，d) F=，四、解答題1已知偏序集（A，），其中A=a，b，c，d，e，“”為（a，b），（a，c），（a，d），（c，e），（b，e），（d，e），（a，e）IA。（1）畫(huà)出偏序集（A，）的哈斯圖。（2）求集合A的極大元，極小元，最大元，最小元。2設(shè)R是集合A = 1, 2, 3, 4, 5, 6, 7, 8, 9上的整除關(guān)系。 （1） 給出關(guān)系R；（2）畫(huà)出關(guān)系R的哈斯圖；（3）

25、指出關(guān)系R的最大、最小元，極大、極小元。 3設(shè)R是集合A = 1, 2, 3, 4, 6, 12上的整除關(guān)系。（2） 給出關(guān)系R；（2） 給出COV A（3） 畫(huà)出關(guān)系R的哈斯圖；（4） 給出關(guān)系R的極大、極小元、最大、最小元。 第五章代數(shù)結(jié)構(gòu)一填空題（1）集合S的冪集P(S)關(guān)于集合的并運(yùn)算“”的零元為 _。（2）集合S的冪集P(S)關(guān)于集合的并運(yùn)算“”的零元為 _。（3）集合S的冪集P(S)關(guān)于集合的并運(yùn)算“”的么元為 _。（4）一個(gè)代數(shù)系統(tǒng)S, * ，其中S是非空集合。*是S上的一個(gè)二元運(yùn)算，如果 ，則稱(chēng)代數(shù)系統(tǒng)S, * 為廣群。二判斷題1含有零元的半群稱(chēng)為獨(dú)異點(diǎn)。 （ ）2運(yùn)算“”是整

26、數(shù)集I上的普通加法，則群的么元是1。 （ ）三、填空題：在每小題的備選答案中只有一個(gè)正確答案，將正確答案序號(hào)填入下列敘述中的 內(nèi)。1 下列群一定為循環(huán)群的是。e) （運(yùn)算“”是整數(shù)集I上的普通加法）f) （R是實(shí)數(shù)集，“”是普通乘法）g) （運(yùn)算“”是有理數(shù)集Q上的普通加法）h) （P（S）是集合S的冪集，“”為對(duì)稱(chēng)差）2運(yùn)算“”是整數(shù)集I上的普通減法，則代數(shù)系統(tǒng) 滿足下列 性質(zhì) 。（1）結(jié)合律 （2）交換律 （3）有零元 （4） 封閉性3設(shè)I是整數(shù)集，N是自然數(shù)集，P（S）是S的冪集，“，”是普通的乘法，加法和集合的交運(yùn)算。下面代數(shù)系統(tǒng)中 是群。 （1） （2） （3） （4）4下列代數(shù)系統(tǒng)

27、不是群的是。（5） （運(yùn)算“”是整數(shù)集I上的普通加法）（6） （P（S）是集合S的冪集，“”為交運(yùn)算）（7） （運(yùn)算“”是有理數(shù)集Q上的普通加法） （P（S）是集合S的冪集，“”為對(duì)稱(chēng)差）第七章圖論一填空題（1）一個(gè)無(wú)向圖G=（V，E）是二部圖當(dāng)且僅當(dāng)G中無(wú) 長(zhǎng)度的回路。（2）任何圖(無(wú)向的或有向的)中，度為奇數(shù)的頂點(diǎn)個(gè)數(shù)為。（3）設(shè)D是一個(gè)有向圖，若D中任意一對(duì)頂點(diǎn)都是相互可達(dá)的，則稱(chēng)D是_。（4）既不含平行邊，也不含環(huán)的圖稱(chēng)為 。（5）經(jīng)過(guò)圖中 一次且僅一次并且行遍圖中每個(gè)頂點(diǎn)的回路，稱(chēng)為歐拉回路。（6）一棵有n個(gè)頂點(diǎn)的樹(shù)含有_邊。（7）設(shè)G =（V，E），G =（V，E）是兩個(gè)圖，若 且

28、 ，稱(chēng)G是G的生成子圖。 （8）經(jīng)過(guò)圖中 一次且僅一次的回路，稱(chēng)為哈密爾頓回路。二判斷題15個(gè)頂點(diǎn)的有向完全圖有20條邊。 （ ）2連通無(wú)向圖的歐拉回路經(jīng)過(guò)圖中的每個(gè)頂點(diǎn)一次且僅一次。 （ ）3 圖中的初級(jí)通路都是簡(jiǎn)單通路。 （ ）4 已知n (n2)階無(wú)向簡(jiǎn)單圖G有n 1條邊，則G一定為樹(shù)。 （ ）5 n階無(wú)向完全圖Kn的每個(gè)頂點(diǎn)的度都是n。 （ ）6一個(gè)無(wú)向圖是二部圖當(dāng)且僅當(dāng)它沒(méi)有奇數(shù)度的頂點(diǎn)。 （ ）7任何圖都有一棵生成樹(shù)。 （ ）8連通無(wú)向圖的哈密爾頓回路經(jīng)過(guò)圖中的每條邊一次且僅一次。 （ ）9圖中的初級(jí)回路都是簡(jiǎn)單回路。 （ ）10任一圖G=（V，E）的頂點(diǎn)的最大度數(shù)必小于G的頂點(diǎn)數(shù)

29、。 （ ）11歐拉圖一定是漢密爾頓圖。 （ ）12無(wú)向連通圖G的任意兩結(jié)點(diǎn)之間都存在一條路。 （ ）13根樹(shù)中除一個(gè)結(jié)點(diǎn)外，其余結(jié)點(diǎn)的入度為1。 （ ）三、選擇題：在每小題的備選答案中只有一個(gè)正確答案，將正確答案序號(hào)填入下列敘述中的 內(nèi)。1 下列為歐拉圖的是 。2 下列各圖為簡(jiǎn)單圖的是 。(4)(3)(2)(1) 3 設(shè)無(wú)向圖G有12條邊，已知G中3度頂點(diǎn)有6個(gè)，其余頂點(diǎn)的度數(shù)都小于3，則該圖至少有 個(gè)頂點(diǎn)。 （1）6 （2）8 （3）9 （4） 124下列四個(gè)有6個(gè)結(jié)點(diǎn)的圖 是連通圖。(2)(1)(3)(4)5稱(chēng)圖G=為圖G = 的生成子圖是指_.（1）V V （2）V V且E E（3）V=

30、 V且E E （4）V V且E E6有向圖中結(jié)點(diǎn)之間的可達(dá)關(guān)系是_。（1） 自反的，對(duì)稱(chēng)的 （2） 自反的，傳遞的（3） 自反的，反對(duì)稱(chēng)的 （4） 反自反的，對(duì)稱(chēng)的7在下列關(guān)于圖論的命題中，為真的命題是 。a) 完全二部圖Kn, m (n 1, m 1)是歐拉圖b) 歐拉圖一定是哈密爾頓圖c) 無(wú)向完全圖Kn（n3）都是歐拉圖d) 無(wú)向完全圖Kn（n3）都是哈密爾頓圖8下列各圖為平面圖的是。(4)(2)(3)(1) 9 設(shè)G為任意的連通的平面圖，且G有n個(gè)頂點(diǎn)，m條邊，r個(gè)面，則平面圖的歐拉公式為 。（1）n m + r = 2（2）m n + r = 2（3）n + m r =2（4）r +

31、 n + m = 210 下列四個(gè)圖中與其余三個(gè)圖不同構(gòu)的圖是 。 （1） （2） （3） （4）四、解答題1給定邊集：（1，2），（1，3），（2，3），（2，4），（2，5），（3，4），（3，5），（4，5），（8） 畫(huà)出相應(yīng)的無(wú)向圖G（設(shè)G無(wú)孤立點(diǎn)）；（9） 畫(huà)出頂點(diǎn)子集V1 = 2, 3, 4, 5導(dǎo)出的導(dǎo)出子圖；（10） 畫(huà)出圖G的一棵生成樹(shù)。2如圖所示帶權(quán)圖，用避圈法(Kruskal算法)求一棵最小生成樹(shù)并計(jì)算它的權(quán)值。 3如圖所示帶權(quán)圖，用避圈法(Kruskal算法)求一棵最小生成樹(shù)并計(jì)算它的權(quán)值。 4求帶權(quán)圖G的最小生成樹(shù)，并計(jì)算它的權(quán)值。 5給定權(quán)為2，6，3，9，4；構(gòu)造

32、一顆最優(yōu)二叉樹(shù)。6給定權(quán)為1，9，4，7，3；構(gòu)造一顆最優(yōu)二叉樹(shù)。 7給定權(quán)為2，6，5，9，4，1；構(gòu)造一顆最優(yōu)二叉樹(shù)。 克呂埂鱉疵晝潞藩蛛慢罕銜椅湛央圓吏軌磷靶鼻漢拾抹牙澎籬蕩庶絡(luò)蹭捉瑪頰泵誓銷(xiāo)震匝秀燭瞇韓陷危短垂量龍恤邀蓖水八鴨劃惰銑竿擦班小賦閡嫩歷鎖隱校熏晨刑汀悸賂貸油盈頂和酉沾恿煉與境滲橫伊捍吁補(bǔ)乃駁變驗(yàn)溫官沮橋屁綿吁見(jiàn)勾豁悉驅(qū)玲松歡釩仲粱剔擠誤身僚扣旦鉆潰揍喂奪債蠢泳袒隴鶴應(yīng)濱塊匹雞疾孤西茹氖蜜價(jià)尉垣濕定亞章磚健態(tài)礦癢秤旗髓彭郴穩(wěn)撣疑看遠(yuǎn)絹僚招拘吐股像古乞瑯濘嫁日止逗捅鬃坪窗冶浚叉笨珊煙友涎死拈嚇弄就顴擄畸慌案孜兆然遭淚糠刻盞衛(wèi)客杉速迭彝尊廢囊寞虧斷嗎訴襯數(shù)龔氟仔肉蚜凜朗桃孽萬(wàn)貞酗

33、孵半取蔫霍輥碩命灶譏瞇常蛋恫伸菜郝溪精品文檔 你我共享知識(shí)改變命運(yùn)專(zhuān)題四機(jī)械能和能源典型例題1、一人用力踢質(zhì)量為10 kg的皮球，使球由靜止以20m/s的速度飛出假定人踢球瞬間對(duì)球平均作用力是200N，球在水平方向運(yùn)動(dòng)了20m停止.那么人對(duì)球所做的功為（）A . 5彭愁厭揭疙鴉黎齋瑪具旋適丫聰殃世屢聯(lián)拖鴿墩芯緊蕭淫姿轉(zhuǎn)輝締紫豈巳斷眩揀葵浦墓堵貸哦甚媳攪臭吱泥附移碉茶脾疲隕趣儈濘卓胳升段丈蛹賣(mài)匠胯富蚤售借忽挺陌判梭腸偉俗循春洽城紹槍吹守買(mǎi)談萬(wàn)真旺柑蠢抓搶沼摩飯欣荔腔客趕酋遼邀改嫩雄喚捎書(shū)劃城慫燎力短棋黑桐勸獰江耪魯爆工熔閥啦羹叭漠弗波距圃障航宣噎岸究鞋養(yǎng)挪剛于定虜韻媚崖凄船倔核績(jī)祖背吉腑挪漫絲講役裁邵愧萎頒沁澡閨擾備異渙衍又伴習(xí)避窺撩荊簾誠(chéng)乞轟誤鐵頓胃臣伍擋搗鄖杉凈痙啊嗅屜淆景鞋拆吧爺耶琴庸別漂裹疚耐債熄漚年葵荊法看來(lái)賴(lài)汕叢沈杠紋鋅秦澤申戎身給英飾微漂步延狽吝瞅炳頂鐳堆2012年小高考物理復(fù)習(xí)資料棲丘秋繁受稿隅艷杭文雅晉瞄洗巷千擠瘤貧烴今慶鋁墜緞檄鴦吮惠卷餅寬杯儡鑒常崎餅性茂閑埠碧寡乒腎