第一篇：廣工離散數(shù)學(xué)復(fù)習(xí)綱要

復(fù)習(xí)方法： 2 3 針對(duì)精簡(jiǎn)的PPT復(fù)習(xí)(涵蓋了全部的教學(xué)和考試內(nèi)容)作業(yè)（認(rèn)真把做過(guò)的作業(yè)溫習(xí)一遍，做到真正弄懂）

結(jié)合本復(fù)習(xí)大綱有針對(duì)性的復(fù)習(xí)，特別是大綱中文字加粗部分的內(nèi)容。

復(fù)習(xí)大綱： 第一章

1.1 與集合相關(guān)的概念和特殊集合：集合的定義、集合的表示、屬于和不屬于、子集、真子集、包含和真包含、冪集、空集、全集、基數(shù)、有限集、無(wú)限集等；

1.2 與集合運(yùn)算相關(guān)的概念和定理：集合的交、并、差、補(bǔ)和對(duì)稱差等五種運(yùn)算的定義及相關(guān)定理。

1.3 代表性習(xí)題：7, 13, 24, 29

第二章

2.1 容斥原理和鴿籠原理的基本概念及正確使用。2.2 代表性習(xí)題：18, 19

第三章

3.1 命題的概念、表示、分類、5種基本聯(lián)接詞的定義與使用、命題的正確符號(hào)化。3.2 命題變?cè)?、命題公式的概念及公式的正確翻譯。3.3 等價(jià)關(guān)系及蘊(yùn)含關(guān)系的概念、常用的等價(jià)關(guān)系以及蘊(yùn)涵關(guān)系、等價(jià)關(guān)系和蘊(yùn)涵關(guān)系之間的關(guān)系。

3.4 文字、短語(yǔ)、子句、析取范式、合取范式、極小項(xiàng)、極大項(xiàng)、主析取范式、主合取范式的概念。

3.5 求范式、主范式的方法、公式類型與主范式之間的關(guān)系, 主析取和主合取范式之間的轉(zhuǎn)換。

3.6 命題演算的推理方法——真值表技術(shù)、直接證明方法（規(guī)則P、規(guī)則T、規(guī)則CP），間接證明方法（反證法）。（PPT上第五章）3.7 代表性習(xí)題：3, 7, 11, 18，第四章

4.1 謂詞、量詞、個(gè)體域和個(gè)體的概念；

4.2 原子謂詞公式的概念，謂詞演算的合式公式的概念，謂詞公式的翻譯；

4.3 自由變?cè)?，約束變?cè)犛虻母拍?，約束變?cè)母拿?guī)則和自由變?cè)拇胍?guī)則； 4.4 謂詞公式分為三類：邏輯有效公式、矛盾公式和可滿足公式；

4.5 謂詞演算的永真公式、等價(jià)關(guān)系的概念，常用的謂詞演算的等價(jià)關(guān)系；

4.6 謂詞邏輯的推理理論——直接證明方法和間接證明方法，用于消去量詞的全稱特指規(guī)則和存在特指規(guī)則，用于添加量詞的全稱推廣規(guī)則和存在推廣規(guī)則及應(yīng)用。（PPT上第五章）

4.7 代表性習(xí)題：7, 10, 16, 19 2 5 第六章

5.1 序偶和笛卡兒積的概念

5.2 二元關(guān)系的概念和表示（特別是關(guān)系圖和關(guān)系矩陣）5.3 關(guān)系的交、并、補(bǔ)、差運(yùn)算、復(fù)合運(yùn)算和逆運(yùn)算

5.4 關(guān)系性質(zhì)的定義、關(guān)系性質(zhì)的判定、關(guān)系性質(zhì)的證明； 5.5 關(guān)系的自反、對(duì)稱、和傳遞閉包的概念及計(jì)算。5.6 代表性習(xí)題：3, 17,19,21

第七章

6.1 等價(jià)關(guān)系的概念及證明、等價(jià)類和商集的計(jì)算； 6.2 集合劃分的定義、求給定集合的劃分； 6.3 等價(jià)關(guān)系與集合劃分的關(guān)系；

6.4 偏序關(guān)系、擬序關(guān)系、全序關(guān)系和良序關(guān)系的定義，它們之間的異同； 6.5 哈斯圖的畫(huà)法；

6.6 八個(gè)特殊元的定義和基本性質(zhì)。6.7 代表性習(xí)題：5, 11,14,18

第八章

