廣東海洋大學離散數(shù)學08-09年考試試卷B

PAGE1第6頁共10頁GDOU-B-11-302GDOU-B-11-302班級：姓名：學號：試題共4班級：姓名：學號：試題共4頁加白紙3張密封線《離散數(shù)學》課程試題課程號：1920015-0eq\o\ac(□,√)考試□A卷eq\o\ac(□,√)閉卷□考查eq\o\ac(□,√)B卷□開卷題號一二三四五總分閱卷教師各題分數(shù)2010153520100實得分數(shù)注：第一、第二和第三大題的答案直接寫在試卷上指定空格內(nèi)。只有計算題和證明題的答案寫在答題紙上。填空題（每空1分，共20分）1、命題是具有真值的。2、，則；3、，，則；而。4、設：這門課讓人喜歡；：這本書有趣；：這本書習題很難；則下列語句：1）若這本書有趣，習題也不很難，則這門課就不會讓人喜歡。2）這本書沒趣，習題也不很難，并且這門課不讓人喜歡。3）這門課讓人喜歡當且僅當這本書有趣且這本書習題不很難。符號化為1）；2）；3）。5、。6、上的包含關系為，則子集的極大元為，最大元為，上界為；7、若非空集合上的關系是、和的，則稱為等價關系；8、無向圖，則有生成樹當且僅當，要確定的一棵生成樹，必刪去的條邊；9、實數(shù)集上定義如下二元運算：1）；2）；3）；4）其中可結合的有，可交換的有，既不可結合也不交換的有；10、無向圖中所有頂點度數(shù)之和等于邊數(shù)的倍。二、單項選擇題（每題1分，共10分）1、下列語句中，真命題是；A、我正在說謊；B、這句話是錯的；C、若1+2=3則雪是黑的；D、若1+2=5則1=2；2、下列哪個公式是永真式；A、；B、；C、；D、3、對任意集合，下列結論正確的是；A、；B、；C、；D、；4、上關系，則具有；A、傳遞性和反對稱性；B、傳遞性和對稱性；C、自反性和對稱性；D、反自反性和對稱性；5、下列代數(shù)系統(tǒng)，是獨異點（為實數(shù)集，為整數(shù)集，為正整數(shù)集）；A、；B、；C、為求兩數(shù)中較大數(shù)；D、為求最大公約數(shù)；6、任何一個有限群在同構意義下可看作是；A、循環(huán)群；B、置換群；C、變換群；D、群；7、具有6個頂點的非同構無向樹的數(shù)目為；A、4；B、5；C、6；D、8；8、若，則不同的映射個數(shù)為；A、個；B、個；C、個；D、個；9、則；A、；B、；C、；D、10、無向圖是哈密頓圖，，均有；A、；B、；C、；D、。三、判斷題（每題1分，共15分）1、語句“愛美之心人皆有之”可以用命題邏輯中的簡單命題來描述（）2、所謂的“推理是有效的”是指該推理的前提和結論都是正確的（）3、由于引入了論域的概念，在一階邏輯中，不存在永真或永假的公式（）4、在一階邏輯（謂詞邏輯）中，量詞也存在分配律，全稱量詞對合取存在分配律，存在量詞對析取存在分配律（）5、空集是一切集合的子集（）6、（）7、R為二元關系，A是集合，R在A上的限制RA還是一個關系，并且是R的子關系（）8、一個關系如果不是自反的，就一定是反自反的。（）9、不存在一種關系，即是等價關系，同時也是偏序關系（）10、Abel群肯定是獨異點（）11、平凡圖是連通圖（）12、在有向圖的可達矩陣中，對角線元素可能是0（）13、完全圖Kn(n≥1)都是哈密頓圖（）14、Kruskal算法構造最小生成樹的過程中，按照權從大到小添加邊，避免回路的出現(xiàn)即可（）15、在后續(xù)課程《編譯原理》中有重要應用的逆波蘭式是指：運算符號在他的兩個運算對象之后（）三、計算題（10+10+5+10=35分）1、求的主析取范式和成真賦值；2、有向圖D為1）求鄰接矩陣A；2）計算A3；3）D中v3到v4的長度為3的通路有幾條？說明理由。3、為群，其中，為模加法；1）求幺元（單位元）；2）求；3）計算；4、一棵樹有2個2度頂點，1個3度頂點，3個4度頂點，求其樹葉數(shù)。四、證明題（每題10分，共20分）1、前提：結論：證明：2、設是自然數(shù)集，定義上的二元關系，則是等價關系。PAGE1第10頁共10頁GDOU-B-11-302GDOU-B-11-302廣東海洋大學2008——2009學年第二學期《離散數(shù)學》評分細則課程號：1920015-0eq\o\ac(□,√)考試□A卷eq\o\ac(□,√)閉卷□考查eq\o\ac(□,√)B卷□開卷填空題（每空1分，共20分）1、唯一，陳述句；2、；3、；4、1），2），3）；5、；6、，無，；7、自反，對稱和傳遞的；8、連通，；9、2）和3），2）和4），1）；10、2。二、單項選擇題（每題1分，共10分）1~5題：DCAAB；6～10題：BCBDC三、判斷題（每題1分，共15分）對的有：4、5、7、10、11、15錯的有：1、2、3、6、8、9、12、13、14四、計算題（10+10+5+10=35分）1、2分2分2分2分成真賦值：001、011、100、1112分2、解：1）A=3分2）A3=3分3）二條；2分因為2分3、解：1）；1分2）；2分3）3分4、解：設樹葉數(shù)為，2分樹枝數(shù)為，2分由握手定理有：4分故2分五、證明題（每題10分，共20分）1、①前提引入1分②①置換1分③②置換1分④③UI規(guī)則1分⑤前提引入