2023年自考類計算機類(工學(xué)類)離散數(shù)學(xué)歷年高頻考題帶答案難題附詳解

2023年自考類計算機類(工學(xué)類)離散數(shù)學(xué)歷年高頻考題帶答案難題附詳解（圖片大小可自由調(diào)整）第1卷一.歷年考點試題黑鉆版(共50題)1.證明：邊e是圖G的一條割邊，當(dāng)且僅當(dāng)圖G中不存在包含邊e的簡單回路。2.設(shè)A、B、C是集合，若A∩B=A∩C，～A∩B=～A∩C，證明：B=C。3.利用等值演算法求命題公式(P∧(Q→R))→Q的主合取范式。4.3個頂點可構(gòu)成______分不同構(gòu)的簡單無向圖，可構(gòu)成______個不同構(gòu)的簡單有向圖。5.用矩陣的方法求下圖中頂點v3、v4之間長度為3的通路的數(shù)目。

6.設(shè)R={〈3，1〉，〈2，3〉，〈5，3〉，〈3，4〉}是集合A={1，2，3，4，5}上的關(guān)系，則domR=______，ranR=______。7.用推理方法證明：。8.設(shè)R為實數(shù)集，At={x|x∈R∧Kt≤x≤t+1}，其中K0=K2=0，K1=K3=-1，K4=-2，令S={At|t=0，1，2，3，4}。畫出偏序集＜S，＞的哈斯圖并求它的極大元、極小元、最大元、最小元。說明該偏序集構(gòu)成什么格。9.在Klein四元群G={e，a，b，c}中，______是1階元，______是2階元。10.用二叉樹表示算術(shù)表達式((a-b*c)*d+e)÷(f*g+h)。11.格L是分配格，當(dāng)且僅當(dāng)L既不含有與______同構(gòu)的子格，也不含有與______同構(gòu)的子格。12.一棵樹有4個3度結(jié)點，3個2度結(jié)點，其他的都是1度結(jié)點，那么這棵樹的結(jié)點數(shù)是______A.10B.11C.12D.1313.關(guān)于謂詞公式，下列描述中錯誤的是______

A．的轄域是

B．z是該謂詞公式的約束變元

C．的轄域是P(x，y)

D．x是該謂詞公式的約束變元14.設(shè)群G=〈M2(R)，—〉，H={A|A∈M2(R)，且A=AT}，其中AT表示A的轉(zhuǎn)置，證明：H是G的子群。15.含n個命題變元的任一命題公式的指派個數(shù)是______A.nB.n2C.2nD.22n16.任意一條鏈都是______A.分配格B.有補格C.有界格D.有界分配格17.下列公式不是合式公式的為______

A．P→Q∧·R·

B．﹁P→(Q→R)

C．P→(P∨Q)

D．18.設(shè)A，B，C是集合。證明：(A-B)-C=A-(B∪C)。19.下列屬于兩個命題變元P、Q的大項的是______A.﹁P∧P∧QB.﹁P∨P∨QC.﹁P∧QD.﹁P∨Q20.證明：整數(shù)集Z上的小于等于關(guān)系“≤”是一個偏序關(guān)系。21.設(shè)A={＜a，b＞|a，b為正整數(shù)}，在A上定義二元關(guān)系～如下：＜a，b＞～＜c，d＞當(dāng)且僅當(dāng)a+b=c+d。證明：～是一個等價關(guān)系。22.一棵樹有2個3度結(jié)點，其余結(jié)點都是葉子，則葉子數(shù)是______A.7B.6C.5D.423.無向圖G的邊數(shù)m=16，且G有3個4度頂點，4個3度頂點，其余頂點的度數(shù)均小于3，則G中至少應(yīng)有______個頂點。A.10B.11C.12D.1324.下列命題公式為永假式的是______A.﹁(P→Q)B.﹁(P→Q)∧QC.(P→Q)∨QD.﹁P∧(P→Q)25.設(shè)A={1，2，3，4}上的關(guān)系R={＜1，2＞，＜2，4＞，＜3，3＞，＜1，3＞}，則R的自反閉包，r(R)=______，對稱閉包s(R)=______。26.若是格，，則下列說法正確的是______A.子集{a，b)在A中有最大下界，沒有最小上界B.子集{a，b}在A中沒有最大下界，有最小上界C.子集{a，b}在A中沒有最大下界，也沒有最小上界D.子集{a，b}在A中有最大下界，也有最小上界27.對公式中的自由變元代入可寫為______。28.設(shè)集合X為人的全體，在X上定義關(guān)系R、S分別為R={＜a，b＞|a，b∈X∧a是b的母親}，S={＜a，b＞|a，b∈X∧a是b的父親}，那么關(guān)系{＜a，b＞|a，b∈X∧a是b的外祖父}的表達式為______

