離散數(shù)學(xué)知到智慧樹章節(jié)測(cè)試課后答案2024年秋泰山學(xué)院

離散數(shù)學(xué)知到智慧樹章節(jié)測(cè)試課后答案2024年秋泰山學(xué)院第一章單元測(cè)試

下列哪個(gè)命題公式是重言式？()

A:，

B:，

C:，

D:，

答案:，

設(shè)p：我有錢，q：我去看電影。命題“雖然我有錢，但是我不去看電影”符號(hào)化為____

答案:0設(shè)p，q的真值為0，r，s的真值為1，則的真值為____。

答案:無若解釋I使命題公式A為真，使公式A?B也為真，則解釋I使公式B為(

）。

A:假，

B:可滿足，

C:與解釋I無關(guān)

D:真，

答案:真，

任何兩個(gè)重言式的合取或析取，仍然是一個(gè)重言式。（）

A:對(duì)B:錯(cuò)

答案:對(duì)命題公式等值于（）。

A:，

B:，

C:

D:,

答案:,

n個(gè)命題變項(xiàng)可以產(chǎn)生（）個(gè)互不等值的極小項(xiàng)。

A:2n，

B:n，

C:,

D:，

答案:,

已知____是聯(lián)結(jié)詞的完備集，僅用聯(lián)結(jié)詞“”表達(dá)為____。

答案:無求命題公式的主析取范式和主合取范式。

答案:無判斷下列推理是否正確，并證明你的結(jié)論。

如果他是計(jì)算機(jī)系本科生或者是計(jì)算機(jī)系研究生，那么他一定學(xué)過DELPHI語言而且學(xué)過C++語言。只要他學(xué)過DELPHI語言或者C++語言，那么他就會(huì)編程序。因此如果他是計(jì)算機(jī)系本科生，那么他就會(huì)編程序。

答案:0

第二章單元測(cè)試

設(shè)L(x,y):x大于y，則L(x,y)是一個(gè)命題。（）

A:錯(cuò)B:對(duì)

答案:錯(cuò)在一階邏輯中將命題符號(hào)化時(shí)，針對(duì)不同的個(gè)體域，同一個(gè)命題符號(hào)化之后的結(jié)果可能相同也可能不同。（）

A:對(duì)B:錯(cuò)

答案:對(duì)給定解釋N如下：

在解釋N下，下面公式中真命題有（）。

A:

B:

C:

D:

答案:

；

下列公式中，邏輯有效式是（）。

A:

B:

C:

D:

答案:

；

在一階邏輯中，任何合式公式都存在與之等值的前束范式，并且前束范式是唯一存在的。（）

A:對(duì)B:錯(cuò)

答案:錯(cuò)每列火車都比某些汽車快。，則該命題符號(hào)化為（）

A:

B:

C:

D:

答案:

給定解釋I如下：

下列公式為真的是（）

A:

B:

C:

D:

答案:

；

；

答案:無

答案:無，請(qǐng)問哪幾個(gè)正確（）

A:

B:

C:

D:

答案:

；

第三章單元測(cè)試

為真。（）

A:錯(cuò)B:對(duì)

答案:對(duì)為真。（）

A:錯(cuò)B:對(duì)

答案:錯(cuò)為真。（）

A:對(duì)B:錯(cuò)

答案:對(duì)為假。（）

A:錯(cuò)B:對(duì)

答案:錯(cuò)=____。

答案:無=____。

答案:無=____。

答案:無=____。

答案:無證明。

答案:無證明

答案:無化簡(jiǎn)。

答案:無已知，證明。

答案:無一個(gè)班有50個(gè)學(xué)生，在第一次考試中有26人得5分，在第二次考試中有21人得5分。如果兩次考試中都沒得到5分的有17人，則兩次考試都得5分的有多少人？分別用包含排斥原理和文氏圖求解。

答案:0

第四章單元測(cè)試

集合A={1,2,…,10}上的關(guān)系R={＜x,y＞|x+y=10,x,y∈A}，則R的性質(zhì)為（）。

A:傳遞的

B:對(duì)稱的

C:自反的

D:對(duì)稱的、傳遞的

答案:對(duì)稱的

集合A上的偏序關(guān)系的三個(gè)性質(zhì)是（）。

A:傳遞性

B:對(duì)稱性

C:自反性

D:反對(duì)稱性

答案:傳遞性

；自反性

；反對(duì)稱性

集合A上的等價(jià)關(guān)系的三個(gè)性質(zhì)是（）。

A:反對(duì)稱性

B:傳遞性

C:自反性

D:對(duì)稱性

答案:傳遞性

；自反性

；對(duì)稱性

A上的恒等關(guān)系既是等價(jià)關(guān)系又是偏序關(guān)系。（）

A:錯(cuò)B:對(duì)

答案:對(duì)若R和S都是非空集A上的等價(jià)關(guān)系，則R?S是A上的等價(jià)關(guān)系。（）

A:錯(cuò)B:對(duì)

答案:對(duì)設(shè)Ａ＝｛1,2,3,4,5,6｝，B=____，從Ａ到B的關(guān)系Ｒ＝｛＜x,y＞|x=y2｝，則R=（），____}

