離散數(shù)學面試題及答案

一、單項選擇題（每題2分，共10題）1.集合\(A=\{1,2,3\}\)，其冪集\(P(A)\)的元素個數(shù)是（）A.3B.6C.8D.92.命題公式\(P\toQ\)的等價式是（）A.\(\negP\landQ\)B.\(\negP\lorQ\)C.\(P\land\negQ\)D.\(P\lor\negQ\)3.設(shè)\(R\)是集合\(A\)上的關(guān)系，若\(R\)是自反的、對稱的和傳遞的，則\(R\)是（）A.等價關(guān)系B.偏序關(guān)系C.全序關(guān)系D.擬序關(guān)系4.無向圖\(G\)有\(zhòng)(10\)條邊，\(4\)個\(3\)度頂點，其余頂點度數(shù)均為\(2\)，則\(G\)的頂點數(shù)為（）A.7B.8C.9D.105.下列哪個是前綴碼（）A.\(\{0,10,110,1111\}\)B.\(\{0,10,010,110\}\)C.\(\{1,01,001,000\}\)D.\(\{1,11,101,001\}\)6.若集合\(A=\{a,b\}\)，\(B=\{1,2\}\)，則\(A\timesB\)的元素個數(shù)是（）A.2B.4C.6D.87.公式\(\forallx(P(x)\to\existsyQ(y))\)的前束范式是（）A.\(\forallx\existsy(P(x)\toQ(y))\)B.\(\existsx\forally(P(x)\toQ(y))\)C.\(\forallx\forally(P(x)\toQ(y))\)D.\(\existsx\existsy(P(x)\toQ(y))\)8.一個有\(zhòng)(n\)個頂點的完全圖\(K_n\)的邊數(shù)為（）A.\(n(n-1)\)B.\(\frac{n(n-1)}{2}\)C.\(n(n+1)\)D.\(\frac{n(n+1)}{2}\)9.設(shè)\(A=\{1,2,3\}\)，\(R=\{(1,1),(2,2),(3,3),(1,2)\}\)，則\(R\)的對稱閉包\(s(R)\)是（）A.\(\{(1,1),(2,2),(3,3),(1,2),(2,1)\}\)B.\(\{(1,1),(2,2),(3,3)\}\)C.\(\{(1,2),(2,1)\}\)D.\(\{(1,1),(2,2),(3,3),(1,2)\}\)10.下面哪種圖一定是歐拉圖（）A.有偶數(shù)個頂點的連通圖B.有偶數(shù)條邊的連通圖C.每個頂點度數(shù)均為偶數(shù)的連通圖D.每個頂點度數(shù)均為奇數(shù)的連通圖二、多項選擇題（每題2分，共10題）1.以下屬于邏輯聯(lián)結(jié)詞的有（）A.\(\neg\)B.\(\land\)C.\(\lor\)D.\(\to\)E.\(\leftrightarrow\)2.集合\(A=\{1,2,3,4\}\)，以下哪些是\(A\)的劃分（）A.\(\{\{1\},\{2\},\{3\},\{4\}\}\)B.\(\{\{1,2\},\{3,4\}\}\)C.\(\{\{1,2,3\},\{4\}\}\)D.\(\{\{1\},\{2,3,4\}\}\)E.\(\{\{1,2,3,4\}\}\)3.下列哪些是命題（）A.\(x+1=2\)B.地球是太陽系的行星C.今天天氣真好！D.\(2+3=5\)E.請把門關(guān)上。4.設(shè)\(R\)和\(S\)是集合\(A\)上的關(guān)系，以下正確的有（）A.\((R\cupS)^{-1}=R^{-1}\cupS^{-1}\)B.\((R\capS)^{-1}=R^{-1}\capS^{-1}\)C.\((R\circS)^{-1}=S^{-1}\circR^{-1}\)D.若\(R\)是自反的，\(S\)是自反的，則\(R\circS\)是自反的E.若\(R\)是對稱的，\(S\)是對稱的，則\(R\circS\)是對稱的5.以下哪些圖是平面圖（）A.樹B.完全圖\(K_3\)C.完全二分圖\(K_{2,3}\)D.完全圖\(K_5\)E.完全二分圖\(K_{3,3}\)6.對于群\((G,\cdot)\)，以下說法正確的有（）A.存在單位元\(e\)B.每個元素有逆元C.運算滿足結(jié)合律D.運算滿足交換律E.子群一定是正規(guī)子群7.以下哪些是離散數(shù)學的研究內(nèi)容（）A.集合論B.數(shù)理邏輯C.圖論D.代數(shù)結(jié)構(gòu)E.組合數(shù)學8.設(shè)集合\(A=\{a,b,c\}\)，\(R\)是\(A\)上的關(guān)系，\(R=\{(a,b),(b,c),(c,a)\}\)，則\(R\)具有（）A.自反性B.反自反性C.對稱性D.反對稱性E.傳遞性9.下列哪些公式是永真式（）A.\(P\to(P\lorQ)\)B.\((P\land\negP)\toQ\)C.\(P\land\negP\)D.\(P\lor\negP\)E.\((P\toQ)\land(Q\toR)\to(P\toR)\)10.以下關(guān)于格的說法正確的有（）A.是偏序集B.任意兩個元素有最大下界C.任意兩個元素有最小上界D.一定是布爾代數(shù)E.所有鏈都是格三、判斷題（每題2分，共10題）1.空集是任何集合的子集。（）2.命題公式\((P\landQ)\toP\)是矛盾式。（）3.集合\(A\)上的恒等關(guān)系\(I_A\)是等價關(guān)系。（）4.有向圖中所有頂點的入度之和等于出度之和。（）5.若\(f\)是從集合\(A\)到集合\(B\)的單射函數(shù)，則\(|A|\leq|B|\)。（）6.完全圖\(K_n\)都是哈密頓圖。（）7.一個二元關(guān)系\(R\)如果是對稱的和傳遞的，那么它一定是自反的。（）8.代數(shù)系統(tǒng)\((Z,+)\)（\(Z\)是整數(shù)集，\(+\)是普通加法）是群。（）9.命題公式的主析取范式和主合取范式是唯一的。（）10.無向圖中，如果兩個頂點之間存在路徑，則這兩個頂點是連通的。（）四、簡答題（每題5分，共4題）1.簡述集合的基本運算有哪些？答：集合基本運算有并、交、差、補。并是把兩個集合元素合并；交是取兩個集合公共元素；差是從一個集合去掉另一個集合元素；補是在全集里取集合的剩余元素。2.什么是關(guān)系的傳遞閉包？答：關(guān)系\(R\)的傳遞閉包是包含\(R\)的最小的傳遞關(guān)系。通過對\(R\)進行一系列復合運算，添加必要有序?qū)?，使其滿足傳遞性得到。3.簡述圖的連通分量的概念。答：圖的連通分量是圖的極大連通子圖。一個圖可能不連通，其各個連通部分就是連通分量，不同連通分量之間頂點不連通。4.說明命題邏輯中重言式、矛盾式和可滿足式的區(qū)別。答：重言式是在任何賦值下都為真的命題公式；矛盾式是在任何賦值下都為假的命題公式；可滿足式是存在至少一種賦值使其為真的命題公式。五、討論題（每題5分，共4題）1.討論等價關(guān)系在實際生活中的應(yīng)用。答：在實際生活中，等價關(guān)系應(yīng)用廣泛。如在學生分組中，按成績相近劃分小組，成績相近是一種等價關(guān)系。還有在商品分類中，按功能、特性等分類，同類商品間具有等價關(guān)系，方便管理和銷售。2.探討圖論在計算機網(wǎng)絡(luò)中的作用。答：圖論在計算機網(wǎng)絡(luò)中作用重大。網(wǎng)絡(luò)拓撲結(jié)構(gòu)可用圖表示，頂點代表節(jié)點，邊代表連接。利用圖論算法可進行路徑規(guī)劃，找到最優(yōu)傳輸路徑，還能分析網(wǎng)絡(luò)的連通性、可靠性等，保障網(wǎng)絡(luò)正常運行。3.說說代數(shù)結(jié)構(gòu)在密碼學中的應(yīng)用思路。答：代數(shù)結(jié)構(gòu)如群、環(huán)、域等在密碼學中常用。利用群的運算性質(zhì)可設(shè)計加密算法，通過元素的運算實現(xiàn)信息加密。例如基于有限域上的離散對數(shù)問題設(shè)計密碼體制，保證信息傳輸?shù)谋Ｃ苄院桶踩浴?.論述離散數(shù)學對培養(yǎng)邏輯思維能力的重要性。答：離散數(shù)學對培養(yǎng)邏輯思維能力很重要。其包含的數(shù)理邏輯部分讓我們學會嚴謹推理和判斷真假。集合論、關(guān)系和代數(shù)結(jié)構(gòu)等內(nèi)容鍛煉我們分析結(jié)構(gòu)、抽象思維能力，使思維更有條理、更嚴謹，利于解決復雜問題。答案一、單項選擇題1.C2.B3.A4