2016年10月自考02324離散數(shù)學(xué)試題及答案含解析

離散數(shù)學(xué)年月真題

02324201610

1、【單選題】

A:

B:

C:

答D:案：C

解析：

給定一個(gè)謂詞公式A，其中有一部分公式形如，則稱它為A的x約束部

分，稱B(x)為相應(yīng)量詞的作用域或轄域。

2、【單選題】設(shè)無向樹T有3個(gè)度數(shù)為4的結(jié)點(diǎn)，其余結(jié)點(diǎn)都為樹葉，則T的結(jié)點(diǎn)數(shù)為

10

11

A:

12

B:

13

C:

答D:案：B

解析：設(shè)無向樹T的結(jié)點(diǎn)個(gè)數(shù)為x，則其樹葉數(shù)為x-3。由握手定理及樹的性質(zhì)得方程：

3×4+（x-3）=2e=2(x-1)，解得x=11.

3、【單選題】設(shè)集合A有3個(gè)元素，則A中的劃分有

3個(gè)

5個(gè)

A:

6個(gè)

B:

9個(gè)

C:

答D:案：B

解析：3個(gè)元素的集合可能產(chǎn)生的所有劃分有如下幾種情況：（1）劃分塊數(shù)為1的劃分?jǐn)?shù)

有1個(gè)；（2）劃分塊數(shù)為2的劃分?jǐn)?shù)有3個(gè)；（3）劃分塊數(shù)為3的劃分?jǐn)?shù)有1個(gè)。所以

共有5種不同的劃分。

4、【單選題】下列關(guān)系不可能是相容關(guān)系的是

恒等關(guān)系

全域關(guān)系

A:

等價(jià)關(guān)系

B:

擬序關(guān)系

C:

答D:案：D

解析：滿足自反性和對稱性的關(guān)系稱為相容關(guān)系。恒等關(guān)系、全域關(guān)系、等價(jià)關(guān)系均滿足

自反性、對稱性和傳遞性。滿足反自反和傳遞性的關(guān)系稱為擬序關(guān)系。所以，擬序關(guān)系可

能是相容關(guān)系。

5、【單選題】設(shè)論域?yàn)檎麛?shù)集，下列命題中真值為假的是

A:

B:

C:

答D:案：C

解析：選項(xiàng)A、D中，令x=0,y=0,則x+y=0，所以A為真，D也為真。選項(xiàng)B中令y=-x，

則B為真。故真值為假的是C。

6、【單選題】4個(gè)結(jié)點(diǎn)的非同構(gòu)的無向樹的數(shù)目是

5

4

A:

3

B:

2

C:

答D:案：D

解析：根據(jù)無向樹的性質(zhì)，4個(gè)結(jié)點(diǎn)的無向樹有3條邊。4個(gè)結(jié)點(diǎn)構(gòu)成的無向樹中的樹葉

數(shù)（即度數(shù)為1的結(jié)點(diǎn)）可能有2個(gè)或3個(gè)兩種情形。故其非同構(gòu)的無向樹的數(shù)目只能是

2個(gè)。

7、【單選題】下列命題公式是永真式的為

A:

B:

C:

答D:案：C

解析：

8、【單選題】下列語句是原子命題的為

x+y>xy

請給我來點(diǎn)掌聲吧

A:

小明既愛唱歌又愛跳舞

B:

火星上有生物

C:

答D:案：D

解析：不能再分解成更簡單的命題，稱為原子命題。A中含有項(xiàng)，不是謂詞邏輯中的原子

命題；B不是命題；C是復(fù)合命題；D是命題邏輯中的原子命題。

9、【單選題】設(shè)Z為整數(shù)集合，則下列集合關(guān)于數(shù)的加法運(yùn)算不能構(gòu)成獨(dú)異點(diǎn)的是

A:

B:

C:

答D:案：C

解析：獨(dú)異點(diǎn)是滿足封閉、可結(jié)合、有幺元的代數(shù)系統(tǒng)。由于C中無幺元，故C不是獨(dú)異

點(diǎn)。

10、【單選題】則既是S的

元素又是S的子集的為

A:

B:

C:

答D:案：B

解析：A中的{1}只是S的元素，而不是子集；C中的{Ф}既不是S的元素，也不是其子

集；D中的{1,2}只是S的元素。

11、【單選題】設(shè)p：他怕困難；q:他獲得成功。命題“除非他不怕困難，否則他不會獲得

成功”可符號化為

A:

B:

C:

答D:案：A

解析：原命題可翻譯為“如果他獲得成功，則他一定不怕困難”。

