數(shù)據(jù)結(jié)構(gòu)總復(fù)習(xí)+習(xí)題+解答.pdf

數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)資料 1 16 數(shù)據(jù)結(jié)構(gòu)總復(fù)習(xí)數(shù)據(jù)結(jié)構(gòu)總復(fù)習(xí) 習(xí)題習(xí)題解答解答 第一章第一章 緒論緒論 1 1 理解基本概念理解基本概念 1 數(shù)據(jù)是信息的載體 是描述客觀事物的數(shù) 字符以及能輸入到計算機(jī)中 被計算機(jī)識別 和處理的符號的集合 2 數(shù)據(jù)元素是數(shù)據(jù)的基本單位 可由若干數(shù)據(jù)項組成 3 數(shù)據(jù)對象是性質(zhì)相同的數(shù)據(jù)元素的集合 4 數(shù)據(jù)結(jié)構(gòu)指某一數(shù)據(jù)元素集合中所有數(shù)據(jù)成員之間的關(guān)系 定義為 數(shù)據(jù)結(jié)構(gòu) D R 5 數(shù)據(jù)結(jié)構(gòu)三要素 邏輯結(jié)構(gòu) 物理結(jié)構(gòu) 作用于數(shù)據(jù)結(jié)構(gòu)的運(yùn)算 6 邏輯結(jié)構(gòu) 數(shù)據(jù)元素間的邏輯關(guān)系 分為線性結(jié)構(gòu)和非線性結(jié)構(gòu) 集合 樹和圖結(jié)構(gòu) 7 物理結(jié)構(gòu) 數(shù)據(jù)元素及其關(guān)系在計算機(jī)上的映像 通常按順序存儲或鏈?zhǔn)酱鎯?8 抽象數(shù)據(jù)類型定義了一個數(shù)據(jù)對象 數(shù)據(jù)對象中各元素之間的關(guān)系以及一組處理數(shù)據(jù)的 操作 特征 數(shù)據(jù)抽象和信息隱藏 9 數(shù)據(jù)類型和數(shù)據(jù)結(jié)構(gòu)的異同 同 它們都具有抽象性 并不特指適用于何處 可根據(jù)問題需要用他們來表示數(shù)據(jù)元 素間的關(guān)系 異 數(shù)據(jù)結(jié)構(gòu)本身是一種數(shù)據(jù)的組織和使用形式 通過把數(shù)據(jù)定義成數(shù)據(jù)類型才能在 計算機(jī)上使用 1 2 算法特性與性能分析算法特性與性能分析 1 算法的定義 解決特定問題的一系列操作 2 算法的 5 大特性 要素 輸入 輸出 確定性 可行性和有限性 3 算法時間復(fù)雜度分析 尋找關(guān)鍵操作 基本操作 通常為循環(huán)的最內(nèi)層程序段 計算關(guān) 鍵操作的執(zhí)行次數(shù) 一般結(jié)果為問題規(guī)模 n 的多項式 時間復(fù)雜度為該多項式的最高次冪 T n O 1 的含義 常量時間復(fù)雜度 表示算法執(zhí)行時間與問題規(guī)模無關(guān) 4 算法空間復(fù)雜度分析 算法執(zhí)行時所需要的輔助空間 S n O 1 的含義 常量空間復(fù)雜度 表示算法執(zhí)行時需要的輔助空間與問題規(guī)模無關(guān) 也 稱為算法原地工作 題 1 1 如何理解抽象數(shù)據(jù)類型 答 定義了一個數(shù)據(jù)對象 數(shù)據(jù)對象中各元素之間的關(guān)系以及一組處理數(shù)據(jù)的操作 題 1 2 數(shù)據(jù)元素間的邏輯結(jié)構(gòu)關(guān)系有哪些 答 四種 分別是集合結(jié)構(gòu) 線性結(jié)構(gòu) 樹狀結(jié)構(gòu) 圖狀結(jié)構(gòu) 題 1 3 通常從時間復(fù)雜度和空間復(fù)雜度來評價算法的優(yōu)劣 題 1 4 下面算法的時間復(fù)雜度為 C int i j for i 0 i m i for j 0 j n j a i j i j 數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)資料 2 16 A O m2 B O n2 C O m n D O m n 題 1 5 分析以下程序段的時間復(fù)雜度為 O log2n k 1 while k 0 個數(shù)據(jù)元素的有限序列 其特點為 存在唯一首元素 尾元素 除首元素 和尾元素外 其余每個元素只有一個前驅(qū)和后繼 2 2 線性表的存儲表示線性表的存儲表示 1 線性表的順序存儲 2 線性表的鏈?zhǔn)酱鎯?3 其他形式的鏈表 循環(huán)單鏈表 帶尾指針的循環(huán)鏈表 雙向鏈表 雙向循環(huán)鏈表 靜態(tài)鏈表 4 根據(jù)實際問題 靈活選擇存儲方式 5 各種鏈表判空條件 6 順序存儲與鏈?zhǔn)酱鎯Φ膬?yōu)缺點 順序表是靜態(tài)分配 無需為了表示元素間的關(guān)系而增加額外的輔助空間 存儲密度大 可 按元素序號隨機(jī)訪問 但進(jìn)行插入 刪除時 需要移動大量元素 鏈表是動態(tài)分配 需要增加指針域來表示元素間的邏輯關(guān)系 存儲密度小 不能進(jìn)行隨機(jī) 訪問 插入 刪除時不需要移動元素 只需要修改相關(guān)指針域即可 2 3 線性表的基本運(yùn)算線性表的基本運(yùn)算 1 在順序表中執(zhí)行插入 刪除運(yùn)算要點 插入時 應(yīng)先判斷表是否已滿以及插入位置的合法性 在第 i 個位置插入時 需要把從第 i 個位置到最后一個的元素 n i 1 向后移動 刪除時 應(yīng)先判斷表是否空以及刪除位置的合法性 刪除第 i 個位置元素時 需要把從 i 1 到最后一個的元素 n i 向前移動 2 在單鏈表中執(zhí)行插入 刪除運(yùn)算要點 插入 刪除時 需要找到被插入或刪除結(jié)點的前驅(qū)結(jié)點 指針更改順序很重要 防止后繼結(jié)點丟失 刪除的結(jié)點要記著釋放空間 2 4 綜合應(yīng)用綜合應(yīng)用 根據(jù)給定需求 在順序存儲或鏈?zhǔn)酱鎯ι蠈崿F(xiàn)相應(yīng)操作 重點是鏈表 題 2 1 一維數(shù)組和順序表的異同 同 一維數(shù)組與順序表都可按元素下標(biāo)直接 或隨機(jī) 存取元素 異 數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)資料 3 16 一維數(shù)組中各元素間可以有空元素 而順序表中的元素必須按順序存放 一維數(shù)組的基本操作只有按下標(biāo)存取 而順序表可以有線性表的所有操作 如插入 刪除等 一維數(shù)組的大小一經(jīng)分配便不可變 而順序表的長度是可變的 題 2 2 線性表的特點是 除第一個元素外其他每個元素有且只有一個直接前驅(qū) 除最后一個 元素外其他每個元素都有且只有一個直接后繼 那么 循環(huán)鏈表的每一個結(jié)點都有直接后繼 雙向鏈表的每一個結(jié)點都有直接前驅(qū)和直接后繼 它們還是線性表嗎 解 循環(huán)鏈表和雙向鏈表示存儲結(jié)構(gòu) 線性表是邏輯結(jié)構(gòu) 線性與非線性是從邏輯上劃分的 因此 循環(huán)鏈表和雙向鏈表是線性表 它們是線性表的不同存儲形式 題 2 2 在一個單鏈表 L 中 P 為中間某結(jié)點 在 P 前插入 S 結(jié)點 可否在 O 1 時間復(fù)雜度 內(nèi)完成 解 int FrontIn Node q Type e Node p p Node malloc sizeof Node p data q data q data e q next p return 0 題 2 3 長度為 n 的非空線性表采用順序存儲結(jié)構(gòu) 在表的第 i 個位置刪除一個數(shù)據(jù)元素 i 的合法值應(yīng)該是 D A i 0 B 1 i n 1 C 1 i n 1 D 1 i n 題 2 4 若線性表最常用的操作是存取第 i 個元素及其前趨的值 則采用 D 存儲方式節(jié) 省時間 A 單鏈表 B 雙鏈表 C 單循環(huán)鏈表 D 順序表 題 2 5 某線性表最常用的操作是在最后一個結(jié)點之后插入一個結(jié)點或刪除第一個結(jié)點 故采 用 D 存儲方式最節(jié)省運(yùn)算時間 A 單鏈表 B 僅有頭結(jié)點的單循環(huán)鏈表 C 雙鏈表 D 僅有尾指針的單循環(huán)鏈表 題 2 6 鏈表不具有的特點是 B A 插入 刪除不需要的移動元素 B 可隨機(jī)訪問任一元素 C 不必事先估計存儲空間 D 所需空間與線性長度成正比 數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)資料 4 16 題 2 7 設(shè) rear 是指向非空的帶頭結(jié)點的單循環(huán)鏈表的尾指針 若想刪除鏈表第一個結(jié)點 則執(zhí)行 D A s rear rear rear next free s B rear rear next free rear C rear rear next next free rear D s rear next next rear next next s next free s 題 2 8 在一個長度為 n 的順序表中第 i 個元素 1 inext NULL If p next data 2 1 q p next p next q next q next L next L next q q p p p next If p data 2 1 q next p next p next L next L next p 題 2 10 編寫算法 PolyNode Derivative PolyNode PL 其功能是 求某一元多項式的導(dǎo)數(shù) 參數(shù)為一元多項式單鏈表 返回值為該一元多項式導(dǎo)數(shù)的一元多項式鏈表頭指針 帶頭結(jié) 點 PolyNode Derivative PolyNode PL PolyNode p q p PL while p next sqr 0 p next sqr If p next NULL q p next p next NULL free q return PL 第三章第三章 棧和隊列棧和隊列 棧和隊列是兩種特殊的線性表 它們的邏輯結(jié)構(gòu)和線性表相同 只是其操作的位置受限制 3 1 棧的定義 存儲與基本運(yùn)算棧的定義 存儲與基本運(yùn)算 1 只允許在表的末端 棧頂 進(jìn)行插入和刪除的線性表 具有 LIFO 特性 2 一串元素依次進(jìn)棧 其出棧順序與進(jìn)棧和出棧操作的排列組合有關(guān) Catalan 數(shù) 3 棧的存儲結(jié)構(gòu) 順序存儲和鏈?zhǔn)酱鎯?4 兩棧共享空間 初始化 top 0 1 top 1 M 棧滿 top 0 1 top 1 ?？?1 號?？?top 0 1 2 號?？?top 1 M 進(jìn)棧 根據(jù)進(jìn)哪個棧 具體操作不同 出棧 根據(jù)進(jìn)哪個棧 具體操作不同 題 3 1 設(shè)輸入序列為 1 2 3 4 則借助棧所得到的輸出序列不可能是 B A 1 2 3 4 B 4 1 2 3 C 1 3 4 2 D 4 3 2 1 題 3 2 鏈?zhǔn)綏Ｖ荒茼樞虼嫒?而順序棧不但能順序存取 還能直接存取 這種說法對嗎 解 不對 直接存取破壞順序棧結(jié)構(gòu) 所以順序棧不能直接存取 題 3 3 向一個棧頂指針為 top 的鏈棧中插入一個 S 所指結(jié)點時 則執(zhí)行 C A top next S B S next top next top next S C S next top top S D S next top top next 數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)資料 6 16 3 2 棧與遞歸棧與遞歸 1 什么是遞歸 自己定義或調(diào)用自己 2 遞歸的優(yōu)點 結(jié)構(gòu)清晰 正確性容易證明 3 遞歸適合條件 原問題可以層層分解為類似子問題 子問題規(guī)模更小 最小子問題有解 4 遞歸的缺點 為什么要消除遞歸 時空效率低 無法得到遞歸過程的某中間狀態(tài) 5 遞歸進(jìn)層 保留本層參數(shù)與返回地址 保存斷點 進(jìn)棧 為被調(diào)函數(shù)的局部變量分配存儲空間 給下層參數(shù)賦值 轉(zhuǎn)移到被調(diào)函數(shù)入口 6 遞歸退層 保存被調(diào)函數(shù)計算機(jī)結(jié)果 釋放被調(diào)函數(shù)的數(shù)據(jù)區(qū) 恢復(fù)上層參數(shù) 出棧 轉(zhuǎn)入到保存的返回地址繼續(xù)執(zhí)行 3 3 隊列的定義 存儲與基本運(yùn)算隊列的定義 存儲與基本運(yùn)算 1 允許在表的一端 隊尾 進(jìn)行插入 另一端 隊頭 進(jìn)行刪除的線性表 具有 FIFO 特性 2 一串元素依次進(jìn)隊 其出隊序列只有一種 3 隊列的存儲結(jié)構(gòu) 順序存儲和鏈?zhǔn)酱鎯?4 循環(huán)隊列 假設(shè)犧牲一個空間來區(qū)分隊空和隊滿 front 指向隊頭元素 rear 指向隊尾的 后一個單元 隊滿 rear 1 maxSize front 隊空 front rear 元素個數(shù)計算 rear front maxSize maxSize 提示 當(dāng) front 指向隊頭元素的前一個單元 rear 指向隊尾元素 操作會稍有變動 以上兩種方式都不影響對隊列中元素個數(shù)的計算 注 也可用增加一個標(biāo)志的方法來區(qū)分隊空和隊滿 題 3 4 棧和隊列的共同點是 C A 都是先進(jìn)后出 B 都是先進(jìn)先出 C 只允許在端點處插入和刪除元素 D 沒有共同點 題 3 5 線性表 棧和隊列都是線性結(jié)構(gòu) 可以在線性表的端點位置插入和刪除元素 對于 棧只能在棧頂位置插入和刪除元素 對于隊列只能在隊列頭位置插入元素和在隊列尾位 置刪除元素 類似題目 棧 隊列和線性表有什么異同 題 3 6 排隊是日常生活中常見的一種現(xiàn)象 比如 在商店排隊付款 當(dāng)?shù)匾晃活櫩屯瓿筛?款離開后 其他顧客依次前移 下面用數(shù)據(jù)結(jié)構(gòu)中的隊列來模擬這種排隊現(xiàn)象 define QUEUE 40 struct Queue int queue QUEUE int Rear Rear 記錄隊列尾 數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)資料 7 16 void Out struct Queue Q int t i 0 if Q Rear 0 t Q queue 0 while i Q Rear Q queue i Q queue i 1 i Q Rear 3 4 綜合應(yīng)用綜合應(yīng)用 棧 括號匹配 四則運(yùn)算 進(jìn)制轉(zhuǎn)換等 隊列 鍵盤輸入緩沖等 根據(jù)實際問題 選擇?；蜿犃型瓿伤惴ㄔO(shè)計 第四章第四章 串串 4 1 串的定義和基本術(shù)語串的定義和基本術(shù)語 1 串的定義 串是特殊的線性表 其特殊性在于組成串的元素為字符 2 空串 長度為 0 的字符串 3 空格串 由空格組成的字符串 4 經(jīng)典的串模式匹配算法時間復(fù)雜度為 O mn KMP 算法的時間復(fù)雜度為 O m n 題 4 1 在下列關(guān)于 串 的陳述中 不正確的說明是 B A 串可以用順序存儲 B 串是由字母和數(shù)字構(gòu)成 C 串可以用鏈?zhǔn)酱鎯?分塊存儲 D 在 C 語言中 串的最后隱含一個字符 0 第五章第五章 數(shù)組和廣義表數(shù)組和廣義表 5 1 數(shù)組數(shù)組 1 數(shù)組可以看成是一般線性表的擴(kuò)充 一維數(shù)組即為線性表 而二維數(shù)組可以定義為 其 數(shù)據(jù)元素為一維數(shù)組 線性表 的線性表 多維數(shù)組依次類推 2 數(shù)組的基本操作 獲取指定位置元素和修改指定位置元素 3 數(shù)組存儲方式 順序存儲 可按行或按列存儲 4 一維數(shù)組 二維數(shù)組和三維數(shù)組中某元素地址的計算 一維數(shù)組 A 1 n 每個元素占 k 個字節(jié) Loc A i Loc A 1 i 1 k 數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)資料 8 16 二維數(shù)組 A 1 m 1 n 每個元素占 k 個字節(jié) 按行存儲時 Loc A i j Loc A 1 1 i 1 n j 1 k 按列存儲時 Loc A i j Loc A 1 1 j 1 m i 1 k 三維數(shù)組 A 1 m 1 n 1 r 每個元素占 k 個字節(jié) 按行存儲時 Loc A i j t Loc A 1 1 1 i 1 n r j 1 r t 1 k 按列存儲時 Loc A i j k Loc A 1 1 1 j 1 n r i 1 r t 1 k 5 特殊矩陣壓縮存儲 特殊矩陣 元素分布有規(guī)律或非零元素很多的矩陣 如上三角矩陣 下三角矩陣 對稱矩 陣 帶狀矩陣 稀疏矩陣 壓縮原則 值相同的元素且分布有規(guī)律的元素只分配一個空間 領(lǐng)元素不分配空間 上三角矩陣 下三角矩陣 對稱矩陣 帶狀矩陣一般壓縮在一維數(shù)組中 稀疏矩陣一般用 三元組或十字鏈表壓縮存儲 掌握壓縮后的存儲地址或下標(biāo)計算關(guān)系 注意下標(biāo)從 0 還是 1 開始 題 5 1 什么是特殊矩陣 其壓縮原則是什么 答 元素分布有規(guī)律或非零元素很多的矩陣 題 5 2 三維數(shù)組 a 4 5 6 下標(biāo)從 0 開始 a 有 4 5 6 個元素 每個元素的長度是 2 則 a 2 3 4 的地址是 1270 設(shè) a 0 0 0 的地址是 1000 數(shù)據(jù)以行為主序方式存儲 題 5 3 設(shè)矩陣 A 是一個對稱矩陣 為了節(jié)省存儲 將其下三角部分按行序存放在一維數(shù)組 B 1 n n 1 2 中 對任一下三角部分中任一元素Aij 在一組數(shù)組B的下標(biāo)位置K的值是 B A i i 1 2 j 1 B i i 1 2 j C i i 1 2 j 1 D i i 1 2 j 題 5 4 稀疏矩陣一般的壓縮存儲方法有兩種 即 D A 二維數(shù)組和三維數(shù)組 B 三元組合散列 C 三元組和十字鏈表 D 散列和十字鏈表 5 2 廣義表廣義表 1 定義 廣義表是特殊的線性表 其特殊性在于廣義表中的 di 既可以是單個元素 還可以是 一個廣義表 2 表頭 廣義表中的第一個元素 表尾 除了第一個元素外 其余元素構(gòu)成的廣義表 3 廣義表的存儲結(jié)構(gòu) 頭尾鏈 同層結(jié)點鏈 題 5 4 已知廣義表 LS a b c d e f 運(yùn)用 head 和 tail 函數(shù)取出 LS 中原子 e 的運(yùn)算是 A A head tail head tail LS B tail head LS C head tail LS D head tail tail head LS 題 5 5 廣義表 a b c d 的表尾是 C 數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)資料 9 16 A a B C a b c d D a b c d 第六章第六章 樹和二叉樹樹和二叉樹 6 1 二叉樹二叉樹 1 二叉樹的 5 個基本性質(zhì) 性質(zhì) 1 在二叉樹的第 i 層上至多有 2i 1 個結(jié)點 i 1 性質(zhì) 2 深度為 k 的二叉樹至多有 2k 1 個結(jié)點 k 1 性質(zhì) 3 對任意一棵二叉樹 T 若終端結(jié)點數(shù)為 n0 而其度數(shù)為 2 的結(jié)點數(shù)為 n2 則 n0 n2 1 需要掌握其證明過程 性質(zhì) 4 具有 n 個結(jié)點的完全二叉樹的深度為 log2n 1 性質(zhì) 5 對于具有 n 個結(jié)點的完全二叉樹 如果按照從上到下和從左到右的順序?qū)Χ鏄渲?的所有結(jié)點從 1 開始順序編號 則對于任意的序號為 i 的結(jié)點有 1 如 i 1 則序號為 i 的結(jié)點是根結(jié)點 無雙親結(jié)點 如 i 1 則序號為 i 的結(jié)點的雙親結(jié) 點序號為 2 如 2 i n 則序號為 i 的結(jié)點無左孩子 如 2 i n 則序號為 i 的結(jié)點的左孩子結(jié)點 的序號為 2 i 3 如 2 i 1 n 則序號為 i 的結(jié)點無右孩子 如 2 i 1 n 則序號為 i 的結(jié)點的右孩 子結(jié)點的序號為 2 i 1 2 二叉樹的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu) 順序存儲 將二叉樹補(bǔ)為完全二叉樹 從上到下 從左到右依次存儲每個結(jié)點 利用性質(zhì) 5 來計算結(jié)點之間的關(guān)系 鏈?zhǔn)酱鎯?用二叉鏈表來表示 n 個結(jié)點的二叉樹 共有 n 1 個空鏈域 n 1 個分分支 3 二叉樹的遍歷與應(yīng)用 給定二叉樹 寫出先序 中序和后序序列 給定二叉樹的先序和中序 或者后序和中序 確定二叉樹 二叉樹遍歷的應(yīng)用 二叉樹的層次遍歷 4 二叉樹遍歷算法的非遞歸算法 5 線索二叉樹 目的 如何判斷某結(jié)點沒有左 右孩子 如何查找某結(jié)點的前驅(qū)或后繼 手工線索化 題 6 1 如圖所示的二叉樹 回答以下問題 1 其中序遍歷序列為 GDBAEHIFC 2 其前序遍歷序列為 ABDGCEFHI 3 其后序遍歷序列為 GDBEIHFCA 題 6 2 深度為 k 的二叉樹上只有度為 0 和度為 2 的結(jié)點 則這類二叉樹上所含結(jié)點總數(shù)最 少有 個 數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)資料 10 16 題 6 3 對任意一棵樹 設(shè)它有 n 個結(jié)點 這 n 個結(jié)點的度之和為 n 1 題 6 4 一棵左 右子樹均不空的二叉樹在先序線索化后 其中空的鏈域的個數(shù)是 1 個 題6 5 已知二叉樹的前序遍歷序列是abdgcefh 中序遍歷序列是dgbaechf 則其后遍歷序列為 D A bdgcefha B gdbecfha C bdgaechf D gdbehfca 題 6 6 在一棵非空二叉樹中 葉了節(jié)點的總數(shù)比度為 2 的節(jié)點總數(shù)多 C 個 A 1 B 0 C 1 D 2 題 6 7 設(shè)樹 T 的度為 4 其中度為 1 2 3 和 4 的結(jié)點個數(shù)分別為 4 2 1 1 則 T 中的葉子數(shù)為 D A 5 B 6 C 7 D 8 題 6 8 將算數(shù)表達(dá)式 a b c d e f g h 轉(zhuǎn)化為二叉樹 題 6 9 表達(dá)式 A B C D E F G H I J 的后綴表達(dá)式是 ABC D E FG H IJ 中綴表達(dá)式相當(dāng)于對二叉樹表達(dá)式進(jìn)行中序遍歷 后綴表達(dá)式相當(dāng)于對二叉樹表達(dá)式進(jìn)行后序遍歷 題 6 10 已知一棵二叉樹的前序遍歷的結(jié)果是 ABDGCEFHI 中序遍 歷的結(jié)果是 DGBAECHIF 畫出這棵二叉樹 以及對二叉樹進(jìn)行 后序線索化后的后繼線索 用帶箭頭的線表示 6 11 算法設(shè)計 統(tǒng)計二叉樹中所有度為 1 的結(jié)點的個數(shù) 給二叉樹中的每個結(jié)點設(shè)置其層次 在中線線索二叉樹中查找某結(jié)點 P 的前驅(qū)結(jié)點 6 2 樹樹 數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)資料 11 16 1 樹的三種存儲形式 雙親表示法 孩子鏈表示法 孩子兄弟表示法 2 樹和二叉樹之間的轉(zhuǎn)換 樹的先根遍歷 二叉樹的先序遍歷 樹的后根遍歷 二叉樹的中序遍歷 3 樹和森林之間的轉(zhuǎn)換 森林的先序 中序和后序遍歷與二叉樹的先序 中序和后序遍歷一一對應(yīng) 6 3 Huffman 樹樹 1 Huffman 樹的構(gòu)造過程 2 前綴碼概念 3 計算帶權(quán)路徑長度 題 6 8 下面幾個符號串編碼集合中 不是前綴編碼的是 B A 0 10 110 1111 B 11 10 001 101 0001 C 00 010 0110 1000 D b c aa ac abs abb abc 題 6 9 假設(shè)字符 a b c d e 的頻度分別為 34 14 25 12 15 計算 Huffman 編碼 請寫 出各個符號的 huffman 編碼及編碼樹 要求 Huffman 樹的右子樹不大于左子樹 且左子樹標(biāo) 為 0 a 00 b 010 c 10 d 011 e 11 第七章第七章 圖圖 7 1 圖的基本術(shù)語與存儲結(jié)構(gòu)圖的基本術(shù)語與存儲結(jié)構(gòu) 1 基本術(shù)語 有向圖 無向圖 稠密圖 稀疏圖 連通圖 連通分量 強(qiáng)連通圖 強(qiáng)連通分量 簡單路徑 出度 入度 度 生成樹 網(wǎng) 2 圖的鄰接矩陣存儲方式與基本操作 1 采用兩個數(shù)組來表示圖 一個是用于存儲頂點信息的一維數(shù)組 另一個是用于存儲圖中頂 點之間關(guān)聯(lián)關(guān)系的二維數(shù)組 鄰接矩陣 2 無向圖的鄰接矩陣是對稱的 有向圖的鄰接矩陣不一定對稱 圖的鄰接矩陣存儲結(jié)構(gòu)所需 空間與頂點 n 有關(guān)系 其空間復(fù)雜度為 O n2 與邊 e 無關(guān) 因此適合存稠密圖 3 基本操作 有向圖中求頂點 i 出度 第 i 行中非 0 且非無窮的元素個數(shù) 有向圖中求頂點 i 入度 第 i 列中非 0 且非無窮的元素個數(shù) 無向圖中求頂點 i 的度 第 i 行 列 中非 0 且非無窮的元素個數(shù) 3 圖的鄰接表存儲方式與基本操作 數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)資料 12 16 1 基本思想 只存有關(guān)聯(lián)的信息 表頭結(jié)點表和邊表 如圖 一個圖的鄰接矩陣表示法是唯一的 而圖的鄰接表表示法是不唯一的 2 有向圖的邊只存一次 無向圖的邊存 2 次 圖的鄰接表存儲結(jié)構(gòu)所需空間與頂點 n 和邊 2 都有關(guān)系 其空間復(fù)雜度為 O n e 因此適合存稀疏圖 3 基本操作 有向圖中求頂點 i 出度 第 i 個結(jié)點的邊表結(jié)點個數(shù) 有向圖中求頂點 i 入度 遍歷所有結(jié)點的邊表結(jié)點 統(tǒng)計鄰接點為 i 的結(jié)點個數(shù) 無向圖中求頂點 i 的度 第 i 個結(jié)點的邊表結(jié)點個數(shù) 由于求入度效率低 可以建立逆鄰接表 題 7 1 有 n 個結(jié)點的有向圖的邊數(shù)最多有 B A n B n n 1 C n n 1 2 D 2n 題 7 2 在一個有向圖中 所有頂點的入度之和等于所有頂點的出度之和的 1 倍 題 7 3 假定一個圖具有 n 個頂點和 e 條邊 則采用鄰接矩陣表示時 其相應(yīng)的空間復(fù)雜度為 n e 7 2 圖的遍歷及其應(yīng)用圖的遍歷及其應(yīng)用 知識點 1 圖的深度優(yōu)先遍歷 類似于二叉樹的先根遍歷 通常用遞歸或棧來實現(xiàn) 2 圖的廣度優(yōu)先遍歷 類似于二叉樹的層次遍歷 通常用隊列來實現(xiàn) 根據(jù)圖的鄰接矩陣或鄰接表存儲結(jié)構(gòu) 給出圖的邏輯結(jié)果 根據(jù)圖中頂點間的關(guān)系 給出圖的鄰接矩陣或鄰接表存儲結(jié)構(gòu) 從某點出發(fā)的圖的深度或廣度優(yōu)先遍歷序列 廣度或深度優(yōu)先生成樹 在鄰接矩陣和鄰接表上的圖的深度和廣度優(yōu)先遍歷算法 3 圖的應(yīng)用 1 最小生成樹 Prim 算法和 Kruskal 算法 2 拓?fù)渑判?3 關(guān)鍵路徑 4 最短路徑 數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)資料 13 16 題 7 4 關(guān)鍵路徑是 AOE 網(wǎng)中從源點到匯點的 最長 路徑 題 7 5 判定一個有向圖上是否存在回路 處理可以利用拓?fù)渑判蚍椒ㄍ?還可以用 D A 求關(guān)鍵路徑的方法 B 求最短路徑的 Dijkstra 方法 C 廣度優(yōu)先遍歷算法 D 深度優(yōu)先遍歷算法 題 7 6 已知二維數(shù)組表示的圖的鄰接矩陣如下圖所示 試分別畫出自頂點 1 出發(fā)進(jìn)行遍歷所得的 深度優(yōu)先生成樹和廣度優(yōu)先生成樹 1 7 10 6 2 3 4 5 9 8 1 7 9 3 10 5 4 8 6 2 題 7 7 用克魯斯卡爾算法將下列的圖構(gòu)造成最小生成樹 畫出生成過程 2 0 5 4 1 3 第八章第八章 查找查找 8 1 基于線性表的查找基于線性表的查找 1 查找成功的平均查找長度 ASL 2 順序查找 既適合順序表 也適合鏈表 查找成功的平均查找長度為 n 1 2 3 折半查找 要求元素有序且順序存儲 用折半判定樹來分析其查找性能 其平均查找長度為 log2n 4 分塊查找 數(shù)據(jù)分塊后 塊內(nèi)有序 塊間無序 每塊的最大或最小元素組成索引表 索引表由于 有序 可按折半查找 塊內(nèi)因為無序 只能順序查找 其查找性能由兩部分組成 數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)資料 14 16 題 8 1 鏈表適用于 A 查找 A 順序 B 二分法 C 順序 也能二分法 D 隨機(jī) 題 8 2 有一個長度為 12 的有序表 按二分查找法對該表進(jìn)行查找 在表內(nèi)各元素等概率情況下查找 成功所需的平均比較次數(shù)為 B A 35 12 B 37 12 C 39 12 D 43 12 題 8 3 己知有序表為 13 19 24 35 47 50 62 83 95 115 138 當(dāng)用二分法查找 19 時 需 2 次查找 成功 中間位置計算時下取整 題 8 4 折半查找的前提條件是什么 答 順序存儲 數(shù)組有序 題 8 5 分塊查找的基本思想 答 塊間有序 塊內(nèi)無序 8 2 基于樹的查找基于樹的查找 1 二叉排序樹的定義 二叉樹排序樹或者是一棵空樹 或者是具有如下性質(zhì)的二叉樹 1 若它的左子樹非空 則左子樹上所有結(jié)點的值均小于根結(jié)點的值 2 若它的右子樹非空 則右子樹上所有結(jié)點的值均大于 或大于等于 根結(jié)點的值 3 它的左右子樹也分別為二叉排序樹 2 給定一個序列 能構(gòu)建一棵二叉排序樹 并分析其查找性能 3 二叉排序樹按照中序遍歷 會得到一個非遞減的序列 4 二叉排序樹的平均查找性能與折半類似 但其插入和刪除元素時不需要移動元 素 但在最壞情況下 初始序列有序時 會蛻化為順序查找 n 1 2 5 平衡二叉排序樹的定義 每個結(jié)點的左右子樹高度之差的絕對值小于或等于 1 平衡因子 左右子樹高度之差 失衡類型 LL LR RR RL 6 m 路查找樹 7 B 樹 題 8 6 設(shè)有一組記錄的關(guān)鍵字為 19 14 23 1 68 20 84 27 55 11 10 79 構(gòu)造二叉排序樹 并計算等概率 情況下 查找成功的平均查找長度 解 41 12 題 8 7 平衡因子的取值范圍是 1 0 1 8 3 哈希查找哈希查找 1 基本思想 在元素的關(guān)鍵字 k 和元素的存儲位置 p 之間建立一個對應(yīng)關(guān)系 H 使得 p H k H 稱 為哈希函數(shù) 創(chuàng)建哈希表時 把關(guān)鍵字為 k 的元素直接存入地址為 H k 的單元 以后當(dāng)查找關(guān)鍵 字為 k 的元素時 再利用哈希函數(shù)計算出該元素的存儲位置 p H k 從而達(dá)到按關(guān)鍵字直接存取 元素的目的 2 哈希函數(shù) 除留余數(shù)法考的多 數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)資料 15 16 3 處理沖突的方法 線性探測再散列 二次探測再散列 再哈希法和鏈地址法 4 裝填因子 5 查找成功和不成功的平均查找長度 6 影響哈希查找效率的因素 哈希函數(shù) 處理沖突的方法 裝填因子 題 8 6 在各種查找方法中 平均查找長度與結(jié)點個數(shù) n 無關(guān)的查找方法是哈希查找法 題 8 7 設(shè)有一組記錄的關(guān)鍵字為 19 14 23 1 68 20 84 27 55 11 10 79 散列函數(shù)為 H key key MOD 13 采用線性探測在散列解決沖突 構(gòu)造哈希表 并計算查找成功與不成功的平均查找長度 ASLs 7 3 ASLu 91 13 第九章第九章 排序排序 9 1 排序基本概念排序基本概念 1 內(nèi)部排序與外部排序 內(nèi)部排序是整個排序過程完全在內(nèi)存中進(jìn)行 當(dāng)待排序記錄數(shù)據(jù)量太大時 內(nèi)存無法容納全部數(shù)據(jù) 排序需要借助外部存儲設(shè)備才能完成 稱為外部排序 2 排序的穩(wěn)定性 是否穩(wěn)定的判斷方法 排序過程中 需要交換或移動數(shù)據(jù) 若交換或移動元素時 中間可能會隔若干 個元素時 空運(yùn)移動 這種排序方法必定不穩(wěn)定 如希爾 簡單選擇 快速和堆 9 2 簡單排序簡單排序 1 直接插入排序 冒泡排序 簡單選擇排序 2 掌握每種排序算法基本思想 并能針對給定的某序列 寫出完整排序過程 3 三種排序算法的時間復(fù)雜度均為 O n2 空間復(fù)雜度為 O 1 4 直接插入和冒泡排序的最好情況均為元素已經(jīng)有序 最壞情況為逆序 簡單選擇排序與元素初始 序列的排列無關(guān) 9 3 改進(jìn)排序改進(jìn)排序 1 希爾排序 快速排序 堆排序 歸并排序 2 掌握每種排序