1、數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)選擇填空解答題（問答題）算法題數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)復(fù)習(xí)原則1 理解各章基本概念（選擇、填空、判斷）2 存儲結(jié)構(gòu)： 1）掌握基本存儲結(jié)構(gòu)（ 表、棧、隊列、二叉樹（順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu)（動態(tài)、靜態(tài)）；存儲信息、含義及C 語言描述） 2）理解復(fù)雜存儲結(jié)構(gòu)（圖、樹）數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)3 算法 1）掌握基本算法及應(yīng)用 如：構(gòu)造、銷毀、插入、刪除、遍歷、查找、排序等，主要步驟、基本思想、主要操作的實現(xiàn)（C語言描述） 2）復(fù)雜算法 掌握方法，能讀懂程序（能填空；能寫出主要數(shù)據(jù)結(jié)構(gòu)的變化狀態(tài)）4 會計算基本（簡單）算法的時間復(fù)雜度。第一章 緒論 第一章 題型選擇填空解答 數(shù)據(jù)結(jié)構(gòu)和算法的有關(guān)概念數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)的邏輯

2、結(jié)構(gòu)及分類數(shù)據(jù)的存儲結(jié)構(gòu)抽象數(shù)據(jù)類型（ADT）算法算法的時間復(fù)雜度 數(shù)據(jù)結(jié)構(gòu):帶有結(jié)構(gòu)和操作的數(shù)據(jù)元素集合。 數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)的存儲結(jié)構(gòu) 數(shù)據(jù)操作的定義（功能）數(shù)據(jù)操作的實現(xiàn)(在計算機(jī)上) 線性結(jié)構(gòu) 非線性結(jié)構(gòu) 順序存儲 鏈?zhǔn)酱鎯?線性表棧、隊列樹結(jié)構(gòu)圖結(jié)構(gòu) 散列存儲索引存儲串及數(shù)組結(jié)構(gòu)操作集合結(jié)構(gòu)第二章 線性表 第二章 題型選擇填空解答算法線性表 線性表的概念:線性表的邏輯結(jié)構(gòu)、基本操作線性表的存儲和實現(xiàn)順序存儲結(jié)構(gòu)-類型定義基本操作算法 線性表的存儲和實現(xiàn)線性鏈表循環(huán)鏈表雙向鏈表實現(xiàn)方式動態(tài)鏈表、靜態(tài)鏈表鏈表的類型定義鏈表的基本操作算法鏈表其它操作算法typedef struct Ln

3、ode ElemType data; Struct Lnode *next;LNode, *LinkList;頭指針aia1ai+1ai-1anL線性鏈表的類型定義第三章 棧和隊列 第三章 題型 選擇填空解答算法 3.1 棧棧的概念、特點棧的順序存儲結(jié)構(gòu)和實現(xiàn)棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)和實現(xiàn) 順序棧、鏈?zhǔn)綏５念愋投x 順序棧、鏈?zhǔn)綏５幕静僮魉惴?表達(dá)式求值（算符優(yōu)先算法）(方法)理解棧在遞歸函數(shù)執(zhí)行過程中的作用編寫遞歸算法 棧的應(yīng)用 隊列隊列的概念、特點循環(huán)隊列鏈?zhǔn)疥犃?循環(huán)隊列、鏈?zhǔn)疥犃械念愋投x 循環(huán)隊列、鏈?zhǔn)疥犃械幕静僮魉惴?第四章 串 4.1 串的有關(guān)概念 4.2 串的存儲和實現(xiàn) 4.3 串

4、的基本運(yùn)算 串的存儲結(jié)構(gòu)串的順序存儲結(jié)構(gòu)定長順序存儲結(jié)構(gòu)串的堆分配存儲和實現(xiàn)S=a1a2 . an第五章數(shù)組和廣義表 第五章 題型選擇填空解答算法 5.1 數(shù) 組 (選擇、填空、解答)數(shù)組的邏輯結(jié)構(gòu)數(shù)組的基本操作數(shù)組的存儲方法多維數(shù)組元素存儲地址的計算(低下標(biāo)優(yōu)先)0 1 n-1 n n+1 2n-1 mn-1a00 a01 a0n-1 a10 a11 a1n-1 am-10 am-11 am-1n-1 5.2.矩陣的壓縮存儲特殊矩陣的概念特殊矩陣的壓縮存儲方法（對稱矩陣）5.2.2 稀疏矩陣的壓縮存儲稀疏矩陣的概念稀疏矩陣的壓縮存儲三元組順序表i j e12345678M.dataM.muM

