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

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

考試時間：120分鐘

專業(yè)：計算機科學與技術

總分：100分一、單項選擇題（每題2分，共20分）以下哪種數(shù)學結構是離散的？

A.實數(shù)域

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

C.有理數(shù)域

D.komplexnumberfield以下哪種關系是等價關系？

A.小于關系

B.等于關系

C.大于關系

D.包含關系以下哪種圖是連通圖？

A.完全圖

B.樹圖

C.環(huán)圖

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

A.p→q

B.p∧q

C.p∨q

D.以上都是以下哪種遞歸關系是線性遞歸關系？

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

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

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

D.以上都是以下哪種離散數(shù)學結構是半群？

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

B.有理數(shù)域

C.實數(shù)域

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

A.完全圖

B.樹圖

C.環(huán)圖

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

A.p→q

B.p∧q

C.p∨q

D.p→?q以下哪種遞歸關系是非線性遞歸關系？

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

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

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

D.以上都是以下哪種離散數(shù)學結構是群？

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

B.有理數(shù)域

C.實數(shù)域

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