數(shù)據(jù)結(jié)構(gòu)教學(xué)清華大綱

1、計(jì)算機(jī)科學(xué)與技術(shù)系（本科）數(shù)據(jù)結(jié)構(gòu)課程教學(xué)大綱第一部分大綱說明一、課程的性質(zhì)和任務(wù)數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)本科生的一門必修課程。本課程介紹如何組織各種數(shù)據(jù)在計(jì)算機(jī)中的、傳遞和轉(zhuǎn)換。內(nèi)容包括：數(shù)組、表、棧和隊(duì)列、遞歸、樹與森林、圖、堆與優(yōu)先級(jí)隊(duì)列、集合與搜索結(jié)構(gòu)、排序、索引與散列結(jié)構(gòu)等。課程采用面象的觀點(diǎn)數(shù)據(jù)結(jié)構(gòu)技術(shù)，并以兼有面向過面識(shí)和面象雙重特色的 ) 語言作為算法的描述工具，強(qiáng)化數(shù)據(jù)結(jié)構(gòu)基本知象程序設(shè)計(jì)基本能力的雙基訓(xùn)練。為后續(xù)計(jì)算機(jī)專業(yè)課程的學(xué)習(xí)打下堅(jiān)實(shí)的基礎(chǔ)。二、先修課要求面象程序設(shè)計(jì)、計(jì)算機(jī)數(shù)學(xué) 離散數(shù)學(xué) 。三、課程的教學(xué)基本要求1、掌握重要數(shù)據(jù)結(jié)構(gòu)的概念、使用方法及實(shí)現(xiàn)技術(shù)；

2、2、學(xué)會(huì)做簡(jiǎn)單的算法分析，包括算法的時(shí)間代價(jià)和空間代價(jià)。、教學(xué)方法和教學(xué)形式建議面授為主，結(jié)合面授輔導(dǎo)、電子郵件答疑，進(jìn)行必要的上機(jī)實(shí)驗(yàn)。五、課程教學(xué)要求的層次1、熟練掌握：要求學(xué)生能夠全面、深入理解和熟練掌握所學(xué)內(nèi)容，并能夠用其知識(shí)分析、設(shè)計(jì)和解答相關(guān)的應(yīng)用問題。2、掌握：要求學(xué)生能夠較好地理解和掌握，并且能夠做簡(jiǎn)單的分析。3、了解：要求學(xué)生能夠一般地了解的所學(xué)內(nèi)容。四第二部分多種總體設(shè)計(jì)初步方案一、學(xué)時(shí)分配課程教學(xué)總學(xué)時(shí)數(shù)為96 學(xué)時(shí)，4 學(xué)分，其中講授學(xué)時(shí) 64，實(shí)驗(yàn) 32二、教學(xué)環(huán)節(jié)1、面授教學(xué)本課程是計(jì)算機(jī)專業(yè)基礎(chǔ)課，內(nèi)容多且?guī)в幸欢ǖ某橄笮?，學(xué)習(xí)起來有一定難度。為保證教學(xué)效果，采取

3、教師授課方式，盡可能利用多種學(xué)生能夠很快掌握課程的主要知識(shí)和解決問題的方法。2、面授輔導(dǎo)或答疑進(jìn)行教學(xué)，使本課程教學(xué)過程中，面授輔導(dǎo)和答疑是必不可少的教學(xué)環(huán)節(jié)。由專任助教任教，以習(xí)題課、專題方法進(jìn)行總結(jié)和深入或答疑的方式，對(duì)課程中的重要概念和典型問題的解決，鞏固和加深課堂內(nèi)學(xué)到的知識(shí)。必要時(shí)可采用電子郵件方式直接與教師聯(lián)系進(jìn)行答疑。3、與練習(xí)是獲取知識(shí)的重要。教師講課只是起到拋磚引玉的作用，關(guān)鍵還在于學(xué)生的。為達(dá)到的效果，除讀懂教科書中所講內(nèi)容外，還需大量做題。其目的是要通過做題弄懂、加深對(duì)概念的理解，提高程序設(shè)計(jì)，解決問題的能力。為此，安排一定的實(shí)驗(yàn)上機(jī)學(xué)時(shí)。要求學(xué)生珍惜實(shí)驗(yàn)機(jī)時(shí)，真正做到學(xué)