答案:B={1,4}R={(1,1),(2,4)}設(shè)S=____，Ａ上的關(guān)系Ｒ＝｛<1,2>，<2,1>，<2,3>，<3,4>｝，則RR=（），

____}

答案:無R是A=____上的等價(jià)關(guān)系，R=IA∪____

則由R誘導(dǎo)的劃分為（）。____,____,____}

答案:為了給出完整而準(zhǔn)確的答案，我們首先需要理解題目中的概念。題目描述了一個(gè)等價(jià)關(guān)系R由兩個(gè)部分組成：一個(gè)為自反關(guān)系IA（即對(duì)角線關(guān)系，每個(gè)元素只與自身相關(guān)），另一個(gè)是由某個(gè)集合A到自身的函數(shù)定義的關(guān)系。等價(jià)關(guān)系具有自反性、對(duì)稱性和傳遞性。題目中還提到了由R誘導(dǎo)的劃分。給定等價(jià)關(guān)系R由兩部分組成：1.自反關(guān)系IA：對(duì)角線上每個(gè)元素都與自己相關(guān)。2.另一個(gè)關(guān)系，假設(shè)為函數(shù)f從A到A，這表示對(duì)于A中的每一個(gè)元素a，都有f(a)與a相關(guān)。由R誘導(dǎo)的劃分意味著，我們可以將集合A分解成若干個(gè)互不相交的子集（也稱為等價(jià)類），使得集合中的任意兩個(gè)元素屬于同一個(gè)子集當(dāng)且僅當(dāng)它們?cè)赗關(guān)系下相互關(guān)聯(lián)。由于R包含IA和f的組合，我們可以推斷出：-IA確保了每個(gè)元素至少與自己相關(guān)，形成了基礎(chǔ)的等價(jià)類。-f的引入則可能進(jìn)一步將元素按照某種特定規(guī)則分組，使得f(a)與a相關(guān)的元素也被視為同一個(gè)等價(jià)類的一部分。因此，由R誘導(dǎo)的劃分將是：1.包含元素a和f(a)的等價(jià)類，表示通過應(yīng)用函數(shù)f，a和它對(duì)應(yīng)的f(a)被分在同一組。2.包含元素b和f(b)的等價(jià)類，表示通過應(yīng)用函數(shù)f，b和它對(duì)應(yīng)的f(b)被分在同一組。3.包含元素c和f(c)的等價(jià)類，表示通過應(yīng)用函數(shù)f，c和它對(duì)應(yīng)的f(c)被分在同一組。所以，由R誘導(dǎo)的劃分是：{{a,f(a)},{b,f(b)},{c,f(c)}}。請(qǐng)注意，這里的表示形式是基于假設(shè)f是一個(gè)函數(shù)，并且每個(gè)元素與其對(duì)應(yīng)的f值形成一組。具體的等價(jià)類取決于具體函數(shù)f的定義。設(shè)RíA×A，證明R自反?IAíR。

