**電大理工部計算機教研室
資料結構是**電大計算機應用專業一門統設必修課和專業基礎課，它主要研究資料的各種邏輯結構，在計算機中的儲存結構，對資料進行的插入、查詢、刪除、排序、遍歷等運算，這些運算在儲存結構上具體實現的演算法。學習好該課程將為學好整個計算機專業打下堅實的基礎。
第一部分各章複習要求
下面按照主教材中各章次序給出每章的具體複習要求，以便指導同學們更好地進行期末複習。
第一章緒論
重點掌握的內容：
1. 資料結構的二元組表示，對應的圖形表示，序偶和邊之間的對應關係。
2. 集合結構、線性結構、樹結構和圖結構的特點。
3. 抽象資料型別的定義和表示方法。
4. 一維和二維陣列中元素的按下標和按位址的訪問方式以及相互轉換，元素位址和陣列位址的計算，元素占用儲存空間大小和陣列占用儲存空間大小的計算。
5. 普通函式過載和操作符函式過載的含義，定義格式和呼叫格式。
6. 函式定義中值引數和引用引數的說明格式及作用，函式被呼叫執行時對傳送來的實際引數的影響。
7. 演算法的時間複雜度和空間複雜度的概念，計算方法，數量級表示。
8. 乙個簡單演算法的最好、最差和平均這三種情況的時間複雜度的計算。
對於本章的其餘內容均作一般掌握。
第二章線性表
重點掌握的內容：
1. 線性表的定義和抽象資料型別的描述，線性表中每一種操作的功能，對應的函式名、返回值型別和參數列中每個引數的作用。
2. 線性表的順序儲存結構的型別定義，即list型別的定義和每個域的定義及作用。
3. 線性表的每一種運算在順序儲存結構上實現的演算法，及相應的時間複雜度。
4. 鏈結儲存的概念，線性表的單鏈結和雙鏈結儲存的結構，向單鏈表中乙個結點之後插入新結點或從單鏈表中刪除乙個結點的後繼結點的指標鏈結過程。
5. 單鏈表中結點的結構，每個域的定義及作用，即lnode型別的定義及結構。
6. 帶表頭附加結點的鍊錶、迴圈鍊錶、雙向鍊錶的結構特點。
7. 線性表的每一種運算在單鏈表上實現的演算法及相應的時間複雜度。
8. 在順序儲存或鏈結儲存的線性表上實現指定功能的演算法的分析和設計。
對於本章的其餘內容均作一般掌握。
第三章稀疏矩陣和廣義表
重點掌握的內容：
1. 稀疏矩陣的定義和三元組線性表表示。
2. 稀疏矩陣的順序儲存、帶行指標向量的鏈結儲存、十字鏈結儲存的型別定義，在每一種儲存中非零元素結點的結構。
3. 廣義表的定義和表示，廣義表長度和深度的計算。
4. 廣義表的鏈結儲存結構中結點型別的定義，分別求廣義表長度和深度的遞迴演算法，它們對應的時間複雜度。
一般掌握的內容：
1. 稀疏矩陣的轉置運算和演算法描述。
2. 兩個稀疏矩陣的做加法的過程和演算法描述。
對於本章的其餘內容均作一般了解。
第四章棧和佇列
重點掌握的內容：
1. 棧的定義和抽象資料型別的描述，棧中每一種操作的功能，對應的函式名、返回值型別和參數列中每個引數的作用。
2. 棧的順序儲存結構的型別定義，即stack型別的定義和每個域的定義及作用。
3．棧的每一種運算在順序儲存結構上實現的演算法，及相應的時間複雜度。
4. 棧的每一種運算在鏈結儲存結構上實現的演算法及相應的時間複雜度。
5. 算術表示式的中綴表示和字尾表示，以及相互轉換的規則，字尾表示式求值的方法。
6. 佇列的定義和抽象資料型別的描述，佇列中每一種操作的功能，對應的函式名、返回值型別和參數列中每個引數的作用。
7. 佇列的順序儲存結構的型別定義，即queue型別的定義和每個域的定義及作用。
8. 佇列的每一種運算在順序儲存結構上實現的演算法及相應的時間複雜度。
9. 利用棧和佇列解決簡單問題的演算法分析和設計。
一般掌握的內容：
1. 字尾表示式求值的演算法，把中綴表示式轉換為字尾表示式的演算法。
2. 求解階乘問題和迷宮問題的方法和演算法。
3. 佇列的鏈結儲存結構，以及實現每一種佇列運算的演算法和相應的時間複雜度。
第五章樹和二叉樹
重點掌握的內容：
1. 樹和二叉樹的定義，對於一棵具體樹和二叉樹的二元組表示及廣義表表示。
2. 樹和二叉樹的概念，如結點的度、樹的度、樹的層數、樹的深度等。
3. 樹和二叉樹的性質，如已知樹或二叉樹的深度h可求出相應的最多結點數，已知結點數n可求出對應樹或二叉樹的最大和最小高度。
4. 二叉樹中結點的編號規則和對應的順序儲存結構。
5. 二叉樹的鏈結儲存結構及儲存結點的型別定義，即btreenode型別的定義和每個域的定義及作用。
6. 二叉樹的先序、中序、後序遍歷的遞迴過程和遞迴演算法，中序遍歷的非遞迴演算法，按層遍歷的過程和演算法，每種演算法的時間複雜度。
7. 普通樹的鏈結儲存結構，gtreenode型別的定義和每個域的定義及作用。
8．普通樹的先根、後根和按層遍歷的過程及演算法。
9. 在鏈結儲存的二叉樹上實現指定功能的演算法分析和設計。
對於本章的其餘內容均作一般掌握。
第六章二叉樹的應用
重點掌握的內容：
1. 二叉搜尋樹的定義和性質。
2. 二叉搜尋樹查詢的遞迴演算法和非遞迴演算法，相應的時間複雜度，查詢乙個元素的查詢長度，即從樹根結點到該結點的路徑上的結點數。
3. 二叉搜尋樹插入的遞迴演算法和非遞迴演算法，相應的時間複雜度，根據一組資料生成一棵二叉搜尋樹的過程。
4. 堆的定義和順序儲存結構，小根堆和大根堆的異同。
5. 向堆中插入元素的過程、演算法描述及時間複雜度。
6. 從堆中刪除元素的過程、演算法描述及時間複雜度。
7. 哈夫曼樹的定義，樹的帶權路徑長度的計算，根據若干個葉子結點的權構造哈夫曼樹的過程。
對本章的其餘內容均作一般了解。
第七章圖
重點掌握的內容：
1. 圖的頂點集和邊集的表示。
2. 圖的一些概念的含義，如頂點、邊、度、完全圖、子圖、路徑、路徑長度、連通圖、權、網等。
3. 圖的鄰接矩陣、鄰接表和邊集陣列三種儲存結構及相應的空間複雜度。
4. 儲存圖使用的vexlist, adjmatrix, adjlist, edgenode, edgeset, edge等型別的定義及用途。
5. 圖的深度優先和廣度優先搜尋遍歷的過程。
6. 對分別用鄰接矩陣和用鄰接表表示的圖進行深度優先搜尋遍歷的過程、演算法描述以及相應的時間複雜度。
7. 對分別用鄰接矩陣和用鄰接表表示的圖進行廣度優先搜尋遍歷的過程、演算法描述以及相應的時間複雜度。
8. 圖的生成樹、生成樹的權、最小生成樹等的定義。
9. 根據普里姆演算法求圖的最小生成樹的過程和演算法描述。
10．根據克魯斯卡爾演算法求圖的最小生成樹的過程和演算法描述。
11. 圖的拓撲序列和拓撲排序的概念，求圖的拓撲序列的方法，對用鄰接表表示的圖進行拓撲排序的過程和演算法。
對本章的其餘內容均作一般掌握。它包括建立圖的鄰接矩陣、鄰接表、邊集陣列演算法，建立圖的逆鄰接表和十字鄰接表等內容。
第八章查詢
重點掌握的內容：
1. 在一維陣列上進行順序查詢的過程、演算法、平均查詢長度和時間複雜度。
2. 在一維陣列上進行二分查詢的過程、遞迴和非遞迴演算法、平均查詢長度和時間複雜度，二分查詢乙個給定值元素的查詢長度（即查詢路徑上的元素數），二分查詢對應的判定樹的性質。
3. 索引儲存的概念，索引表的儲存結構和索引項的儲存結構，索引查詢乙個元素的過程、平均查詢長度和時間複雜度。
4. 雜湊儲存的概念，雜湊函式、雜湊表、衝突、同義詞、裝填因子等術語的含義。
5. 利用除留餘數法建立雜湊函式求元素雜湊位址的方法。
6. 利用開放定址法中的線性探查法處理衝突進行雜湊儲存和查詢的過程，利用鏈結法處理衝突進行雜湊儲存和查詢的過程。
7. 根據除留餘數法構造雜湊函式，採用線性探查法或鏈結法處理衝突，把一組資料雜湊儲存到雜湊表中，計算出乙個給定值元素的查詢長度和查詢所有元素的平均查詢長度。
8. b_樹中每個結點的結構，樹根結點或非樹根結點中關鍵字的個數範圍和子樹的個數範圍，b_的結構特性，從b_樹上查詢乙個給定值元素的過程。
一般掌握的內容：
1. 索引查詢和分塊查詢演算法。
2. b_樹查詢演算法。
3. 向b_樹中插入元素的過程。
對本章的其餘內容均作一般了解。
第九章排序
重點掌握的內容：
1. 直接插入、直接選擇和氣泡排序的方法，排序過程及時間複雜度。
2. 在堆排序中建立初始堆的過程和利用堆排序的過程，對乙個分支結點進行篩運算的過程、演算法及時間複雜度，整個堆排序的演算法描述及時間複雜度。
3. 快速排序的方法，對一組資料的排序過程，對應的二叉搜尋樹，快速排序過程中劃分的層數和遞迴排序區間的個數。
4. 快速排序的遞迴演算法，它在平均情況下的時間和空間複雜度，在最壞情況下的時間和空間複雜度。
5. 二路歸併排序的方法和對資料的排序過程，每趟排序前、後的有序表長度，二路歸併排序的趟數、時間複雜度和空間複雜度。
一般掌握的內容：
1. 每一種排序方法的穩定性。
2. 直接插入排序和直接選擇排序的演算法。
一般了解的內容：
1. 二路歸併排序過程中涉及的每個演算法。
2. 氣泡排序演算法。
第二部分期末複習題示例
資料結構複習
0.緒論 一 填空題 1 資料的邏輯結構是資料元素之間的邏輯關係，通常有下列4類 2 資料的儲存結構是資料在計算機儲存器裡的表示，主要有4種基本儲存方法 二 選擇題 1 乙個演算法必須在執行有窮步之後結束，這是演算法的 a 正確性 b 有窮性 c 確定性 d 可行性 2 演算法的每一步必須有確切的定...
資料結構複習
1.以niklus wirth的觀點，程式等於什麼?2.演算法的重要特性。3.好演算法的標準。4.線性結構的特點。5.線性結構與非線性結構的區別。6.列出所學過的線性結構與非線性結構。7.頭指標 頭結點 首元結點的區別。8.帶頭結點和不帶頭結點的線性鍊錶的區別。9.單鏈表 雙鏈表 迴圈鍊錶的區別及各...
資料結構複習
2 掌握圖的兩種儲存結構，鄰接矩陣及鄰接表 重點掌握圖的鄰接矩陣表示方法。掌握給定乙個圖，採用鄰接矩陣或鄰接表表示法，對圖中邊 頂點的度 任意兩點是否有邊相連的確定方法 3 最小生成樹，重點掌握採用普里姆演算法及克魯斯卡爾演算法如何求最小生成樹 4 重點掌握圖的深度優先遍歷及廣度優先遍歷 重點掌握圖...