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