第二章線性表
1.線性表的邏輯結構:資料元素之間存在一對一的線性關係
線性表的儲存結構:順序和鏈式;順序表和煉表。
順序錶用一維陣列實現,鍊錶有單鏈表和雙鏈表及迴圈鍊錶。(每種鍊錶含有指標的個數)
2.掌握順序表和煉表的查詢,插入、刪除和排序操作的演算法時間複雜度。
第三章棧和佇列
1. 棧和佇列邏輯結構:資料元素之間存在一對一的線性關係,是操作受限的線性表。
棧和佇列儲存結構:順序和鏈式。
2.掌握習題的資料元素進棧和出棧形成的序列。
3.掌握迴圈佇列的對空和對滿的判斷條件。
第五章陣列
1. 掌握陣列的順序表示和實現
2. 陣列中資料元素儲存位址的計算
3.了解矩陣的壓縮儲存
第六章數和二叉樹
1. 樹的邏輯結構:資料元素之間存在一對多的非線性關係。樹和二叉樹中每個結點最多乙個前驅結點,除了葉子結點有多個後繼結點。
儲存結構:順序和鏈式,主要是鏈式。
2. 掌握二叉樹的基本形態:
3. 二叉樹的性質:
性質 1 :在二叉樹的第 i 層上至多有2i-1 個結點
性質 2:深度為 k 的二叉樹上至多含 2k-1 個結點(k≥1)
性質 3 :對任何一棵二叉樹,若它含有n0 個葉子結點、n2 個度為 2 的結點,則必存在關係式:n0 = n2+1。
性質 3 :對任何一棵二叉樹,若它含有n0 個葉子結點、n2 個度為 2 的結點,則必存在關係式:n0 = n2+1。
性質 4 :若對含 n 個結點的完全二叉樹從上到下且從左至右進行 1 至 n 的編號,則對完全二叉樹中任意乙個編號為 i 的結點:編號為 2i 的結點為其左孩子結點;編號為2i+1 的結點為其右孩子結點。
4.n個結點的二叉鍊錶中有2n個指標域,其中有n-1個非空的指標域,有n+1個空鏈域。
5. 掌握樹的三種遍歷方法:先(根)序的遍歷、中(根)序的遍歷、後(根)序的遍歷。
先序和中序、中序和後序都能唯一的確定一顆二叉樹,但先序和後序不能唯一的確定一顆二叉樹。
6. 掌握樹、森林轉換為二叉樹的和二叉樹轉換為樹和森林的方法。
樹轉換為二叉樹:左子樹是左邊第乙個孩子,右子樹是其右邊相鄰的兄弟。樹轉換為二叉樹後,二叉樹沒有右子樹。左是孩子,右是兄弟
按相反的規則二叉樹轉換為樹:乙個結點的左子樹成為孩子,右子樹成為兄弟。
每一棵樹都有唯一的一棵二叉樹與之對應
森林轉換為二叉樹:
(1 將森林中的每棵樹轉換成相應的二叉樹。
(2)第一棵二叉樹不動,從第二棵二叉樹開始,依次把後一棵二叉樹的根結點作為前一棵二叉樹根結點的右孩子,當所有二叉樹連在一起後,所得到的二叉樹就是由森林轉換得到的二叉樹。
二叉樹轉換為森林:
第七章圖
1.掌握圖的基本概念和術語。如完全圖、有向完全圖、連通圖,至稠密圖。
2.有向圖無向圖的鄰接矩陣和鄰接表及其特點。
3.掌握由圖能寫出鄰接矩陣和鄰接表,由鄰接矩陣和鄰接表畫出乙個圖的方法
4.掌握圖的遍歷兩種方法及其遍歷的頂點序列。
5.掌握拓撲序列的概念,對有向圖進行拓撲序列。
第九章查詢
1、掌握順序查詢法、折半查詢法、二叉排序樹查詢基本思想和查詢過程。每種查詢方法的平均查詢長度
2、掌握(雜湊表)雜湊表的概念
3、掌握(雜湊表)雜湊表函式構造方法:6種,重點是除留餘數法
4、掌握雜湊表處理衝突的方法:重點是開放定址法的線性探測再雜湊
5. 掌握雜湊表等概率情況下查詢成功和不成功的平均查詢長度
第十章內部排序
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 重點掌握圖的深度優先遍歷及廣度優先遍歷 重點掌握圖...