北京工業(yè)大學(xué) 數(shù)據(jù)結(jié)構(gòu) 期末復(fù)習(xí)

考試題型 單選 5題 共10分填空 5題 共10分簡(jiǎn)答題 5題 共45分算法閱讀 15分算法設(shè)計(jì) 20分考試要求 閉卷 第1章概論 DS描述 按一定邏輯關(guān)系組織的數(shù)據(jù)元素的表示及相關(guān)操作數(shù)據(jù)邏輯結(jié)構(gòu) 線性結(jié)構(gòu) 樹(shù)形結(jié)構(gòu)和圖形結(jié)構(gòu)數(shù)據(jù)存儲(chǔ)結(jié)構(gòu) 順序方法 鏈接方法 索引方法 散列方法抽象數(shù)據(jù)類型ADT算法4個(gè)特性 通用性 有效性 確定性 有窮性算法分析 T n S n 算法分析的相關(guān)概念 最差 最佳與平均情況的意義 ADT的定義 三元組表示ADT D R P ADT抽象數(shù)據(jù)類型名 數(shù)據(jù)對(duì)象D 數(shù)據(jù)關(guān)系R 基本操作P ADT抽象數(shù)據(jù)類型名用C 類模板的聲明表示ADT ADT定義類模板 類模板代表一類類 不代表具體的類類模板的定義格式 template 類型參數(shù)Type 使用時(shí)用具體數(shù)據(jù)類型代替classclassName private TypedataList public methodName C 引入模板概念 是想突出數(shù)據(jù)的邏輯結(jié)構(gòu)而忽略其具體的數(shù)據(jù)類型 聲明 定義和使用C 類模板 2 類模板 描述了一組相關(guān)的類 它們只能通過(guò)類型來(lái)區(qū)分1 類模板聲明 僅提供了類的名稱和類的模板參數(shù)template 類模板Array可接受任何類型作為參數(shù)classArray Elem data intsize 聲明類模板Array的類數(shù)據(jù)public Array intsz 函數(shù)成員intGetSize 2 函數(shù)成員定義templateArray Array intsz size sz data newElem size templateintArray GetSize returnsize 3 類模板的用法Arrayint array 100 Array接收int作參數(shù) int array為長(zhǎng)100的int型數(shù)組對(duì)象 常見(jiàn)上限g n 的種類 用于比較各算法優(yōu)劣 O 1 O logn O n O nlogn O n2 常數(shù)階對(duì)數(shù)線性對(duì)數(shù)乘積平方 O n3 O 2n O n 立方指數(shù)階乘常數(shù) g n 1對(duì)數(shù) g n logn線性增長(zhǎng) g n n二階增長(zhǎng) g n n2g n nlog n n nlog n 增長(zhǎng)率 n2指數(shù)增長(zhǎng) g n an 題型舉例 算法指的是 A 計(jì)算機(jī)程序B 解決問(wèn)題的計(jì)算方法C 排序算法D 解決問(wèn)題的有限運(yùn)算序列將長(zhǎng)度為n的單鏈表接在長(zhǎng)度為m的單鏈表之后的算法時(shí)間復(fù)雜度為 A O n B O 1 C O m D O m n 第2章線性表 清楚線性表定義 理解類定義及抽象數(shù)據(jù)類型中定義的各個(gè)基本操作含義存儲(chǔ)形式 順序存儲(chǔ)結(jié)構(gòu) 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn) 1 邏輯結(jié)構(gòu)與物理結(jié)構(gòu)一致 2 屬于隨機(jī)存取方式缺點(diǎn) 插入 刪除元素需要移動(dòng) 平均約一半的元素 限制了長(zhǎng)度變化鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn) 1 邏輯結(jié)構(gòu)與物理結(jié)構(gòu)不一致 2 屬于順序存取方式 2 1 2線性表的存儲(chǔ)結(jié)構(gòu) 邏輯結(jié)構(gòu) 存儲(chǔ)空間的映射數(shù)據(jù) 存儲(chǔ)單元建立映射關(guān)系 存儲(chǔ)單元之間關(guān)系建立映射線性表2類存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ) 定長(zhǎng)的一維數(shù)組結(jié)構(gòu) 向量型順序存儲(chǔ)結(jié)構(gòu) 為整個(gè)元素動(dòng)態(tài)分配連續(xù)空間特點(diǎn) 邏輯相鄰物理也相鄰鏈?zhǔn)酱鎯?chǔ) 變長(zhǎng)的線性表存儲(chǔ)結(jié)構(gòu) 按需分配 插入 分配一個(gè)結(jié)點(diǎn) 刪除 回收一結(jié)點(diǎn) 特點(diǎn) 邏輯相鄰物理不一定相鄰 鏈表 單向 循環(huán) 雙向 不特殊說(shuō)明 均帶頭結(jié)點(diǎn) 避免對(duì)空表的特殊處理 算法 時(shí)間復(fù)雜性 在有序表中插入 刪除結(jié)點(diǎn)給定元素位置 插入 刪除相應(yīng)結(jié)點(diǎn)注意 對(duì)循環(huán)鏈表操作時(shí) 尾部的判斷雙向鏈表的插入 刪除結(jié)點(diǎn)刪除結(jié)點(diǎn)一定要釋放空間 2 4線性表實(shí)現(xiàn)方法的比較 順序表優(yōu)點(diǎn)存儲(chǔ)緊湊 邏輯結(jié)構(gòu)由存儲(chǔ)相對(duì)位置體現(xiàn) 沒(méi)使用指針 不用花費(fèi)附加開(kāi)銷 隨機(jī)訪問(wèn) 給定下標(biāo) 常量時(shí)間可定位 鏈表優(yōu)點(diǎn)不限定長(zhǎng)度 無(wú)需事先了解線性表的長(zhǎng)度 允許線性表的長(zhǎng)度有很大變化 不必移動(dòng) 僅需改指針即可插刪 能夠適應(yīng)經(jīng)常插入刪除內(nèi)部元素的情況 適用不能確定長(zhǎng)度上限 頻繁插刪 用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)按位置頻繁進(jìn)行讀取 數(shù)據(jù)域占用空間小于指針域 用順序存儲(chǔ)結(jié)構(gòu) 有序的順序表與無(wú)序的順序表相比 其操作優(yōu)勢(shì)是 A 刪除快B 插入快C 生成快D 查找快 若對(duì)線性表進(jìn)行的主要操作是按下標(biāo)存取 且很少插入和刪除 則應(yīng)該采用的存儲(chǔ)結(jié)構(gòu)是 若需要頻繁地對(duì)線性表進(jìn)行插入和刪除時(shí) 則應(yīng)該采用的存儲(chǔ)結(jié)構(gòu)是 題型舉例 第3章棧與隊(duì)列 棧與隊(duì)列的定義 ADT定義及基本操作 棧的應(yīng)用 會(huì)跟蹤遞歸函數(shù)執(zhí)行過(guò)程深度 縱向 周游表達(dá)式求值 中綴 后綴 求值 隊(duì)列的應(yīng)用 按層周游注意 熟悉ADT的操作形式 會(huì)直接調(diào)用抽象數(shù)據(jù)類型中定義的操作 算符優(yōu)先關(guān)系表 錯(cuò) 左 右 a b c d e abc de 后綴表達(dá)式求值 循環(huán) 依次分析輸入序列 1 輸入是操作數(shù) 則入棧 2 輸入是運(yùn)算符 則兩次出棧 取操作數(shù)2和操作數(shù)1 按照運(yùn)算符進(jìn)行計(jì)算 將結(jié)果入棧 重復(fù) 直至遇到結(jié)束符 此時(shí)棧頂值就是輸入表達(dá)式的值 第4章字符串 了解 基本概念存儲(chǔ)結(jié)構(gòu) 順序 標(biāo)準(zhǔn)類 基本操作的含義 第5章二叉樹(shù) 定義 性質(zhì) 存儲(chǔ)結(jié)構(gòu) 相應(yīng)的類定義 滿二叉樹(shù) 完全二叉樹(shù)及擴(kuò)充二叉樹(shù)抽象數(shù)據(jù)類型定義中的基本操作含義深度周游 遞歸與非遞歸 廣度周游二叉搜索樹(shù)插入 刪除 改進(jìn) 與檢索算法 必須能夠跟蹤執(zhí)行過(guò)程 求ASL 堆概念 建堆 篩選 插 刪的相關(guān)算法 過(guò)程 Huffman樹(shù)構(gòu)造及Huffman編碼 深度優(yōu)先周游二叉樹(shù) 遞歸實(shí)現(xiàn) templatevoidBinaryTree PreOrder BinaryTreeNode root if root NULL Visit root value 前序DepthOrder root leftchild 訪問(wèn)左子樹(shù)DepthOrder root rightchild 訪問(wèn)右子樹(shù) Visit root 中序 Visit root 后序 生成二叉搜索樹(shù)45 53 12 37 3 100 61 24 90 78 二叉搜索樹(shù)的刪除 在二叉搜索樹(shù)里刪除結(jié)點(diǎn)時(shí) 不是把以這個(gè)結(jié)點(diǎn)為根的子樹(shù)都刪除掉 只是刪除一個(gè)結(jié)點(diǎn) 并且還要保持二叉搜索樹(shù)的性質(zhì) 刪除過(guò)程分為兩種情況 沒(méi)有左子樹(shù)有左子樹(shù) 沒(méi)有左子樹(shù) 若結(jié)點(diǎn)p沒(méi)有左子樹(shù) 則用右子樹(shù)的根代替被刪除的結(jié)點(diǎn)p 有左子樹(shù) 改進(jìn) 若p 50 有左子樹(shù) 則在左子樹(shù)里找中序周游的最后一個(gè)結(jié)點(diǎn)s 40 刪除s 用s的左子樹(shù)代替s 用s代替被刪p這種方法可以降低二叉樹(shù)的高度 已知序列72 73 71 23 94 16 05 68建堆 72 最小堆的插入 插入過(guò)程 插入點(diǎn)追加到最后 自下而上依次比較父與子 直到滿足堆的定義 插入1320 1314 13 最小堆的刪除 用最后結(jié)點(diǎn)替換被刪結(jié)點(diǎn) 自上至下調(diào)整成堆 最后結(jié)點(diǎn) 被刪結(jié)點(diǎn) 只影響其子樹(shù)的最小堆性質(zhì) 12 14 19 24 18 22 15 17 20 刪除1414 2626 1926 22 26 5 6Huffman樹(shù)及其應(yīng)用 外部路徑長(zhǎng)度li擴(kuò)充二叉樹(shù)從根到每個(gè)外部結(jié)點(diǎn)的路徑長(zhǎng)度之和外部路徑長(zhǎng)度最小的二叉樹(shù) 是完全二叉樹(shù)帶權(quán)外部路徑長(zhǎng)度 weightedexternalpath 最小的二叉樹(shù) Huffman樹(shù)要求給出一個(gè)具有n個(gè)外部結(jié)點(diǎn)的擴(kuò)充二叉樹(shù)每個(gè)外部結(jié)點(diǎn)Ki有一個(gè)wi與之對(duì)應(yīng) 作為該外部結(jié)點(diǎn)的權(quán)此擴(kuò)充二叉樹(shù)的葉結(jié)點(diǎn)帶權(quán)外部路徑長(zhǎng)度總和最小注意 不管內(nèi)部結(jié)點(diǎn) 也不用有序特點(diǎn) 權(quán)越大的葉結(jié)點(diǎn)離根越近 3 5 29 14 7 8 c3 d4 e5 23 f6 11 h8 b2 建樹(shù) g7 a下標(biāo) 1 1 0 1 0 1 1 0 0 0 a 0001b 10c 1110d 1111f 01g 0000h 001 與算法有關(guān)的典型例題 已知一棵二叉樹(shù)的前序和中序 后序和中序 遍歷序列 構(gòu)造對(duì)應(yīng)的二叉樹(shù)通過(guò)二叉樹(shù) 獲得對(duì)應(yīng)的樹(shù)與森林的相關(guān)信息深度周游與廣度周游二叉樹(shù) 31 具有n個(gè)結(jié)點(diǎn)的滿二叉樹(shù) 其葉子結(jié)點(diǎn)的個(gè)數(shù)為 如果一棵二叉樹(shù)的任何結(jié)點(diǎn) 或者是樹(shù)葉 或者恰有兩棵非空子樹(shù) 則此二叉樹(shù)稱作滿二叉樹(shù) 性質(zhì)3 任何一棵二叉樹(shù) n0 n2 1 某棵二叉樹(shù)的前序序列為ABDEFC 中序序列為DBFEAC 則該二叉樹(shù)對(duì)應(yīng)的后序序列的結(jié)果為 五個(gè)分別帶權(quán)值為9 2 5 7 12的葉子結(jié)點(diǎn)構(gòu)造Huffman樹(shù) 進(jìn)行編碼 并寫(xiě)出該樹(shù)的帶權(quán)外部路徑長(zhǎng)度WPL 給定關(guān)鍵碼序列 創(chuàng)建二叉搜索樹(shù) 并刪除某個(gè)結(jié)點(diǎn) 按照教材中的改進(jìn)算法 求ASL堆排序 給定關(guān)鍵碼序列 建初堆 插入 刪除結(jié)點(diǎn)后 調(diào)整為堆 第6章樹(shù) 樹(shù)與森林定義 ADT定義 基本操作樹(shù) 森林 周游 深度優(yōu)先 廣度優(yōu)先 先根次序周游森林 前序周游二叉樹(shù)后根次序周游森林 中序周游二叉樹(shù)樹(shù) 森林 與二叉樹(shù)的等價(jià)轉(zhuǎn)換樹(shù)與森林的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)動(dòng)態(tài) 左子 右兄 二叉鏈表表示法 森林與二叉樹(shù)的等價(jià)轉(zhuǎn)換 森林由 部分組成 森林中第一棵樹(shù)的根結(jié)點(diǎn)森林中第一棵樹(shù)的子樹(shù)森林森林中其它樹(shù)構(gòu)成的森林 動(dòng)態(tài) 左子 右兄 二叉鏈表表示法 35 B C D E F G A 6 1 4樹(shù)的周游1 深度優(yōu)先周游樹(shù) 一 先根次序周游森林 前序周游二叉樹(shù)首棵樹(shù)根 首棵樹(shù)各子樹(shù) 余下各樹(shù)根 左子樹(shù) 右子樹(shù)依次從左至右對(duì)森林每棵樹(shù)進(jìn)行先序周游二 后根次序周游森林 中序周游二叉樹(shù)首棵樹(shù)各子樹(shù) 首棵樹(shù)根 余下各樹(shù)左子樹(shù) 根 右子樹(shù)依次從左至右對(duì)森林每棵樹(shù)進(jìn)行后序周游先序 ABCEFDGHJI后序 BEFCDAJHIG 帶右鏈的先根次序表示法 這種表示法與llink rlink表示法相比 用ltag代替了llink 占用的存儲(chǔ)單元要少些 但并不丟失信息可以從結(jié)點(diǎn)的次序和ltag的值完全可以推知llinkltag 0 有左子 它的llink指向該結(jié)點(diǎn)數(shù)組右鄰ltag 1 沒(méi)有左子 它的llink為空 第7章圖 有向圖 網(wǎng) 弧 入 出度 有向完全圖無(wú)向圖 網(wǎng) 邊 度 無(wú)向完全圖圖的ADT定義存儲(chǔ)結(jié)構(gòu) 相鄰矩陣 鄰接表 及類定義圖周游算法 深度 廣度 最小生成樹(shù) prim 拓?fù)渑判?單源最短路徑 必須會(huì)嚴(yán)格按照算法手工走給定實(shí)例 典型題目 能夠完成拓?fù)渑判虻膱D一定是一個(gè) n個(gè)頂點(diǎn)的無(wú)向連通圖至少有的邊的條數(shù)是 已知一個(gè)有向圖的相鄰矩陣表示 計(jì)算第i個(gè)結(jié)點(diǎn)的入度的方法是 已知一個(gè)無(wú)向圖的頂點(diǎn)集為 a b c d e 其相鄰矩陣如下所示 1 畫(huà)出該圖的圖形 0100110010000110110110110 2 根據(jù)此相鄰矩陣 從頂點(diǎn)b出發(fā)進(jìn)行深度優(yōu)先周游和廣度優(yōu)先周游 寫(xiě)出相應(yīng)周游的頂點(diǎn)序列 第8章內(nèi)排序 直接插入排序 冒泡排序 快速排序 直接選擇排序 堆排序 歸并排序 桶式排序 基數(shù)排序 手工排序每趟過(guò)程各種排序方法的性能對(duì)比 穩(wěn)定性 時(shí)空 各種排序方法的適用場(chǎng)合 時(shí)間復(fù)雜度 排序算法的理論性能表8 3 在下列排序方法中 平均時(shí)間性能為O nlogn 且空間性能最好的是 A 快速排序B 堆排序C 歸并排序D 基數(shù)排序堆排序在最壞的情況下的時(shí)間復(fù)雜度是 A O log2n B O log2n2 C O nlog2n D O n2 第10章檢索 43 相關(guān)概念 ASL順序查找 二分查找 分塊查找散列表 常見(jiàn)的散列函數(shù)與解決沖突的方法 計(jì)算ASL 查找特點(diǎn) 構(gòu)造方法 開(kāi)散列方法拉鏈法 散列表中每個(gè)槽添加一個(gè)鏈表表頭 當(dāng)發(fā)生沖突時(shí)就拉出一條鏈 建立一個(gè)鏈表方式的同義詞表 動(dòng)態(tài)申請(qǐng)同義詞空間例 77 7 110 95 14 75 62 h Key Key 11同義詞表中同義詞可按值的順序 訪問(wèn)頻率的順序排列 ASL 1 7 1 4 2 2 3 1 例如 關(guān)鍵碼集合 19 01 23 14 55 68 11 82 36 設(shè)定哈希函數(shù)H ke