【正文】 進(jìn)方法；[實現(xiàn)提示]可以用一個二維數(shù)組存儲迷宮圖，值為1或者0分別表示通路和不通； 搜索路徑可以參考樹的深度優(yōu)先和廣度優(yōu)先算法。（2）整個統(tǒng)計過程中只對小說文字掃描一遍以提高效率。出現(xiàn)位置所在行的行號可以用鏈表存儲。程序的輸出結(jié)果是每個詞的出現(xiàn)次數(shù)和出現(xiàn)位置所在行的行號，格式自行設(shè)計。文學(xué)研究助手[問題描述]文學(xué)研究人員需要統(tǒng)計某篇英文小說中某些形容詞的出現(xiàn)次數(shù)和位置。（2）顯示輸入序列和棧的變化過程。假設(shè)操作數(shù)是正整數(shù)，運(yùn)算符只含加減乘除等四種運(yùn)算符，界限符有左右括號和表達(dá)式起始、結(jié)束符“”，如：（7+15）*（2328/4）。[選作內(nèi)容]（1）求多個景點的最佳（最短）游覽路徑。要求能夠回答有關(guān)景點介紹、游覽路徑等問題。三．設(shè)計要求學(xué)生要發(fā)揮自主學(xué)習(xí)的能力，充分利用時間，安排好課設(shè)的時間計劃，并在課設(shè)過程中不斷檢測自己的計劃完成情況，及時的向教師匯報。要結(jié)構(gòu)清晰，重點函數(shù)的重點變量，重點功能部分要加上清晰的程序注釋。給出實現(xiàn)功能的一組或多組測試數(shù)據(jù)，程序調(diào)試后，將按照此測試數(shù)據(jù)進(jìn)行測試的結(jié)果列出來。學(xué)好數(shù)據(jù)結(jié)構(gòu)對掌握實際編程能力是很有幫助的?？偝煽冇善綍r成績和考試成績組成。條件允許可采用CAI、電子教案、幻燈片、參觀等進(jìn)行輔助教學(xué)。待填入哈希表的人名共有30個，取平均查找長度的上限為2。（二）實驗過程 編程實現(xiàn)實驗內(nèi)容（三）實驗教學(xué)基本要求通過實例，使學(xué)生熟悉圖的各種存儲結(jié)構(gòu)的特性，掌握如何應(yīng)用圖結(jié)構(gòu)解決具體問題。實驗后學(xué)生提交實驗報告。每門課恰好占一個學(xué)期。（四）實驗設(shè)備和材料 計算機(jī)。棧以順序結(jié)構(gòu)實現(xiàn)，隊列以鏈表結(jié)構(gòu)實現(xiàn)。（二）教學(xué)內(nèi)容 本章知識點：(理解)；(掌握)；(掌握)；(掌握)；(掌握)；（熟悉）；，外存讀/寫次數(shù)的計算方法(掌握)。（二）教學(xué)內(nèi)容 本章知識點：(掌握)； (掌握)；(掌握)。（三）重點與難點重點：圖的存儲結(jié)構(gòu)；圖的遍歷 難點：圖遍歷的算法；第八章動態(tài)存儲管理（一）目的要求了解邊界標(biāo)識法和伙伴系統(tǒng)；無用單元收集和緊縮；（二）教學(xué)內(nèi)容 本章知識點：（了解）；（了解）。（三）重點與難點 重點：二叉樹的概念、性質(zhì)；二叉樹的遍歷方式；構(gòu)造二叉排序樹。（二）教學(xué)內(nèi)容 本章知識點：(掌握)； (掌握)；，領(lǐng)會以三元組表示稀疏矩陣時進(jìn)行運(yùn)算采用的處理方法(掌握)；，學(xué)會廣義表的表頭，表尾分析方法(掌握)； (掌握)。難點：遞歸的編程實現(xiàn)；循環(huán)隊列和鏈隊列的基本運(yùn)算。難點：鏈?zhǔn)酱鎯Y(jié)構(gòu)及其常用算法；雙向循環(huán)鏈表。（三）重點與難點重點：數(shù)據(jù)結(jié)構(gòu)的定義；算法的描述方法。三、主要內(nèi)容、重點及深度本門課程共60學(xué)時，其中理論教學(xué)48學(xué)時，實驗教學(xué)12學(xué)時。包括樹的定義、樹的術(shù)語、樹的抽象數(shù)據(jù)類型掌握：二叉樹的概念、性質(zhì)及二叉樹的表示熟練掌握：二叉樹的遍歷方法掌握：線索化二叉樹的特性及尋找某結(jié)點的前驅(qū)和后繼的方法熟練掌握：堆的定義，堆的建立、堆的插入與刪除、堆的向上和向下調(diào)整等算法以及用來實現(xiàn)優(yōu)先級隊列的方法掌握：樹與森林的實現(xiàn)，重點在用二叉樹實現(xiàn)掌握：森林與二叉樹的轉(zhuǎn)換；樹的遍歷算法掌握：二叉樹的計數(shù)方法及從二叉樹遍歷結(jié)果得到二叉樹的方法掌握：霍夫曼樹的實現(xiàn)方法、構(gòu)造霍夫曼編碼的方法及帶權(quán)路徑長度的計算七、集合與搜索 5學(xué)時教學(xué)內(nèi)容：集合及其表示：集合基本概念；以集合為基礎(chǔ)的抽象數(shù)據(jù)類型；用位向量實現(xiàn)集合抽象據(jù)類型；用有序鏈表實現(xiàn)集合的抽象數(shù)據(jù)類型并查集：并查集的定義；并查集的實現(xiàn)簡單的搜索結(jié)構(gòu)：搜索的概念；靜態(tài)搜索結(jié)構(gòu)；順序搜索；基于有序順序表的順序搜索和折半搜索二叉搜索樹：二叉搜索樹的定義；二叉搜索樹上的搜索；二叉搜索樹的插入；二叉搜索樹的刪除AVL樹：AVL樹定義；平衡化旋轉(zhuǎn)；AVL樹的插入和刪除；AVL樹高度教學(xué)要求：掌握：集合的基本概念及其表示方法，包括位數(shù)組及有序鏈表的表示及其相關(guān)操作的實現(xiàn)算法掌握：利用并查集實現(xiàn)集合的方法熟練掌握：靜態(tài)搜索表的順序搜索和折半搜索算法及其性能分析方法熟練掌握：二叉搜索樹的表示、搜索、插入、刪除算法及其性能分析方法掌握：AVL樹的平衡化旋轉(zhuǎn)、構(gòu)造、插入、刪除時的調(diào)整方法及其性能分析八、圖 7學(xué)時教學(xué)內(nèi)容：圖的基本概念：圖的基本概念；圖的抽象數(shù)據(jù)類型圖的存儲表示：鄰接矩陣；鄰接表；鄰接多重表圖的遍歷與連通性：深度優(yōu)先搜索；廣度優(yōu)先搜索；連通分量；關(guān)節(jié)點與重連通分量最小生成樹：kruskul算法；prim算法單源最短路徑問題：dijkstra算法活動網(wǎng)絡(luò)：AOV網(wǎng)絡(luò)與拓?fù)渑判颍籄OE網(wǎng)絡(luò)與關(guān)鍵路徑教學(xué)要求：理解：圖的基本概念和圖的抽象數(shù)據(jù)類型掌握：圖的3種存儲表示：鄰接矩陣、鄰接表和鄰接多重表。四、棧和隊列 3學(xué)時教學(xué)內(nèi)容：棧：棧的抽象數(shù)據(jù)類型；棧的順序存儲表示；棧的鏈接存儲表示表達(dá)式求值：中綴表達(dá)式求值；中綴表示到后綴表示的轉(zhuǎn)換隊列 ：隊列的抽象數(shù)據(jù)類型；隊列的順序存儲表示；隊列的鏈接存儲表示；隊列的應(yīng)用舉例優(yōu)先級隊列：優(yōu)先級隊列的定義；優(yōu)先級隊列的存儲表示教學(xué)要求：熟練掌握：棧的定義、特性和棧的抽象數(shù)據(jù)類型，棧的順序表示、鏈表表示以及相應(yīng)操作的實現(xiàn)。課程考試具體規(guī)定請參看該課程考核說明?？荚嚳荚囀菍W(xué)生掌握知識水平的檢驗。要求學(xué)生珍惜實驗機(jī)時，真正做到學(xué)有所獲。教師講課只是起到拋磚引玉的作用，關(guān)鍵還在于學(xué)生的自學(xué)。各地方電大應(yīng)聘請有經(jīng)驗、認(rèn)真負(fù)責(zé)的教師任教，以習(xí)題課、專題討論或答疑的方式，對課程中的重要概念和典型問題的解決方法進(jìn)行總結(jié)和深入討論，鞏固和加深課堂內(nèi)學(xué)到的知識。第二部分 多種媒體教材一體化總體設(shè)計初步方案一、學(xué)時分配課程教學(xué)總學(xué)時數(shù)為 72學(xué)時，4學(xué)分，其中講授學(xué)時48，實驗24教 學(xué) 內(nèi) 容講授學(xué)時實驗學(xué)時一、數(shù)據(jù)結(jié)構(gòu)基本概念及算法分析3學(xué)時2學(xué)時二、數(shù)組3學(xué)時2學(xué)時三、鏈表3學(xué)時3學(xué)時四、棧和隊列3學(xué)時2學(xué)時五、遞歸3學(xué)時2學(xué)時六、樹與森林9學(xué)時4學(xué)時七、集合與搜索5學(xué)時2學(xué)時八、圖7學(xué)時4學(xué)時九、排序7學(xué)時3學(xué)時十、索引與散列結(jié)構(gòu)5學(xué)時二、教學(xué)環(huán)節(jié)電視教學(xué)本課程是計算機(jī)專業(yè)基礎(chǔ)課，內(nèi)容多且?guī)в幸欢ǖ某橄笮?，學(xué)習(xí)起來有一定難度。五、課程教學(xué)要求的層次熟練掌握：要求學(xué)生能夠全面、深入理解和熟練掌握所學(xué)內(nèi)容，并能夠用其知識分析、設(shè)計和解答相關(guān)的應(yīng)用問題。為后續(xù)計算機(jī)專業(yè)課程的學(xué)習(xí)打下堅實的基礎(chǔ)。第二篇：數(shù)據(jù)結(jié)構(gòu)教學(xué)大綱中央廣播電視大學(xué)“開放教育試點”計算機(jī)科學(xué)與技術(shù)專業(yè)（本科）《數(shù)據(jù)結(jié)構(gòu)》課程教學(xué)大綱第一部分 大綱說明一、課程的性質(zhì)和任務(wù)《數(shù)據(jù)結(jié)構(gòu)》是計算機(jī)科學(xué)與技術(shù)專業(yè)本科生的一門必修課程。重點：外部排序算法 難點：多路平衡歸并的實現(xiàn) 第11章 算法設(shè)計的一般方法（2學(xué)時）1．重點（1）有效算法的概念，問題固有難度的概念；（2）遞歸法；分治法；平衡原則；貪心法；動態(tài)規(guī)劃的基本原理；（3）．難點（1）問題固有難度的概念；（2）遞歸分治法的效率分析（寫出時間耗費(fèi)的遞推式，并求解）；（3）動態(tài)規(guī)劃法中的狀態(tài)轉(zhuǎn)移方程的確定。重點：各種算法的基本思想及實現(xiàn)。難點：圖的遍歷算法，最短路徑算法。難點：哈夫曼樹構(gòu)造的方法和算法第7章 圖（11學(xué)時） 圖的定義和術(shù)語 圖的存儲結(jié)構(gòu)（數(shù)組表示法，鄰接表，十字鏈表，鄰接多重表） 圖的遍歷（深度優(yōu)先搜索，廣度優(yōu)先搜索） 圖的連通性問題（無向圖的連通分量和生成樹，有向圖的強(qiáng)連通分量，最小生成樹，關(guān)節(jié)點和重連通分量） 有向無環(huán)圖及其應(yīng)用（拓?fù)渑判?，關(guān)鍵路徑） 最短路徑（從某個源點到其余各項點的最短路徑，每一對頂點之間的最短路徑）基本要求：了解：圖的基本概念和相關(guān)術(shù)語。第6章 樹與二叉樹（15學(xué)時） 樹的定義和基本術(shù)語 二叉樹（二叉樹的定義，二叉樹的性質(zhì)，二叉樹的存儲結(jié)構(gòu)） 遍歷二叉樹和線索二叉樹（遍歷二叉樹，線索二叉樹） 樹和森林（樹的存儲結(jié)構(gòu)，森林與二叉樹的轉(zhuǎn)換，樹和森林的遍歷） 樹與等價問題 赫夫曼樹及其應(yīng)用（最優(yōu)二叉樹（赫夫曼樹），赫夫曼編碼） 回溯法與樹的遍歷 樹的計數(shù)基本要求：了解：理解樹與森林的定義與術(shù)語。也可以采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。重點：主要操作和運(yùn)算。重點： 棧和隊列的算法實現(xiàn)。第3章 棧與隊列（4學(xué)時） 棧（定義，棧的表示和實現(xiàn)） 棧的應(yīng)用舉例（數(shù)制轉(zhuǎn)換，括號匹配的檢驗，行編輯程序，迷宮求解，表達(dá)式求值） 棧與遞歸的實現(xiàn) 隊列及其實現(xiàn)（定義，鏈隊列，循環(huán)隊列） *離散事件模擬教學(xué)要求：熟練掌握棧和隊列的特性和在不同存儲結(jié)構(gòu)前提下的算法實現(xiàn)。掌握：要求熟練掌握處理線性表的各種算法。本課程以提高學(xué)生的計算機(jī)應(yīng)用能力和綜合素質(zhì)為目標(biāo)，通過課程教學(xué)，為學(xué)生構(gòu)建數(shù)據(jù)結(jié)構(gòu)與算法方面的知識體系，使學(xué)生一方面能夠根據(jù)問題選擇合適的數(shù)據(jù)結(jié)構(gòu)，設(shè)計高效的算法，提高程序設(shè)計能力，另一方面，在工程應(yīng)用中，具有甄別好算法的能力，也就是要從建模、解模和綜合等三個方面，提高學(xué)生的程序設(shè)計能力。通過本課程的教學(xué)，使學(xué)生知道求解非數(shù)值類問題的基本模型（表、樹、圖），模型的特點和適用場合，能夠根據(jù)問題設(shè)計和選擇好的算法，為學(xué)習(xí)后續(xù)的操作系統(tǒng)、編譯原理和軟件工程等專業(yè)課程，設(shè)計應(yīng)用程序打下基礎(chǔ)。第2章 線性表（8學(xué)時） 線性表的類型定義 線性表的順序表示和實現(xiàn) 線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)（線性鏈表，循環(huán)鏈表，雙向鏈表） 一元多項式的表示及相加基本要求：了解：兩種存儲結(jié)構(gòu)（順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)）及一元多項式的表示及相加。難點：鏈表的理解。掌握： 熟練掌握棧和隊列的特性和在不同存儲結(jié)構(gòu)前提下的算法實現(xiàn)。掌握：掌握串的基本概念和運(yùn)算。認(rèn)識到數(shù)組可以作為順序存儲結(jié)構(gòu)用于順序表、字符串和稀疏矩陣的實現(xiàn)。難點：廣義表的遞歸算法。重點： 樹的存儲結(jié)構(gòu)和遍歷算法。重點：圖的兩種主要存儲結(jié)構(gòu)及遍歷算法。掌握哈希表查找算法。掌握：基本掌握外排算法的基本思想，不同排序方法的比較。由于本課程內(nèi)容較多，在實際教學(xué)中可根據(jù)大綱內(nèi)容，進(jìn)行適當(dāng)調(diào)整。課程采用面向?qū)ο蟮挠^點討論數(shù)據(jù)結(jié)構(gòu)技術(shù)，并以兼有面向過程和面向?qū)ο箅p重特色的C++語言作為算法的描述工具，強(qiáng)化數(shù)據(jù)結(jié)構(gòu)基本知識和面向?qū)ο蟪绦蛟O(shè)計基本能力的雙基訓(xùn)練。四、教學(xué)方法和教學(xué)形式建議電視授課為主，結(jié)合面授輔導(dǎo)、面授或電子郵件答疑，進(jìn)行必要的上機(jī)實驗。六、課程實驗實驗內(nèi)容和要求由省級電大作出具體規(guī)定，從2004年春開始按該課程實驗教材規(guī)定進(jìn)行。面授輔導(dǎo)或答疑本課程教學(xué)過程中，面授輔導(dǎo)和答疑是必不可少的教學(xué)環(huán)節(jié)。自學(xué)與練習(xí)自學(xué)是獲取知識的重要手段。為此，安排一定的實驗上機(jī)學(xué)時。除學(xué)校提供的時間外，要求課外學(xué)生利用自己可能擁有的計算機(jī)條件，完成更多的練習(xí)，不通過大量的實踐，能力和知識水平得不到有效得提高。因此，不要出難題、怪題，但也不要過于簡單，適當(dāng)有一些編程題。有動態(tài)鏈表和靜態(tài)鏈表之分了解：鏈表有單鏈表、循環(huán)單鏈表、雙向鏈表之分了解：單鏈表的結(jié)構(gòu)、特點掌握：單鏈表的類定義、構(gòu)造函數(shù)、單鏈表的插入與刪除算法了解：帶表頭結(jié)點的單鏈表的優(yōu)點和類定義及相應(yīng)操作的實現(xiàn)熟練掌握：用模板定義的單鏈表類了解：循環(huán)鏈表的特點，循環(huán)鏈表的類定義，以及用循環(huán)鏈表解決問題的方法掌握：雙向鏈表的特點，雙向鏈表的類定義及相關(guān)操作的實現(xiàn)，用雙向鏈表解決問題的方法。包括什么是遞歸，有那些種類的遞歸，遞歸問題的遞歸求解方法掌握：遞歸過程的機(jī)制與利用遞歸工作棧實現(xiàn)遞歸的方法了解：迷宮問題的遞歸求解思路及如何利用棧實現(xiàn)迷宮問題的非遞歸解法掌握：利用遞歸解決問題的分治法和回溯法掌握：廣義表的定義及其實現(xiàn)方法掌握：廣義表的遞歸算法六、樹與森林 9學(xué)時教學(xué)內(nèi)容：樹和森林的概念：樹的定義；樹的術(shù)語；樹的抽象數(shù)據(jù)類型二叉樹：二叉樹的定義；二叉樹的性質(zhì)；二叉樹的抽象數(shù)據(jù)類