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