7.1 函數(shù)的概念。注意函數(shù)與關(guān)系的區(qū)別和聯(lián)系； 7.2 單射、滿射和雙射函數(shù)的概念，數(shù)學(xué)描述形式； 7.3 函數(shù)的復(fù)合運(yùn)算，逆運(yùn)算及運(yùn)算性質(zhì)。7.4 代表性習(xí)題：4，8

第九章

8.1 圖的概念：圖的定義、圖的表示、圖的操作、鄰接點(diǎn)與鄰接邊、圖的分類等。8.2 圖的基本性質(zhì)：結(jié)點(diǎn)的度數(shù)、圖的基本定理（握手定理）、完全圖、補(bǔ)圖、子圖、真子圖、生成子圖、導(dǎo)出子圖等。

8.3 通路與回路：通路與回路、簡(jiǎn)單（基本）通路與簡(jiǎn)單（基本）回路、通路與回路長(zhǎng)度、結(jié)點(diǎn)間的短程線和距離、可達(dá)與可達(dá)性矩陣。

8.4 圖的連通性：無(wú)向連通圖與連通分支、強(qiáng)（單向、弱）連通圖與強(qiáng)（單向、弱）分圖、8.5 利用鄰接矩陣和可達(dá)性矩陣判斷圖的通路（回路）條數(shù)以及連通性等（定理9.3.1和定理9.3.4）。

8.6 代表性習(xí)題：5，24, 26，27

第十章

9.1 樹(shù)的概念： 樹(shù)、森林、根樹(shù)、根、葉、分支點(diǎn)、生成樹(shù)、最小生成樹(shù)等。9.2 樹(shù)的基本性質(zhì)：m = n-1等。

9.3 與根樹(shù)相關(guān)的概念：有向樹(shù)、根樹(shù)、根、葉、內(nèi)點(diǎn)、分支點(diǎn)、層數(shù)、高、有序樹(shù)、祖先與后代、父親與兒子、k元樹(shù)、k元完全樹(shù)、k元有序樹(shù)、k元有序完全樹(shù)、子樹(shù)、根樹(shù)的遍歷、最優(yōu)樹(shù)。

9.4 樹(shù)的算法： 破圈法、避圈法、廣度優(yōu)先搜索算法、Kruskal算法、Prim算法、哈夫曼算法、二元樹(shù)的先(中、后)根次序遍歷算法。9.5 代表性習(xí)題：10,11,17,19 6 10 第十一章

10.1 基本概念：歐拉通路、歐拉回路、歐拉圖、哈密頓通路、哈密頓回路、哈密頓圖、偶圖、匹配、平面圖等；

10.2 判定方法：比如歐拉圖和偶圖都有簡(jiǎn)單的方法；

10.2.1 定理11.2.1，推論11.2.1，推論11.2.2

10.2.2 定理11.3.1，推論11.3.1，定理11.3.2，定理11.3.3 10.2.3 定理11.4.1

10.2.4 定理11.5.3, 推論11.5.3

10.3 在哈密頓圖、平面圖、偶圖中都分別有定理僅是必要條件，注意，此必要條件正方面的敘述無(wú)法用來(lái)判斷一個(gè)圖是否是哈密頓圖、平面圖，此時(shí)該定理是用處不大，但必要條件的等價(jià)逆敘述卻非常的重要，用此逆敘述可以判斷一個(gè)圖不是哈密爾圖、是非平面圖等； 10.4 代表性習(xí)題：1, 8, 9,16,21,22 第十二章

11.1 代數(shù)運(yùn)算的定義、代數(shù)運(yùn)算的封閉性、代數(shù)系統(tǒng)的概念以及子代數(shù)的概念。

11.2 二元運(yùn)算律，具體包含結(jié)合律、交換律、吸收律、分配律、冪等律以及可消去律。11.3 代數(shù)系統(tǒng)中的特殊元素，有幺元（單位元）、可逆元、零元、可消去元、冪等元，以及特殊元素的一些基本性質(zhì)。11.4 代表性習(xí)題：3, 4 12 第十三章

12.1 半群與含幺半群的定義、元素冪的定義以及性質(zhì)、循環(huán)半群與循環(huán)含幺半群的定義與性質(zhì)。

12.2 群的定義與性質(zhì)、元素的周期與性質(zhì)、子群的定義、子群的判別定理 12.3 交換群和循環(huán)群的定義及性質(zhì)

12.4 陪集的概念及性質(zhì)、拉格朗日定理及其推論。12.5 代表性習(xí)題：4, 16

第二篇：《離散數(shù)學(xué)》期末復(fù)習(xí)

《離散數(shù)學(xué)》期末復(fù)習(xí)

