簡介這份2023年同等學(xué)力申碩計(jì)算機(jī)國考數(shù)學(xué)真題解析面向報(bào)考計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的備考考生聚焦離散數(shù)學(xué)、集合論、圖論與組合數(shù)學(xué)等核心模塊覆蓋邏輯表達(dá)、冪集運(yùn)算、完全二叉樹、偏序關(guān)系、平面圖性質(zhì)及容斥原理等題型。所有試題均附詳細(xì)解析可幫助讀者梳理解題脈絡(luò)、強(qiáng)化數(shù)學(xué)推導(dǎo)能力。資料僅含1個(gè)docx文檔大小約2.61MB按選擇、填空、計(jì)算分類組織便于逐項(xiàng)攻克已有560人學(xué)習(xí)瀏覽適合沖刺階段查漏補(bǔ)缺或系統(tǒng)回顧國考數(shù)學(xué)要點(diǎn)。通過真題演練讀者能深入掌握全稱量詞與存在量詞轉(zhuǎn)換、鏈與反鏈分析、圖的著色計(jì)數(shù)等難點(diǎn)提升離散結(jié)構(gòu)綜合運(yùn)用水平。1. 2023 同等學(xué)力申碩計(jì)算機(jī)真題里的離散數(shù)學(xué)與組合數(shù)學(xué)答案不是背出來的2023 同等學(xué)力申碩計(jì)算機(jī)真題里離散數(shù)學(xué)和組合數(shù)學(xué)是很多人考前最沒底的部分概念多、題面短一步推錯(cuò)整道題就沒了。常見做法是把復(fù)習(xí)時(shí)間全壓在算法和數(shù)據(jù)庫上結(jié)果考場上面對一道“判斷是否為等價(jià)關(guān)系”的選擇題四個(gè)選項(xiàng)長得一樣只能靠蒙。實(shí)際上這兩個(gè)科目的命題規(guī)律很清晰題型高度固定按考點(diǎn)拆開練是性價(jià)比很高的一環(huán)。離散數(shù)學(xué)考的是“定義-判定-推導(dǎo)”三步定義記得住判定步驟不跳推導(dǎo)每一步有依據(jù)答案就穩(wěn)。組合數(shù)學(xué)則更依賴“先分類后分步”的計(jì)數(shù)習(xí)慣以及把“至少”轉(zhuǎn)成“補(bǔ)集”的思維。兩者都不是靠背答案能解決的需要的是能重復(fù)動(dòng)筆的解析套路。下面不打算把 2023 真題原卷逐字復(fù)述而是用同型題把這類題的拆法講清楚先看題型分布再按考點(diǎn)逐個(gè)過最后給一個(gè)避坑清單。這樣不管拿到的是哪一年的真題你都能直接用同一套方法去解析、去核對答案而不是被某一道不會(huì)的題卡住。2. 先拆題型再做題離散數(shù)學(xué)與組合數(shù)學(xué)的考點(diǎn)分布和復(fù)習(xí)優(yōu)先級(jí)2.1 選擇填空 vs 計(jì)算證明兩類題型決定兩種復(fù)習(xí)方式同等學(xué)力申碩計(jì)算機(jī)卷子里數(shù)學(xué)部分通常采用客觀題加主觀題混出的形式。選擇題和填空題的特點(diǎn)是題面短、選項(xiàng)接近主要考查概念辨析和性質(zhì)記憶計(jì)算題和證明題則要求把推導(dǎo)過程寫完整評卷時(shí)會(huì)看步驟分即使最后答案錯(cuò)了中間寫出關(guān)鍵變換也可能拿一部分分。這個(gè)差異直接決定了復(fù)習(xí)方式客觀題靠“刷判斷”把容易混淆的結(jié)論反復(fù)對比比如歐拉圖條件到底是“所有頂點(diǎn)度數(shù)為偶數(shù)”還是“連通且所有頂點(diǎn)度數(shù)為偶數(shù)”主觀題靠“寫推導(dǎo)”每一道題都要像考試一樣完整寫下來不能看一眼覺得會(huì)就跳過。另一個(gè)常見誤區(qū)是只按章節(jié)順序復(fù)習(xí)不看題型權(quán)重。離散數(shù)學(xué)里的命題邏輯幾乎年年出現(xiàn)圖論證明題偶爾出現(xiàn)組合數(shù)學(xué)里的排列組合基本是計(jì)算題遞推關(guān)系則更多以小題出現(xiàn)。如果你時(shí)間有限應(yīng)該先拿確定性高的題型再補(bǔ)冷門考點(diǎn)。我的習(xí)慣是第一輪不按教材目錄走而是按“題型-考點(diǎn)”對照表走把每個(gè)考點(diǎn)對應(yīng)的考法列出來再?zèng)Q定練多少遍。還有一個(gè)容易被忽視的點(diǎn)客觀題與主觀題對公式記憶的要求不同。選擇題里四個(gè)選項(xiàng)會(huì)幫你排除一部分錯(cuò)誤比如量詞否定題你只要記得“否定要推進(jìn)到謂詞內(nèi)部”就能排除兩個(gè)選項(xiàng)證明題則沒有任何提示每一步都必須寫出依據(jù)。所以復(fù)習(xí)時(shí)不能只做選擇題至少要把每個(gè)核心考點(diǎn)的證明題各練一遍否則考場上一到“請證明”就容易卡住。2.2 高頻考點(diǎn)地圖邏輯、集合、圖論、計(jì)數(shù)四條主線把整本離散數(shù)學(xué)和組合數(shù)學(xué)壓縮成四條主線更容易避免“翻到哪里看到哪里”。第一條主線是數(shù)理邏輯包括命題邏輯與謂詞邏輯常考真值表、等價(jià)式、范式和量詞否定第二條主線是集合與關(guān)系包括子集計(jì)數(shù)、等價(jià)關(guān)系、偏序關(guān)系、關(guān)系閉包第三條主線是圖論基礎(chǔ)包括樹的性質(zhì)、歐拉圖、哈密頓圖和二分圖判定第四條主線是組合計(jì)數(shù)包括加法原理、乘法原理、排列組合、容斥原理、錯(cuò)排以及簡單遞推。這四條主線之間有明顯的承接關(guān)系數(shù)理邏輯培養(yǎng)符號(hào)化能力集合與關(guān)系提供結(jié)構(gòu)判斷工具圖論把關(guān)系變成圖來直觀處理組合計(jì)數(shù)則解決“有多少種選法”的計(jì)數(shù)問題。復(fù)習(xí)時(shí)不要把它們割裂開比如等價(jià)關(guān)系可以用圖論的連通分量來理解傳遞閉包本身就是一張有向圖的連通性計(jì)算?？紙錾虾芏嗑C合題正是在這種交叉點(diǎn)上做文章常見組合是“集合關(guān)系里的哈斯圖 偏序集的極值判斷”以及“一筆畫問題 歐拉圖判定”。我在給備考者做復(fù)習(xí)計(jì)劃時(shí)通常會(huì)讓他們先花一個(gè)晚上把這四條主線對應(yīng)的章節(jié)標(biāo)題寫在紙上再依次默寫每個(gè)章節(jié)下面至少三個(gè)考點(diǎn)。默寫不出來的考點(diǎn)就是第一周需要優(yōu)先補(bǔ)的短板。這個(gè)動(dòng)作比直接刷一套真題更能暴露知識(shí)地圖的缺口。2.3 用考點(diǎn)-題型對照表給復(fù)習(xí)排優(yōu)先級(jí)下表是我整理考點(diǎn)時(shí)常用的排優(yōu)先級(jí)方式。優(yōu)先級(jí)列里的 P0 表示必須完全拿下、P1 表示盡量不丟分、P2 表示學(xué)有余力再深入。你不需要照搬但建議按這個(gè)思路自己做一張把近三年真題里見過的考點(diǎn)填進(jìn)去?？键c(diǎn)常見題型判定關(guān)鍵優(yōu)先級(jí)命題邏輯等價(jià)式選擇、證明真值表或等價(jià)變換P0謂詞邏輯與量詞否定選擇、填空否定推進(jìn)順序P0集合與子集計(jì)數(shù)選擇、填空空集、全集邊界P1等價(jià)/偏序關(guān)系選擇、證明三條性質(zhì)逐條驗(yàn)證P1關(guān)系閉包計(jì)算自反/對稱/傳遞閉包公式P1樹與生成樹選擇、證明邊數(shù)、連通、無回路P1歐拉圖與哈密頓圖選擇、判斷連通性度數(shù)條件P1排列組合計(jì)算順序敏感還是無關(guān)P0容斥原理計(jì)算、證明補(bǔ)集優(yōu)先P0錯(cuò)排計(jì)算D_n 前幾項(xiàng)P2遞推關(guān)系計(jì)算、選擇初始條件遞推式P2用這張表做優(yōu)先級(jí)排序時(shí)有一個(gè)容易被忽略的原則優(yōu)先處理“題面變化少、解法固定”的考點(diǎn)。比如量詞否定、歐拉圖條件、錯(cuò)排公式都屬于解法固定型練三五道同型題就能穩(wěn)定拿分而綜合證明題變化多短期提升有限優(yōu)先級(jí)反而要往后放。每完成一個(gè) P0 考點(diǎn)就在表上標(biāo)注當(dāng)天正確率正確率低于八成時(shí)不要直接進(jìn)下一個(gè)考點(diǎn)。刷題量可以按這個(gè)參考P0 考點(diǎn)每個(gè)至少 8 到 10 道P1 考點(diǎn)每個(gè) 5 到 6 道P2 考點(diǎn)每個(gè) 3 道左右。數(shù)量不是目的正確率才是。如果連續(xù)三道同型題都做對說明這個(gè)考點(diǎn)已經(jīng)過關(guān)如果一道題卡了十五分鐘就直接看答案然后重新推導(dǎo)不要死磕。2.4 把一套真題變成考點(diǎn)標(biāo)注表三遍讀題法真題的價(jià)值不在于做對多少而在于能不能從題目里讀到考點(diǎn)。我一般推薦用三遍讀題法處理一套卷子第一遍通讀只標(biāo)題型不寫答案把每道題歸入數(shù)理邏輯、集合關(guān)系、圖論、組合計(jì)數(shù)四條主線之一標(biāo)在題號(hào)旁邊第二遍細(xì)讀把題干里的關(guān)鍵詞圈出來比如“等價(jià)關(guān)系”“至少”“歐拉回路”“錯(cuò)排”與考點(diǎn)對照表一一對應(yīng)第三遍定向讀只看錯(cuò)題和卡住題反推它考的是哪個(gè)判定條件然后把這個(gè)考點(diǎn)旁寫一個(gè)“坑”字。很多考生真題做了三套卻說不出每套題覆蓋哪些考點(diǎn)就是因?yàn)橹蛔鲱}沒標(biāo)注。用三遍讀題法三套題下來就會(huì)形成自己的考點(diǎn)坐標(biāo)。到了考試前一周你不需要再看整本教材只看這張標(biāo)注表上出現(xiàn)過“坑”的考點(diǎn)就夠了。這個(gè)方法不需要額外工具一張 A4 紙、三支不同顏色的筆就能完成。3. 離散數(shù)學(xué)真題解析用“定義回查法”拿下邏輯、關(guān)系和圖論3.1 命題邏輯與謂詞邏輯真值表、等價(jià)變換與量詞否定命題邏輯的核心是判斷兩個(gè)公式是否等價(jià)以及把一個(gè)自然語言命題準(zhǔn)確符號(hào)化。常用的工具是真值表把每個(gè)命題變元的所有真值組合都列出來比較兩列結(jié)果。這個(gè)方法的優(yōu)點(diǎn)是機(jī)械、不易錯(cuò)缺點(diǎn)是變量多于三個(gè)時(shí)表會(huì)變大。所以考試中更推薦等價(jià)變換法比如蘊(yùn)含等值式 P→Q ? ?P∨Q、德摩根律、分配律等這些公式需要在做題前默寫一遍能明顯提高推導(dǎo)速度。謂詞邏輯的難點(diǎn)在量詞否定。題目常給出“不存在……”或“不是所有……”這樣的自然語言要求符號(hào)化或判斷真值。解法順序是先確定論域再把自然語言拆成主謂結(jié)構(gòu)然后逐層寫量詞和謂詞。否定出現(xiàn)時(shí)記住兩條規(guī)則??xP(x) 等價(jià)于 ?x?P(x)??xP(x) 等價(jià)于 ?x?P(x)。遇到連續(xù)量詞時(shí)從外層向內(nèi)層逐次套用同時(shí)注意轄域里的聯(lián)結(jié)詞也要跟著取反。同型題設(shè)論域?yàn)槿空麛?shù)P(x)x 是偶數(shù)Q(x)x 是質(zhì)數(shù)。請符號(hào)化“不是所有質(zhì)數(shù)都是偶數(shù)”并判斷該命題的真假。解答原句等價(jià)于“??x(Q(x)→P(x))”。先用量詞否定規(guī)則得到 ?x?(Q(x)→P(x))。再對蘊(yùn)含公式取反Q(x)→P(x) 等價(jià)于 ?Q(x)∨P(x)所以它的否定是 Q(x)∧?P(x)。最終公式為 ?x(Q(x)∧?P(x))用自然語言說就是“存在一個(gè)質(zhì)數(shù)且不是偶數(shù)”。整數(shù)中 3 是質(zhì)數(shù)但不是偶數(shù)因此命題真值為真。核對答案時(shí)要注意有些參考書會(huì)把質(zhì)數(shù)限定為正整數(shù)結(jié)論不變但推導(dǎo)里的論域要寫清楚。如果題目把 P、Q 的順序調(diào)換答案可能會(huì)變成“不是所有偶數(shù)都是質(zhì)數(shù)”邏輯上等價(jià)但自然語言句意不同別一看到相似題就直接套公式。檢查符號(hào)化是否正確的最快方式是反著翻譯一遍把公式讀回成自然語言看與原句是否一致。3.2 集合與關(guān)系等價(jià)類、偏序與閉包的判定順序集合與關(guān)系最常考的三種題型是判斷一個(gè)二元關(guān)系是否為等價(jià)關(guān)系或偏序關(guān)系計(jì)算關(guān)系的三種閉包給定等價(jià)關(guān)系寫出等價(jià)類。解題順序建議固定為先檢查自反性再檢查對稱性或反對稱性最后檢查傳遞性。因?yàn)樽苑葱宰钊菀淄ㄟ^集合元素逐一檢查傳遞性最容易出錯(cuò)放在最后。關(guān)系矩陣是一種高效檢查工具。把關(guān)系 R 寫成 n×n 的 0-1 矩陣后對角線全為 1 說明自反矩陣轉(zhuǎn)置等于自己說明對稱傳遞性則需要看是否滿足 R°R?R直接算復(fù)合矩陣或逐對檢查。對于偏序關(guān)系額外要求反對稱也就是矩陣中關(guān)于對角線對稱的兩個(gè)位置不能同時(shí)為 1除非正好在對角線上。同型題設(shè)集合 A{1,2,3}關(guān)系 R{(1,1),(2,2),(3,3),(1,2),(2,3)}。判斷 R 是否為等價(jià)關(guān)系并求其傳遞閉包。解答自反性滿足對角線三元組都在對稱性不滿足因?yàn)?(1,2) 在但 (2,1) 不在所以 R 不是等價(jià)關(guān)系。求傳遞閉包時(shí)觀察 (1,2)、(2,3)傳遞性要求 (1,3) 也必須加入加入后檢查 (1,3) 與 (2,3) 之間沒有新的傳遞需求因此傳遞閉包為 R∪{(1,3)}也就是 {(1,1),(2,2),(3,3),(1,2),(2,3),(1,3)}。這道題最容易錯(cuò)的地方是判斷等價(jià)關(guān)系時(shí)先看傳遞性結(jié)果把順序搞亂漏掉對稱性檢查。有一個(gè)小技巧任何等價(jià)關(guān)系對應(yīng)的關(guān)系矩陣必然對稱且對角線全 1看到矩陣不對稱就可以直接排除不必再做傳遞性。求傳遞閉包時(shí)用 Warshall 算法會(huì)得到同樣結(jié)果但簡單題用逐步添加法更快。偏序關(guān)系的典型考法是畫哈斯圖然后找極大元、極小元、最大元、最小元。做題時(shí)先刪掉自環(huán)和傳遞邊只保留直接覆蓋關(guān)系再畫圖。最大元與極大元的區(qū)別是最大元必須與所有元素可比極大元只是沒有比自己更大的元素。一個(gè)偏序集可能沒有最大元但可以有多個(gè)極大元這個(gè)區(qū)分也是選擇題常設(shè)的坑。3.3 圖論樹、歐拉圖、哈密頓圖的判定表與典型答案圖論判斷最推薦的方法是“判定表法”考試前把每個(gè)概念的先決條件寫成一列逐條對照。比如樹的條件是連通且無回路等價(jià)替換為 n 個(gè)頂點(diǎn) n-1 條邊且連通歐拉圖的條件是連通且所有頂點(diǎn)度數(shù)為偶數(shù)半歐拉圖是連通且恰好兩個(gè)奇度頂點(diǎn)哈密頓圖沒有簡潔的充要條件但可以先用 Dirac 定理做充分性判斷若 n≥3 且每個(gè)頂點(diǎn)度數(shù)都不小于 n/2則圖是哈密頓圖。這只是充分條件不滿足不代表不是哈密頓圖所以考試常以“是否一定存在哈密頓回路”來繞彎。圖的類型判定條件考試常見陷阱樹連通、無回路邊數(shù)n-1只記邊數(shù)不驗(yàn)證連通性歐拉圖連通且所有頂點(diǎn)度數(shù)均為偶數(shù)忘記連通性或把奇偶度看反半歐拉圖連通且恰好兩個(gè)奇度頂點(diǎn)把“恰好兩個(gè)”寫成“至少兩個(gè)”哈密頓圖Dirac 充分條件n≥3每個(gè)頂點(diǎn)度數(shù)≥n/2把充分條件當(dāng)充要條件同型題某個(gè)無向圖有 6 個(gè)頂點(diǎn)、9 條邊每個(gè)頂點(diǎn)度數(shù)都是 3。問該圖是否可能為歐拉圖解答歐拉圖要求所有頂點(diǎn)度數(shù)為偶數(shù)而這里每個(gè)頂點(diǎn)度數(shù)為 3是奇數(shù)因此無論是否連通都不可能是歐拉圖。如果題目把度數(shù)改成 4則還需要確認(rèn)連通性否則也不能直接下結(jié)論。這個(gè)陷阱非常典型因?yàn)楹芏嗳嗽诳紙錾峡吹健岸葦?shù)相等”就開始套公式忽略了最前面的連通性前置。圖論證明題里樹的等價(jià)定義很實(shí)用n 個(gè)頂點(diǎn)的無向圖只要滿足“連通且無回路”“連通且邊數(shù)為 n-1”“無回路且邊數(shù)為 n-1”“任意兩頂點(diǎn)之間有唯一路徑”中的任意兩條就可以推出其他條件。考試時(shí)寫證明不要只背定義要把條件之間的推導(dǎo)鏈寫出來步驟分通常來自這里。4. 組合數(shù)學(xué)真題解析計(jì)數(shù)、容斥和遞推的實(shí)戰(zhàn)拆解4.1 排列組合先問“順序是否敏感”再選公式組合計(jì)數(shù)的第一原則是拿到計(jì)數(shù)題先問一句“交換兩個(gè)元素后算不算同一個(gè)結(jié)果”。算同一個(gè)用組合 C不算同一個(gè)用排列 A。第二步問“這個(gè)結(jié)果是分幾步完成的還是分幾類情況”分步用乘法原理分類用加法原理。這兩個(gè)問題理順了排列組合題基本不會(huì)跑偏。常見題型包括從 n 個(gè)不同元素中取 m 個(gè)并排序方案數(shù)是 A(n,m)n!/(n-m)!取 m 個(gè)但不排序方案數(shù)是 C(n,m)A(n,m)/m!。有重復(fù)元素的排列需要除以重復(fù)元素的全排列數(shù)圓周排列則比直線排列少一個(gè)“旋轉(zhuǎn)對稱”常見公式是 (n-1)!。同型題有 5 本不同的數(shù)學(xué)書和 3 本不同的英語書從中選 3 本要求至少有一本是數(shù)學(xué)書共有多少種選法解答先算無限制的總數(shù)C(8,3)56。再算不滿足條件的補(bǔ)集也就是 3 本全是英語書只有 C(3,3)1 種。所以滿足條件的選法是 56-155 種。這道題同樣適用于容斥思路說明“補(bǔ)集優(yōu)先”和容斥本質(zhì)上是同一件事。如果題目改成“至少兩本是數(shù)學(xué)書”補(bǔ)集為“0 本或 1 本數(shù)學(xué)書”即 C(3,3)C(3,2)C(5,1)11516總數(shù) 56-1640也可以用分類法驗(yàn)證。注意分類法在選項(xiàng)接近的選擇題里容易漏計(jì)數(shù)我的習(xí)慣是用補(bǔ)集先出答案再用分類法檢查兩個(gè)結(jié)果一致時(shí)再填答題卡。重復(fù)元素排列題也是高頻錯(cuò)誤點(diǎn)。比如“把 3 個(gè)紅球和 2 個(gè)藍(lán)球排成一列”不是 5!而是 5!/(3!2!)10。原因是從位置角度5 個(gè)位置先選 3 個(gè)放紅球剩下放藍(lán)球即 C(5,3)10。這類題只要把“相同元素”識(shí)別出來借助組合數(shù)可以少背一條公式。4.2 容斥原理與錯(cuò)排計(jì)數(shù)至少問題優(yōu)先走補(bǔ)集容斥原理在同等學(xué)力計(jì)算機(jī)考試?yán)锍Ｒ詢蓚€(gè)或三個(gè)集合交集的形式出現(xiàn)。兩個(gè)集合時(shí)|A∪B||A||B|-|A∩B|三個(gè)集合時(shí)要加回三交集。碰到“至少屬于一個(gè)集合”“既不是…也不是…”這類表述都可以先畫韋恩圖再套容斥公式。關(guān)鍵是把每個(gè)區(qū)域的人數(shù)或元素?cái)?shù)標(biāo)全尤其不能漏掉“三者都不是”的區(qū)域。兩個(gè)集合的容斥用在計(jì)數(shù)題里本質(zhì)上是把重疊部分重復(fù)計(jì)算了一次然后減掉一次?？荚嚂r(shí)如果你對自己的計(jì)算沒把握可以把每個(gè)集合的元素?cái)?shù)拆開寫再合并同類項(xiàng)。這樣即使最終答案算錯(cuò)步驟里也能看到清晰的容斥結(jié)構(gòu)能拿到部分分。錯(cuò)排是一個(gè)更具體的計(jì)數(shù)模型n 個(gè)元素重新排列要求每個(gè)元素都不在原來的位置。常用遞推公式 D_n(n-1)(D_{n-1}D_{n-2})初值 D_10D_21也常用 D_32D_49?？荚嚥粫?huì)讓你現(xiàn)場推公式記住前四個(gè)值更劃算。同型題4 個(gè)人各寫一張賀卡把 4 張賀卡混在一起再隨機(jī)發(fā)回問沒有一個(gè)人拿到自己寫的賀卡的發(fā)放方式有多少種解答這就是錯(cuò)排 D_49。算的時(shí)候先從排列總數(shù) 4!24 出發(fā)再逐步排除至少一人拿到自己賀卡的情況會(huì)得到同一個(gè)結(jié)果。建議考生把錯(cuò)排數(shù)和前面的 C(n,m) 放在同一張記憶卡片上因?yàn)檫@類題答案通常不是靠現(xiàn)場推導(dǎo)而是靠快速調(diào)取值。4.3 遞推關(guān)系與生成函數(shù)寫出初始條件再套公式遞推關(guān)系題的典型表述是“每一步只能上 1 級(jí)或 2 級(jí)樓梯”“平面被 n 條直線劃分成多少區(qū)域”。這類題的關(guān)鍵不是背遞推公式而是先確認(rèn)兩個(gè)邊界條件n1 時(shí)有幾種走法n2 時(shí)有幾種走法。邊界寫錯(cuò)后面全錯(cuò)。同型題上樓梯每次可以上 1 級(jí)或 2 級(jí)問上到第 10 級(jí)臺(tái)階共有多少種不同走法。解答設(shè) f(n) 為上到第 n 級(jí)的方法數(shù)。最后一步可能來自第 n-1 級(jí)或第 n-2 級(jí)因此 f(n)f(n-1)f(n-2)。初始值 f(1)1f(2)2。逐項(xiàng)算f(3)3f(4)5f(5)8f(6)13f(7)21f(8)34f(9)55f(10)89。所以答案是 89。檢查時(shí)可以用小值驗(yàn)證比如 f(3)3手動(dòng)枚舉 111、12、21 確實(shí)為 3說明遞推式正確。特征方程法是解線性遞推的高頻工具。對于 f(n)p f(n-1)q f(n-2)設(shè)特征方程 x^2-px-q0解出兩個(gè)根寫出通項(xiàng) f(n)c1 r1^nc2 r2^n再用初始值定 c1、c2?？紙錾先绻阌弥痦?xiàng)遞推能推出答案就不必用通項(xiàng)公式但證明題可能要求寫出通項(xiàng)這時(shí)特征方程是標(biāo)準(zhǔn)做法。生成函數(shù)在近幾年真題里出現(xiàn)頻率不高但一旦出現(xiàn)往往是比較固定的套模型題給出數(shù)列的遞推關(guān)系要求寫它的生成函數(shù)或反過來由生成函數(shù)求數(shù)列通項(xiàng)。這類題計(jì)算步驟長但變化少適合放到復(fù)習(xí)后期專門練。熟練之后可以用待定系數(shù)法把遞推式轉(zhuǎn)成生成函數(shù)方程再展開提取系數(shù)。備考時(shí)間不足時(shí)先保排列組合和容斥生成函數(shù)可以放一放。5. 避坑真題解析里最常翻車的五個(gè)失分點(diǎn)與答案核對四步法5.1 量詞否定反了真值表推得對邏輯鏈卻斷了現(xiàn)象做謂詞邏輯符號(hào)化時(shí)把“不是所有質(zhì)數(shù)都是偶數(shù)”寫成 ??x(Q(x)→P(x)) 的下一步直接寫成 ??x(Q(x)→P(x))量詞從 ? 變成 ?但否定符號(hào)沒有推進(jìn)到謂詞內(nèi)部。真值表推到最后發(fā)現(xiàn)兩個(gè)公式的真假對不上又找不到錯(cuò)在哪一步。原因只背了“否定要變符號(hào)”的口訣卻不清楚變的是量詞還是否定符號(hào)的位置。實(shí)際上 ??xP(x) 與 ?x?P(x) 是兩套公式不能把 ?? 和 ?? 混用。解決寫下否定公式后先檢查最前面的否定符號(hào)是否已經(jīng)被推進(jìn)到謂詞部分。如果公式里還有“??”或“??”說明還沒有完成否定。每次做完后用自然語言重讀一遍讀不通就說明符號(hào)化有問題。5.2 集合計(jì)數(shù)漏掉空集送分題變成必錯(cuò)題現(xiàn)象題目問“集合 A{a,b,c} 有多少個(gè)真子集”答案寫成 2^3-17這是對的但問“有多少個(gè)子集”時(shí)有人還是寫 7漏掉空集。還有一類變體是求“非空真子集”正確答案是 2^3-26錯(cuò)誤答案五花八門。原因刷題時(shí)反復(fù)強(qiáng)調(diào)真子集公式把“子集”和“真子集”的條件混淆或者一看到集合就默認(rèn)要減一。解決做題時(shí)把“子集”兩字圈出來旁邊寫“包含空集”再寫公式 2^n看到“真子集”旁邊寫“不含全集”公式 2^n-1看到“非空子集”不含空集公式也是 2^n-1如果問“非空真子集”兩個(gè)都要去掉公式是 2^n-2。這個(gè)區(qū)分不值得丟分但每次考試都會(huì)有人倒在這里。5.3 歐拉圖只記“偶數(shù)度”連通性被丟在一邊現(xiàn)象給一個(gè)由兩個(gè)連通分量組成的圖每個(gè)分量內(nèi)部所有頂點(diǎn)度數(shù)都是偶數(shù)問是否為歐拉圖很多人回答是。在他們看來每個(gè)頂點(diǎn)度數(shù)都是偶數(shù)已經(jīng)滿足了條件。原因歐拉圖定理的記憶碎片化了只記結(jié)論“所有頂點(diǎn)度數(shù)均為偶數(shù)”忘掉前提“圖是連通圖”。這個(gè)定理本身是充要條件兩個(gè)條件缺一不可。解決把條件拼成一句話“一個(gè)圖存在經(jīng)過每條邊一次的回路需要同時(shí)滿足圖連通 且 每個(gè)頂點(diǎn)的度數(shù)為偶數(shù)”。做題時(shí)先花 5 秒檢查連通性再檢查度數(shù)。如果題目給的是有向圖還要額外看每個(gè)頂點(diǎn)的入度是否等于出度。同等學(xué)力考試多以無向圖為主但有向圖版本偶爾作為干擾項(xiàng)出現(xiàn)。5.4 組合“至少”不轉(zhuǎn)補(bǔ)集又慢又容易重復(fù)計(jì)數(shù)現(xiàn)象“至少有一本數(shù)學(xué)書”這類題有些考生習(xí)慣分三種情況討論步驟多、耗時(shí)還可能在計(jì)算 C(5,1)C(3,2) 時(shí)把某種情況重復(fù)算進(jìn)去。最后答案看似合理實(shí)際多算了。原因缺少“補(bǔ)集優(yōu)先”的思維慣性?？吹健爸辽佟本拖氲椒诸悰]有意識(shí)到“總數(shù)減不滿足”通常更快也更不容易出錯(cuò)。解決看到“至少”先寫總數(shù)再寫不滿足條件的補(bǔ)集計(jì)算完用分類法交叉驗(yàn)證。比如至少一本科普書的選法補(bǔ)集是“一本科普書都沒有”至少兩項(xiàng)符合要求的組合補(bǔ)集是“符合 0 項(xiàng)或 1 項(xiàng)”。把補(bǔ)集作為默認(rèn)路線分類法只用來檢查能明顯降低重復(fù)計(jì)數(shù)概率。5.5 答案核對四步法從“看懂答案”到“確認(rèn)獨(dú)立做題”這個(gè)方法不是坑而是防坑工具。很多備考者卡在“看懂答案”和“獨(dú)立做出”之間本質(zhì)是復(fù)盤方式不對。只看答案時(shí)注意力會(huì)順著解析走覺得自己全會(huì)合上資料后才發(fā)現(xiàn)第一步都寫不出來。第一步第一遍獨(dú)立做題哪怕慢。不要一上來就看答案至少寫出前兩步思路再對照。第二步對照答案時(shí)用不同顏色標(biāo)出“卡住點(diǎn)”比如傳遞性檢查、補(bǔ)集轉(zhuǎn)化不要只標(biāo)對錯(cuò)號(hào)。第三步對計(jì)算題用兩種方法各算一遍比如分類法和補(bǔ)集法或者逐項(xiàng)遞推和特征方程法兩個(gè)結(jié)果一致才算穩(wěn)。第四步把錯(cuò)題歸入四個(gè)考點(diǎn)邏輯、集合關(guān)系、圖論、組合計(jì)數(shù)每類挑一道代表性錯(cuò)題周末重做。提示真題的參考答案偶爾會(huì)把“半歐拉圖”和“歐拉圖”混用核對時(shí)以教材定義為準(zhǔn)。看到答案與你沖突先不要急著改重新讀題看有沒有“通路”和“回路”的區(qū)別。5.6 考場時(shí)間分配失衡選擇題死磕證明題留白現(xiàn)象考試時(shí)在一道量詞否定選擇題上反復(fù)驗(yàn)證花了八分鐘結(jié)果后面的圖論證明題只剩兩分鐘整道題空白交卷。對答案時(shí)發(fā)現(xiàn)那道選擇題用否定推進(jìn)法一分鐘就能出結(jié)果。原因?qū)γ款}時(shí)間沒有上限意識(shí)總想“再做一步就能確定”導(dǎo)致單題超時(shí)。證明題雖然分值高但需要完整的推導(dǎo)時(shí)間被選擇題擠占后很難補(bǔ)救。解決平時(shí)限時(shí)訓(xùn)練時(shí)給自己定規(guī)則選填題每題不超過 2 分鐘計(jì)算題每題不超過 8 分鐘證明題每題不少于 10 分鐘。進(jìn)了考場先掃一遍試卷把一眼能確定答案的題先做掉再做計(jì)算題最后集中攻證明題。如果某道選擇題在兩分鐘內(nèi)沒有確定答案先選一個(gè)最可能的并做標(biāo)記回頭有時(shí)間再驗(yàn)算。6. 把解析能力變成考場得分三周刷題法和一個(gè)復(fù)盤習(xí)慣如果距離考試還有三周我建議按下面這個(gè)節(jié)奏來。第一周按考點(diǎn)刷不按試卷刷。把第 2 章那張考點(diǎn)表拿出來每天完成兩個(gè) P0/P1 考點(diǎn)每個(gè)考點(diǎn)做 6 到 8 道同型題并填正確率。正確率低于 80% 的考點(diǎn)第二天重做錯(cuò)題后再進(jìn)下一個(gè)考點(diǎn)。第二周整卷限時(shí)。找一份真題卷按考試時(shí)間做數(shù)學(xué)部分控制在 60 分鐘內(nèi)完成。不限時(shí)做題和限時(shí)做題是完全不同的狀態(tài)很多考生平時(shí)都會(huì)一到限時(shí)就在量詞否定和容斥上反復(fù)糾結(jié)導(dǎo)致后面證明題沒時(shí)間。第三周只做錯(cuò)題清單。把前兩周錯(cuò)過的題重新做一遍不看解析。這一步的收獲通常比第一周還大因?yàn)殄e(cuò)題暴露的是思維漏洞而不是知識(shí)多少。我的復(fù)盤習(xí)慣是每道錯(cuò)題旁邊只寫一個(gè)“錯(cuò)因詞”比如“量詞否定”“漏空集”“未驗(yàn)證連通性”“沒轉(zhuǎn)補(bǔ)集”。這個(gè)動(dòng)作看起來簡單但能快速定位高頻錯(cuò)誤比抄一整段解析有用得多?？记白詈笠惶煳也辉倏葱骂}只看這些錯(cuò)因詞哪個(gè)詞陌生就回去重做對應(yīng)那道題。另一個(gè)值得養(yǎng)成的習(xí)慣是“按定義回查”?？紙錾先绻貌粶?zhǔn)某個(gè)概念比如哈密頓圖的充分條件就默念一遍 Dirac 定理的定義而不是憑印象猜。定義記準(zhǔn)了選擇題等于送分計(jì)算題也不容易跑偏。我備考時(shí)最虧的一件事是把大量時(shí)間花在看解析上以為看懂了就等于會(huì)做了。后來改成“先推后看看完重推”正確率明顯提升。希望幫到你。本文還有配套的精品資源點(diǎn)擊獲取