數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)

1、數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)通過(guò)本課程的學(xué)習(xí)，應(yīng)能掌握數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)、存儲(chǔ)方通過(guò)本課程的學(xué)習(xí)，應(yīng)能掌握數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)、存儲(chǔ)方法和基本運(yùn)算，培養(yǎng)自己運(yùn)用法和基本運(yùn)算，培養(yǎng)自己運(yùn)用C+語(yǔ)言正確編寫(xiě)算法及語(yǔ)言正確編寫(xiě)算法及調(diào)試的能力，運(yùn)用數(shù)據(jù)結(jié)構(gòu)解決簡(jiǎn)單的實(shí)際問(wèn)題的能力，調(diào)試的能力，運(yùn)用數(shù)據(jù)結(jié)構(gòu)解決簡(jiǎn)單的實(shí)際問(wèn)題的能力，可為后續(xù)計(jì)算機(jī)方面課程的學(xué)習(xí)打下堅(jiān)實(shí)的基礎(chǔ)?？蔀楹罄m(xù)計(jì)算機(jī)方面課程的學(xué)習(xí)打下堅(jiān)實(shí)的基礎(chǔ)。本課程學(xué)習(xí)的目的本課程學(xué)習(xí)的目的:基本要求基本要求:1、掌握重要數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及基本運(yùn)算、掌握重要數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及基本運(yùn)算的實(shí)現(xiàn)，會(huì)的實(shí)現(xiàn)，會(huì)運(yùn)用線性表、二叉樹(shù)等設(shè)計(jì)算法以解決一些簡(jiǎn)運(yùn)

2、用線性表、二叉樹(shù)等設(shè)計(jì)算法以解決一些簡(jiǎn)單的實(shí)際問(wèn)題，會(huì)通過(guò)閱讀算法理解算法單的實(shí)際問(wèn)題，會(huì)通過(guò)閱讀算法理解算法；2、學(xué)會(huì)做簡(jiǎn)單的算法分析，包括算法的時(shí)間復(fù)雜度和空、學(xué)會(huì)做簡(jiǎn)單的算法分析，包括算法的時(shí)間復(fù)雜度和空間復(fù)雜度。間復(fù)雜度。題型：一、選擇題（一、選擇題（20分）分）20*1二、填空題（二、填空題（20分）分）10*2三、應(yīng)用題（三、應(yīng)用題（45分分二叉樹(shù)（二叉樹(shù)的遍二叉樹(shù)（二叉樹(shù)的遍歷和轉(zhuǎn)換、哈夫曼樹(shù)和編碼）、圖（最小歷和轉(zhuǎn)換、哈夫曼樹(shù)和編碼）、圖（最小生成樹(shù)或單源點(diǎn)最短路徑）、查找（散列生成樹(shù)或單源點(diǎn)最短路徑）、查找（散列查找）、排序（希爾、快速或堆）查找）、排序（希爾、快速或堆）5*

3、9四、算法設(shè)計(jì)題（四、算法設(shè)計(jì)題（15分分單鏈表的應(yīng)用、單鏈表的應(yīng)用、二叉樹(shù)遍歷的應(yīng)用）二叉樹(shù)遍歷的應(yīng)用）題目給出函數(shù)框架，只需實(shí)現(xiàn)函數(shù)功能題目給出函數(shù)框架，只需實(shí)現(xiàn)函數(shù)功能即可即可設(shè)一顆二叉樹(shù)以二叉鏈表為存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)一個(gè)設(shè)一顆二叉樹(shù)以二叉鏈表為存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)一個(gè)算法求此二叉樹(shù)上度為算法求此二叉樹(shù)上度為1 1的結(jié)點(diǎn)個(gè)數(shù)。的結(jié)點(diǎn)個(gè)數(shù)。 struct BiNode /二叉樹(shù)的結(jié)點(diǎn)結(jié)構(gòu)二叉樹(shù)的結(jié)點(diǎn)結(jié)構(gòu) int data; BiNode *lchild, *rchild;int count(BiNode * root) /* root為二叉樹(shù)的根結(jié)點(diǎn)為二叉樹(shù)的根結(jié)點(diǎn)*/ 第一章第一章概論概論基本要求

