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

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

02324201710

1、【單選題】令P：他怕困難，q：他戰(zhàn)勝困難，命題“他戰(zhàn)勝困難是因?yàn)樗慌吕щy”的

符號(hào)化形式為（）。

A:

B:

C:

答D:案：A

解析：“他不怕困難”是“他怕困難”的否定式，命題“他戰(zhàn)勝困難是因?yàn)樗慌吕щy”

化成基本結(jié)構(gòu)為“因?yàn)樗慌吕щy，所以他戰(zhàn)勝困難”，典型的蘊(yùn)涵式。因此，符號(hào)化形

式為，選A。

2、【單選題】令F(x)：x為蘋果，H(x,y)：x與y完全相同，L(x,y):x=y，則命題“沒(méi)有完

全相同的蘋果”的符號(hào)化形式為（）。

A:

B:

C:

答D:案：B

解析：

本題命題“沒(méi)有完全相同的蘋果”中，沒(méi)有指明個(gè)體域，因而采用全總個(gè)體域。其中“相

同的蘋果”需要任意兩個(gè)蘋果進(jìn)行比較，即是“兩個(gè)蘋果”同時(shí)“非同一個(gè)蘋果”且“完

全相同”，符號(hào)化為“”；“沒(méi)有”為否定詞；則“沒(méi)有完全相同的蘋

果”符號(hào)化為“”，因此選B。

3、【單選題】一棵樹(shù)有2個(gè)4度結(jié)點(diǎn)，3個(gè)3度結(jié)點(diǎn)，其余為樹(shù)葉，則該樹(shù)中樹(shù)葉個(gè)數(shù)是

（）。

7

8

A:

9

B:

10

C:

答D:案：C

解析：根據(jù)無(wú)向樹(shù)的定義，2個(gè)4度結(jié)點(diǎn)可以組成“艸”樹(shù)狀，3個(gè)3度節(jié)點(diǎn)可以通過(guò)

“艸”6個(gè)結(jié)點(diǎn)中選擇任意3個(gè)結(jié)點(diǎn)上分別懸掛2片樹(shù)葉即可。這樣樹(shù)葉總個(gè)數(shù)為9。故

選C。

4、【單選題】設(shè)集合A={a,b,c,d}，現(xiàn)有A上的二元關(guān)系R={<a,b>,<b,c>,<c,b>,<

b,a>,}，則A是（）。

自反的

對(duì)稱的

A:

反對(duì)稱的

B:

傳遞的

C:

答D:案：B

解析：

二元關(guān)系R中典型滿足即滿足對(duì)稱的關(guān)系的定義。故選B。

5、【單選題】下圖中為歐拉圖的是（）。

A:

B:

C:

答D:案：C

解析：根據(jù)歐拉圖的定義，具有歐拉回路的圖為歐拉圖，其充分必要條件是連通的且不含

有奇度頂點(diǎn)。而ABD三個(gè)選項(xiàng)中均有奇度頂點(diǎn)，故選C。

6、【單選題】下列謂詞公式中，不是前束范式的為（）。

A:

B:

C:

答D:案：D

解析：根據(jù)一階邏輯前束范式的定義，所有約束量詞只能在公式最前面，后面公式不能出

現(xiàn)量詞，排除選項(xiàng)ABC，故選D。

7、【單選題】表示集合之間關(guān)系的圖是（）。

文氏圖

哈斯圖

A:

歐拉圖

B:

樹(shù)

C:

答D:案：A

解析：根據(jù)集合代數(shù)理論，表示集合之間關(guān)系與運(yùn)算的圖為文氏圖，故選A。

8、【單選題】無(wú)向完全圖的

邊的條數(shù)為（）。

10

15

A:

20

B:

30

C:

答D:案：B

解析：根據(jù)無(wú)向完全圖的定義，可以6結(jié)點(diǎn)中每一個(gè)都與其余5個(gè)相鄰接，其邊數(shù)計(jì)算公

式為n(n-1)/2，帶入n=6，則為15，故選B。

9、【單選題】設(shè)T是n階樹(shù)(n≥2)，則T不具有的性質(zhì)是（）。

連通圖

哈密頓圖

A:

有n－1條邊

B:

至少有兩片樹(shù)葉

C:

答D:案：B

解析：根據(jù)樹(shù)的定義及等價(jià)命題，n階樹(shù)一定是連通的，且有n-1條邊，至少有兩片樹(shù)

葉，但不會(huì)有回路，因此不是哈密頓圖（具有哈密頓回路的圖），故選B。

10、【單選題】設(shè)R、S均為集合A上的二元關(guān)系，下面命題正確的是（）。

A:

B:

C:

答D:案：A