A．

B．

C．

D．29.畫出K4的2條邊的所有非同構(gòu)的生成子圖。30.對于公式，下列說法正確的是______

A．y是自由變元

B．y是約束變元

C．的轄域是R(x，y)

D．的轄域是31.用Kruskal算法求下圖中的一棵最小生成樹。要求寫出詳細過程，并畫出該最小生成樹。

32.設(shè)有向圖G為歐拉圖，則圖G中每個頂點的入度______出度。(填“大于”“等于”“小于”)33.的前束范式為______。34.集合A={0，2，4}上的下列關(guān)系矩陣中，符合等價關(guān)系條件的是______

A．

B．

C．

D．35.令p：今天下雪了，q：路滑，則命題“雖然今天下雪了，但是路不滑”可符號化為______

A．

B．

C．p∧q

D．36.設(shè)〈A，+，·〉是環(huán)，如果〈A，·〉是可交換的，則稱〈A，+，·〉是______。37.n個命題變元的______稱為小項，其中每個變元與它的否定不能同時出現(xiàn)，但兩者必須______。38.設(shè)S=R(R為實數(shù)集)，定義S上的二元運算*，即，有a*b=a+b+ab，則〈S，*〉是否構(gòu)成群?39.求下圖所給的帶權(quán)無向圖的最小生成樹，并計算它的權(quán)。

40.設(shè)a：小華，P(x)：x是教授，f(x)：x的父親，則語句“小華的父親是教授”可符號化為______A.P(f(a))B.P(a)∧f(a)C.f(P(a))D.P(a)∨f(a)41.設(shè)群G=＜A，*＞中，A的元素個數(shù)大于1，若元素a∈A的逆元素為b∈A，則a*b的運算結(jié)果是______A.aB.bC.G中的零元D.G中的幺元42.無向圖G有8條邊，1個1度頂點，2個2度頂點，1個5度頂點，其余頂點的度數(shù)均為3，則3度頂點的個數(shù)為______A.2B.3C.4D.543.設(shè)R={〈3，1〉，〈2，3〉，〈5，3〉，〈3，4〉}是集合A={1，2，3，4，5}上的關(guān)系，則domR=______，ranR=______。44.設(shè)解釋I如下：D={2，3}，已知F(2，2)=F(3，3)=0，F(xiàn)(2，3)=F(3，2)=1，f(2，2)=f(2，3)=2，f(3，2)=f(3，3)=3。

求謂詞公式在I下的真值。45.設(shè)X={1，2，3，5，6，10，15，30}，y={2，3，6，12，24，36}，W={1，2，3，6，18，54}，T={2n|n為正整數(shù)}，這些集合中關(guān)于整除關(guān)系不構(gòu)成格的是______A.XB.WC.TD.y46.設(shè)＜G，*＞是階大于1的群，則下列命題中錯誤的是______A.G中每個元素都有逆元B.存在幺元C.存在零元D.運算*是可結(jié)合的47.下圖是A={1，2，3}上關(guān)系R的關(guān)系圖G(R)，從G(R)可判斷出R所具有的性質(zhì)是______