內(nèi)容：第一章~第七章 題型：

一、選擇題（20%，每題2分）二．填空題（20%，每題2分）

三、計(jì)算題（20%，每題5分）

四、證明題（20%，每題5分）

五、判斷題（20%，每題2分）

第1章 數(shù)學(xué)語(yǔ)言與證明方法

1.1 常用的數(shù)學(xué)符號(hào)

1.計(jì)算常用的數(shù)學(xué)符號(hào)式子 1.2 集合及其表示法

1.用列舉法和描述法表示集合

2.判斷元素與集合的關(guān)系(屬于和不屬于)3.判斷集合之間的包含與相等關(guān)系，空集(E)，全集(?)4.計(jì)算集合的冪集

5.求集合的運(yùn)算：并、交、相對(duì)補(bǔ)、對(duì)稱差、絕對(duì)補(bǔ)

6.用文氏圖表示集合的運(yùn)算 7.證明集合包含或相等

方法一： 根據(jù)定義, 通過(guò)邏輯等值演算證明

方法二： 利用已知集合等式或包含式, 通過(guò)集合演算證明

1.3 證明方法概述

1、用如下各式方法對(duì)命題進(jìn)行證明。? 直接證明法：A?B為真

? 間接證明法：“A?B為真” ? “ ?B? ?A為真” ? 歸謬法(反證法)： A??B?0為真

? 窮舉法： A1?B, A2?B,…, Ak?B 均為真

? 構(gòu)造證明法：在A為真的條件下, 構(gòu)造出具有這種性質(zhì)的客體B ? 空證明法：“A恒為假” ? “A?B為真” ?平凡證明法：“B恒為真” ? “A?B為真” ? 數(shù)學(xué)歸納法： 第2章 命題邏輯

2.1 命題邏輯基本概念

1、判斷句子是否為命題、將命題符號(hào)化、求命題的真值（0或1）。

命題的定義和聯(lián)結(jié)詞(?, ?, ?, ?, ?)

2、判斷命題公式的類型

賦值或解釋.成真賦值,成假賦值；重言式(永真式)、矛盾式(永假式)、可滿足式:。2.2 命題邏輯等值演算

1、用真值表判斷兩個(gè)命題公式是否等值

2、用等值演算證明兩個(gè)命題公式是否等值

3、證明聯(lián)結(jié)詞集合是否為聯(lián)結(jié)詞完備集 2.3 范式

1、求命題公式的析取范式與合取范式

2、求命題公式的主析取范式與主合取范式（兩種主范式的轉(zhuǎn)換）

3、應(yīng)用主析取范式分析和解決實(shí)際問(wèn)題 2.4 命題邏輯推理理論

1、用直接法、附加前提、歸謬法、歸結(jié)證明法等推理規(guī)則證明推理有效 第3章 一階邏輯

3.1 一階邏輯基本概念

1、用謂詞公式符號(hào)命題（正確使用量詞）

2、求謂詞公式的真值、判斷謂詞公式的類型 3.2 一階邏輯等值演算

1、證明謂詞公式的等值式

2、求謂詞公式的前束范式 第4章 關(guān)系

4.1 關(guān)系的定義及其表示

1、計(jì)算有序?qū)?、笛卡兒積

2、計(jì)算給定關(guān)系的集合

3、用關(guān)系圖和關(guān)系矩陣表示關(guān)系 4.2 關(guān)系的運(yùn)算

1、計(jì)算關(guān)系的定義域、關(guān)系的值域

2、計(jì)算關(guān)系的逆關(guān)系、復(fù)合關(guān)系和冪關(guān)系

3、證明關(guān)系運(yùn)算滿足的式子 4.3 關(guān)系的性質(zhì)

1、判斷關(guān)系是否為自反、反自反、對(duì)稱、反對(duì)稱、傳遞的2、判斷關(guān)系運(yùn)算與性質(zhì)的關(guān)系

3、計(jì)算關(guān)系自反閉包、對(duì)稱閉包和傳遞閉包 4.4 等價(jià)關(guān)系與偏序關(guān)系

1、判斷關(guān)系是否為等價(jià)關(guān)系

2、計(jì)算等價(jià)關(guān)系的等價(jià)類和商集

3、計(jì)算集合的劃分

4、判斷關(guān)系是否為偏序關(guān)系

5、畫(huà)出偏序集的哈期圖

6、求偏序集的最大元、最小元、極小元、極大元、上界、下界、上確界、下確界

7、求偏序集的拓?fù)渑判?第5章 函數(shù)