4、有所獲。學(xué)生在上機(jī)做實(shí)驗(yàn)前，應(yīng)事先將程序、調(diào)試數(shù)據(jù)、上機(jī)操作順序準(zhǔn)備好，并教學(xué)內(nèi)容講授學(xué)時(shí)一、數(shù)據(jù)結(jié)構(gòu)基本概念及算法分析4 學(xué)時(shí)二、數(shù)組4 學(xué)時(shí)三、鏈表4 學(xué)時(shí)四、棧和隊(duì)列4 學(xué)時(shí)五、遞歸4 學(xué)時(shí)六、樹與森林12 學(xué)時(shí)七、集合與搜索6 學(xué)時(shí)八、圖10 學(xué)時(shí)九、排序10 學(xué)時(shí)十、索引與散列結(jié)構(gòu)6 學(xué)時(shí)提前使用這些調(diào)試數(shù)據(jù)人工執(zhí)行過。目的是提高上機(jī)的效率和成功率，嚴(yán)禁或拷貝他人的成果，自覺培養(yǎng)科學(xué)、嚴(yán)謹(jǐn)?shù)淖黠L(fēng)。除學(xué)校提供的時(shí)間外，要求課外學(xué)生利用自己可能擁有的計(jì)算機(jī)條件，完成的練習(xí)，不通過大量的實(shí)踐，能力和知識(shí)水平得不到有效得提高。4、是對(duì)學(xué)生掌握知識(shí)水平的檢驗(yàn)。本著多練多考的原則，各地方電大可以

5、再平時(shí)多做一些小考。要求內(nèi)容緊扣大綱要求，既要能夠檢驗(yàn)學(xué)生的掌握情況，又要體現(xiàn)水平。因此，不要出難題、怪題，但也不要過于簡(jiǎn)單，適當(dāng)有一些編程題。學(xué)生的本課程成績(jī)按平時(shí)作業(yè)滿分 30 分，期中分 50 分分配，合計(jì)計(jì)算。滿分 20 分，期末滿第三部分教學(xué)內(nèi)容和教學(xué)要求第一章 數(shù)據(jù)結(jié)構(gòu)基本概念及簡(jiǎn)單的算法分析1、教學(xué)內(nèi)容：數(shù)據(jù)結(jié)構(gòu)抽象數(shù)據(jù)類型及面象概念：數(shù)據(jù)類型；數(shù)據(jù)抽象與抽象數(shù)據(jù)類型；面向?qū)ο蟮母拍?；用于描述?shù)據(jù)結(jié)構(gòu)的語言數(shù)據(jù)結(jié)構(gòu)的抽象層次算法定義性能分析與度量：算法的性能標(biāo)準(zhǔn)；算法的后期測(cè)試；算法的事前估計(jì)；空間復(fù)雜度度量；時(shí)間復(fù)雜度度量；時(shí)間復(fù)雜度的漸進(jìn)表示法；漸進(jìn)的空間復(fù)雜度2、教學(xué)要求：