12、【單選題】在整數(shù)集Z上，下列運(yùn)算滿足結(jié)合律的是

A:

B:

C:

答D:案：D

解析：

13、【單選題】下列圖對應(yīng)的格是有補(bǔ)格的為

A:

B:

C:

答D:案：D

解析：設(shè)<L,∧,∨,0,1>是有界格,a∈L,若存在b∈L使得a∧b=0和a∨b=1成立,

則稱b是a的補(bǔ)元。4個(gè)選項(xiàng)均為有界格，1為全上界，0為全下界。但A中，b、c均沒

有補(bǔ)元。B中b沒有補(bǔ)元。C中d沒有補(bǔ)元。D中a、b互為補(bǔ)元；c、d互為補(bǔ)元，所以D

是有補(bǔ)格。

14、【單選題】設(shè)G為連通的無向簡單圖。若G恰有2個(gè)奇度結(jié)點(diǎn)，則G一定具有

歐拉回路

歐拉通路

A:

哈密爾頓回路

B:

哈密爾頓通路

C:

答D:案：B

解析：圖中行遍所有頂點(diǎn)且恰好經(jīng)過每條邊一次的通路稱為歐拉通路。無向圖G是半歐拉

圖（即有歐拉通路）當(dāng)且僅當(dāng)G連通且恰有兩個(gè)奇度頂點(diǎn)。

15、【單選題】設(shè)F（x）：x是火車；G（y）：y是汽車；H（x，y）：x比y快；則下列

語句可以表示成公式的是

每列火車都比所有汽車快

每列火車郡比某些汽車快

A:

某些火車比某些汽車快

B:

某些火車比所有汽車快

C:

答D:案：D

解析：存在量詞表示“存在一個(gè)（些）”、“某些”。

16、【問答題】

答案：{<4,2>}

解析：復(fù)合運(yùn)算有兩種，左復(fù)合和右復(fù)合。本課程的教材中將復(fù)合約定成右復(fù)合。

17、【問答題】設(shè)G是一個(gè)有11個(gè)頂點(diǎn)的簡單無向圖。如果G恰有一個(gè)回路，則G的邊數(shù)

最大是______________

答案：11

解析：刪除G中回路上的任一條邊，則G中無回路。此時(shí)，圖中邊數(shù)最大時(shí)，圖G一定是

連通圖，也即，刪除G中回路上的任一條邊后，得到一顆無向樹，根據(jù)樹的性質(zhì)，其邊數(shù)

為11-1=10，加上刪除的回路上的邊，G中共有11條邊。

18、【問答題】

答案：{1,3,4}，{a,c,d}

解析：domR和ranR分別是關(guān)系R的定義域和值域。

19、【問答題】

答案：M100

解析：根據(jù)大項(xiàng)編碼規(guī)則，其對應(yīng)的大項(xiàng)應(yīng)為M100

20、【問答題】

答案：{<a,b>,<b,a>,<b,c>,<c,b>}；{<a,b>,<b,c>,<a,c>}

解析：s(R)=R∪R-1,t(R)=R∪R2∪R3∪…∪Rn

21、【問答題】

答案：{1,4},{1,4,a,c}

解析：

22、【問答題】若連通平面圖G有8條邊，3個(gè)面，則G有___________個(gè)結(jié)點(diǎn)。

答案：7

解析：根據(jù)歐拉公式，設(shè)G為n階m條邊r個(gè)面的連通平面圖，則n-m=2。因此，n=m-

r+2=8-3+2=7。

23、【問答題】

答案：2,16

解析：設(shè)o為S上的二元運(yùn)算,如果存在e∈S，使得對任意x∈S都有eox=xoe=x，則稱e

是S中關(guān)于o運(yùn)算的幺元（也稱單位元）。2，4，8，16四個(gè)元素與2的最小公倍數(shù)分別是

2，4，8，16，根據(jù)定義，2是該代數(shù)系統(tǒng)的幺元。設(shè)o為S上的二元運(yùn)算,如果存在

θ∈S，使得對任意x∈S都有θox=xoθ=θ，則稱θ是S中關(guān)于o運(yùn)算的零元。2，4，8，

16四個(gè)元素與16的最小公倍數(shù)均為16，根據(jù)定義，16是該代數(shù)系統(tǒng)的零元。

24、【問答題】設(shè)論域是全體人類，F(xiàn)（x）：x能呼吸，要求只能使用存在量詞，命題“所

有人都能呼吸”可符號化為___________________。

答案：

解析：

“所有人都能呼吸”可理解為“不存在不能呼吸的人”。也可先符號化“所有人都能呼