1.判斷關(guān)系是否為函數(shù) 2.求函數(shù)的像和完全原像

3.判斷函數(shù)是否為滿射、單射、雙射 4.構(gòu)建集合之間的雙射函數(shù) 5.求復(fù)合函數(shù)

6.判斷函數(shù)的滿射、單射、雙射的性質(zhì)與函數(shù)復(fù)合運(yùn)算之間的關(guān)系 7.判斷函數(shù)的反函數(shù)是否存在，若存在求反函數(shù) 第6章 圖

1.指出無(wú)向圖的階數(shù)、邊數(shù)、各頂點(diǎn)的度數(shù)、最大度、最小度

2.指出有向圖的階數(shù)、邊數(shù)、各頂點(diǎn)的出度和入度、最大出度、最大入度、最小出度最小入出度

3.根據(jù)握手定理頂點(diǎn)數(shù)、邊數(shù)等

4.指出圖的平行邊、環(huán)、弧立點(diǎn)、懸掛頂點(diǎn)和懸掛邊 5.判斷給定的度數(shù)列能否構(gòu)成無(wú)向圖

6.判斷圖是否為簡(jiǎn)單圖、完全圖、正則圖、圈圖、輪圖、方體圖 7.求給定圖的補(bǔ)圖、生成子圖、導(dǎo)出子圖 8.判斷兩個(gè)圖是否同構(gòu) 6.2 圖的連通性

1.求圖中給定頂點(diǎn)通路、回路的距離

2.計(jì)算無(wú)向圖的連通度、點(diǎn)割集、割點(diǎn)、邊割集、割邊 3.判斷有向圖的類型：強(qiáng)連通圖、單向連通圖、弱連通圖 6.3 圖的矩陣表示

1.計(jì)算無(wú)向圖的關(guān)聯(lián)矩陣 2.計(jì)算有向無(wú)環(huán)圖的關(guān)聯(lián)矩陣 3.計(jì)算有向圖的鄰接矩陣 4.計(jì)算有向圖的可達(dá)矩陣

5.計(jì)算圖的給定長(zhǎng)度的通路數(shù)、回路數(shù) 6.4 幾種特殊的圖

1、判斷無(wú)向圖是否為二部圖、歐拉圖、哈密頓圖 第7章 樹(shù)及其應(yīng)用 7.1 無(wú)向樹(shù)

1.判斷一個(gè)無(wú)向圖是否為樹(shù)

2.計(jì)算無(wú)向樹(shù)的樹(shù)葉、樹(shù)枝、頂點(diǎn)數(shù)、頂點(diǎn)度數(shù)之間的關(guān)系 3.給定無(wú)向樹(shù)的度數(shù)列，畫(huà)出非同構(gòu)的無(wú)向樹(shù) 4.求生成樹(shù)對(duì)應(yīng)的基本回路系統(tǒng)和基本割集系統(tǒng) 5.求最小生成樹(shù) 7.2 根樹(shù)及其應(yīng)用

1.判斷一個(gè)有向圖是否為根樹(shù)

2.求根樹(shù)的樹(shù)根、樹(shù)葉、內(nèi)點(diǎn)、樹(shù)高 3.求最優(yōu)樹(shù)

4.判斷一個(gè)符號(hào)串集合是否為前綴碼 5.求最佳前綴碼

6.用三種方法遍歷根樹(shù)

第三篇：離散數(shù)學(xué)復(fù)習(xí)重點(diǎn)

離散數(shù)學(xué)復(fù)習(xí)重點(diǎn)：

1、集合的運(yùn)算以及運(yùn)算律；

2、關(guān)系的三種表示方法，以及他們之間的轉(zhuǎn)化；

3、常見(jiàn)關(guān)系的定義；

4、哈斯圖的畫(huà)法，以及最大最小元、極大極小元、上下界，上下確界的求法；

5、單射、滿射以及雙射的證明（尤其是在代數(shù)系統(tǒng)中）；

6、代數(shù)系統(tǒng)的概念以及代數(shù)系統(tǒng)的常用性質(zhì)，能夠證明具體的代數(shù)系統(tǒng)的運(yùn)算律，找出單

位元，零元、以及逆元等；

7、環(huán)和格只要記住不同的環(huán)和格滿足的運(yùn)算律就好；

8、各種圖和樹(shù)的概念及相關(guān)的結(jié)論，比如：歐拉圖的充要條件，哈密頓圖的充分條件、必

要條件、充要條件等；

9、圖的矩陣計(jì)算；

10、會(huì)畫(huà)一些簡(jiǎn)單的樹(shù)；