A.自反，對稱，傳遞B.反自反，對稱，反對稱，傳遞C.反自反，對稱，非傳遞D.非對稱48.設(shè)集合A有n個元素，集合B有m個元素，且，求的元素個數(shù)。49.設(shè)無向簡單圖G有9個結(jié)點。證明：G中至少存在兩個度數(shù)相同的結(jié)點。50.約束變元改名規(guī)則：將量詞轄域中，______及其轄域中該變元的所有約束出現(xiàn)均改為本轄域中未曾出現(xiàn)過的個體變元，其余不變。第1卷參考答案一.歷年考點試題黑鉆版1.參考答案：(1)充分性。設(shè)圖G的邊e=(u，v)不包含在G的任一條簡單回路中，則u，v之間除e外無任何通路，否則，若u，v之間存在另一條通路，那么加上邊e就形成一條回路，這與題意矛盾。因此，去掉邊e，則G不連通，故e為G的割邊。

(2)必要性。設(shè)邊e是G的割邊，e包含在某一條簡單回路中，刪去e則不影響G的連通性，這與e是割邊矛盾。所以e不包含在G的任何簡單回路中。2.參考答案：(A∩B)∪(～A∩B)=(A∩C)∪(～A∩C)，

(A∪～A)∩B=(A∪～A)∩C，

E∩B=E∩C，

B=C。3.參考答案：4.參考答案：4；16[考點]本題主要考查的知識點為簡單無向圖和簡單有向圖。[解析]3個結(jié)點構(gòu)成的不同構(gòu)的簡單無向圖如下：

3個結(jié)點構(gòu)成的不同構(gòu)的簡單有向圖如下：

5.參考答案：題中的有向圖的鄰接矩陣為

從A的3次冪可以得出，v3到v4長度為3的通路有2條，v4到v3長度為3的通路有1條。6.參考答案：{2，3，5}；{1，3，4}7.參考答案：(1)

P規(guī)則

(2)p→q

T(1)E

(3)

P規(guī)則

(4)q→r

T(3)E

(5)p→r

T(2)(4)I

(6)r→s

P規(guī)則

(7)p→s

T(5)(6)I8.參考答案：A0={x|x∈R∧0≤x≤1}=[0，1]，

A1={x|∈R∧-1≤x≤2}=[-1，2]，

A2={x|∈R∧0≤x≤3}=[0，3]，

A3={x|∈R∧-1≤x≤4}=[-1，4]，

A4={x|∈R∧-2≤x≤5}=[-2，5]，

哈斯圖如下圖所示，極大元與最大元為A，極小元與最小元為A0，這個偏序集構(gòu)成有界格、分配格。

9.參考答案：e；a、b、c10.參考答案：算術(shù)表達式((a-b*c)*d+e)÷(f*g+h)的二叉樹表示如下圖：

11.參考答案：鉆石格；五角格12.參考答案：D[考點]本題主要考查的知識點為樹的邊數(shù)與樹的結(jié)點數(shù)之間的關(guān)系。[解析]設(shè)數(shù)的結(jié)點數(shù)為x，則樹的邊數(shù)為x-1，度為1的結(jié)點數(shù)為x-4-3=x-7個。由圖的結(jié)點度數(shù)之和與邊數(shù)的關(guān)系得4×3+3×2+(x-7)×1=2(x-1)，解得x=13，即這棵樹的結(jié)點個數(shù)為13。13.參考答案：B[考點]本題主要考查的知識點為轄域、約束變元、自由變元。[解析]z是自由變元，應(yīng)選B。14.參考答案：顯然H非空，

根據(jù)子群判定定理可知，H是子群。15.參考答案：C16.參考答案：A17.參考答案：D18.參考答案：證明：

(1)若x∈(A-B)-C，則x∈A-B但，

即x∈A但

即x∈A但

即x∈A-(B∪C)；

所以

(2)若x∈A-(B∪C)，則x∈A但；

即x∈A但

即x∈A-B但

即x∈(A-B)-C；

所以

(3)因此，(A-B)-C=A-(B∪C)。19.參考答案：D20.參考答案：①，則有a≤a，所以關(guān)系“≤”具有自反性。

②，a≤b且b≤a，則a=b，所以關(guān)系“≤”具有反對稱性。

③，a≤b且b≤c，則a≤c，所以關(guān)系“≤”具有傳遞性。