答案:0設(shè)A={1,2,…,10}。B、C、D是否為A的劃分？若是，則求出由它誘導(dǎo)的等價(jià)關(guān)系.

（1）B={{1,3,6},{2,8,10},{4,5,7}};

（2）C={{1,5,7},{2,4,8,9},{3,5,6,10}};

（3）D={{1,2,7},{3,5,10},{4,6,8},{9}}

答案:0

第五章單元測(cè)試

給定下列各圖，為簡(jiǎn)單圖的是（）。

A:

B:

C:

D:

答案:

下面各序列中，可以構(gòu)成無向簡(jiǎn)單圖的是（）。

A:（1,1,2,2,2）

B:（1,3,4,4,3）

C:（3,3,4,2,3）

D:（1,1,2,2,3）

答案:（1,1,2,2,2）

下面給出的無向圖中，為多重圖的是（）。

A:G=＜V，E＞,其中V={a,b,c,d,e}，E={（a,b）,（b,e）,（e,b）,（a,e）,（d,e）}

B:G=＜V，E＞,其中V={a,b,c,d,e}，E={（a,b）,（b,e）,（e,d）,（c,c）}

C:G=＜V，E＞,其中V={a,b,c,d,e}，E={（a,b）,（b,c）,（c,d）,（a,e）}

D:G=＜V，E＞,其中V={a,b,c,d,e}，E={（a,c）,（b,e）,（a,e）,（d,e）}

答案:G=＜V，E＞,其中V={a,b,c,d,e}，E={（a,b）,（b,e）,（e,b）,（a,e）,（d,e）}

下列各組數(shù)中，能夠構(gòu)成無向圖的度數(shù)列的是（）。

A:1,1,1,2,4

B:1,2,3,4,5

C:3,3,2,3

D:2,2,4,2,2

答案:2,2,4,2,2

一個(gè)無向圖有16條邊，每個(gè)頂點(diǎn)都是2度的，則這個(gè)無向圖中有幾個(gè)頂點(diǎn)（）。

A:10

B:4

C:16

D:8

答案:16

下面圖中強(qiáng)連通圖為（）。

A:

B:

C:

D:

答案:

對(duì)如下無向圖

下面選項(xiàng)中哪一個(gè)不是該無向圖的點(diǎn)割集。（）

A:{v2，v4}

B:{v6}

C:{v3，v5}

D:{v2}

答案:{v2，v4}

不含平行邊的圖稱為簡(jiǎn)單圖。（）

A:對(duì)B:錯(cuò)

答案:錯(cuò)任何圖（無向圖或有向圖）中，度數(shù)為奇數(shù)的頂點(diǎn)個(gè)數(shù)為偶數(shù)。（）

A:對(duì)B:錯(cuò)

答案:對(duì)頂點(diǎn)數(shù)相同，邊數(shù)相同，度數(shù)序列也相同的兩個(gè)圖一定同構(gòu)。（）

A:錯(cuò)B:對(duì)

答案:錯(cuò)給圖著色時(shí)，若圖為圈，長(zhǎng)度為偶數(shù)的圈要用2種顏色，長(zhǎng)度為奇數(shù)的圈要用3種顏色。（）

A:對(duì)B:錯(cuò)

答案:對(duì)給圖著色時(shí)，奇階輪圖要用3種顏色，偶階輪圖要用4種顏色。（）

A:對(duì)B:錯(cuò)

答案:對(duì)項(xiàng)目網(wǎng)絡(luò)圖有一個(gè)始點(diǎn)和一個(gè)終點(diǎn)，始點(diǎn)的出度為0，終點(diǎn)的入度為0。（）

A:對(duì)B:錯(cuò)

答案:錯(cuò)無向圖的關(guān)聯(lián)矩陣中每一列都恰好有兩個(gè)1或一個(gè)2。（）

A:對(duì)B:錯(cuò)