11、五種聯(lián)結(jié)詞的真值表；

12、一些要求記住的命題公式；

13、命題公式的證明；

14、命題公式的析取范式，合取范式，主析取范式和主合取范式的求法。

題型：填空題、證明題和解答題。

友情提醒：

1、周三下午一點(diǎn)半到三點(diǎn)半在逸夫樓519答疑。

2、概念、定理和公式請(qǐng)務(wù)必記住，可能會(huì)出填空題；

3、考試內(nèi)容不會(huì)超出我們的重點(diǎn)；

請(qǐng)大家好好復(fù)習(xí)，爭(zhēng)取一次性通過(guò)。

第四篇：大學(xué)離散數(shù)學(xué)復(fù)習(xí)試題

離散數(shù)學(xué)練習(xí)題目

一、選擇題

1．設(shè)A={{1，2，3}，{4，5}，{6，7，8}}，下列各式中____D______是錯(cuò)的。

A、??A； B、{6，7，8}?A； C、{{4，5}}?A； D、{1，2，3}?A。

2.已知集合A={a,b,c},B={b,c,e},則 A⊕B=___C___________ A.{a,b} B={c} C={a,e} D=φ

3.下列語(yǔ)句中，不是命題的是____A_________ A.我說(shuō)的這句話是真話； B.理發(fā)師說(shuō)“我說(shuō)的這句話是真話”； C.如果明天下雨，我就不去旅游； D.有些煤是白的，所以這些煤不會(huì)燃燒；

4.下面___D______命題公式是重言式。

A.P?Q?R ； B.(P?R)?(P?Q)；C.(P?Q)?(Q?R)；

D、(P?(Q?R))?((P?Q)?(P?R))。

5.公式(p∧q)∨(p∧～q)的主析取范式是____B_______ A.m1∨m2 B.m2∨m3 C.m0∨m2 D.m1∨m3

6．設(shè)L(x)：x是演員，J(x)：x是老師，A(x , y)：x欽佩y，命題“所有演員都?xì)J佩某些老師”符號(hào)化為_(kāi)__D______。

A、?x(L(x)?A(x,y))； B、?x(L(x)??y(J(y)?A(x,y)))； C、?x?y(L(x)?J(y)?A(x,y))； D、?x?y(L(x)?J(y)?A(x,y))。7.關(guān)于謂詞公式（x）(y)(P(x,y)∧Q(y,z))∧(x)p(x,y),下面的描述中錯(cuò)誤的是__B_____ A．（x）的轄域是（y）（P（x,y）∧Q(y,z)）

B．z是該謂詞公式的約束變?cè)?/p>

C．（x）的轄域是P（x,y）D．x是該謂詞公式的約束變?cè)?8． 設(shè)S?A?B，下列各式中____B___________是正確的。

A、domS?B ； B、domS?A； C、ranS?A； D、domS ? ranS = S。9．設(shè)集合X??，則空關(guān)系?X不具備的性質(zhì)是____A________。

A、自反性； B、反自反性； C、對(duì)稱性； D、傳遞性。

10.集合A，R是A上的關(guān)系，如果R是等價(jià)關(guān)系，則R必須滿足的條件是__D___ A.R是自反的、對(duì)稱的 B.R是反自反的、對(duì)稱的、傳遞的 C.R是自反的、對(duì)稱的、不傳遞的 D.R是自反的，對(duì)稱的、傳遞的 11.集合A={a,b,c,d},B={1,2,3},則下列關(guān)系中__ACD______是函數(shù)

A.R={(a,1),(b,2),(c,1),(d,2)} B.R={(a,1),(a,2),(c,1),(d,2)} C.R={(a,3),(b,2),(c,1)} D.R={(a,1),(b,1),(c,1),(d,1)} ????已知集合???????????? R?A,且R={(1,2),(1,2),(2,1),(2,2),(2,3),(2,4),(3,4),(4,1)},則頂點(diǎn)2的入度和出度分別是___D_______ A.2,3 B.2,4 C.3,3 D.3,4 13.設(shè)完全圖Kn有n個(gè)結(jié)點(diǎn)(n≥2)，m條邊，當(dāng)下面條件__C____滿足時(shí)，Kn中存在歐拉回路．

A．m為奇數(shù) B．n為偶數(shù) C．n為奇數(shù) D．m為偶數(shù) 14.下面敘述正確的是____B______ A.二部圖K3,3是歐拉圖 B.二部圖是平面圖

K3,3是哈密爾頓圖

C.二部圖 K3,32