4、:1、熟悉數(shù)據(jù)、數(shù)據(jù)元素、熟悉數(shù)據(jù)、數(shù)據(jù)元素(數(shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng))、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)的、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)的邏輯結(jié)構(gòu)與物理結(jié)構(gòu)概念邏輯結(jié)構(gòu)與物理結(jié)構(gòu)概念2、熟悉邏輯結(jié)構(gòu)分線性和非線性（樹(shù)、圖）結(jié)構(gòu)、熟悉邏輯結(jié)構(gòu)分線性和非線性（樹(shù)、圖）結(jié)構(gòu) 及每及每種結(jié)構(gòu)的基本特征種結(jié)構(gòu)的基本特征3、了解物理結(jié)構(gòu)分順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)、了解物理結(jié)構(gòu)分順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)4、了解算法的定義、算法的特性、算法的時(shí)間復(fù)雜度、了解算法的定義、算法的特性、算法的時(shí)間復(fù)雜度、算法的空間復(fù)雜度算法的空間復(fù)雜度5、了解簡(jiǎn)單的計(jì)算語(yǔ)句頻度和估算算法時(shí)間復(fù)雜度的、了解簡(jiǎn)單的計(jì)算語(yǔ)句頻度和估算算法時(shí)間復(fù)雜度的方法方法第二章第二章線性表線性表基本要求

5、：1、了解、了解線性表的邏輯結(jié)構(gòu)特性，以及線性表的兩種存儲(chǔ)線性表的邏輯結(jié)構(gòu)特性，以及線性表的兩種存儲(chǔ)實(shí)現(xiàn)方式實(shí)現(xiàn)方式2、熟練掌握、熟練掌握兩種存儲(chǔ)結(jié)構(gòu)的描述方法。鏈表是本章的重兩種存儲(chǔ)結(jié)構(gòu)的描述方法。鏈表是本章的重點(diǎn)和難點(diǎn)。點(diǎn)和難點(diǎn)。3、靈活掌握、靈活掌握順序表的定義與基本操作的實(shí)現(xiàn)，包括插入、順序表的定義與基本操作的實(shí)現(xiàn)，包括插入、刪除算法的實(shí)現(xiàn)；刪除算法的實(shí)現(xiàn)；4、靈活掌握、靈活掌握鏈表結(jié)構(gòu)實(shí)現(xiàn)線性表基本操作的實(shí)現(xiàn)算法；鏈表結(jié)構(gòu)實(shí)現(xiàn)線性表基本操作的實(shí)現(xiàn)算法；5、能夠從時(shí)間和空間復(fù)雜度的角度綜合比較線性表兩種能夠從時(shí)間和空間復(fù)雜度的角度綜合比較線性表兩種存儲(chǔ)結(jié)構(gòu)的不同特點(diǎn)及其適用場(chǎng)合。存儲(chǔ)結(jié)

6、構(gòu)的不同特點(diǎn)及其適用場(chǎng)合。6、會(huì)用線性表解決簡(jiǎn)單的實(shí)際問(wèn)題。、會(huì)用線性表解決簡(jiǎn)單的實(shí)際問(wèn)題。第三章第三章棧、隊(duì)列棧、隊(duì)列基本要求：1、掌握、掌握棧和隊(duì)列的定義、特性，并能正確應(yīng)用它們解決實(shí)棧和隊(duì)列的定義、特性，并能正確應(yīng)用它們解決實(shí)際問(wèn)題；會(huì)通過(guò)閱讀算法理解算法。際問(wèn)題；會(huì)通過(guò)閱讀算法理解算法。2、熟練掌握、熟練掌握棧的順序表示、鏈表表示以及相應(yīng)操作的實(shí)現(xiàn)。棧的順序表示、鏈表表示以及相應(yīng)操作的實(shí)現(xiàn)。特別注意?？蘸蜅M的條件；（主要是出棧和入棧）掌握特別注意棧空和棧滿的條件；（主要是出棧和入棧）掌握遞歸函數(shù)的閱讀。遞歸函數(shù)的閱讀。3、熟練掌握熟練掌握隊(duì)列的順序表示、鏈表表示以及相應(yīng)操作的實(shí)隊(duì)列的

7、順序表示、鏈表表示以及相應(yīng)操作的實(shí)現(xiàn)。特別是循環(huán)隊(duì)列中隊(duì)頭與隊(duì)尾指針的變化情況及隊(duì)列現(xiàn)。特別是循環(huán)隊(duì)列中隊(duì)頭與隊(duì)尾指針的變化情況及隊(duì)列空和隊(duì)列滿的條件及元素的個(gè)數(shù)?？蘸完?duì)列滿的條件及元素的個(gè)數(shù)。循環(huán)隊(duì)列循環(huán)隊(duì)列空：空：front=rear滿：滿：(rear+1)%MAXN=front隊(duì)列的元素個(gè)數(shù)：隊(duì)列的元素個(gè)數(shù)：（rear-front+MAXN)%MAXN入隊(duì)入隊(duì):rear=(rear+1)%MAXN;datarear=x;出隊(duì)：出隊(duì)：front=(front+1)%MAXNreturn(datafront);第第4 4章章 串和數(shù)組串和數(shù)組1、掌握數(shù)組在以行（列）為主的存儲(chǔ)結(jié)構(gòu)中的地址計(jì)算