答案:對(duì)有向圖的鄰接矩陣中所有元素之和等于對(duì)應(yīng)圖中邊數(shù)的兩倍。（）

A:對(duì)B:錯(cuò)

答案:錯(cuò)完全圖K4的所有非同構(gòu)的生成子圖中，2條邊的有（）個(gè)。____。

答案:3一個(gè)無向圖有21條邊，3個(gè)4度頂點(diǎn)，其余都是3度頂點(diǎn)，則該圖有（）個(gè)頂點(diǎn)。____。

答案:該圖有12個(gè)頂點(diǎn)。任何圖（無向圖或有向圖）中所有頂點(diǎn)的度數(shù)之和等于邊數(shù)的（）倍。____。

答案:2在一個(gè)n階圖中，若從頂點(diǎn)u到v(uv)存在通路，則從u到v存在長(zhǎng)度小于等于（）的通路。____。

答案:無下圖至少要用（）種顏色著色。____。

答案:無35條邊，每個(gè)頂點(diǎn)的度數(shù)至少為3的圖最多有（）個(gè)頂點(diǎn)。____。

答案:27求圖中從頂點(diǎn)b頂點(diǎn)到g的最短路徑為（）。____。

答案:無畫出4階3條邊的所有非同構(gòu)的無向簡(jiǎn)單圖。

答案:為了回答這個(gè)問題，我們需要畫出所有可能的4階（即有4個(gè)頂點(diǎn)）且由3條邊構(gòu)成的非同構(gòu)無向簡(jiǎn)單圖。無向簡(jiǎn)單圖意味著圖中沒有方向的邊，且每對(duì)頂點(diǎn)之間最多只有一條邊連接。對(duì)于4個(gè)頂點(diǎn)的圖，我們有以下情況：1.**完全圖**：所有頂點(diǎn)兩兩之間都有邊相連，即K4。在這種情況下，所有頂點(diǎn)都與其它三個(gè)頂點(diǎn)相連，形成一個(gè)完全圖。2.**三叉星圖**：存在一個(gè)中心頂點(diǎn)與其他三個(gè)頂點(diǎn)相連，而這三者之間不直接相連。這種圖有一個(gè)中心頂點(diǎn)與其余三個(gè)頂點(diǎn)各有一條邊相連。3.**雙星圖**：有兩個(gè)不相交的頂點(diǎn)集合，每個(gè)集合內(nèi)部頂點(diǎn)兩兩相連，但兩個(gè)集合間的頂點(diǎn)不相連。具體而言，可以想象為一個(gè)頂點(diǎn)與另兩個(gè)頂點(diǎn)相連形成一個(gè)小三角形，然后另一個(gè)頂點(diǎn)單獨(dú)存在不與前三個(gè)頂點(diǎn)相連。4.**線性排列**：四個(gè)頂點(diǎn)按順序排列，每?jī)蓚€(gè)相鄰的頂點(diǎn)之間有一條邊相連。這實(shí)際上是一種特殊的雙星圖，其中兩個(gè)集合的大小分別為1和3。5.**特殊配置**：除上述三種基本類型外，還有其他配置，但在4個(gè)頂點(diǎn)的情況下，上述已經(jīng)覆蓋了所有可能的非同構(gòu)情況。因此，我們不需要繪制所有可能的圖，因?yàn)閷?duì)于4個(gè)頂點(diǎn)和3條邊的限制，實(shí)際上只有上述幾種基本的非同構(gòu)圖形。如果你需要具體的圖像，建議使用繪圖工具或者軟件來生成這些圖形，以更直觀地理解它們的結(jié)構(gòu)。設(shè)有向圖D的度數(shù)列為2,2,3,3，入度列為0,0,2,3，試求出D的出度列。

答案:0設(shè)G為9階無向圖，每個(gè)頂點(diǎn)的度數(shù)不是5就是6，證明G中至少有5個(gè)6度頂點(diǎn)或至少有6個(gè)5度頂點(diǎn)。