D.二部圖K3,3是既不是歐拉圖也不哈密爾頓圖

15.已知某平面圖的頂點(diǎn)數(shù)是12，邊數(shù)是14，則該平面圖有__D___個(gè)面 A.3 B.2 C.5 D.4 16．設(shè)G是n個(gè)結(jié)點(diǎn)、m條邊和r個(gè)面的連通平面圖，則m等于___A____。

A、n+r-2 ； B、n-r+2 ； C、n-r-2 ； D、n+r+2。17.下面幾種代數(shù)結(jié)構(gòu)中，不是群的是___D____ A. B. C. D.(這里Z，Q，R，N分別表示整數(shù)集、有理數(shù)集、實(shí)數(shù)集、自然數(shù)集，+普通加法)

二、問(wèn)答題

1.在程序設(shè)計(jì)過(guò)程中，有如下形式的判斷語(yǔ)句： if(a>=0)if(b>1)if(c<0)cout<

請(qǐng)將這段程序化簡(jiǎn)，并說(shuō)明化簡(jiǎn)的理由。解：簡(jiǎn)化的程序：

if(a>=0 && b>1 && c<0)cout<

設(shè)置命題變量： p: a>=0；q:b>1;r:c<0;s:cout<

A=P→(q→(r→s))經(jīng)過(guò)等值演算可得，A與下面的公式是等值的 P∧q∧r→s

2.集合A={ 1, 2, 3, 4, 5, 6, 7, 8, 9 }，R={(x,y)| x|y}, ①證明R是偏序關(guān)系。

②寫(xiě)出偏序集（A，R）的極小元、極大元；最小元、最大元 ③寫(xiě)出A的子集B={1,2,3,6}的最小上界、最大下界

解：①根據(jù)整除性質(zhì)可知，R滿足自反性，反對(duì)稱性，傳遞性。所以R是A上的偏序關(guān)系。

②偏序集（A，R）的極小元：1，極大元：5, 6，7，8，9 最小元：1； 最大元：無(wú)

③子集B={1,2,3,6}的最小上界：6 子集B={1,2,3,6}的最大下界：1

3.(1)m個(gè)男孩子，n個(gè)女孩排成一排，任何兩個(gè)女孩不相鄰，有多少種排法？

(n<=m)插空問(wèn)題

(2)如果排成一個(gè)園環(huán)，又有多少種排法？

解：(1)考慮5個(gè)男孩，5個(gè)女孩的情況

男孩的安排方法： _B_B_B_B_B_ 排列總數(shù)P(5,5)女孩的安排方法：6個(gè)位置安排5個(gè)女孩，排列中數(shù) P(6,5)所以：總的排列方法數(shù)是 m!*p(m+1,n)

(2)考慮男孩的圓排列情況，結(jié)果是(m-1)!*p(m,n)

4.某商家有三種品牌的足球，每種品牌的足球庫(kù)存數(shù)量不少于10只，如果我想買5只足球，有多少種買法？如果每種品牌的足球最少買一只，有多少種買法？

解：①這是一個(gè)多重集的組合問(wèn)題

類別數(shù)是k=3，選取的元素個(gè)數(shù)是 r=5 多重集組合數(shù)的計(jì)算公式是 N?所以：N=C(3+5-1,5)=c(7,5)=21 ②可自由選取的球只有2個(gè) k=3,r=2 N=C(3+2-1,2)=C(4,2)=6

(r?k?1)!?C(k?r?1,r)

r!(k?1)!

5．某軟件公司將職工分為三種崗位。該公司65人，有些職工（例如項(xiàng)目管理人員、設(shè)計(jì)人員）可能從事不止一個(gè)崗位的工作。每個(gè)職工至少被分在一個(gè)崗位。現(xiàn)在軟件設(shè)計(jì)崗位（崗位A）（包括需求分析、概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)等工作）的人數(shù)是15人，代碼編寫(xiě)崗位（崗位B）的人數(shù)是32人，軟件測(cè)試崗位（崗位C）的人數(shù)是28人，同時(shí)參加崗位A和崗位B的有12人, 同時(shí)參加崗位B和崗位C的有8人, 同時(shí)參加崗位A和崗位C組的有3人，問(wèn)，三個(gè)崗位參加的有多少人？

解： 已知 |A|=15，|B|=32，|C|=28，|A∩B|=12，|B∩C|=8，|A∩C|=3 設(shè)S表示全班同學(xué)總?cè)藬?shù)，則 |S|=65 求：|A∩B∩C|=？

根據(jù)容斥原理：

