第一章緒論
一． 基本概念和術語
資料結構是一門研究非數值計算的程式設計問題中計算機的操作物件以及它們之間的關係和操作等的學科。
術語：資料、資料元素、資料物件、資料結構、抽象資料型別、演算法。
資料結構的形式定義（二元組）
資料的邏輯結構：（四類基本結構）線性結構、樹型結構、圖狀結構、集合
它們各自的特性？
資料的儲存結構（物理結構）：主要有順序儲存結構（以儲存位址相鄰來表示邏輯上的相鄰關係），鏈式儲存結構（用指標來指示邏輯上的相鄰關係）
抽象資料型別（三元組）
演算法的定義，演算法的5個重要特性。
二． 演算法的時間複雜度和空間複雜度
演算法的評價：正確性、可讀性、健壯性、高效率、低儲存量
求語句頻度、時間複雜度
第二章線性表
一． 線性表的定義
線性結構的特點
二． 線性表的儲存結構
1． 順序儲存結構（順序表）：隨機訪問
插入/刪除元素時，需移動元素的次數。
2． 鏈式儲存結構（鍊錶，分為單(向)鍊錶、雙(向)鍊錶）：非隨機訪問（順序訪問）
帶頭結點的鍊錶和不帶頭結點的鍊錶；
迴圈/非迴圈的鍊錶；
鍊錶空與非空的情況（判斷條件）。
3． 兩種儲存結構的優缺點比較，各適合那些場合。
三． 線性表操作的實現（演算法描述）
插入元素、刪除元素、查詢、判表是否滿足某種特性、逆置等。
例：判斷題：1. 線性表的邏輯順序與儲存順序總是一致的。
2. 線性結構的基本特徵是：每個結點有且僅有乙個直接前驅和乙個直接後繼。
3. 線性表的鏈式儲存結構優於順序儲存結構。
選擇題：線性表l在( )情況下適於使用鍊錶結構實現。
a. 不需修改l的結構b. 需不斷對l進行刪除、插入
c. 需經常修改l中結點值 d. l中含有大量結點
填空題：1. 對於順序表，在第i個元素前插入乙個元素需移動個元素，要刪除第i個元素，需移動個元素。
2. 在雙向迴圈鍊錶中某結點（由指標p指示）之後插入s指標所指結點的操作是：
第三章棧和佇列
一． 棧
1． 棧的定義、特點（後進先出）
2． 棧的儲存結構：順序儲存結構鏈式儲存結構
3． 棧的應用：二叉樹的先序、中序、後序遍歷演算法圖的深度優先遍歷演算法
（將遞迴演算法改寫為非遞迴演算法可借助棧來完成；
遞迴演算法的執行需用棧來實現。）
二． 佇列
1． 佇列的定義、特點（先進先出）
2． 佇列的儲存結構：順序儲存結構（迴圈佇列），鏈式儲存結構
3． 佇列的應用：二叉樹層序遍歷演算法圖的廣度優先遍歷演算法
4． 迴圈佇列：·隊空、隊滿的判斷條件
·求佇列的長度
例：判斷題：因為棧是特殊的線性表，所以對線性表的所有操作都可以用於對棧操作。
填空題：迴圈佇列隊滿的條件是
第四章串
第五章陣列和廣義表
第六章樹和二叉樹
一． 樹、二叉樹的定義
二． 二叉樹
1． 二叉樹的性質（5條）
2． 二叉樹的儲存結構：順序儲存結構（按完全二叉樹層序存放）
鏈式儲存結構（二叉鍊錶、三叉鍊錶）（空鏈域的個數）
3． 遍歷二叉樹：先序、中序、後序、層序
應用：給定二叉樹的先序和中序（或後序和中序）序列，畫出相應的二叉樹。
三． 樹和森林
1． 樹的儲存結構：雙親表示法孩子表示法孩子-兄弟（二叉樹）表示法
2． 樹（森林）與二叉樹的相互轉換
3． 樹的遍歷：先根、後根次序遍歷
4． 森林的遍歷：先序、中序遍歷
四． 赫夫曼樹及其應用
1． 構造最優二叉樹（赫夫曼樹），求wpl
2． 赫夫曼編碼
五． 各種二叉樹概念的區分
1． 滿二叉樹（若深度為k，結點數？）
2． 完全二叉樹（若深度為k，結點數至多、至少？）
3． 正則二叉樹（嚴格二叉樹）（若深度為k，結點數至多、至少？）
4． 最優二叉樹
5． （折半查詢的）判定樹
6． 二叉排序（二叉查詢樹）樹
7． 平衡二叉樹
8． 堆
六． 二叉樹有關的遞迴演算法
例：判斷題：1. 已知二叉樹的先序序列和後序序列並不能唯一地確定這棵二叉樹，因為不知道二叉樹的根結點是哪乙個。
2. 一般二叉樹的第i層上有2i-1個結點，深度為k的二叉樹有2k-1個結點。
選擇題：1. 下列二叉樹中，( )可用於實現符號不等長高效編碼。
a. 最優二叉樹 b. 二叉查詢樹 c. 平衡二叉樹 d. 二叉排序樹
2．結點數為ｎ的二叉樹高度至多為( )。
a. 不定 bc. log2n+1 d. log2n
填空題：1. 將滿/完全二叉樹（含n個結點）中各結點從上到下，從左到右進行編號（根結點編號為1），則編號為i的結點，其雙親編號為其左孩子編號為其右孩子編號為
2. 對樹的遍歷有先根次序遍歷樹和後根次序遍歷樹。若以二叉鍊錶作樹的儲存結構,則樹的先根遍歷可借用二叉樹的遍歷演算法來實現,而樹的後根遍歷可借用二叉樹的遍歷演算法來實現。
應用題：1. 已知某二叉樹的先序遍歷序列是abcdefghi，中序遍歷序列是bdceaghfi，畫出該二叉樹。
2. 以資料集(4,5,6,7,10,12,18)為葉結點權值，構造一棵赫夫曼樹，給出每個葉子的赫夫曼編碼，並求其帶權路徑長度。
第七章圖
一. 圖的定義和術語
無向圖、有向圖、（無向/有向）完全圖、子圖、（強）連通圖、（強）連通分量、生成樹
二． 圖的儲存結構
無向圖（或網）：鄰接矩陣、鄰接表
有向圖（或網）：鄰接矩陣、鄰接表、逆鄰接表
三． 圖的遍歷（針對具體的儲存結構進行）
深度優先搜尋遍歷圖（利用棧） 廣度優先搜尋遍歷圖（利用佇列）
四． 圖的遍歷的應用
求無向圖的連通分量、生成樹（生成森林）
五． 圖的應用
求最小生成樹（無向網）：prim演算法、kruskal演算法
分別用這兩種方法依次得到最小生成樹邊的過程
例：判斷題：乙個連通圖的連通分量是包含該圖中的所有（n個）頂點和任意n-1條邊的子圖。
應用題：已知圖g如下，畫出該有向圖的鄰接矩陣和鄰接表，並根據你的鄰接表分別寫出深度優先遍歷和廣度優先遍歷的頂點序列。abc
de第九章查詢
一． 靜態查詢表
1. 順序查詢表（設定崗哨）
2. 有序查詢表（折半/二分查詢） 要求：元素值有序的順序表
查詢演算法，折半查詢的判定樹
二． 動態查詢表
1． 二叉排序樹（二叉查詢樹）
定義、查詢、插入、刪除
特徵：中序遍歷有序
從空樹開始，依次插入元素，建立一棵二叉排序樹
2． 平衡二叉樹
定義、查詢、插入
從空樹開始，依次插入元素，建立一棵平衡的二叉排序樹
3． n個元素的二叉排序樹、平衡二叉樹的（最大、最小）深度
三． 雜湊表
1． 雜湊表的定義
2． 雜湊函式的構造方法
3． 處理衝突的方法
4． 雜湊表的造表、查詢
5． 裝填因子影響雜湊表的查詢效率
四． 平均查詢長度的計算
1． 等概率情況下，查詢成功時的平均查詢長度asl
2． 查詢不成功時的查詢長度
例：判斷題： 1. 任乙個二叉排序樹的平均查詢長度都小於用順序查詢法查詢同樣結點的線性表的平均查詢長度。
2. 當二叉排序樹是一棵平衡樹時，其平均查詢長度為o(log2n)。
選擇題：1. 折半查詢演算法要求被查詢的表是( )。
a. 鍵值有序的鍊錶 b. 鍵值不一定有序的鍊錶
c. 鍵值有序的順序表 d. 鍵值不一定有序的順序表
2. 若查詢表是乙個有序的單鏈表，則應採用( )方法。
a. 順序查詢 b. 折半查詢c. 分塊查詢 d. 雜湊查詢
3．設線性表中元素的關鍵字序列為（8,16,24,29,35,40,46,58,66,73,87,98），用折半查詢法查關鍵字等於87的元素時，需依次比較關鍵字（ ）。
a. 40,58,87 b. 46,87 c. 40,66,87 d. 46,66,87
應用題：1. 已知如下所示長度為8的表: (12，71，36，45，47，50，2，9)，按表中元素順序構造一棵平衡的二叉排序樹，請畫出該樹。（二叉排序樹）
2. 設雜湊表長為16，雜湊函式為h(key)=key mod 13，用開放定址法的二次探測再雜湊處理衝突。依次存入10個元素：
17,24,36,21,83,96,13,34,57,46，請畫出它們在雜湊表中的分布情形，並計算等概率時的asl。
3. 對於上題，如果採用鏈位址法處理衝突，請畫出相應的雜湊表，並計算等概率時的asl。
第一十章內部排序
一． 內部排序的方法（排序過程）
1． 直接插入排序
2． 希爾排序
3． 起泡排序
4． 快速排序
5． 簡單選擇排序
6． 堆排序
7． 歸併排序
二． 各種內部排序方法的比較
（最好、最壞、平均）時間複雜度平均空間複雜度
三 ．排序方法的穩定性
哪些是穩定的排序方法，哪些是不穩定的排序方法？
例：判斷題：歸併排序和堆排序的平均時間和最壞情況下的時間效能都是o(nlogn),因此，它們在最壞情況下的時間效能比快速排序好。
應用題：若要按公升序對關鍵字序列(36,45,85,16,23,16,58,22,59,74,12,46)進行排序，請寫出：(1). 堆排序初始建堆(大頂堆)的結果；
(2). 以第乙個元素為樞軸的快速排序一趟掃瞄的結果；
(3). 起泡排序第一趟的結果；
(4). 希爾排序第一趟（增量5）的結果
資料結構總複習題
第一章概論 一 填空題 1 資料的儲存結構可用四種基本的儲存方法表示，分別是順序 鏈式 索引和雜湊。2 乙個演算法具有5個特性 有窮性 確定性 可行性，有零個或多個輸入 有乙個或多個輸出 3 資料結構包括資料的邏輯結構 儲存結構和運算 或基本操作 這三個方面的內容。4 資料結構中評價演算法的兩個重要...
資料結構總複習題 da an
一 填空題 1.資料結構是研究資料的 邏輯結構 和 物理結構，並在這種結構上定義相關的運算，設計實現這些運算的演算法，分析演算法的效率。演算法的效率包括時間和空間兩個方面，分別稱為 時間複雜度 和 空間複雜度 2.資料的基本單位是 資料元素，資料的最小單位是 資料項。3.演算法是對特定問題求解 步驟...
資料結構複習
0.緒論 一 填空題 1 資料的邏輯結構是資料元素之間的邏輯關係，通常有下列4類 2 資料的儲存結構是資料在計算機儲存器裡的表示，主要有4種基本儲存方法 二 選擇題 1 乙個演算法必須在執行有窮步之後結束，這是演算法的 a 正確性 b 有窮性 c 確定性 d 可行性 2 演算法的每一步必須有確切的定...