簡(jiǎn)介軟件設(shè)計(jì)師中級(jí)考點(diǎn)筆記精華版面向正在備考軟考中級(jí)的考生用于快速回顧高頻考點(diǎn)、難點(diǎn)公式與易錯(cuò)點(diǎn)。文檔系統(tǒng)覆蓋數(shù)據(jù)結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)包括鄰接矩陣、順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)、散列存儲(chǔ)和索引存儲(chǔ)深入解析二叉排序樹(shù)、滿二叉樹(shù)、平衡二叉樹(shù)、哈夫曼樹(shù)等內(nèi)容并給出哈夫曼樹(shù)構(gòu)造、WPL計(jì)算等典型例題。查找部分涵蓋二分查找和分塊查找排序部分梳理直接插入、簡(jiǎn)單選擇、冒泡、希爾、快速、堆、歸并、基數(shù)等常用算法并附時(shí)間復(fù)雜度與穩(wěn)定性對(duì)比。壓縮包內(nèi)共有1個(gè)Word文檔包體大小3.37MB要點(diǎn)式整理、結(jié)構(gòu)緊湊適合考前突擊、日常查閱和自行標(biāo)注重點(diǎn)復(fù)習(xí)時(shí)可隨時(shí)按章節(jié)索引結(jié)合例題與對(duì)比表格鞏固記憶。該筆記已有381位學(xué)習(xí)者下載可幫助考生快速定位薄弱環(huán)節(jié)理解算法適用條件與典型陷阱提升復(fù)習(xí)效率。1. 軟考中級(jí)在考什么數(shù)據(jù)結(jié)構(gòu)模塊的考點(diǎn)分布與拿分策略軟件設(shè)計(jì)師中級(jí)備考上午科目里性價(jià)比最高的模塊就是數(shù)據(jù)結(jié)構(gòu)。軟考中級(jí)每年在這塊穩(wěn)定出十幾道選擇題圖的鄰接矩陣、哈夫曼樹(shù)、八大排序復(fù)雜度、原碼補(bǔ)碼范圍幾乎輪著考單個(gè)考點(diǎn)分值不高但出現(xiàn)的概率極高。這份考點(diǎn)筆記的精華恰好集中在這里每個(gè)考點(diǎn)都帶判定模板和真題解析把能拿的分先攥住?？甲C復(fù)習(xí)時(shí)間緊的人建議從數(shù)據(jù)結(jié)構(gòu)切進(jìn)去內(nèi)容不算多規(guī)律性強(qiáng)但概念相近“看著都熟、一做就錯(cuò)”的題占一半。下面按考點(diǎn)模塊過(guò)一遍高頻考點(diǎn)、真題做法和容易踩的坑照著背能少翻車。2. 圖與存儲(chǔ)結(jié)構(gòu)鄰接矩陣求度、四種存儲(chǔ)結(jié)構(gòu)選型與真題2.1 鄰接矩陣無(wú)向圖看行、有向圖分出行和列圖的表示里鄰接矩陣是選擇題常客。它的規(guī)則很簡(jiǎn)潔無(wú)向圖的鄰接矩陣是對(duì)稱矩陣第 i 行元素之和就是頂點(diǎn) i 的度有向圖要分開(kāi)算第 i 行元素之和是頂點(diǎn) i 的出度第 j 列元素之和是頂點(diǎn) j 的入度。考試很少讓你建一棵完整的圖通常直接給你矩陣某一行或某一列問(wèn)度數(shù)。比如原文里的例題頂點(diǎn) 4 的度就是第四行元素求和結(jié)果是 2。這類題真正考的不是“會(huì)不會(huì)遍歷矩陣”而是有沒(méi)有記住“無(wú)向看行、有向出度看行、入度看列”這個(gè)方向。用一段代碼模擬一遍比死記口訣更快# 4頂點(diǎn)無(wú)向圖的鄰接矩陣索引從0開(kāi)始 graph [ [0, 1, 1, 0], # 頂點(diǎn)1 [1, 0, 1, 1], # 頂點(diǎn)2 [1, 1, 0, 1], # 頂點(diǎn)3 [0, 1, 1, 0], # 頂點(diǎn)4 ] # 求頂點(diǎn)4的度第4行索引3所有元素求和 degree sum(graph[3]) print(degree) # 輸出2從代碼里能直接看到第 4 行只有兩個(gè)位置是 1分別對(duì)應(yīng)頂點(diǎn) 2 和頂點(diǎn) 3所以頂點(diǎn) 4 的度是 2。為什么無(wú)向圖的矩陣對(duì)稱因?yàn)橐粭l邊是雙向的頂點(diǎn) 2 和頂點(diǎn) 3 之間有邊那么第 2 行第 3 列和第 3 行第 2 列都會(huì)同時(shí)寫(xiě)成 1上面的 graph 里第 2 行和第 3 行就是互相鏡像的。對(duì)角線的位置在沒(méi)有自環(huán)時(shí)總是 0有些題目會(huì)特意問(wèn)“鄰接矩陣第 i 行第 i 列為什么是 0”答案就是該頂點(diǎn)到自身沒(méi)有邊。如果題目換成有向圖答題方向立刻變化行和是出度列和是入度。原文給的例子“頂點(diǎn) 3 的出度和入度分別為 5 和 16”意思是第 3 行有 5 個(gè)非零元素第 3 列有 16 個(gè)非零被 16 條邊指進(jìn)來(lái)。答題時(shí)先看題目說(shuō)的是“有向”還是“無(wú)向”再看問(wèn)的是“行”還是“列”兩步定位就能拿分。還有一個(gè)小細(xì)節(jié)鄰接矩陣的空間開(kāi)銷是 O(n^2)所以它適用在頂點(diǎn)數(shù)目不多的時(shí)候頂點(diǎn)多了矩陣會(huì)非常稀疏題目偶爾會(huì)拿這個(gè)點(diǎn)做迷惑項(xiàng)。2.2 順序、鏈?zhǔn)?、散列、索引四種存儲(chǔ)結(jié)構(gòu)怎么選存儲(chǔ)結(jié)構(gòu)的題幾乎都以“適合什么場(chǎng)景”的形式出現(xiàn)。順序存儲(chǔ)結(jié)構(gòu)用一組地址連續(xù)的存儲(chǔ)單元依次存放數(shù)據(jù)元素適合頻繁查詢鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)在計(jì)算機(jī)中用一組任意的存儲(chǔ)單元存放單元可以連續(xù)也可以不連續(xù)通過(guò)指針把前后元素串起來(lái)適合頻繁插入、刪除、更新。單鏈表、循環(huán)鏈表、雙鏈表都屬于鏈?zhǔn)酱鎯?chǔ)雙鏈表有兩個(gè)指針域靈活度高于單鏈表但每個(gè)結(jié)點(diǎn)多占一個(gè)指針域的內(nèi)存開(kāi)支也更大。散列存儲(chǔ)把數(shù)據(jù)元素的存儲(chǔ)位置和關(guān)鍵碼建立確定對(duì)應(yīng)關(guān)系本質(zhì)就是鍵值對(duì)查找技術(shù)哈希表是它的典型形態(tài)。索引存儲(chǔ)是單獨(dú)的物理數(shù)據(jù)庫(kù)結(jié)構(gòu)存的是某個(gè)表中一列或若干列值的集合以及指向這些值的數(shù)據(jù)頁(yè)邏輯指針清單數(shù)據(jù)庫(kù)索引就是最典型的應(yīng)用。記憶上可以抓一條主線查詢?yōu)橹鬟x順序變動(dòng)為主選鏈?zhǔn)秸业每爝x散列數(shù)據(jù)庫(kù)里的大表檢索選索引。真遇到“既要頻繁插入刪除、又要查詢”的題通常還是選鏈?zhǔn)揭驗(yàn)轫樞虮碓谥虚g插入要整體挪動(dòng)后續(xù)元素代價(jià)太大。鏈表內(nèi)部也要看清分支單鏈表一個(gè)指針域只能往后走循環(huán)鏈表尾結(jié)點(diǎn)指向頭結(jié)點(diǎn)形成環(huán)雙鏈表前后都能走靈活度最高。選擇題如果同時(shí)出現(xiàn)“循環(huán)鏈表”和“雙鏈表”優(yōu)先確認(rèn)是不是只在兩個(gè)端點(diǎn)增刪雙端操作多時(shí)循環(huán)鏈表和雙鏈表各有優(yōu)勢(shì)別一看到雙鏈表就直接選。存儲(chǔ)結(jié)構(gòu)核心特點(diǎn)典型適用場(chǎng)景順序存儲(chǔ)地址連續(xù)隨機(jī)訪問(wèn)快頻繁查詢數(shù)據(jù)穩(wěn)定不常變鏈?zhǔn)酱鎯?chǔ)存儲(chǔ)單元任意指針串聯(lián)頻繁插入、刪除、更新散列存儲(chǔ)關(guān)鍵碼與存儲(chǔ)位置建立對(duì)應(yīng)關(guān)系按關(guān)鍵字快速定位索引存儲(chǔ)單獨(dú)結(jié)構(gòu)存值集合和邏輯指針數(shù)據(jù)庫(kù)檢索避免全表掃描2.3 真題演練無(wú)向圖和有向圖的度數(shù)計(jì)算把原文例題當(dāng)作真題走一遍題目問(wèn)“頂點(diǎn) 4 的度是多少”先確認(rèn)矩陣是無(wú)向圖再定位到第四行。第四行元素求和得 2所以答案是 2。這類題容易錯(cuò)的地方在于行號(hào)從 0 開(kāi)始還是從 1 開(kāi)始題目如果寫(xiě)“頂點(diǎn) 4”行下標(biāo)記得是第 4 行而不是 graph[4]因?yàn)樗饕菑?0 起算的實(shí)際要訪問(wèn) graph[3]這個(gè)偏移量就是一道送命題。有向圖的變形題也是同一套思路給出鄰接矩陣問(wèn)某頂點(diǎn)的出度和入度出度看對(duì)應(yīng)行有多少個(gè)非零元素入度看對(duì)應(yīng)列有多少個(gè)非零元素。原文里的 5 和 16 就是行和列分別統(tǒng)計(jì)出來(lái)的結(jié)果。這里有個(gè)血淚經(jīng)驗(yàn)求入度時(shí)總有人慣性去看行因?yàn)椤叭搿笔峭锏姆较虻徑泳仃嚨牧胁攀羌^的終點(diǎn)看列才是入度。另外如果題目給的是帶權(quán)鄰接矩陣問(wèn)度數(shù)時(shí)只數(shù)非零格子就行可不要順手把權(quán)值全部加起來(lái)度是邊的條數(shù)不是邊權(quán)之和這兩者千萬(wàn)別混。3. 樹(shù)結(jié)構(gòu)高頻考點(diǎn)二叉排序樹(shù)、哈夫曼樹(shù)與AVL樹(shù)的判定模板3.1 二叉排序樹(shù)中序遞增、左小右大、最大結(jié)點(diǎn)無(wú)右子樹(shù)二叉排序樹(shù)是樹(shù)結(jié)構(gòu)里的基礎(chǔ)考點(diǎn)。它的定義有三句話左子樹(shù)所有節(jié)點(diǎn)的值都小于根節(jié)點(diǎn)的值右子樹(shù)所有節(jié)點(diǎn)的值都大于等于根節(jié)點(diǎn)的值左右子樹(shù)本身也分別是二叉排序樹(shù)。注意這里是“大于等于”有些教材會(huì)強(qiáng)調(diào)重復(fù)值放右子樹(shù)考試按這個(gè)約定走。查找的時(shí)候?qū)?shù)做中序遍歷得到的序列是遞增的反過(guò)來(lái)給你一棵二叉樹(shù)只要中序遍歷結(jié)果不是遞增序列它就不是二叉排序樹(shù)這是最穩(wěn)的判定法。還有一個(gè)反直覺(jué)的結(jié)論關(guān)鍵字最大的結(jié)點(diǎn)可以有左子樹(shù)但一定沒(méi)有右子樹(shù)。很多考生把“最大”理解成“一定是葉子”其實(shí)只要它沒(méi)有右孩子仍然可以帶著一棵左子樹(shù)。比如根是 50右子樹(shù)里有個(gè)結(jié)點(diǎn) 60它的左孩子是 55這時(shí) 60 是整棵樹(shù)最大的關(guān)鍵字但它不是葉子。答題時(shí)遇到“最大關(guān)鍵字結(jié)點(diǎn)的右指針一定為空”的說(shuō)法是對(duì)的遇到“一定沒(méi)有左子樹(shù)”就是錯(cuò)的。這類選擇題的套路很固定題目給出一組插入順序或者一棵樹(shù)的形態(tài)問(wèn)是否符合二叉排序樹(shù)定義答案無(wú)外乎兩種解法。一種是模擬插入看每個(gè)新值是不是按比較路徑走到正確位置另一種直接中序遍歷序列遞增就沒(méi)錯(cuò)。后一種速度最快遇到遞歸形態(tài)的樹(shù)先別急著畫(huà)全圖把中序序列寫(xiě)出來(lái)再判斷。3.2 哈夫曼樹(shù)WPL最短、每次取兩個(gè)最小權(quán)值合并哈夫曼樹(shù)也叫最優(yōu)二叉樹(shù)定義是帶權(quán)路徑長(zhǎng)度 WPL 最短的樹(shù)權(quán)值越大的葉子節(jié)點(diǎn)越靠近根節(jié)點(diǎn)。構(gòu)造步驟很簡(jiǎn)單從所有節(jié)點(diǎn)里取出權(quán)值最小的兩個(gè)合成一個(gè)新的父節(jié)點(diǎn)父節(jié)點(diǎn)權(quán)值等于兩者之和再放回候選集合反復(fù)執(zhí)行直到只剩一棵樹(shù)?？荚?yán)锬J(rèn)的做題模板是“左小右大、左 0 右 1”新節(jié)點(diǎn)畫(huà)成左小右大的順序給左分支記 0、右分支記 1每個(gè)字符的編碼就是從根出發(fā)到該葉子經(jīng)過(guò)的所有分支拼接。用代碼模擬一遍合并過(guò)程能幫你看懂為什么權(quán)值大的自然編碼短import heapq # 示例頻率僅演示構(gòu)造流程真題頻率以題目給的表格為準(zhǔn) freq [(a, 45), (b, 13), (c, 12), (d, 16), (e, 9), (f, 5)] heap [[w, [s, ]] for s, w in freq] heapq.heapify(heap) while len(heap) 1: left heapq.heappop(heap) # 每次取當(dāng)前兩個(gè)最小頻率 right heapq.heappop(heap) for node in left[1:]: node[1] 0 node[1] # 左分支前綴0 for node in right[1:]: node[1] 1 node[1] # 右分支前綴1 heapq.heappush(heap, [left[0] right[0]] left[1:] right[1:]) for s, code in sorted(heap[0][1:], keylambda x: (len(x[1]), x[0])): print(f{s}: {code})這段代碼的關(guān)鍵在 while 循環(huán)里每次彈出兩個(gè)最小值左邊的編碼統(tǒng)一在前面加 0右邊的統(tǒng)一加 1然后合成新節(jié)點(diǎn)放回堆里。頻率越小的節(jié)點(diǎn)越容易被早期合并編碼也就越長(zhǎng)反過(guò)來(lái)頻率大的節(jié)點(diǎn)越晚進(jìn)入合并編碼長(zhǎng)度就越短這正好對(duì)應(yīng)“權(quán)值大靠近根”的性質(zhì)。真題里給的頻率數(shù)據(jù)各不相同不能直接套用代碼里的數(shù)字但構(gòu)造流程永遠(yuǎn)是這樣反復(fù)取最小兩個(gè)合并。原文里那道經(jīng)典真題是一個(gè)文件中出現(xiàn) 6 個(gè)字符若采用定長(zhǎng)編碼碼長(zhǎng)應(yīng)為多少若采用 Huffman 編碼字符序列 face 的編碼是多少。第一問(wèn)答案選 B3 位因?yàn)?6 個(gè)字符用 2^24 不夠覆蓋2^38 剛好夠用所以碼長(zhǎng)最少是 3。第二問(wèn)需要先在草稿紙上畫(huà)出哈夫曼樹(shù)按左 0 右 1 賦值然后從根節(jié)點(diǎn)走到 f、a、c、e 四個(gè)字符把經(jīng)過(guò)的分支值依次連起來(lái)得到 110001001101所以答案選 A。這類題最怕的是樹(shù)畫(huà)對(duì)了但方向反了左 1 右 0 會(huì)導(dǎo)致所有編碼全部鏡像因此畫(huà)樹(shù)之前先在草稿紙邊緣寫(xiě)下“左 0 右 1”這點(diǎn)算算是一個(gè)血淚經(jīng)驗(yàn)。3.3 平衡二叉樹(shù)與滿二叉樹(shù)判定的邊界別搞混平衡二叉樹(shù)又稱 AVL 樹(shù)性質(zhì)是一棵空樹(shù)或者左右兩個(gè)子樹(shù)的高度差絕對(duì)值不超過(guò) 1并且左右兩個(gè)子樹(shù)也都是平衡二叉樹(shù)。判定時(shí)要遞歸檢查每個(gè)結(jié)點(diǎn)不是只看根結(jié)點(diǎn)左右高度相等就夠了。最常見(jiàn)的失分場(chǎng)景是給一棵左子樹(shù)高度 3、右子樹(shù)高度 1 的樹(shù)表面看“左邊比右邊高 2”已經(jīng)失衡但有人會(huì)先中序遍歷發(fā)現(xiàn)遞增就誤判成合法的二叉排序樹(shù)這里忘記檢查平衡因子。滿二叉樹(shù)在原文里描述為除最后一層無(wú)任何子節(jié)點(diǎn)外每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)或 0 個(gè)子節(jié)點(diǎn)。這個(gè)描述更直觀畫(huà)圖就能檢驗(yàn)逐層掃過(guò)去每個(gè)內(nèi)部結(jié)點(diǎn)要么有兩個(gè)孩子要么是葉子不存在只有一個(gè)孩子的中間結(jié)點(diǎn)。滿二叉樹(shù)和平衡二叉樹(shù)的判定是兩個(gè)動(dòng)作一個(gè)數(shù)孩子個(gè)數(shù)一個(gè)數(shù)高度差別同時(shí)只做一次就收工?？荚?yán)锶绻瑫r(shí)給出“是二叉排序樹(shù)、是平衡二叉樹(shù)、是滿二叉樹(shù)”三個(gè)選項(xiàng)要分別驗(yàn)證三條線中序遞增驗(yàn)證排序樹(shù)性質(zhì)高度差驗(yàn)證平衡性孩子數(shù)驗(yàn)證滿樹(shù)結(jié)構(gòu)三條都過(guò)才能選“三者都滿足”。4. 查找與排序二分查找、分塊查找與八大排序復(fù)雜度總表4.1 二分查找有序表才能用比較次數(shù)少但插入刪除難二分查找也叫折半查找適用情況是“不經(jīng)常變動(dòng)而查找頻繁”的有序列表。優(yōu)點(diǎn)是很明確的比較次數(shù)少、查找速度快、平均性能好缺點(diǎn)同樣致命要求待查表必須有序插入刪除困難。選擇題最愛(ài)把“有序”和“頻繁變動(dòng)”兩個(gè)條件拆出來(lái)做陷阱看到“無(wú)序列表直接用二分”基本可以秒排除。標(biāo)準(zhǔn)實(shí)現(xiàn)是三個(gè)分支不?？s區(qū)間def binary_search(a, target): low, high 0, len(a) - 1 while low high: mid (low high) // 2 if a[mid] target: # 中間位置記錄與查找關(guān)鍵字相等 return mid elif a[mid] target: # 中間位置記錄的關(guān)鍵字大于查找關(guān)鍵字 high mid - 1 # 去前一半子表繼續(xù)找 else: low mid 1 # 去后一半子表繼續(xù)找 return -1 # 子表不存在時(shí)說(shuō)明沒(méi)找到代碼里的核心是每次比較后都把區(qū)間縮小一半。mid 大于目標(biāo)就往左縮小于目標(biāo)就往右縮最終要么找到位置要么 low 超過(guò) high。如果題目問(wèn)的是“比較次數(shù)”記住每次砍半的特性n 個(gè)元素最多需要約 log2(n1) 次比較這是二分查找平均性能好的數(shù)學(xué)基礎(chǔ)。答題時(shí)若題目給的是鏈表而不是數(shù)組基本不能直接二分因?yàn)殒湵頍o(wú)法隨機(jī)定位到中間位置這也是?？嫉囊粋€(gè)隱含條件。4.2 分塊查找索引表定塊、塊內(nèi)順序查找適合動(dòng)態(tài)變化分塊查找介于順序查找和折半查找之間。它的做法是把一個(gè)大線性表分解成若干塊每塊里的節(jié)點(diǎn)可以任意存放但塊與塊之間必須排序。更準(zhǔn)確地說(shuō)按關(guān)鍵碼值非遞減排列時(shí)第 i 塊中的所有節(jié)點(diǎn)關(guān)鍵碼值必須小于第 i1 塊中的所有節(jié)點(diǎn)。同時(shí)還要建一個(gè)索引表把每塊的最大關(guān)鍵碼值作為索引項(xiàng)按塊順序存到一個(gè)輔助數(shù)組里這個(gè)輔助數(shù)組本身是有序的。查找分兩步先在索引表中查確定要找的節(jié)點(diǎn)屬于哪一塊因?yàn)樗饕碛行蚩梢杂庙樞虿檎乙部梢杂谜郯氩檎以僭趯?duì)應(yīng)的塊內(nèi)部用順序查找逐項(xiàng)比對(duì)。分塊查找的適用場(chǎng)景是節(jié)點(diǎn)動(dòng)態(tài)變化的情況速度比順序查找快得多但又不如折半查找。平均查找長(zhǎng)度的估算公式常按“索引表查找長(zhǎng)度 塊內(nèi)查找長(zhǎng)度”相加若 n 個(gè)節(jié)點(diǎn)分成大小相等的 b 塊每塊有 sn/b索引用順序查找則約為 (b1)/2 (s1)/2。遇到數(shù)值題就先把塊數(shù)和塊長(zhǎng)算出來(lái)再代入注意塊長(zhǎng)是不是能被整除。4.3 八大排序復(fù)雜度總表穩(wěn)定性、最壞情況與輔助空間排序部分的考點(diǎn)高度集中于一張總表。直接插入排序每趟把一個(gè)記錄插入到有序隊(duì)列的合適位置像斗地主抓牌理牌簡(jiǎn)單選擇排序每趟選出關(guān)鍵字最小的記錄放到已排序序列末尾冒泡排序兩兩比較并交換不滿足次序的對(duì)希爾排序按步長(zhǎng)分組組內(nèi)做直接插入步長(zhǎng)逐步減小到 1快速排序一趟把數(shù)據(jù)分成“左邊都比它小、右邊都比它大”兩部分再遞歸堆排序基于完全二叉樹(shù)的堆結(jié)構(gòu)歸并排序把相鄰有序序列成對(duì)合并基數(shù)排序不比較關(guān)鍵字大小而是按各位數(shù)值做分配與收集。排序方法最好時(shí)間復(fù)雜度平均時(shí)間復(fù)雜度最壞時(shí)間復(fù)雜度輔助空間穩(wěn)定性直接插入O(n)O(n^2)O(n^2)O(1)穩(wěn)定簡(jiǎn)單選擇O(n^2)O(n^2)O(n^2)O(1)不穩(wěn)定冒泡排序O(n)O(n^2)O(n^2)O(1)穩(wěn)定希爾排序不存在O(n^1.3)不存在O(1)不穩(wěn)定快速排序O(nlog2n)O(nlog2n)O(n^2)O(log2n)不穩(wěn)定堆排序O(nlog2n)O(nlog2n)O(nlog2n)O(1)不穩(wěn)定歸并排序O(nlog2n)O(nlog2n)O(nlog2n)O(n)穩(wěn)定基數(shù)排序O(d(nrd))O(d(nrd))O(d(nrd))O(rd)穩(wěn)定這張表不要死背整片先分陣營(yíng)O(n^2)家族是直接插入、簡(jiǎn)單選擇、冒泡外加快速排序的最壞情況O(nlog2n)家族是快速、堆、歸并希爾排序平均約 O(n^1.3)它沒(méi)有公認(rèn)的最好和最壞標(biāo)準(zhǔn)所以表里寫(xiě)“不存在”。穩(wěn)定性記一個(gè)口訣直接插入、冒泡、歸并、基數(shù)穩(wěn)定其余四個(gè)不穩(wěn)定?？焖倥判螂m然平均性能最好但它不穩(wěn)定這一點(diǎn)是每年都有人翻車的黑匣子出題人最喜歡拿“快速排序是穩(wěn)定的”這種假命題做迷惑項(xiàng)。4.4 真題演練堆排序候選序列判定與多路歸并路數(shù)堆排序的判定題給的是一個(gè)層序序列需要用堆的定義逐項(xiàng)檢驗(yàn)。堆要求序列滿足對(duì)每個(gè) i1,2,…,?n/2?有 ki ≤ k(2i) 且 ki ≤ k(2i1)這是小頂堆或者 ki ≥ k(2i) 且 ki ≥ k(2i1)這是大頂堆。原文給出四個(gè)序列正確答案選 B原因是把它按層序?qū)懗赏耆鏄?shù)后每個(gè)父結(jié)點(diǎn)都小于等于自己的左右孩子滿足小頂堆條件。用代碼驗(yàn)證最直觀def is_min_heap(arr): n len(arr) for i in range(1, n // 2 1): # 只需檢查到最后一個(gè)非葉結(jié)點(diǎn) left 2 * i # 左孩子下標(biāo) right 2 * i 1 # 右孩子下標(biāo) if left n and arr[i-1] arr[left-1]: return False # 父結(jié)點(diǎn)大于左孩子不是小頂堆 if right n and arr[i-1] arr[right-1]: return False # 父結(jié)點(diǎn)大于右孩子不是小頂堆 return True candidates [ (10, 50, 80, 30, 60, 20, 15, 18), (10, 18, 15, 20, 50, 80, 30, 60), (10, 15, 18, 50, 80, 30, 60, 20), (10, 30, 60, 20, 15, 18, 50, 80), ] for cand in candidates: print(is_min_heap(cand)) # 只有第二組輸出True代碼用 1 開(kāi)始編號(hào)的層序位置i 遍歷到 n//2 就夠因?yàn)樽詈笠粋€(gè)非葉結(jié)點(diǎn)之后全是葉子不需要檢查。每個(gè)父結(jié)點(diǎn)只要大于任何一個(gè)孩子就立刻返回 False。手算時(shí)也按同樣思路畫(huà)完全二叉樹(shù)自頂向下檢查所有父結(jié)點(diǎn)別只比相鄰元素大小堆不是簡(jiǎn)單的遞減遞增序列它要求的是整棵樹(shù)的父子關(guān)系。歸并路數(shù)這道題也?？既魧?duì) 27 個(gè)元素只進(jìn)行三趟多路歸并排序選取的歸并路數(shù)是幾。背公式“歸并趟數(shù) ?log_k m?”m 是元素個(gè)數(shù)k 是路數(shù)。這里反過(guò)來(lái)給趟數(shù)求路數(shù)log_k(27)3所以 k3答案選 B。這類題要注意公式方向題目給的是趟數(shù)讓你反推路數(shù)還是給路數(shù)讓你算趟數(shù)代入前先寫(xiě)清楚未知量是誰(shuí)。5. 高頻失分點(diǎn)碼制范圍、表達(dá)式出棧、廣義表、尋址方式與穩(wěn)定性5.1 失分點(diǎn)一四種碼制的定點(diǎn)數(shù)范圍記混錯(cuò)在哪問(wèn) n 位機(jī)器字長(zhǎng)補(bǔ)碼定點(diǎn)整數(shù)的表示范圍時(shí)填成和原碼一樣的 ±(2^(n-1)-1)漏掉那個(gè)最負(fù)的數(shù)。為什么錯(cuò)原碼、反碼、補(bǔ)碼、移碼的范圍不是四條都相同只有原碼和反碼的上下界一樣補(bǔ)碼和移碼的下界會(huì)多出一個(gè)最負(fù)值。怎么答對(duì)記住這個(gè)記憶技巧設(shè) A2^(n-1)B1-2^(-(n-1))四張表可以壓縮成一對(duì)規(guī)律碼制定點(diǎn)整數(shù)范圍定點(diǎn)小數(shù)范圍原碼[-(A-1), A-1][-B, B]反碼[-(A-1), A-1][-B, B]補(bǔ)碼[-A, A-1][-1, B]移碼[-A, A-1][-1, B]為什么補(bǔ)碼能多表示一個(gè)最小負(fù)數(shù)因?yàn)樵a和反碼里 0 都有兩種表示比如 1000 和 0000 都代表 0浪費(fèi)了一個(gè)位置補(bǔ)碼把負(fù)零的編碼騰出來(lái)表示最負(fù)的數(shù)。由此也帶出兩個(gè)必背結(jié)論計(jì)算機(jī)做數(shù)字加減運(yùn)算最適合用補(bǔ)碼浮點(diǎn)數(shù)的階碼最適合用移碼。選擇題不會(huì)讓你真算邊界一般就是考“誰(shuí)的表示范圍比原碼多一個(gè)數(shù)”以及“加減用補(bǔ)碼、階碼用移碼”。5.2 失分點(diǎn)二前綴表達(dá)式和后綴表達(dá)式的出棧順序搞反錯(cuò)在哪后綴表達(dá)式“3 4 ”里彈出棧頂 4 和次頂 3正確的運(yùn)算是 34有人按“先彈出放左邊”的錯(cuò)誤規(guī)則算成 43減法一出現(xiàn)就徹底算錯(cuò)。為什么錯(cuò)后綴表達(dá)式從左往右掃描前綴表達(dá)式從右往左掃描兩邊的彈出順序和運(yùn)算方向不一樣很多考生把兩者的規(guī)則混成一套。怎么答對(duì)用一句操作口令后綴是“次頂元素 op 棧頂元素”前綴是“棧頂元素 op 次頂元素”。拿原文例子驗(yàn)證后綴“3 4 5 × 6 -”從左掃到 時(shí)彈出 4 和 3算出 347再入棧遇到 × 彈出 5 和 7算 7×535最后遇到 - 彈出 6 和 35算 35-629。前綴“- × 3 4 5 6”從右掃先把 6、5、4、3 全部入棧遇到 彈出 3 和 4算 347遇到 × 彈出 7 和 5算 7×535遇到 - 彈出 6 和 35算 35-629。兩個(gè)表達(dá)式指向同一個(gè)結(jié)果掃的方向相反但規(guī)則對(duì)稱。用代碼實(shí)現(xiàn)后綴求值能把順序固定下來(lái)def eval_suffix(expr): stack [] for token in expr: if token.isdigit(): stack.append(int(token)) else: b stack.pop() # 先彈出的是右邊操作數(shù) a stack.pop() # 后彈出的是左邊操作數(shù) if token : stack.append(a b) elif token -: stack.append(a - b) elif token *: stack.append(a * b) elif token /: stack.append(a / b) return stack[0] print(eval_suffix([3, 4, , 5, *, 6, -])) # 輸出29代碼里的 b 和 a 的賦值順序就是得分關(guān)鍵b 先 pop 代表右側(cè)操作數(shù)a 后 pop 代表左側(cè)操作數(shù)。減法 3-4 和 4-3 結(jié)果是完全不同的考試時(shí)慢三步也要把彈出順序?qū)憣?duì)寧可多畫(huà)一個(gè)棧示意也不要憑感覺(jué)直接心算。5.3 失分點(diǎn)三廣義表的長(zhǎng)度和深度數(shù)錯(cuò)層數(shù)錯(cuò)在哪把“長(zhǎng)度”理解為全部原子元素的個(gè)數(shù)把“深度”理解為有多少個(gè)數(shù)字或字母。為什么錯(cuò)這兩個(gè)概念都跟括號(hào)層數(shù)綁定長(zhǎng)度是去掉最外層括號(hào)后剩下的元素個(gè)數(shù)深度是括號(hào)的最大嵌套層數(shù)。怎么答對(duì)剝括號(hào)的時(shí)候只剝一層數(shù)這一層里有多少個(gè)由逗號(hào)隔開(kāi)的元素元素本身可以是一個(gè)子表深度則從最外層往里一層層數(shù)看括號(hào)最多套了幾層。原文給過(guò)一組對(duì)照答案L1((a,(a,b),((a,b),c)))L2((1,2,3))L3(1,2,3)。它們的長(zhǎng)度和深度分別是L1 為 4 和 4L2 為 1 和 2L3 為 3 和 1。只看 L2 和 L3 最有感覺(jué)L2 剝掉最外層括號(hào)剩下的是一個(gè)整體 (1,2,3)所以長(zhǎng)度是 1但它從外到內(nèi)有兩層括號(hào)深度是 2L3 剝掉最外層括號(hào)剩下 1、2、3 三個(gè)元素長(zhǎng)度是 3深度是 1?？荚囉龅綇?fù)雜嵌套時(shí)先在草稿紙上把每一層括號(hào)標(biāo)序號(hào)再分別數(shù)逗號(hào)就不會(huì)把深度和長(zhǎng)度攪在一起。5.4 失分點(diǎn)四尋址方式里“操作數(shù)”和“操作數(shù)的地址”分不清錯(cuò)在哪把立即尋址和直接尋址混成一種或者把寄存器尋址和寄存器間接尋址反過(guò)來(lái)。為什么錯(cuò)考題描述只換幾個(gè)字比如“操作數(shù)包含在指令中”和“操作數(shù)的地址在指令中”很多考生掃一眼就憑印象選。怎么答對(duì)盯住一個(gè)判斷標(biāo)準(zhǔn)指令里裝的是數(shù)本身還是數(shù)的存放地址尋址方式指令里的內(nèi)容理解要點(diǎn)立即尋址操作數(shù)本身獲取操作數(shù)最快不用訪存直接尋址操作數(shù)的地址按地址再去內(nèi)存取數(shù)寄存器尋址操作數(shù)在寄存器中數(shù)在寄存器里直接讀寄存器間接尋址操作數(shù)的地址在寄存器中寄存器里放的是地址這套題經(jīng)常搭配 CPU 組成一起出。CPU 由運(yùn)算器、控制器、寄存器和內(nèi)部總線組成控制器不僅要保證程序正確執(zhí)行還要能處理異常事件。選擇題如果問(wèn)“獲取操作數(shù)最快的是哪種尋址”答案永遠(yuǎn)是立即尋址因?yàn)椴僮鲾?shù)直接躺在指令里連讀內(nèi)存都省了。而“操作數(shù)的地址在寄存器中”這種描述必須選寄存器間接尋址不要把“寄存器”和“數(shù)在寄存器中”畫(huà)等號(hào)。5.5 失分點(diǎn)五排序穩(wěn)定性憑感覺(jué)亂標(biāo)快速排序最常被冤枉錯(cuò)在哪看到快速排序平均時(shí)間復(fù)雜度最優(yōu)就順手標(biāo)成“穩(wěn)定”。為什么錯(cuò)穩(wěn)定性的定義跟復(fù)雜度完全無(wú)關(guān)它指的是關(guān)鍵字相同的兩個(gè)元素在排序前后相對(duì)順序是否保持不變快速排序的交換過(guò)程會(huì)打亂相同元素的相對(duì)位置所以不穩(wěn)定。怎么答對(duì)直接背四穩(wěn)定四不穩(wěn)定穩(wěn)定陣營(yíng)是直接插入、冒泡、歸并、基數(shù)不穩(wěn)定陣營(yíng)是簡(jiǎn)單選擇、希爾、快速、堆。再記一個(gè)關(guān)聯(lián)線索三個(gè) O(nlog2n) 的高效排序里只有歸并穩(wěn)定快速和堆都不穩(wěn)定說(shuō)明“高效”和“穩(wěn)定”沒(méi)有任何綁定關(guān)系。真題如果給“下列排序算法中不穩(wěn)定的是”這類選項(xiàng)用這個(gè)表逐項(xiàng)排除十秒內(nèi)能出答案。6. 考場(chǎng)答題順序與押題方向考前最后一小時(shí)怎么用6.1 上午題的時(shí)間分配先吃數(shù)據(jù)結(jié)構(gòu)再算碼制和表達(dá)式上午題時(shí)間看起來(lái)夠但計(jì)算題一多就容易崩。建議按“熟悉度優(yōu)先”的次序數(shù)據(jù)結(jié)構(gòu)里的鄰接矩陣度數(shù)、哈夫曼、堆判定、二分查找這類題目屬于看完題干就能落筆的先做碼制范圍、表達(dá)式求值需要列式或者畫(huà)棧放到第二梯隊(duì)。每道題控制在 60 到 90 秒超過(guò)兩分鐘果斷標(biāo)記跳過(guò)等整卷做完再回頭算。跳過(guò)不是放棄而是避免陷入單題死磕的情緒。6.2 考前最后一小時(shí)的三張默寫(xiě)清單最后沖刺不要再看新題把三張表默寫(xiě)一遍第一張是八種排序的復(fù)雜度和穩(wěn)定性總表重點(diǎn)默寫(xiě)哪些穩(wěn)定、哪些有 O(n^2) 最壞情況第二張是四種碼制的定點(diǎn)數(shù)范圍規(guī)律記住“補(bǔ)碼移碼下界多一個(gè)最負(fù)值”和“加減用補(bǔ)碼、階碼用移碼”第三張是四種尋址方式的一句話描述立即尋址最快、直接尋址給地址、寄存器尋址數(shù)在寄存器、寄存器間接尋址寄存器里放地址。默寫(xiě)完順手畫(huà)出哈夫曼“左 0 右 1”和表達(dá)式“后綴先彈右操作數(shù)”兩個(gè)小提醒考試時(shí)看到同類題直接套模板不用現(xiàn)場(chǎng)推導(dǎo)。6.3 押題方向這幾個(gè)高頻位置值得多花十分鐘從往年趨勢(shì)看鄰接矩陣求度、哈夫曼編碼計(jì)算、二分查找比較次數(shù)、堆的判定、廣義表長(zhǎng)度深度、前綴后綴表達(dá)式求值、補(bǔ)碼定點(diǎn)范圍、排序穩(wěn)定性這八類幾乎是必出組合。前四類是數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)盤(pán)后四類是拿來(lái)做壓軸計(jì)算題的常見(jiàn)素材。復(fù)習(xí)時(shí)每類準(zhǔn)備兩道真題練手重點(diǎn)不是做對(duì)而是把答題路徑固定下來(lái)先寫(xiě)判斷依據(jù)再列步驟最后核對(duì)答案。從那以后我每次考前都會(huì)把這三張表和兩個(gè)提醒強(qiáng)制默寫(xiě)一遍考場(chǎng)上看到鄰接矩陣先寫(xiě)“無(wú)觀看行、有向出行入列”看到表達(dá)式先寫(xiě)掃描方向基本沒(méi)再丟過(guò)這類送分題。希望這套梳理對(duì)你有用把高頻考點(diǎn)先攥穩(wěn)軟考中級(jí)的上午題就能拿到一個(gè)不拖后腿的分?jǐn)?shù)。本文還有配套的精品資源點(diǎn)擊獲取