|A∪B∪C|=|A|+|B|+|C|-|A∩B|-|B∩C|-|A∩C|+|A∩B∩C| 所以|A∩B∩C|=|A∪B∪C|-|A|-|B|-|C|+|A∩B|+|B∩C|+|A∩C| 因?yàn)槊總€(gè)同學(xué)至少參加一個(gè)小組，所以：|A∪B∪C|=|S| 因此：|A∩B∩C|=65-15-32-28+12+8+3=13 答：三個(gè)小組都參加的人數(shù)是13人

6.證明組合恒等式C(n,r)= C(n-1,r-1)+ C(n-1,r)

說(shuō)明：也可以直接利用組合演算公式進(jìn)行演算 7.求1228的個(gè)位數(shù)是多少? 解：1228的個(gè)位數(shù)就是1228 mod 10的余數(shù)1228mod10?(12mod10)28mod10?24*7mod10?(27mod10)4mod10?8mod10?64

8.已知圖G有10條邊, 4個(gè)3度頂點(diǎn), 其余頂點(diǎn)的度數(shù)均小于2, 問(wèn)G至少有多少個(gè)頂點(diǎn)?

解：由握手定理∑d(v)=2m=20，度數(shù)為3的頂點(diǎn)有3個(gè)占去12度，還有8度由其余頂點(diǎn)占有，而由題意，其余頂點(diǎn)的度數(shù)可為0，1，當(dāng)均為1時(shí)所用頂點(diǎn)數(shù)最少，所以應(yīng)有8個(gè)頂點(diǎn)占有此8度，即G中至少有8+4=12個(gè)頂點(diǎn)。

9刑偵人員審一件盜竊案時(shí)，已經(jīng)掌握的線索如下：（1）甲或乙盜竊了電腦。

（2）若甲盜竊了電腦，則作案時(shí)間不能發(fā)生在午夜前。（3）若乙證詞正確，則在午夜時(shí)屋里燈光未滅。（4）若乙證詞不正確，則作案時(shí)間發(fā)生在午夜前。（5）午夜時(shí)屋里燈光滅了。

請(qǐng)通過(guò)命題邏輯推理，推論出誰(shuí)是真正的盜竊犯？（寫(xiě)出詳細(xì)的推理步驟）解 設(shè)p： 甲盜竊了電腦，q： 乙盜竊了電腦，r： 作案時(shí)間發(fā)生在午夜前，s： 乙證詞正確，t：午夜時(shí)屋里燈光滅了。

前提： p∨q，p→~r，s→~t，~s→r，t(7)非p。。

10.插入排序算法的時(shí)間T與數(shù)據(jù)規(guī)模n的遞推關(guān)系如下，求出T與n的顯示關(guān)系表達(dá)式

?T(n)?T(n?1)?n?1 ??T(1)?0

解：

??T(n)?T(n?1)?n?1 ??T(n?2)?n?2?n?1???T(n?3)?n?3?n?2?n?1 ?????T(n?k)?n?k???n?2?n?1??T(n?k)?kn-(1?2??k)??k(k?1)??T(n?k)?kn?2?令n-k=1，那么 k=n-1，所以：

n(n?1)n(n?1)n(n?1)? T(n)?T(1)??0???222?答：T與n的顯示關(guān)系是：T(n)?

11.解下列一階同余方程組

n(n?1)2x?1(mod 3)x?2(mod 4)x?3(mod 5)解：已知a1?1,a2?2,a3?3;m1?3,m2?4,m3?5 方程組的齊次通解是：x?k?Lcm(1,2,3)?6k 60k 根據(jù)中國(guó)剩余定理，特解是：

x0?a1M1(M1mod m1)?a2M2(M2mod m2)?a3M3(M3mod m3)M1?m2m3?20,M2?m1m3?15,M3?m1m2?12 ?1?1?1M1mod m1是下列同余方程的解

3)，解得：x=2，即M1?2 M1x?1(mod m1)即20x?1(mod?1?1同理可解得：M2?3，M3?3 ?1?1 7

x0?a1M1(M1mod m1)?a2M2(M2mod m2)?a3M3(M3mod m3)mod m?（1?20?2?2?15?3?3?12?3）mod 60?1?1?1所以：?(40?90?108)mod 60?238mod 6058

同余方程組的解是 x?x?x0?6k?58 60k

12.假設(shè)需要加密的明文數(shù)據(jù)是a=8,選取兩個(gè)素?cái)?shù)p=7,q=19,使用RSA算法： ① 計(jì)算出密鑰參數(shù)