6、了解：數(shù)據(jù)、數(shù)據(jù)對(duì)象、數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)的邏輯結(jié)構(gòu)與物理結(jié)構(gòu)、邏輯結(jié)構(gòu)與物理結(jié)構(gòu)間的關(guān)系了解：么是面數(shù)據(jù)類型、抽象數(shù)據(jù)類型、數(shù)據(jù)抽象和信息隱蔽原則。了解什象了解：算法的定義、算法的特性、算法的時(shí)間代價(jià)、算法的空間代價(jià)掌握：用 C+語言描述算法的方法，能夠使用 C+語言編寫程序第二章 數(shù)組1、教學(xué)內(nèi)容：作為抽象數(shù)據(jù)類型的數(shù)組：數(shù)組的定義和初始化；作為抽象數(shù)據(jù)類型的數(shù)組；數(shù)組的順序方式順序表：順序表的定義和特點(diǎn)；順序表的類定義；順序表的查找、除；使用順序表的事例和刪字符串：字符串的抽象數(shù)據(jù)類型；字符串操作的實(shí)現(xiàn)；字符串的模式匹配2、教學(xué)要求：了解：線性表的邏輯結(jié)構(gòu)特性，以及線性表的兩種實(shí)現(xiàn)方

7、式了解：作為抽象數(shù)據(jù)類型的數(shù)組的定義，數(shù)組的按行順序與按列順序存儲(chǔ)熟練掌握：順序表的定義與實(shí)現(xiàn)，包括搜索、刪除算法的實(shí)現(xiàn)及其平均比較次數(shù)的計(jì)算，掌握應(yīng)用順序表作為集合的簡(jiǎn)單操作了解：稀疏矩陣的定義及其數(shù)組實(shí)現(xiàn)熟練掌握：字符串的定義及實(shí)現(xiàn)第三章 鏈表1、教學(xué)內(nèi)容：?jiǎn)捂湵恚簡(jiǎn)捂湵淼慕Y(jié)構(gòu)；單鏈表的類定義；單鏈表中的結(jié)點(diǎn)的單鏈表；用模板定義的單鏈表類；靜態(tài)鏈表與刪除；帶表頭循環(huán)鏈表：循環(huán)鏈表的類定義；用循環(huán)鏈表解多項(xiàng)式及其相加：多項(xiàng)式的類定義；多項(xiàng)式的加法雙向鏈表2、教學(xué)要求：?jiǎn)栴}；了解：鏈表與數(shù)組一樣，是一種實(shí)現(xiàn)級(jí)結(jié)構(gòu)。有動(dòng)態(tài)鏈表和靜態(tài)鏈表之分了解：鏈表有單鏈表、循環(huán)單鏈表、雙向鏈表之分了解：?jiǎn)捂湵?/p>

8、的結(jié)構(gòu)、特點(diǎn)掌握：?jiǎn)捂湵淼念惗x、構(gòu)造函數(shù)、單鏈表的與刪除算法了解：帶表頭結(jié)點(diǎn)的單鏈表的優(yōu)點(diǎn)和類定義及相應(yīng)操作的實(shí)現(xiàn)熟練掌握：用模板定義的單鏈表類了解：循環(huán)鏈表的特點(diǎn)，循環(huán)鏈表的類定義，以及用循環(huán)鏈表解決問題的方法掌握：雙向鏈表的特點(diǎn)，雙向鏈表的類定義及相關(guān)操作的實(shí)現(xiàn)，解決問題的方法。向鏈表第四章棧和隊(duì)列1、教學(xué)內(nèi)容：棧：棧的抽象數(shù)據(jù)類型；棧的順序表示；棧的表示表達(dá)式求值：中綴表達(dá)式求值；中綴表示到后綴表示的轉(zhuǎn)換隊(duì)列 ：隊(duì)列的抽象數(shù)據(jù)類型；隊(duì)列的順序隊(duì)列的應(yīng)用舉例表示；隊(duì)列的表示；優(yōu)先級(jí)隊(duì)列：優(yōu)先級(jí)隊(duì)列的定義；優(yōu)先級(jí)隊(duì)列的2、教學(xué)要求：表示熟練掌握：棧的定義、特性和棧的抽象數(shù)據(jù)類型，棧的順序表

