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