解析：根據(jù)二元關(guān)系的運(yùn)算規(guī)律，兩個(gè)二元關(guān)系的右復(fù)合只有自反性保持不變，故選A。

11、【單選題】以下關(guān)于圖的矩陣的描述，正確的是（）。

鄰接矩陣即關(guān)系矩陣

可達(dá)矩陣是針對(duì)無(wú)向圖的

A:

無(wú)向圖有鄰接矩陣

B:

可達(dá)矩陣是針對(duì)有向圖的

C:

答D:案：C

解析：根據(jù)圖的矩陣的描述理論，鄰接矩陣與關(guān)系矩陣是不同的，無(wú)向圖與有向圖都有關(guān)

系矩陣，鄰接矩陣僅應(yīng)用于有向圖，故選C。

12、【單選題】一個(gè)6階連通圖的邊數(shù)至少為（）。

4

5

A:

6

B:

7

C:

答D:案：B

解析：根據(jù)連通圖的概念，必須存在6個(gè)頂點(diǎn)至少經(jīng)過(guò)一次的通路，最簡(jiǎn)單的通路就是6

個(gè)點(diǎn)用5條線連接而沒(méi)有圈的情況，故選B。

13、【單選題】下列關(guān)于反函數(shù)的命題，正確的是（）。

單射函數(shù)有反函數(shù)

任意函數(shù)均有反函數(shù)

A:

滿射函數(shù)有反函數(shù)

B:

雙射函數(shù)有反函數(shù)

C:

答D:案：D

解析：根據(jù)反函數(shù)的定義，雙射函數(shù)有反函數(shù)，雙射函數(shù)的反函數(shù)也是雙射函數(shù)，故選

D。

14、【單選題】一個(gè)6階圖，其各結(jié)點(diǎn)度數(shù)之和不可能為（）。

10

12

A:

15

B:

20

C:

答D:案：C

解析：根據(jù)歐拉握手定理，無(wú)向圖的各結(jié)點(diǎn)度數(shù)之和等于邊數(shù)的2倍，因此總度數(shù)不會(huì)是

奇數(shù)，故選C。

15、【單選題】在整數(shù)集合Z上定義*運(yùn)算如下：a、b∈Z，a*b=a+b－10，則代數(shù)系統(tǒng)<Z,*>

是（）。

格

環(huán)

A:

域

B:

群

C:

答D:案：D

解析：根據(jù)運(yùn)算規(guī)律a*b=a+b－10，可以看到具有單位元：由a*e=a推出e=10，同時(shí)具有

逆元：由a*a-1=e推出a-1=20-a，既有單位元又有逆元，恰為群的定義，故選D。

16、【問(wèn)答題】設(shè)Σ={a,b}是字母表，Σ*表示由Σ上的字符構(gòu)成的有限長(zhǎng)度的串的集合

（包含長(zhǎng)度為0的串，即空串在內(nèi)），A={a,b,aa,bb,aaa,bbb}，

B={ω∣ω∈Σ*∧│ω│≥2}，C={ω∣ω∈Σ*∧│ω│≤2}，則A－(B∩C)=________。

答案：{a,b,aaa,bbb}

解析：根據(jù)題意，B∩C=｛所有長(zhǎng)度為2的字符串｝=｛aa,bb,ab,ba｝，則A－(B∩C)=

{a,b,aaa,bbb}。

17、【問(wèn)答題】在整數(shù)域中，命題公式

的真值為_(kāi)_______，命題公式

的真值為_(kāi)_______。

答案：T，F(xiàn)

解析：根據(jù)命題公式的意義，第一個(gè)公式表示對(duì)任意一個(gè)x存在一個(gè)y與之相乘為0，顯

然在整數(shù)域中只要取y=0即可滿足，因此是正確的；第二個(gè)公式表示存在一個(gè)x與任意一

個(gè)y相乘為1，顯然在整數(shù)域是不可能實(shí)現(xiàn)的，因此是錯(cuò)誤的。

18、【問(wèn)答題】設(shè)A為非空有限集合，P(A)為A的冪集，∪為集合的并運(yùn)算，群<P(A)，∪>

中，單位元是________，零元是________。

答案：

解析：

根據(jù)單位元定義，設(shè)任意集合則由即為單位

元；根據(jù)零元的定義，設(shè)任意集合即A為零元。

19、【問(wèn)答題】一個(gè)手鐲等距離地鑲嵌著5顆彩珠，每顆彩珠可以從紅、白、藍(lán)、綠、黃5

種顏色中挑選。如果要求手鐲上的彩珠顏色都不相同，則可以構(gòu)成________種不同顏色彩珠

分布的手鐲。

答案：120

解析：顏色集合由紅、白、藍(lán)、綠、黃5種顏色組成，根據(jù)排列組合知識(shí)可得5！=120。

