離散試卷有答案 (1).doc

一、單項(xiàng)選擇題 1設(shè)A = a, a ，P(A)表示集合A的冪集，下列哪一個(gè)是錯(cuò)的？（ ） A B C D2設(shè)A=1 , 2 , 3 上的二元關(guān)系R = , , , , 則R具備性質(zhì)（ ）A反對(duì)稱的，傳遞的 B反對(duì)稱的 C反對(duì)稱的, 自反的 D傳遞的3集合A = x, y, z , B = 1, 2, 3，下列A到B的二元關(guān)系中，哪一個(gè)能構(gòu)成函數(shù)？（ ）A, , , B, C, , D, , 4下列命題中（ ）是正確的。A歐拉圖的子圖一定是歐拉圖。 B哈密頓圖的子圖一定是哈密頓圖 。 C平面圖的子圖一定是平面圖 。 D樹(shù)的子圖一定是樹(shù)。5設(shè)有向圖D的鄰接矩陣為，則D中長(zhǎng)度為3的通路總數(shù)有( ) 條。 A9 B10 C11 D12二、填空題 1公式的主析取范式為 。2某班共有學(xué)生60人，其中有25人訂雜志甲，26人訂雜志乙，26人訂雜志丙，11人訂雜志甲和乙，9人訂雜志甲和丙，8人訂雜志乙和丙，還有8人未訂任何雜志，則三種雜志都訂的學(xué)生有 人。3設(shè)A = 2，4，5，10，12，20，R為A上的整除關(guān)系，則A的子集B = 4，10，12的極大元為 ，極小元為 ，上界為 ，下界為 。4設(shè) ，則函數(shù)f是 （單射，滿射還是雙射）。5設(shè)集合A= a , b , c , d , e上的的劃分S =a，d，b，c，e，則由劃分S所確定的A上的等價(jià)關(guān)系R = 。6用kruskal算法求得下圖G的一棵最小生成樹(shù)為 。v8圖Gv1v2v3v4v512961248105711v6v737設(shè)連通平面圖G有4個(gè)面，9條邊，則G有 個(gè)結(jié)點(diǎn)。三、解答題 ( 48 = 32分 )1將下列語(yǔ)句翻譯成命題邏輯公式或謂詞邏輯公式。(1)（4分）只有天下大雨，小明才乘公共汽車(chē)上學(xué)。(2)（4分）不是所有整數(shù)都是奇數(shù)。2設(shè)A = 1, 2, 3 上的二元關(guān)系R = , , ，求R的關(guān)系矩陣，關(guān)系圖。3設(shè)是A到 A 的滿射，且，證明 。這里 表示A 上的恒等映射。4畫(huà)圖:(1)一個(gè)既沒(méi)有歐拉回路，又沒(méi)有哈密爾頓回路的圖； （2）一個(gè)具有歐拉回路和哈密爾頓回路的圖，并具體指出這兩個(gè)回路。 5.用哈夫曼算法求帶權(quán)為2,3,6，8,10,11的最優(yōu)二元樹(shù)并計(jì)算此最優(yōu)樹(shù)的權(quán)。6. 設(shè)一棵樹(shù)T有7片樹(shù)葉，3個(gè)度數(shù)為3的結(jié)點(diǎn)，其余結(jié)點(diǎn)的度數(shù)均為4，求T的結(jié)點(diǎn)總數(shù)。7.用二元有序完全樹(shù)表示算術(shù)表達(dá)式并分別用波蘭符號(hào)法和逆波蘭符號(hào)法表示上述算術(shù)表達(dá)式。四、證明題 1用演繹法證明下述論斷的正確性。 2. 設(shè)R是集合A上的一個(gè)具有傳遞和自反性質(zhì)的關(guān)系，T是A上的關(guān)系，使得 ，證明 T是A上的等價(jià)關(guān)系。3.試證明：樹(shù)是一個(gè)偶圖。4用演繹法證明。5 P335 27，28 這類題一 1 2 3 4 5 B A C C B二、12 3 3 10，12； 4，10； 沒(méi)有； 24 單射 567 7三、1解：（1）設(shè)P：天下大雨 Q：小明乘公共汽車(chē)上學(xué)，則有 （2）設(shè)Z（x）：x 是整數(shù)，E(x)：X是奇數(shù) 2解： 3略 4略 5解： 權(quán) （ 定義10.3.7 ） 注：哈夫曼算法見(jiàn)書(shū)本（P292）算法10.3.6以及例10.3.9 6解：設(shè)T有x個(gè)4度結(jié)點(diǎn)，則T的結(jié)點(diǎn)總數(shù) ，邊數(shù) 由握手定理 得 解得 所以結(jié)點(diǎn)總數(shù) 7 （1）+dhgjifeabc（2）算式的波蘭符號(hào)表示式為 （書(shū)上P295：先根次序遍歷算法 省去括號(hào) ）（3）算式的逆波蘭符號(hào)表示式為 （同上，用后根遍歷，省去括號(hào)，規(guī)定 即為 ）四、1證明： 2證明：（1）對(duì)任意的，由R是自反的，得，所以，即T是自反的。 （2）對(duì)任意的，若，則 ，即有 從而，即T是對(duì)稱的。 （3）對(duì)任意的，若，則 且即 且 又因?yàn)镽是傳遞的 ， 所以 從而 ，所以T是傳遞的。 由（1）、（2）、（3）知T是等價(jià)關(guān)系。 3試證明：樹(shù)是一個(gè)偶圖。（P334:18）證：設(shè) G= 是一棵樹(shù)。任選 , 定義 V 的兩個(gè)子集如下：， . 現(xiàn)證明V1 中任二結(jié)點(diǎn)之間無(wú)邊存在。若存在一條邊 （u,v）, u,v, 由于樹(shù)中任意兩個(gè)結(jié)點(diǎn)之間僅存在唯一一條基本通路，故這條基本通路就是他們之間的短程線，設(shè)v0到u 的短程線為 ，則其長(zhǎng)度為k+1,是偶數(shù)，因?yàn)椋╱,v），所以 ，v 是 到 v 的一條通路，且該通路的長(zhǎng)度k+2 為奇數(shù)，從而它不是基本通路， 故v必與某個(gè)相同，從而 是G中的一條基本通路，這與G 是樹(shù)矛盾。4用演繹法證明。證明： (1) P （2） ES，(1) （3） P （4） US，（3） （5） T，（4） （6） T，（5）（2） （7） P （8） US，（7） （6分）（9） T，（8）