8、法；、掌握數(shù)組在以行（列）為主的存儲(chǔ)結(jié)構(gòu)中的地址計(jì)算法；2、掌握對(duì)特殊矩陣（主要是下三角）進(jìn)行壓縮存儲(chǔ)時(shí)的下標(biāo)變換、掌握對(duì)特殊矩陣（主要是下三角）進(jìn)行壓縮存儲(chǔ)時(shí)的下標(biāo)變換公式；公式；3、了解稀疏矩陣的三元組壓縮存儲(chǔ)方法、了解稀疏矩陣的三元組壓縮存儲(chǔ)方法4、理解串的基本操作的含義，并能利用這些基本操作來(lái)實(shí)現(xiàn)串的、理解串的基本操作的含義，并能利用這些基本操作來(lái)實(shí)現(xiàn)串的其它各種操作的方法。其它各種操作的方法?；疽螅夯疽螅?、了解樹(shù)和森林的概念。包括樹(shù)的定義、樹(shù)的術(shù)語(yǔ)；、了解樹(shù)和森林的概念。包括樹(shù)的定義、樹(shù)的術(shù)語(yǔ)；2、熟練掌握二叉樹(shù)的結(jié)構(gòu)特性，熟悉二叉樹(shù)的各種存儲(chǔ)結(jié)構(gòu)、熟練掌握二叉樹(shù)的結(jié)構(gòu)特性

9、，熟悉二叉樹(shù)的各種存儲(chǔ)結(jié)構(gòu)的特點(diǎn)和性質(zhì)；的特點(diǎn)和性質(zhì)；3、熟練掌握二叉樹(shù)的遍歷方法及遍歷算法和算法的應(yīng)用；、熟練掌握二叉樹(shù)的遍歷方法及遍歷算法和算法的應(yīng)用；4、了解樹(shù)的各種存儲(chǔ)結(jié)構(gòu)及其特點(diǎn)，掌握樹(shù)、森林與二叉樹(shù)、了解樹(shù)的各種存儲(chǔ)結(jié)構(gòu)及其特點(diǎn)，掌握樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換方法；的轉(zhuǎn)換方法；5、掌握建立哈夫曼樹(shù)和哈夫曼編碼的方法及帶權(quán)路徑長(zhǎng)度的、掌握建立哈夫曼樹(shù)和哈夫曼編碼的方法及帶權(quán)路徑長(zhǎng)度的計(jì)算計(jì)算.完全二叉樹(shù)、滿二叉樹(shù)完全二叉樹(shù)、滿二叉樹(shù)第第5章章樹(shù)樹(shù)基本要求基本要求1、理解圖的基本概念，熟悉圖的各種存儲(chǔ)結(jié)構(gòu)（鄰接、理解圖的基本概念，熟悉圖的各種存儲(chǔ)結(jié)構(gòu)（鄰接矩陣和鄰接表）；矩陣和鄰接表）；2

10、、熟練掌握?qǐng)D的兩種搜索路徑的遍歷；、熟練掌握?qǐng)D的兩種搜索路徑的遍歷；3、掌握構(gòu)造最小生成樹(shù)（、掌握構(gòu)造最小生成樹(shù)（prim算法）的方法，并理解算法）的方法，并理解克魯斯卡爾算法；克魯斯卡爾算法；4、理解求、理解求AOV網(wǎng)的拓?fù)渑判虻姆椒?；網(wǎng)的拓?fù)渑判虻姆椒ǎ?、掌握用、掌握用Dijkstra方法求解單源最短路徑問(wèn)題；方法求解單源最短路徑問(wèn)題；6、了解在、了解在AOE網(wǎng)中求關(guān)鍵路徑的方法。網(wǎng)中求關(guān)鍵路徑的方法。第第6章章圖圖基本要求基本要求1、熟練掌握順序表和有序表的查找算法及其性能分析、熟練掌握順序表和有序表的查找算法及其性能分析方法方法:順序查找、二分查找（判定樹(shù)）順序查找、二分查找（判定樹(shù)）2、熟練掌握哈希函數(shù)的構(gòu)造及解決沖突的方法（根據(jù)、熟練掌握哈希函數(shù)的構(gòu)造及解決沖突的方法（根據(jù)哈希函數(shù)構(gòu)造哈希表，并計(jì)算平均查找長(zhǎng)度）哈希函數(shù)構(gòu)造哈希表，并計(jì)算平均查找長(zhǎng)度）3、理解二叉排序樹(shù)的特點(diǎn)、創(chuàng)建和查找、理解二叉排序樹(shù)的特點(diǎn)、創(chuàng)建和查找第第7章章查找查找例：設(shè)哈希函數(shù)H(K)=k%13,給定鍵值序列為87,25,310,8,27,132,68,95,187,123,70,63,47 ，處理沖突的方法為線性探測(cè)再散列，試在018的散列地址空間中對(duì)該關(guān)鍵字序列構(gòu)造哈希表，并計(jì)算