5、.nuM.tu3 1 -36 1 151 2 125 2 181 3 94 3 246 4 -73 6 14678 5.3 廣義表廣義表的概念（選擇、填空） 表頭、表尾、長度、深度廣義表的存儲 頭尾鏈表存儲結(jié)構(gòu)廣義表的遞歸算法 復(fù)制廣義表 CopyGList(T,L) 求廣義表的深度GListDepth(L) 判廣義表相等第六章 樹和二叉樹 第六章 題型選擇填空解答算法 二叉樹 (選擇、填空、問答)二叉樹的概念二叉樹的性質(zhì) 二叉樹存儲 二叉樹的的順序存儲 (方法) A B D C E F 1 2 3 4 5 6 7 8 9 10 11 12 13 14ABCDEF2511437二叉樹的鏈?zhǔn)酱鎯?/p>

6、和遍歷（方法、算法）二叉樹的鏈?zhǔn)酱鎯?(類型定義)先序、中序、后序遍歷（方法和編程） 按層遍歷（方法、算法） 二叉樹的遞歸算法 1、查詢二叉樹中某個結(jié)點2、統(tǒng)計二叉樹中葉子結(jié)點的個數(shù)3、求二叉樹的深度4、復(fù)制二叉樹線索二叉樹定義 (選擇、填空、問答)實現(xiàn) (方法）使用 (方法） 樹基本概念 (選擇、填空)結(jié)點(node)結(jié)點所處層次(level)樹的深度(depth)結(jié)點的度(degree)樹的度(degree)分支(branch)結(jié)點葉(leaf)結(jié)點孩子(child)結(jié)點雙親(parent)結(jié)點兄弟(sibling)結(jié)點祖先(ancestor)結(jié)點子孫(descendant)結(jié)點有序樹無序

7、樹森林 樹的存儲和樹的遍歷雙親表示法 (方法）孩子鏈表表示法 (方法）孩子兄弟表示法 (方法）森林與二叉樹的對應(yīng)關(guān)系 (方法）等價關(guān)系、等價類樹的遍歷（方法）先根（序）遍歷：先訪問樹的根結(jié)點，然后依次先根遍歷根的每棵子樹。后根（序）遍歷：先依次后根遍歷每棵子樹，然后訪問根結(jié)點。按層次遍歷：先訪問第一層上的結(jié)點，然后依次遍歷第二層，第n層的結(jié)點。哈夫曼樹與哈夫曼編碼（方法）哈夫曼樹（最優(yōu)二叉樹）的概念構(gòu)造哈夫曼樹(方法）哈夫曼編碼(方法）第七章 圖 第七章 題型選擇填空解答算法圖的術(shù)語與定義（選擇、填空）圖的存儲結(jié)構(gòu)及特點（選擇、類型定義、方法）圖的數(shù)組(鄰接矩陣)存儲表示圖的鄰接表存儲表示圖的

8、遍歷（程序填空、方法）圖的深度遍歷（DFS）圖的廣度遍歷（BFS）圖的最小生成樹（方法）普里姆算法克魯斯卡爾算法有向無環(huán)圖拓?fù)渑判颍ǚ椒ǎ╆P(guān)鍵路徑、最短路徑第九章 查找基本概念（選擇、填空、問答）查找也叫檢索，是根據(jù)給定的某個值，在表中確定一個關(guān)鍵字等于給定值的記錄。關(guān)鍵字是數(shù)據(jù)元素中某個數(shù)據(jù)項的值，它可以標(biāo)識一個數(shù)據(jù)元素。查找方法評價查找速度占用存儲空間多少算法本身復(fù)雜程度平均查找長度ASL(Average Search Length)：為確定記錄在表中的位置，需和給定值進(jìn)行比較的關(guān)鍵字的個數(shù)的期望值叫查找算法的平均查找長度。順序表的查找：順序查找有序表的查找：折半查找靜態(tài)查找（算法編程）查找算法（編程）插入算法（方法）刪除算法（方法）動態(tài)查找二叉排序樹定義二叉排序樹的平衡旋轉(zhuǎn)動態(tài)查找平衡二叉排序樹（方法）定義查找算法插入算法結(jié)點分裂刪除算法結(jié)點合并動態(tài)查找B-樹（方法）定