20、【問(wèn)答題】某連通平面圖有6個(gè)頂點(diǎn)，其平面表示中共有8個(gè)面，則其邊有________

條。

答案：12

解析：根據(jù)連通平面圖的歐拉定理：頂點(diǎn)數(shù)－邊數(shù)＋面數(shù)=2，可得邊數(shù)=6+8-2=12。

21、【問(wèn)答題】設(shè)有集合A={a,b,c,d}上的二元關(guān)系R={<a,b>,<b,a>,<c,c>,<

d,d>}，則R2=______，R3=______。

答案：{<a,a>,<b,b>,<c,c>,<d,d>}，{<a,b>,<b,a>,<c,c>,<d,d>}

解析：

于是R2={<a,a>,<b,b>,<c,c>,<d,d>}，R3={<a,b>,<b,a>,<

c,c>,<d,d>}

22、【問(wèn)答題】為了從無(wú)向完全圖K6中得到其生成樹(shù)，至少需要?jiǎng)h除_______條邊

答案：10

解析：無(wú)向完全圖K6共有邊數(shù)為n(n-1)/2=15條，而有n個(gè)頂點(diǎn)的樹(shù)有n－1條邊，即有

6－1=5條邊，所以至少要?jiǎng)h除15－5=10條邊。

23、【問(wèn)答題】設(shè)有集合A={a,b,c}上的二元關(guān)系

則R1的自反閉包

r(R1)=_______，R1的對(duì)稱閉包s(R1)=_______。

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

{<a,b>,<a,c>,<c,b>,<b,a>,<c,a>,<b,c>}

解析：

于是r(R1)={<a,b>,<a,c>,<c,b>,<a,a>,<b,b>,<c,c>}，

s(R1)={<a,b>,<a,c>,<c,b>,<b,a>,<c,a>,<b,c>}

24、【問(wèn)答題】一個(gè)無(wú)向圖有21條邊，有3個(gè)4度結(jié)點(diǎn)，其余結(jié)點(diǎn)均為3度，則其結(jié)點(diǎn)共

有________個(gè)。

答案：13

解析：根據(jù)歐拉握手定理，無(wú)向圖的各結(jié)點(diǎn)度數(shù)之和等于邊數(shù)的2倍，設(shè)共有x個(gè)節(jié)點(diǎn)，

3*4+（x－3）*3=21*2，則x=13。

25、【問(wèn)答題】設(shè)集合A={1,2,3}，集合B={a,b,c,d,e}，則│A×B│=________，而

│P(A)×B│=________。

答案：15，40

解析：│A│=3，│B│=5，所以│A×B│=3×5=15│P(A)│=2│A│=23=8，│B│=5，所

以│P(A)×B│=8×5=40

26、【問(wèn)答題】用列真值表的方法說(shuō)明下列邏輯等價(jià)式成立

答案：

解析：邏輯等價(jià)式必須具有相同的真值表，這是等價(jià)式的充分必要條件。

27、【問(wèn)答題】用等值演算法推導(dǎo)命題公式

的主析取范式。

答案：

解析：利用等值式的運(yùn)算規(guī)律與置換原則轉(zhuǎn)換成主析取范式。

28、【問(wèn)答題】設(shè)解釋Ⅰ為：個(gè)體域D={a,b}，F(xiàn)(x)與G(x)為2個(gè)一元謂詞，且

F(a)=0，F(xiàn)(b)=1，G(a)=1，G(b)=0。在Ⅰ下，求命題公式

的真值。

答案：

29、【問(wèn)答題】設(shè)集合S={1,2,3}，題29圖為S上的二元關(guān)系R的關(guān)系圖

（1）寫出R的集合表達(dá)

式；（2）寫出R的關(guān)系矩陣。

答案：

解析：根據(jù)二元關(guān)系R的關(guān)系圖的集合表達(dá)式方法與關(guān)系矩陣構(gòu)造方法即得。

30、【問(wèn)答題】求下述集合等式成立的充要條件，并證明結(jié)論

。

答案：

解析：根據(jù)集合的運(yùn)算規(guī)律證明即可

31、【問(wèn)答題】設(shè)n階無(wú)向簡(jiǎn)單圖G=<V,E>，其中邊數(shù)滿足：│E│>(n－1)(n－2)/2，證明

G是連通圖。

答案：證明：假設(shè)G不是連通圖，不妨設(shè)G有兩個(gè)連通分支G1<V1,E1>和G2<V2,E2>，且

│V1│=n1，│V2│=n2，易見(jiàn)n1+n2=n，由于n1≥1，n2≥1，所以n1*n2-(n1+n2)+1≥0

（*）而│E1│≤n1(n1-1)/2,│E2│≤n2(n2-1)/2，從而│E│=│E1│+│E2│