9、示、鏈表表示以及相應(yīng)操作的實(shí)現(xiàn)。特別注意棧空和棧滿的條件了解：在表達(dá)式計(jì)算時(shí)棧是如何使用的，重點(diǎn)了解用后綴表示計(jì)算表達(dá)式及中綴表示改后綴表示的方法和算法思路熟練掌握：隊(duì)列的定義、特性和隊(duì)列的抽象數(shù)據(jù)類型，隊(duì)列的順序表示、鏈表表示以及相應(yīng)操作的實(shí)現(xiàn)。特別是循環(huán)隊(duì)列中隊(duì)頭與隊(duì)尾指針的變化情況掌握：優(yōu)先級(jí)隊(duì)列的定義、特性和優(yōu)先級(jí)隊(duì)列的抽象數(shù)據(jù)類型，優(yōu)先級(jí)隊(duì)列的與刪除算法第五章 遞歸與廣義表1、教學(xué)內(nèi)容：遞歸的概念：遞歸問題的求解遞歸過程與遞歸工作棧：?jiǎn)蜗蜻f歸和尾遞歸的迭代實(shí)現(xiàn)；一般遞歸問題利用棧實(shí)現(xiàn)非遞歸解法廣義表：廣義表的概念；廣義表的表示及操作；廣義表結(jié)構(gòu)的實(shí)現(xiàn)；廣義表的算法；廣義表的遞歸算法2

10、、教學(xué)要求：掌握：遞歸的概念。包括求解方法遞歸，有那些種類的遞歸，遞歸問題的遞歸掌握：遞歸過程的機(jī)制與利用遞歸工作棧實(shí)現(xiàn)遞歸的方法了解：迷宮問題的遞歸求解思路及如何利用棧實(shí)現(xiàn)迷宮問題的非遞歸解法掌握：利用遞歸解決問題的分治法和回溯法掌握：廣義表的定義及其實(shí)現(xiàn)方法掌握：廣義表的遞歸算法第六章 樹與森林1、教學(xué)內(nèi)容：樹和森林的概念：樹的定義；樹的術(shù)語；樹的抽象數(shù)據(jù)類型二叉樹：二叉樹的定義；二叉樹的性質(zhì)；二叉樹的抽象數(shù)據(jù)類型二叉樹的表示：順序表示；二叉鏈表表示遍歷二叉樹：中序遍歷；前序遍歷；后序遍歷；應(yīng)用二叉樹遍歷的事例；二叉樹的計(jì)數(shù)線索化二叉樹：線索；中序線索化二叉樹堆：堆的定義；堆的建立；堆的與

11、刪除；堆的調(diào)整算法樹與森林：樹的表示；森林與二叉樹的轉(zhuǎn)換；遍歷樹；遍歷森林樹：路徑長(zhǎng)度；2、教學(xué)要求：樹；編碼了解：樹和森林的概念。包括樹的定義、樹的術(shù)語、樹的抽象數(shù)據(jù)類型掌握：二叉樹的概念、性質(zhì)及二叉樹的表示熟練掌握：二叉樹的遍歷方法及樹的游標(biāo)類定義掌握：線索化二叉樹的特性及尋找某結(jié)點(diǎn)的前驅(qū)和后繼的方法熟練掌握：堆的定義，堆的建立、堆的算法以及用來實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列的方法與刪除、堆的向上和向下調(diào)整等掌握：樹與森林的實(shí)現(xiàn)，重點(diǎn)在用二叉樹實(shí)現(xiàn)掌握：森林與二叉樹的轉(zhuǎn)換；樹的遍歷算法掌握：二叉樹的計(jì)數(shù)方法及從二叉樹遍歷結(jié)果得到二叉樹的方法掌握：樹的實(shí)現(xiàn)方法、構(gòu)造編碼的方法及帶權(quán)路徑長(zhǎng)度的計(jì)算第七章 集合

