第一篇：(11122)(離散數(shù)學(xué))復(fù)習(xí)大綱(20120605)
《離散數(shù)學(xué)》復(fù)習(xí)大綱
《離散數(shù)學(xué)》復(fù)習(xí)大綱
考試時(shí)：允許帶計(jì)算器，不允許帶手機(jī)。
題型：單選題（10個(gè)*2分=20分），填空題（5個(gè)*3分=15分），大題（8個(gè)，每個(gè)分值不等，共計(jì)65分）
緒論
1、判斷一句話是否是命題（P2）
2、繪制真值表（P2,P3,P4,P5）
第1章：集合1.掌握以下概念：元素、集合、子集，元素與集合的關(guān)系（屬于或不屬于），集合之間的關(guān)系（包含于或不包含于）。
2.求冪集，計(jì)算冪集的基數(shù)。（P28—34，P28—35，P28—36，P28—37，P28—38）
3.利用文氏圖求集合的基數(shù)（P29—60，P28—48）
第2章：關(guān)系與函數(shù)
1.判斷某個(gè)映射是否是函數(shù)（P43），判斷某個(gè)函數(shù)是否有反函數(shù)（P52—33）
2.判斷某個(gè)關(guān)系是否具有自反性、對(duì)稱性、反對(duì)稱性、傳遞性（P50—13）
3.等價(jià)關(guān)系與劃分之間的轉(zhuǎn)換（P50—13）
第3章：布爾代數(shù)
1.求出某個(gè)布爾代數(shù)中某個(gè)定理的對(duì)偶定理（P74）
2.十進(jìn)制、二進(jìn)制、八進(jìn)制之間的轉(zhuǎn)換（P78，P82—14，P82—15，P82—19）
3.根據(jù)電路圖，寫出布爾表達(dá)式，對(duì)布爾表達(dá)式進(jìn)行化簡，畫出簡化之后的電路圖。（P84—53，P85—54）
第4章：自然數(shù)與歸納法：
1、使用數(shù)學(xué)歸納法進(jìn)行等式、不等式、整除式的證明（P122—2，P122—3，P122—6，P122—8，P122—11，P124—39，P123—22，P124—40）
第5章：數(shù)論
1.使用歐幾里德算法進(jìn)行反推（P152—例子）
2.求解模數(shù)方程（P166—9，P166—10）
3.位移加密、摩爾加密的加密解密過程（P167—26，P167—27，P167—28，P167—30）
4.5.6.7.利用快速求冪算法計(jì)算余數(shù)（P167—25）求解歐拉函數(shù)Φ函數(shù)（P166—16）利用歐拉函數(shù)Φ函數(shù)進(jìn)行因式分解（P166—15）RSA加密的加密解密過程（P167—31，P167—32）
第6章：遞歸：
1、使用折半查找法在某個(gè)指定數(shù)組中查找某個(gè)元素時(shí)，得出查找成功或者不成功的結(jié)果時(shí)經(jīng)歷的查找過程。（P207—例子）
第7章：遞歸式求解：
1、遞歸式求解（P234—5，P234—6，P234—11）
第8章：計(jì)數(shù)：
1、當(dāng)從一幅標(biāo)準(zhǔn)撲克（52張）中選出一手牌（5張）時(shí)，計(jì)算出這手牌呈現(xiàn)某種特點(diǎn)（例如：一對(duì)、兩對(duì)、一滾、一連、一滾加一對(duì)、同花、順子、同花順等等）的概率。（該題可能需要使用計(jì)算器）（P252）
第9章：矩陣
1.矩陣加法（P276—方框）
2.矩陣乘法（P277—最后的例子）
3.給出與方程組對(duì)應(yīng)的矩陣方程（P280—方框）
4.矩陣對(duì)應(yīng)的行列式的值（P282—第一個(gè)矩陣，P282—方框）
5.利用克萊姆法則求解方程組（P283—例子，P283—方框）
6.利用矩陣加密解密，其中要用到高斯消去法（P287，P288，P289）
第10章：圖論
1.歐拉路徑和歐拉回路的判斷（P329—圖）
2.判斷圖形是否能“一筆畫出”（P329—圖）
3.利用Prim算法求出最小生成樹（P330—圖，P332—4，P332—13）
4.利用Kruskal算法求出最小生成樹（P330—圖，P332—4，P332—13）
2012-3-12唐斌
第二篇：離散數(shù)學(xué)復(fù)習(xí)重點(diǎn)
離散數(shù)學(xué)復(fù)習(xí)重點(diǎn)：
1、集合的運(yùn)算以及運(yùn)算律；
2、關(guān)系的三種表示方法，以及他們之間的轉(zhuǎn)化；
3、常見關(guān)系的定義；
4、哈斯圖的畫法，以及最大最小元、極大極小元、上下界，上下確界的求法；
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、各種圖和樹的概念及相關(guān)的結(jié)論，比如：歐拉圖的充要條件，哈密頓圖的充分條件、必
要條件、充要條件等；
9、圖的矩陣計(jì)算；
10、會(huì)畫一些簡單的樹；
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)取一次性通過。
第三篇：《離散數(shù)學(xué)》期末復(fù)習(xí)
《離散數(shù)學(xué)》期末復(fù)習(xí)
內(nèi)容：第一章~第七章 題型：
一、選擇題（20%，每題2分）二．填空題（20%，每題2分）
三、計(jì)算題（20%，每題5分）
四、證明題（20%，每題5分）
五、判斷題（20%，每題2分）
第1章 數(shù)學(xué)語言與證明方法
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ù)定義, 通過邏輯等值演算證明
方法二： 利用已知集合等式或包含式, 通過集合演算證明
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í)際問題 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ū)Α⒌芽▋悍e
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、畫出偏序集的哈期圖
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.指出無向圖的階數(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)成無向圖
6.判斷圖是否為簡單圖、完全圖、正則圖、圈圖、輪圖、方體圖 7.求給定圖的補(bǔ)圖、生成子圖、導(dǎo)出子圖 8.判斷兩個(gè)圖是否同構(gòu) 6.2 圖的連通性
1.求圖中給定頂點(diǎn)通路、回路的距離
2.計(jì)算無向圖的連通度、點(diǎn)割集、割點(diǎn)、邊割集、割邊 3.判斷有向圖的類型：強(qiáng)連通圖、單向連通圖、弱連通圖 6.3 圖的矩陣表示
1.計(jì)算無向圖的關(guān)聯(lián)矩陣 2.計(jì)算有向無環(huán)圖的關(guān)聯(lián)矩陣 3.計(jì)算有向圖的鄰接矩陣 4.計(jì)算有向圖的可達(dá)矩陣
5.計(jì)算圖的給定長度的通路數(shù)、回路數(shù) 6.4 幾種特殊的圖
1、判斷無向圖是否為二部圖、歐拉圖、哈密頓圖 第7章 樹及其應(yīng)用 7.1 無向樹
1.判斷一個(gè)無向圖是否為樹
2.計(jì)算無向樹的樹葉、樹枝、頂點(diǎn)數(shù)、頂點(diǎn)度數(shù)之間的關(guān)系 3.給定無向樹的度數(shù)列，畫出非同構(gòu)的無向樹 4.求生成樹對(duì)應(yīng)的基本回路系統(tǒng)和基本割集系統(tǒng) 5.求最小生成樹 7.2 根樹及其應(yīng)用
1.判斷一個(gè)有向圖是否為根樹
2.求根樹的樹根、樹葉、內(nèi)點(diǎn)、樹高 3.求最優(yōu)樹
4.判斷一個(gè)符號(hào)串集合是否為前綴碼 5.求最佳前綴碼
6.用三種方法遍歷根樹
第四篇：離散數(shù)學(xué)復(fù)習(xí)要點(diǎn)
離散數(shù)學(xué)復(fù)習(xí)要點(diǎn)
題型：選擇題、填空題、計(jì)算和證明題
(不用擔(dān)心，考題不難，都是平時(shí)上課講過的內(nèi)容)
命題邏輯：
命題的判定和符號(hào)化（即命題的翻譯）.會(huì)畫命題公式的真值表.理解成真賦值，小項(xiàng).含n個(gè)變?cè)牟坏葍r(jià)的命題公式有多少類.求公式的主合取范式和主析取范式.熟悉命題的等價(jià)公式(命題定律)和蘊(yùn)涵公式(推理定律).謂詞邏輯:
命題的符號(hào)化，即帶量詞的謂詞公式的翻譯，包括一元謂詞和二元謂詞的翻譯.謂詞公式中量詞的作用域.會(huì)求謂詞公式的前束范式.謂詞邏輯中推理的證明(P,T規(guī)則 + EI,EG,UI,UG規(guī)則).集合與關(guān)系:
子集概念，會(huì)求冪集，會(huì)求冪集中元素個(gè)數(shù).會(huì)求兩個(gè)集合的笛卡爾積.關(guān)系的性質(zhì)：（反）自反性，（反）對(duì)稱性，傳遞性。弄清定義，會(huì)判斷。會(huì)求復(fù)合關(guān)系、逆關(guān)系.會(huì)求自反/對(duì)稱/傳遞閉包.會(huì)證明等價(jià)關(guān)系.等價(jià)關(guān)系與劃分的相互轉(zhuǎn)化.圖論：
基本概念: 簡單圖，多重圖，零圖，n階完全圖，結(jié)點(diǎn)的度.握手定理及推論:圖的度數(shù)之和=邊數(shù)的兩倍,邊數(shù)=圖的出度和=圖的入度和.無向圖的連通性.會(huì)判斷有向圖的強(qiáng)連通，單側(cè)連通，弱連通性.會(huì)求圖（包括零圖，完全圖等）的點(diǎn)連通度、邊連通度.由鄰接矩陣求結(jié)點(diǎn)的入度、出度，由鄰接矩陣的冪求結(jié)點(diǎn)間長度為k的路的數(shù)目.歐拉圖的判定.哈密頓圖的判定: 理解必要條件；會(huì)證明充分條件.好好復(fù)習(xí)!預(yù)祝成功!
第五篇：大學(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.下列語句中，不是命題的是____A_________ A.我說的這句話是真話； B.理發(fā)師說“我說的這句話是真話”； 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)化為___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.
二、問答題
1.在程序設(shè)計(jì)過程中，有如下形式的判斷語句： if(a>=0)if(b>1)if(c<0)cout< 請(qǐng)將這段程序化簡，并說明化簡的理由。解：簡化的程序： 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)過等值演算可得，A與下面的公式是等值的 P∧q∧r→s 2.集合A={ 1, 2, 3, 4, 5, 6, 7, 8, 9 }，R={(x,y)| x|y}, ①證明R是偏序關(guān)系。 ②寫出偏序集（A，R）的極小元、極大元；最小元、最大元 ③寫出A的子集B={1,2,3,6}的最小上界、最大下界 解：①根據(jù)整除性質(zhì)可知，R滿足自反性，反對(duì)稱性，傳遞性。所以R是A上的偏序關(guān)系。 ②偏序集（A，R）的極小元：1，極大元：5, 6，7，8，9 最小元：1； 最大元：無 ③子集B={1,2,3,6}的最小上界：6 子集B={1,2,3,6}的最大下界：1 3.(1)m個(gè)男孩子，n個(gè)女孩排成一排，任何兩個(gè)女孩不相鄰，有多少種排法？ (n<=m)插空問題 (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.某商家有三種品牌的足球，每種品牌的足球庫存數(shù)量不少于10只，如果我想買5只足球，有多少種買法？如果每種品牌的足球最少買一只，有多少種買法？ 解：①這是一個(gè)多重集的組合問題 類別數(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è)崗位?，F(xiàn)在軟件設(shè)計(jì)崗位（崗位A）（包括需求分析、概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)等工作）的人數(shù)是15人，代碼編寫崗位（崗位B）的人數(shù)是32人，軟件測(cè)試崗位（崗位C）的人數(shù)是28人，同時(shí)參加崗位A和崗位B的有12人, 同時(shí)參加崗位B和崗位C的有8人, 同時(shí)參加崗位A和崗位C組的有3人，問，三個(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) 說明：也可以直接利用組合演算公式進(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, 問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)通過命題邏輯推理，推論出誰是真正的盜竊犯？（寫出詳細(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ù)中國剩余定理，特解是： 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 解密后的明文與原來的明文是相等的，所以算法正確。 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）寫出A的商集； 14.基于字典序的組合生成算法 問題說明：假設(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三人選派若干人出國考察, 需滿足下述條件:(1)若A去, 則C必須去;(2)若B去, 則C不能去;(3)A和B必須去一人且只能去一人.問有幾種可能的選派方案? 9
點(diǎn)擊咨詢 