東華理工大學(xué)《離散數(shù)學(xué)》2023-2024學(xué)年第一學(xué)期期末試卷

東華理工大學(xué)《離散數(shù)學(xué)》2023-2024學(xué)年第一學(xué)期期末試卷考試課程：離散數(shù)學(xué)

考試時(shí)間：120分鐘

專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)

總分：100分一、單項(xiàng)選擇題（每題2分，共20分）以下哪種數(shù)學(xué)結(jié)構(gòu)是離散的？

A.實(shí)數(shù)域

B.整數(shù)環(huán)

C.有理數(shù)域

D.komplexnumberfield以下哪種關(guān)系是等價(jià)關(guān)系？

A.小于關(guān)系

B.等于關(guān)系

C.大于關(guān)系

D.包含關(guān)系以下哪種圖是連通圖？

A.完全圖

B.樹圖

C.環(huán)圖

D.以上都是以下哪種命題邏輯公式是有效的？

A.p→q

B.p∧q

C.p∨q

D.以上都是以下哪種遞歸關(guān)系是線性遞歸關(guān)系？

A.T(n)=2T(n/2)+n

B.T(n)=T(n-1)+n

C.T(n)=2T(n-1)+1

D.以上都是以下哪種離散數(shù)學(xué)結(jié)構(gòu)是半群？

A.整數(shù)環(huán)

B.有理數(shù)域

C.實(shí)數(shù)域

D.自然數(shù)集合以下哪種圖是二部圖？

A.完全圖

B.樹圖

C.環(huán)圖

D.以上都是以下哪種命題邏輯公式是無效的？

A.p→q

B.p∧q

C.p∨q

D.p→?q以下哪種遞歸關(guān)系是非線性遞歸關(guān)系？

A.T(n)=2T(n/2)+n

B.T(n)=T(n-1)+n

C.T(n)=2T(n-1)+1

D.以上都是以下哪種離散數(shù)學(xué)結(jié)構(gòu)是群？

A.整數(shù)環(huán)

B.有理數(shù)域

C.實(shí)數(shù)域

D.自然數(shù)集合二、判斷題（每題2分，共20分）一個(gè)圖的每個(gè)頂點(diǎn)度數(shù)都是偶數(shù)，則該圖是歐拉圖。（）一個(gè)命題邏輯公式是有效的，當(dāng)且僅當(dāng)它的所有可能的賦值都使其為真。（）一個(gè)遞歸關(guān)系的解可以用遞推公式表示。（）一個(gè)半群可以生成一個(gè)群。（）一個(gè)圖的連通分量數(shù)目是該圖的頂點(diǎn)數(shù)目減去該圖的邊數(shù)目加一。（）一個(gè)命題邏輯公式是無效的，當(dāng)且僅當(dāng)它的所有可能的賦值都使其為假。（）一個(gè)遞歸關(guān)系的解可以用數(shù)學(xué)歸納法證明。（）一個(gè)群可以生成一個(gè)半群。（）一個(gè)圖的歐拉路徑是該圖的一個(gè)閉合路徑。（）一個(gè)命題邏輯公式是等價(jià)的，當(dāng)且僅當(dāng)它的所有可能的賦值都使其為同一個(gè)值。（）三、填空題（每題2分，共20分）一個(gè)圖的頂點(diǎn)度數(shù)是_____________。一個(gè)命題邏輯公式的賦值是_____________。一個(gè)遞歸關(guān)系的解可以用_____________表示。一個(gè)半群的定義是_____________。一個(gè)圖的連通分量數(shù)目是_____________。一個(gè)命題邏輯公式的有效性可以用_____________證明。一個(gè)遞歸關(guān)系的解可以用_____________表示。一個(gè)群的定義是_____________。一個(gè)圖的歐拉路徑是_____________。一個(gè)命題邏輯公式的等價(jià)性可以用_____________證明。四、簡答題（每題10分，共40分）請(qǐng)簡述離散數(shù)學(xué)結(jié)構(gòu)的基本概念及其在計(jì)算機(jī)科學(xué)中的重要性。試述圖論在計(jì)算機(jī)科學(xué)中的應(yīng)用。請(qǐng)簡述命題邏輯的基本概念及其在計(jì)算機(jī)科學(xué)中的應(yīng)用。試述遞歸關(guān)系在計(jì)算機(jī)科學(xué)中的應(yīng)用。