答案:0設(shè)G1與G2均為無向簡(jiǎn)單圖，證明：G1@G2當(dāng)且僅當(dāng)，其中分別為G1與G2的補(bǔ)圖。

答案:無已知n階無向圖G中有m條邊，各頂點(diǎn)的度數(shù)均為3，又已知2n-3=m，問在同構(gòu)的意義下，G是唯一的嗎？若G為簡(jiǎn)單圖，是否唯一？請(qǐng)說明為什么。

答案:0有向圖D如下圖所示，求D中在定義意義下長(zhǎng)度為4的通路總數(shù)，并指出其中有多少條是回路？又有幾條是v3到v4的通路。

答案:無計(jì)算機(jī)系期末要安排7門公共課的考試，課程編號(hào)為1到7。下列每一對(duì)課程有學(xué)生同時(shí)選修：1和2，1和3，1和4，1和7，2和3，2和4，2和5，2和7，3和4，3和6，3和7，4和5，4和6，5和6，5和7，6和7。這7門課的考試至少要安排在幾個(gè)不同的時(shí)間段？給出一個(gè)安排方案。

答案:0

第六章單元測(cè)試

下列無向圖中哪些是二部圖（）。

A:

B:

C:

D:

答案:

；

；

下列圖中哪些是歐拉圖（）。

A:

B:

C:

D:

答案:

；

下列圖中哪些是哈密爾頓圖（）。

A:

B:

C:

D:

答案:

；

下列圖中哪些是不平面圖（）。

A:

B:

C:

D:

答案:

；

；

圖存在完美匹配。（）

A:錯(cuò)B:對(duì)

答案:對(duì)圖存在完美匹配。（）

A:錯(cuò)B:對(duì)

答案:錯(cuò)任何地圖都是4-可著色的。（）

A:錯(cuò)B:對(duì)

答案:對(duì)圖中，____是匹配，____是極大匹配，____是最大匹配，匹配數(shù)是____。

答案:無圖中，____為最大匹配，____完備匹配，____完美匹配。

答案:無圖中，____為完備匹配，____完美匹配。

答案:無

第七章單元測(cè)試

具有2個(gè)頂點(diǎn)的非同構(gòu)無向樹有幾棵（）。

A:1

B:4

C:2

D:3

答案:1

具有4個(gè)頂點(diǎn)的非同構(gòu)無向樹有幾棵（）。

A:4

B:3

C:1

D:2

答案:2

具有6個(gè)頂點(diǎn)的非同構(gòu)無向樹有幾棵（）。

A:5

B:4

C:3

D:6

答案:6

一棵樹有7片樹葉、3個(gè)3度頂點(diǎn)、其余都是4度頂點(diǎn)，則該樹有1個(gè)4度頂點(diǎn)。（）

A:對(duì)B:錯(cuò)

答案:對(duì)一棵樹有2個(gè)4度頂點(diǎn)、3個(gè)3度頂點(diǎn)、其余都是樹葉，則該樹有10片樹葉。（）

A:錯(cuò)B:對(duì)

答案:錯(cuò)對(duì)圖所示的根樹中序行遍法訪問的次序是____，前序行遍法訪問的次序是____，后序行遍法訪問的次序是____。

答案:無圖中所示，實(shí)線邊構(gòu)成的子圖是該圖的一棵生成樹，虛線是弦，求對(duì)應(yīng)于生成樹的基本回路系統(tǒng)和基本割集系統(tǒng)。

答案:無求圖的最小生成樹及其權(quán)

答案:無求權(quán)為1、3、4、5、6的最優(yōu)二叉樹。

答案:最優(yōu)二叉樹通常指的是最小加權(quán)路徑長(zhǎng)度（WPL）的二叉樹。在給定的節(jié)點(diǎn)值中，每個(gè)節(jié)點(diǎn)值代表其在樹中的權(quán)重，節(jié)點(diǎn)的權(quán)重就是該節(jié)點(diǎn)的權(quán)值。對(duì)于權(quán)為1、3、4、5、6的最優(yōu)二叉樹，我們可以采用貪心算法來構(gòu)造