離散試卷有答案

1、精選優(yōu)質文檔-傾情為你奉上一、單項選擇題 1設A = a, a ，P(A)表示集合A的冪集，下列哪一個是錯的？（ ） A B C D2設A=1 , 2 , 3 上的二元關系R = <1 , 1>, <1 , 2> , <1 , 3> , <3 , 3> , 則R具備性質（ ）A反對稱的，傳遞的 B反對稱的 C反對稱的, 自反的 D傳遞的3集合A = x, y, z , B = 1, 2, 3，下列A到B的二元關系中，哪一個能構成函數？（ ）A<x, 1>, <x, 2>, <y, 1>, <z, 3>

2、; B<x, 1>, <y, 3> C<x, 1>, <y, 3>, <z, 1> D<x, 2>, <y, 3>, <y, 2>4下列命題中（ ）是正確的。A歐拉圖的子圖一定是歐拉圖。 B哈密頓圖的子圖一定是哈密頓圖 。 C平面圖的子圖一定是平面圖 。 D樹的子圖一定是樹。5設有向圖D的鄰接矩陣為，則D中長度為3的通路總數有( ) 條。 A9 B10 C11 D12二、填空題 1公式的主析取范式為 。2某班共有學生60人，其中有25人訂雜志甲，26人訂雜志乙，26人訂雜志丙，11人訂雜志甲和乙，9

3、人訂雜志甲和丙，8人訂雜志乙和丙，還有8人未訂任何雜志，則三種雜志都訂的學生有 人。3設A = 2，4，5，10，12，20，R為A上的整除關系，則A的子集B = 4，10，12的極大元為 ，極小元為 ，上界為 ，下界為 。4設 ，則函數f是 （單射，滿射還是雙射）。5設集合A= a , b , c , d , e上的的劃分S =a，d，b，c，e，則由劃分S所確定的A上的等價關系R = 。6用kruskal算法求得下圖G的一棵最小生成樹為 。v8圖Gv1v2v3v4v512961248105711v6v737設連通平面圖G有4個面，9條邊，則G有 個結點。三、解答題 ( 4×8 =

4、 32分 )1將下列語句翻譯成命題邏輯公式或謂詞邏輯公式。(1)（4分）只有天下大雨，小明才乘公共汽車上學。(2)（4分）不是所有整數都是奇數。2設A = 1, 2, 3 上的二元關系R = <1, 1>, <1, 3>, <2, 1>，求R的關系矩陣，關系圖。3設是A到 A 的滿射，且，證明 。這里 表示A 上的恒等映射。4畫圖:(1)一個既沒有歐拉回路，又沒有哈密爾頓回路的圖； （2）一個具有歐拉回路和哈密爾頓回路的圖，并具體指出這兩個回路。 5.用哈夫曼算法求帶權為2,3,6，8,10,11的最優(yōu)二元樹并計算此最優(yōu)樹的權。6. 設一棵樹T有7片樹葉，3

5、個度數為3的結點，其余結點的度數均為4，求T的結點總數。7.用二元有序完全樹表示算術表達式并分別用波蘭符號法和逆波蘭符號法表示上述算術表達式。四、證明題 1用演繹法證明下述論斷的正確性。 2. 設R是集合A上的一個具有傳遞和自反性質的關系，T是A上的關系，使得 ，證明 T是A上的等價關系。3.試證明：樹是一個偶圖。4用演繹法證明。5 P335 27，28 這類題一 1 2 3 4 5 B A C C B二、12 3 3 10，12； 4，10； 沒有； 24 單射 567 7三、1解：（1）設P：天下大雨 Q：小明乘公共汽車上學，則有 （2）設Z（x）：x 是整數，E(x)：X是奇數 2解：

6、3略 4略 5解： 權 （ 定義10.3.7 ） 注：哈夫曼算法見書本（P292）算法10.3.6以及例10.3.9 6解：設T有x個4度結點，則T的結點總數 ，邊數 由握手定理 得 解得 所以結點總數 7 （1）×+dh÷gji÷fe×abc（2）算式的波蘭符號表示式為 （書上P295：先根次序遍歷算法 省去括號 ）（3）算式的逆波蘭符號表示式為 （同上，用后根遍歷，省去括號，規(guī)定 即為 ）四、1證明： 2證明：（1）對任意的，由R是自反的，得，所以，即T是自反的。 （2）對任意的，若，則 ，即有 從而，即T是對稱的。 （3）對任意的，若，則 且即 且

7、 又因為R是傳遞的 ， 所以 從而 ，所以T是傳遞的。 由（1）、（2）、（3）知T是等價關系。 3試證明：樹是一個偶圖。（P334:18）證：設 G=<V, E> 是一棵樹。任選 , 定義 V 的兩個子集如下：， . 現證明V1 中任二結點之間無邊存在。若存在一條邊 （u,v）, u,v, 由于樹中任意兩個結點之間僅存在唯一一條基本通路，故這條基本通路就是他們之間的短程線，設v0到u 的短程線為 ，則其長度為k+1,是偶數，因為（u,v），所以 ，v 是 到 v 的一條通路，且該通路的長度k+2 為奇數，從而它不是基本通路， 故v必與某個相同，從而 是G中的一條基本通路，這與G 是樹矛盾。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