綜上所述，關(guān)系“≤”是一個偏序關(guān)系。21.參考答案：(1)自反性：

對，有a+b=a+b，所以＜a，b＞～＜a，b＞。

故關(guān)系～具有自反性。

(2)對稱性：

設(shè)＜a，b>～＜c，d＞，則有a+b=c+d，亦即c+d=a+b，所以＜a，d＞～＜a，b>。故關(guān)系～具有對稱性。

(3)傳遞性：

設(shè)＜a，b＞～＜c，d＞且＜c，d＞～＜e，f＞，則有a+b=c+d，c+d=e+f，從而有a+b=e+f。所以＜a，b＞～＜e，f>。故關(guān)系～具有傳遞性。

因此，～是一個等價關(guān)系。22.參考答案：D[解析]設(shè)樹的結(jié)點個數(shù)為n，則2×3+(n-2)×1=2×(n-1)，解得n=6，n-2=4，則此樹有4個葉結(jié)點。23.參考答案：B[考點]本題主要考查的知識點為無向圖中邊數(shù)與頂點度數(shù)的關(guān)系。

[解析]設(shè)G中頂點數(shù)為n，則2m=32≤3×4+4×3+2(n-7)，即n≥11，故G中至少有11個頂點。24.參考答案：B[解析]當(dāng)且僅當(dāng)P的真值為T，Q的真值為F時，P→Q為F，其余情況P→Q為T。則選項A的真值可為T也可為F。同理選項C、選項D可為F亦可為T，只有選項B在任何情況下均為F。25.參考答案：{＜1，1＞，＜2，2＞，＜3，3＞，＜4，4＞，＜1，2＞，＜2，4＞，＜1，3＞}；{＜1，2＞，＜2，1＞，＜2，4＞，＜42＞，＜3，3＞，＜1，3＞，＜3，1＞}[考點]本題主要考查的知識點為關(guān)系的自反閉包和對稱閉包。[解析]畫出r(R)，s(R)的關(guān)系圖如下：

所以r(R)={＜1，1＞，＜2，2＞，＜3，3＞，＜4，4＞，＜1，2＞，＜2，4＞，(1，3＞}，

s(R)={＜1，2＞，＜2，1＞，(2，4＞，＜4，2＞，＜3，3＞，＜1，3＞，＜3，1＞}。26.參考答案：D27.參考答案：[考點]本題主要考查的知識點為自由變元的代入規(guī)則。[解析]中，x是自由變元，y既是自由變元又是約束變元。將z代入自由變元x，u代入R(x，y)中的y得，。28.參考答案：C[考點]本題主要考查的知識點為復(fù)合關(guān)系。[解析]為了清晰地表達，將題目換一種表達，R={＜a，b＞|a，b∈X∧a是b的母親}，S={＜c，a>|c，a∈X∧c是a的父親}，關(guān)系{＜c，b＞|c，b∈X∧c是b的外祖父}=。29.參考答案：K4的兩條邊的非同構(gòu)的生成子圖共有2個。由圖中邊與度數(shù)之間的關(guān)系知，兩條邊共產(chǎn)生4度，分配給4個頂點，其圖如下：

30.參考答案：C[考點]本題主要考查的知識點為自由變元、約束變元、轄域。[解析]y既是自由變元，也是約束變元：的轄域是R(x，y)；的轄域是，故選C。31.參考答案：解：根據(jù)Kruskal算法，

①取權(quán)為1的邊e1=(v1，v2)；②取權(quán)為3的邊e2=(v2，v3)；

③取權(quán)為4的邊e3=(v3，v4)；④取權(quán)為4的邊e4=(v3，v5)；

⑤取權(quán)為7的邊e5=(v5，v6)；

最小生成樹如下圖所示。

32.參考答案：等于33.參考答案：[考點]本題主要考查的知識點為前束范式。[解析]34.參考答案：B[考點]本題主要考查的知識點為等價關(guān)系矩陣。[解析]用排除法，等價關(guān)系矩陣為對稱矩陣，而A、C、D項的矩陣不是