數(shù)據(jù)結(jié)構(gòu)課程各章的重點(diǎn)及要點(diǎn)

1、1《《數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)》》考試大綱考試大綱考試大綱考試大綱一、一、一、一、考試大綱的性質(zhì)考試大綱的性質(zhì)數(shù)據(jù)結(jié)構(gòu)是報(bào)考我校軟件工程、計(jì)算機(jī)技術(shù)專業(yè)學(xué)位碩士的考試科目。為幫助考生明確考試復(fù)習(xí)范圍和有關(guān)要求，特制定本考試大綱。二、考試范圍和內(nèi)容二、考試范圍和內(nèi)容二、考試范圍和內(nèi)容二、考試范圍和內(nèi)容1.1.數(shù)據(jù)結(jié)構(gòu)基本概念數(shù)據(jù)結(jié)構(gòu)基本概念(1)數(shù)據(jù)結(jié)構(gòu)的基本概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)的邏輯結(jié)構(gòu)、物理結(jié)構(gòu)、算法等。(2)

2、算法時(shí)間復(fù)雜度和空間復(fù)雜度的分析方法。2.2.線性表線性表(1)線性表的定義。(2)線性表的順序存儲(chǔ)結(jié)構(gòu)和主要算法實(shí)現(xiàn)，如查找、插入和刪除算法。(3)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)和主要算法實(shí)現(xiàn)，如查找、插入和刪除算法。(4)循環(huán)鏈表、雙向鏈表的特點(diǎn)。(5)從時(shí)間和空間復(fù)雜度的角度比較兩種存儲(chǔ)結(jié)構(gòu)的不同特點(diǎn)及其適用場(chǎng)合。(6)線性表的應(yīng)用，如線性表的合并算法。3.3.棧和隊(duì)列棧和隊(duì)列(1)棧的定義及特點(diǎn)，棧的順序存儲(chǔ)和鏈接存儲(chǔ)結(jié)構(gòu)，進(jìn)棧出棧算法，

3、順序棧棧滿和?？盏臈l件。(2)棧的應(yīng)用，如表達(dá)式求值算法，借助棧深入理解遞歸算法。(3)隊(duì)列的定義及特點(diǎn)，隊(duì)列的順序存儲(chǔ)(循環(huán)隊(duì))和鏈接存儲(chǔ)結(jié)構(gòu)，進(jìn)隊(duì)出隊(duì)算法，循環(huán)隊(duì)列中隊(duì)滿及隊(duì)空的條件。4.4.串和數(shù)組串和數(shù)組(1)串的定義。(2)串的古典模式匹配算法。(3)數(shù)組地址的計(jì)算方法。(4)特殊矩陣的壓縮存儲(chǔ)方法。5.5.樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)(1)二叉樹(shù)的定義和性質(zhì)。(2)二叉樹(shù)的兩種存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。(3)二叉樹(shù)的創(chuàng)建和三種不

4、同遍歷算法，利用遍歷算法實(shí)現(xiàn)二叉樹(shù)的其他操作，如計(jì)算二叉樹(shù)結(jié)點(diǎn)個(gè)數(shù)、葉子結(jié)點(diǎn)個(gè)數(shù)、二叉樹(shù)的高度等算法。(4)線索二叉樹(shù)的特性及構(gòu)造方法。(5)樹(shù)和森林的定義、存儲(chǔ)結(jié)構(gòu)與二叉樹(shù)的轉(zhuǎn)換方法。(6)樹(shù)的應(yīng)用，哈夫曼樹(shù)及哈夫曼編碼的構(gòu)造算法、帶權(quán)路徑長(zhǎng)度的計(jì)算。6.6.圖(1)圖的定義和性質(zhì)。(2)圖的兩種存儲(chǔ)結(jié)構(gòu)：鄰接矩陣和鄰接表。(3)圖的兩種遍歷策略：深度優(yōu)先搜索算法和廣度優(yōu)先搜索算法。(4)圖的基本應(yīng)用，包括拓?fù)渑判蛩惴?、求解最短路徑?/p>

5、迪杰斯特拉算法、構(gòu)造最小2生成樹(shù)的兩種算法（普里姆算法和克魯斯卡爾算法）。7.7.查找查找(1)線性表的查找：順序查找和折半查找算法。(2)樹(shù)表的查找：二叉排序樹(shù)的定義，二叉排序樹(shù)的創(chuàng)建、插入、刪除和查找算法。(3)散列表的查找：兩種處理沖突的方法包括開(kāi)放地址法（線性探測(cè)法、二次探測(cè)法）和鏈地址法。(4)上述三種不同查找算法的分析，平均查找長(zhǎng)度ASL的計(jì)算方法及時(shí)間復(fù)雜度分析，不同查找算法的適用場(chǎng)合。8.8.排序排序(1)排序的基本概念

6、。(2)插入排序：直接插入排序、折半插入排序和希爾排序。(3)交換排序：冒泡排序和快速排序。(4)選擇排序：簡(jiǎn)單選擇排序和堆排序。(5)歸并排序：2路歸并排序。(6)上述各種排序方法的特點(diǎn)和排序過(guò)程，時(shí)間和空間復(fù)雜度的分析，排序方法“穩(wěn)定”或“不穩(wěn)定”的含義。排序算法的實(shí)現(xiàn)及適用場(chǎng)合。三、考試方式和時(shí)間三、考試方式和時(shí)間三、考試方式和時(shí)間三、考試方式和時(shí)間考試方式：閉卷筆試?？荚嚂r(shí)間：180分鐘。試卷滿分：150分。考試主要題型：選擇題