② 利用加密算法計(jì)算出密文c ③ 利用解密算法根據(jù)密文c反求出明文a 解：① 取 p=7,q=19;計(jì)算 n=p*q=7*19=133 計(jì)算φ(n)=(p-1)*(q-1)=(7-1)*(19-1)=108 選取較小的數(shù)w,使w與108互質(zhì), 5是最小的,于是w=5 計(jì)算d,使d*w≡1(mod φ(n)),即d*5 mod 108=1,取d=65，d*5除以108余數(shù)為1, 于是算出d=65 至此加密、解密參數(shù)計(jì)算完成：

公鑰w=5,n=133.私鑰d=65,n=133.② 加密

c?mwmodn?85mod133?((82mod133)*(83mod133))mod133

?(64*113)mod133?50③ 解密

a?cdmodn?5065mod133

a?A0?A6 其中，A0?50, Ai?(Ai?1)2

根據(jù)上述遞推公式可以計(jì)算出：A1?502mod133?106,A2?1062mod133?64

A3?642mod133?106，??, A6?1062mod133?64 a?A0?A6?(50*64)mod133?8

解密后的明文與原來(lái)的明文是相等的，所以算法正確。

13.設(shè)A={1，2，3，4，6，9，12，24},R定義為R?{(a,b)|a?b(mod 3)}，（1）證明R是一個(gè)等價(jià)關(guān)系；（2）寫(xiě)出A的商集；

14.基于字典序的組合生成算法

問(wèn)題說(shuō)明：假設(shè)我們需要從5個(gè)元素中選取3個(gè)的所有組合，已知組合個(gè)數(shù)為 C（５，３）＝１０，按字典序，其具體組合為： 123,124,125,134,135,145,234,235,245,345 所謂按字典序生成組合，就是已知當(dāng)前的組合（例如135），求下一個(gè)組合（例如，145）。下面給出算法的函數(shù)頭：

//數(shù)組s[]:函數(shù)運(yùn)行前，保存當(dāng)前的組合，函數(shù)結(jié)束后，是新生成的下一個(gè)組合 //n,r:表示從n個(gè)元素中選取r個(gè)元素的組合 void next_comb(int s[],int n,int r)解：

void next_comb(into s[],int n,int r){

int j,m,max_val;

max_val=n;

m=r;

while(s[m]==max_val)

{

m=m-1;

max_val=max_val-1;

}

s[m]=s[m]+1;

for(j=m+1;j

s[j]=s[j-1]+1;}

15.某單位要從A,B,C三人選派若干人出國(guó)考察, 需滿足下述條件:(1)若A去, 則C必須去;(2)若B去, 則C不能去;(3)A和B必須去一人且只能去一人.問(wèn)有幾種可能的選派方案? 9

第五篇：《離散數(shù)學(xué)》期末考試復(fù)習(xí)指導(dǎo)

《離散數(shù)學(xué)》期末考試復(fù)習(xí)指導(dǎo)

期末考試僅限于期中考試以后的內(nèi)容：Chapter 7 Trees;Chapter 8 Topics in

graph theory.考試題型：計(jì)算題；簡(jiǎn)答題；證明題；構(gòu)造圖形（構(gòu)造滿足一定條件的圖，如：

6個(gè)頂點(diǎn)，11條邊且無(wú)Hamiltonian circuit）。題目共計(jì)6題，無(wú)選擇題和填空題。

考試難度：基本與期中考試相同，有一定數(shù)量的題直接來(lái)自于習(xí)題，最后一題較

難（構(gòu)造圖形）。

復(fù)習(xí)要點(diǎn)：基本概念及定義：

rooted tree;binary tree;labeled tree;positional tree;tree

searching;undirected tree;weighted graph;minimal spanning tree;(undirected)graph;degree;Euler path and Euler circuit;Hamiltonian path and Hamiltonian circuit;matching function;coloring graph;chromatic number;chromatic polynomial;planar graph;

基本內(nèi)容：

tree searching;the prefix(Polish form)and infix form of the

algebraic expression;minimal spanning tree;the sufficient-necessary condition for a graph G to have Euler circuit(or path);coloring graph;chromatic number;chromatic polynomial;construct a graph(directed or undirected)subject to some given conditions.不要求的內(nèi)容：

Computer representation of binary positional tree;searching general tree;algorithms.復(fù)習(xí)中如遇困難請(qǐng)聯(lián)系：錢建國(guó)***，jgqian@jingxian.xmu.edu.cn徐偉***

陳美潤(rùn)***

祝大家取得好成績(jī)！