吸”為，然后再利用等值演算轉(zhuǎn)化為只使用存在量詞。

25、【問答題】含有n個(gè)命題變元的命題公式，共有_________________組指派

答案：2n

解析：設(shè)A是一命題公式，P1,P2,…,Pn為出現(xiàn)在A中的所有命題變元，對P1,P2,…,Pn

各指定一個(gè)真值，稱為對A的一組指派或賦值。

26、【問答題】構(gòu)造命題公式

的真值表。

答案：

解析：

構(gòu)造真值表時(shí)，可先構(gòu)造每個(gè)子公式的真值表。

27、【問答題】利用等值演算法求命題公式

的主析取范式。

答案：

解析：

用等值演算法求主析取范式，其具體步驟包括：①化歸為析取范式。②除去析取范式中

所有永假的簡單合取式。③在簡單合取式中，將重復(fù)出現(xiàn)的合取項(xiàng)和相同變元合并。④

在簡單合取式中補(bǔ)入沒有出現(xiàn)的命題變元，即添加∧(p∨?p)，再用分配律展開，最后合

并相同的小項(xiàng)。建議在利用等值演算法求完主范式后，再利用真值表法比

較一下結(jié)果是否相同？

28、【問答題】

答案：

解析：

（1）哈斯圖是利用偏序自反、反對稱、傳遞性簡化的關(guān)系圖。其實(shí)質(zhì)是偏序關(guān)系的覆蓋

關(guān)系的關(guān)系圖。其特點(diǎn)是：每個(gè)結(jié)點(diǎn)沒有環(huán)，兩個(gè)連通的結(jié)點(diǎn)之間的序關(guān)系通過結(jié)點(diǎn)位置

的高低表示，位置低的元素的順序在前，具有覆蓋關(guān)系的兩個(gè)結(jié)點(diǎn)之間連邊。

29、【問答題】設(shè)圖G如題29圖所示。（1）寫出圖G的鄰接矩陣；（2）G中長度為4

的通路有幾條？（3）上問中有幾條回路？

答案：

解析：

30、【問答題】

答案：

解析：

31、【問答題】設(shè)無向圖G有7個(gè)頂點(diǎn)，每個(gè)頂點(diǎn)的度數(shù)不是4就是5。證明：G中至少有5

個(gè)度數(shù)為4的頂點(diǎn)或至少有4個(gè)度數(shù)為5的頂點(diǎn)。

答案：

解析：握手定理的簡單應(yīng)用。任意無向圖和有向圖的所有頂點(diǎn)度數(shù)之和都等于邊數(shù)的2

倍。

32、【問答題】

答案：

解析：

證明兩個(gè)集合相等，最基本的方法是互為子集法。即要證明X=Y，即證明：

33、【問答題】證明：H關(guān)于

矩陣乘法構(gòu)成一個(gè)群。

答案：

解析：代數(shù)系統(tǒng)是否為群，只需要逐一驗(yàn)證以下四個(gè)條件：(1)封閉性(2)結(jié)合律(3)有

幺元(4)每個(gè)元素有逆元

34、【問答題】今有a、b、c、d、e、f、g共7個(gè)球類運(yùn)動愛好者，已知下列事實(shí)：a喜歡

籃球運(yùn)動；b喜歡籃球運(yùn)動和足球運(yùn)動；c喜歡籃球、排球和乒乓球運(yùn)動；d喜歡網(wǎng)球和足球

運(yùn)動；e喜歡羽毛球和排球運(yùn)動；f喜歡棒球、網(wǎng)球和乒乓球運(yùn)動；g喜歡棒球和羽毛球運(yùn)

動。試問：這7個(gè)人應(yīng)如何圍圓桌排座位，才能使每個(gè)人和他身邊的人有共同球類愛好話

題。須寫出所有可能方案。

答案：

解析：如果兩個(gè)人愛好同一種球類，則用無向邊連接它們，得到圖34-1為按題意構(gòu)造的

關(guān)系圖；求解方案實(shí)際上是尋找圖34-1中是否有哈密頓回路，該哈密頓圖中每個(gè)結(jié)點(diǎn)的

度數(shù)均為2。所以在刪邊時(shí)應(yīng)考慮刪除度數(shù)大于2的結(jié)點(diǎn)關(guān)聯(lián)的邊。由此判斷：因?yàn)榻Y(jié)點(diǎn)

c的度數(shù)為4，所以必須刪掉結(jié)點(diǎn)c關(guān)聯(lián)的兩條邊，邊bc、