12、與搜索1、教學(xué)內(nèi)容：集合及其表示：集合基本概念；以集合為基礎(chǔ)的抽象數(shù)據(jù)類型；用位向量實(shí)現(xiàn)集合抽象據(jù)類型；用有序鏈表實(shí)現(xiàn)集合的抽象數(shù)據(jù)類型并查集：并查集的定義；并查集的實(shí)現(xiàn)簡(jiǎn)單的搜索結(jié)構(gòu)：搜索的概念；靜態(tài)搜索結(jié)構(gòu)；順序搜索；基于有序順序表的順序搜索和折半搜索二叉搜索樹：二叉搜索樹的定義；二叉搜索樹上的搜索；二叉搜索樹的二叉搜索樹的刪除；AVL 樹：AVL 樹定義；平衡化旋轉(zhuǎn)；AVL 樹的和刪除；AVL 樹高度2、教學(xué)要求：掌握：集合的基本概念及其表示方法，包括位數(shù)組及有序鏈表的表示及其相關(guān)操作的實(shí)現(xiàn)算法掌握：利用并查集實(shí)現(xiàn)集合的方法熟練掌握：靜態(tài)搜索表的順序搜索和折半搜索算法及其性能分析方法熟練

13、掌握：二叉搜索樹的表示、搜索、刪除算法及其性能分析方法掌握：AVL 樹的平衡化旋轉(zhuǎn)、構(gòu)造、刪除時(shí)的調(diào)整方法及其性能分析第八章 圖1、教學(xué)內(nèi)容：圖的基本概念：圖的基本概念；圖的抽象數(shù)據(jù)類型圖的表示：鄰接矩陣；鄰接表；鄰接多重表圖的遍歷與連通性：深度優(yōu)先搜索；廣度優(yōu)先搜索；連通分量；關(guān)節(jié)點(diǎn)與重連通分量最小生成樹：kruskul 算法；prim 算法單源最短路徑問題：dijkstra 算法活動(dòng)網(wǎng)絡(luò)：AOV 網(wǎng)絡(luò)與拓?fù)渑判?；AOE 網(wǎng)絡(luò)與關(guān)鍵路徑2、教學(xué)要求：理解：圖的基本概念和圖的抽象數(shù)據(jù)類型掌握：圖的 3 種表示：鄰接矩陣、鄰接表和鄰接多重表。對(duì)于前兩種，要求掌握典型操作，如構(gòu)造、求根、找第一個(gè)鄰

14、接頂點(diǎn)、找下一個(gè)鄰接頂點(diǎn)等操作的實(shí)現(xiàn)算法熟練掌握：圖的兩種遍歷算法與求解連通性問題的方法。包括深度優(yōu)先搜索和廣度優(yōu)先搜索算法、求連通分量的方法(不要求算法)理解：求解關(guān)節(jié)點(diǎn)及構(gòu)造重連通圖的方法(不要求算法)掌握：構(gòu)造最小生成樹的Prim 算法和Kruskal 算法，要求理解算法理解：如何用 Dijkstra 方法求解單源最短路徑問題(不要求算法)熟練掌握：活動(dòng)網(wǎng)絡(luò)的拓?fù)渑判蛩惴ㄕ莆眨呵蠼怅P(guān)鍵路徑的方法第九章 排序1、教學(xué)內(nèi)容：概述排序：直接排序；折半排序；鏈表排序；排序交換排序：起泡排序；快速排序選擇排序：直接選擇排序；錦標(biāo)賽排序；堆排序歸并排序：歸并；迭代的歸并排序算法；遞歸的鏈表歸并排序基數(shù)排序：多關(guān)鍵碼排序；鏈?zhǔn)交鶖?shù)排序外排序：外排序的基本過程；k 路平衡歸并；初始?xì)w并段的生成；最佳歸并樹2、教學(xué)要求：掌握：排序的基本概念和性能分析方法掌握：分析方法排序、交換排序、選擇排序、歸并排序等內(nèi)排序的方法及其性能了解：基數(shù)排序方法及其性能分析方法掌握：多路平衡歸并等外排序方法及敗者樹構(gòu)造方法掌握：生成初始?xì)w并段及敗者樹構(gòu)造方法掌握：最佳歸并