【正文】 （三）重點與難點 存儲器分配策略和算法、無用單元收集時的標志算法 第九章 查找 （一）目的要求 了解靜態(tài)查找 表 (順序表，有序表，索引順序表 )；動態(tài)查找表 (二叉排序樹，平衡二叉樹， B樹和 B+樹 )的建立和查找；掌握哈希表的建立，查找及分析； （二）教學內(nèi)容 本章知識點： 、折半查找和索引查找的方法、應(yīng)用 (掌握 )； (掌握 )； (掌握 )； ， B+樹和鍵樹的特點以及它們的建立過程（理解）； (掌握 )； ； (掌握 )。 （二）教學內(nèi)容 本章知識點： ； (掌握 )； (掌握 )； （比如，最小生成樹、最短路徑、拓撲排序、關(guān)鍵路徑等） (掌握 )。難點：二叉樹的遍歷方式；二叉排序樹的構(gòu)造方法；二叉樹的線索化。 第六章 樹和二叉樹 （一）目的要求 了解樹的基本概念；理解二叉樹的性質(zhì)和存儲結(jié)構(gòu)；遍歷二叉樹和線索二叉樹；理解樹的存儲結(jié)構(gòu)和遍歷；集合的一種表示方法；掌握哈夫曼樹及其應(yīng)用； （二）教學內(nèi)容 本章知識點： (理解 )； (掌握 )； (掌握 )； ，在中序線索樹上找給定結(jié)點的前驅(qū)和后繼的方法 (掌握 )； 結(jié)構(gòu)及其特點 (掌握 )； (掌握 )； (掌握 )。 （三）重點與難點 重點：多維數(shù)組元素存儲地址的計算；稀疏矩陣的三元組表示 ；廣義表的存儲定義、操作。 （三）重點與難點 重點：串定義和存儲方法；串的操作 難點：串操作實現(xiàn)方法 第五章 數(shù)組和廣義表 （一）目的要求 掌握數(shù)組的存儲結(jié)構(gòu)；稀疏矩陣的表示及操作的實現(xiàn)；廣義表的定義和存儲結(jié)構(gòu)；廣義表的遞歸算法。 第四章 串 （一）目的要求 了解串的邏輯結(jié)構(gòu)，存儲結(jié)構(gòu)；掌握串操作的實現(xiàn) (重點難點 BF 和 KMP算法 )串的應(yīng)用。 （三）重點與難點 重點：堆棧和隊列的概念；遞歸的定義；循環(huán)隊列和鏈隊列的基本運算。 第三章 棧和隊列 （一）目的要求 掌握棧的定義，表示及實現(xiàn)；表達式求值；棧與遞歸過程；隊列的定義、表示及實現(xiàn)。 （三）重點與難點 重點：線性表的概念；線性表的順序存儲結(jié)構(gòu)、鏈式存儲結(jié)構(gòu)及其常用算法。 難點：數(shù)據(jù)結(jié)構(gòu)的定義；算法與程序的區(qū)別；時間復雜度及其計算。 （二）教學內(nèi)容 本章知識點： (掌握 )； (掌握 )； （掌握）。其中，理論教學部分： 第一章 緒論 （一）目的要求 了解數(shù)據(jù)結(jié)構(gòu)的意義與發(fā)展過程、數(shù)據(jù)結(jié)構(gòu)在計算機科學中的作用、學習本課程的目的、任務(wù)及要求。通過課堂教學、課外練習和上機實習，使學生了解數(shù)據(jù)對象的特性，數(shù)據(jù)組織的基本方法，并初步具備分析和解決現(xiàn)實世界問題在計算機中如何表示和處理的能力以及培養(yǎng)良好的程序設(shè)計技能，為后續(xù)課程的學習和科研工作的參與打下良好的基礎(chǔ)。各部分分配比例為： 期末考試成績70%，平時作業(yè)及考勤 10%，實驗占 10%，自主設(shè)計作品或期中考核 10%。 該實踐項目主要占用課外時間進行，可由任課教師根據(jù)授課情況和學生的要求決定是否開展此項活動或部分開展此項活動。實踐目的及要求： 在各個章節(jié)的基本編程訓練的基礎(chǔ)上，再結(jié)合課程重點和難點進行較大軟件編制的選題，并在具體題目上提倡與實際應(yīng)用相結(jié)合并由學生自主選題，教師審核。利用一些表現(xiàn)力強的平臺，以動畫形式展現(xiàn)數(shù)據(jù)結(jié)構(gòu)原理，需要學生自學 Flash、 Powerpoint、 網(wǎng)頁制作等，通過自主學習、查閱和收集所需的知識點完成。 說明：實驗報告的要求：見《數(shù)據(jù)結(jié)構(gòu)實驗報告模板》。 要求編寫完整程序，調(diào)試，程序執(zhí)行的輸出結(jié)果要求至少包含輸入數(shù)據(jù)和運行結(jié)果，最好能體現(xiàn) 運行過程。 6．給出一組 3 位整數(shù)，實現(xiàn)基數(shù)排序算法，并對這組數(shù)據(jù)進行排序。 4．給出一組數(shù)據(jù)，實現(xiàn)堆排序算法，并對這組數(shù)據(jù)進行排序。 2．給出一組數(shù)據(jù)，實現(xiàn)希爾排序算法，并對這組數(shù)據(jù)進行排序。按要求完成實驗報告。給出一種解決沖突的方案。 3．給出一組數(shù)據(jù)，構(gòu)造平衡二叉樹。 實驗八 查找（ 2學時） 實驗內(nèi)容和基本要求： 實現(xiàn)或部分實現(xiàn)以下功能： 1．給出一組有序數(shù)據(jù)，實現(xiàn)二分查找算法，并對這組數(shù)據(jù)中的任一數(shù)據(jù)進行查找。 實驗七 圖的應(yīng)用（ 2學時） 實驗內(nèi)容和基本要求： 在實驗六的基礎(chǔ)上，實現(xiàn)或部分實現(xiàn)對圖的以下操作： 1．拓撲排序 2．構(gòu)造最小生成樹 3．求解關(guān)鍵路徑 4．求解最短路徑 要求編寫完整程序，調(diào)試，程序執(zhí)行的輸出結(jié)果要求至少包含輸入數(shù)據(jù)和運行結(jié)果，最好能體現(xiàn)運行過程。實現(xiàn)對圖的以下基本操作： 1．建立圖（圖的鄰接表） 2．深度優(yōu)先遍歷或廣度優(yōu)先遍歷 要求編寫完整程序，調(diào)試，程序執(zhí)行的輸出結(jié)果要求至少包含輸入數(shù)據(jù)和運行結(jié)果，最好能體現(xiàn)運行過程。按要求完成實驗報告。 實驗五 哈夫曼樹（ 2學時） 實驗內(nèi)容和基本要求： 給定一組數(shù)據(jù)，根據(jù)這組數(shù)據(jù)建立一棵 Huffman樹，求出該樹的 WPL，并給出每一個數(shù)據(jù)的 Huffman編碼。要求編寫完整程序，調(diào)試，程序執(zhí)行的輸出結(jié)果要求至少包含輸入數(shù)據(jù)和運行結(jié)果，最好能體現(xiàn)運行過程。 2．設(shè)計一個完全二叉樹，采用順序存儲方式存儲。實驗四 二叉樹（ 2學時） 實驗內(nèi)容和基本要求： 1．設(shè)計一個二叉樹，采用鏈接存儲方式存儲。實現(xiàn)對隊列的以下基本操作： 1．建立初始隊列 2．入隊 3．出隊 要求需要考慮隊列空和隊列滿的情況，編寫完整程序，調(diào)試，程序執(zhí)行的輸出結(jié)果要求至少包含輸入數(shù)據(jù)和運 行結(jié)果，最好能體現(xiàn)運行過程。按要求完成實驗報告。實驗二 棧（ 2學時）實驗內(nèi)容和基本要求： 設(shè)計一個或多個順序棧。對這兩種線性表進行以下基本操作： 1．查找 2．插入 3．刪除 要求考慮時間復雜度和空間復雜度進行算法設(shè)計，編寫完整程序，調(diào)試，程序執(zhí)行的輸出結(jié)果要求至少包含輸入數(shù)據(jù)和運行結(jié)果，最好能體現(xiàn)運行過程。實驗一 線性表 (2 學時 )實驗內(nèi)容和基本要求： 分別設(shè)計兩類順序表。實驗內(nèi)容的選擇要盡量結(jié)合基本內(nèi)容的應(yīng)用實例，要具有一定的典型性和方法的靈活性，但一次實驗內(nèi)容不宜太多、太難。 4．具有一定的邏輯思維和推理能力 四、課程的主要內(nèi)容、基本要求和學時分配建議（總學時數(shù) :18學時） 實驗內(nèi)容可根據(jù)實驗條件及教學情況由任課教師自定。 2． 掌握結(jié)構(gòu)化程序設(shè)計的的基本原理、良好的設(shè)計習慣，并具備較好的程序調(diào)試能力。 三、對先修課的要求 高級程序設(shè)計語言、離散數(shù)學是學習數(shù)據(jù)結(jié)構(gòu)的主要先修課程。 2．應(yīng)達到的實驗?zāi)芰藴? 學會從問題入手，分析研究數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)表示和數(shù)據(jù)處理的特性，以便為應(yīng)用所涉及的數(shù)據(jù)選擇適當?shù)倪壿嫿Y(jié)構(gòu)、存儲結(jié)構(gòu)及其相應(yīng)的操作算法，并初步掌握時間和空間分析技術(shù)。 二、課程性質(zhì)、目的和任務(wù) 1．本實驗課在培養(yǎng)實驗?zāi)芰χ械牡匚缓妥饔? 《數(shù)據(jù)結(jié)構(gòu)》是計算機科學與技術(shù)專業(yè)的重要的專業(yè)基礎(chǔ)課，它所討論的知識內(nèi)容和提倡的技術(shù)和方法，無論對計算機領(lǐng)域的其它課程，還是從事軟件工程的開發(fā)，都有著不可替代的作用。對于前兩種，要求掌握典型操作，如構(gòu)造、求根、找第一個鄰接頂點、找下一個鄰接頂點等操作的實現(xiàn) 算法 熟練掌握：圖的兩種遍歷算法與求解連通性問題的方法。包括什么是遞歸，有那些種類的遞歸，遞歸問題的遞歸求解方法 掌握：遞歸過程的機制與利用遞歸工作棧實現(xiàn)遞歸的方法 了解：迷宮問題的遞歸求解思路及如何利用棧實現(xiàn)迷宮問題的非遞歸解法 掌握：利用遞歸解決問題的分治法和回溯法 掌握：廣義表的定義及其實現(xiàn)方法 掌握：廣義表的遞歸算法 六、樹與森林 9學時 教學內(nèi)容： 樹和森林的概念：樹的定義；樹的術(shù)語；樹的抽象數(shù)據(jù)類型 二叉樹：二叉樹的定義；二叉樹的性質(zhì)；二叉樹的抽象數(shù)據(jù)類型 二叉樹的表示：順序表示；二叉鏈表表示 遍歷二叉樹：中序遍歷；前序遍歷；后序遍歷；應(yīng)用二叉樹遍歷的事例；二叉樹的計數(shù) 線索化二叉樹：線索；中序線索化二 叉樹 堆：堆的定義；堆的建立；堆的插入與刪除；堆的調(diào)整算法 樹與森林：樹的存儲表示；森林與二叉樹的轉(zhuǎn)換；遍歷樹；遍歷森林 霍夫曼樹：路徑長度；霍夫曼樹；霍夫曼編碼 教學要求： 了解：樹和森林的概念。特別注意?？蘸蜅M的條件 了解：在表達式計算時棧是如何使用的，重點了解用后綴表示計算表達式及中綴表示改后綴表示的方法和算法思路 熟練掌握：隊列的定義、特性和隊列的抽象數(shù)據(jù)類型，隊列的順 序表示、鏈表表示以及相應(yīng)操作的實現(xiàn)。有動態(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)，用雙向鏈表解決問題的方法。 第三部分 教學內(nèi)容和教學要求 一、數(shù)據(jù)結(jié)構(gòu)基本概念及簡單的算法分析 3學時 教學內(nèi)容： 什么是數(shù)據(jù)結(jié)構(gòu) 抽象數(shù)據(jù)類型及面向?qū)ο蟾拍睿簲?shù)據(jù)類型；數(shù)據(jù)抽象與抽象數(shù)據(jù)類型；面向?qū)ο蟮母拍?；用于描述?shù)據(jù)結(jié)構(gòu)的語言 數(shù)據(jù)結(jié)構(gòu)的抽象層次 算法定義 性能分析與度量：算法的性能標準；算法的后期測試；算法的事前估計；空間復雜度度量；時間復雜度度量；時間復雜度的漸進表示法；漸進的空間復雜度 教學要求： 了解：什么是數(shù)據(jù)、數(shù)據(jù)對象、數(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ù)抽象和 信息隱蔽原則。因此，不要出難題、怪題，但也不要過于簡單，適當有一些編程題。本著多練多考的原則，各地方電大可以再平時多做一些小考。 除學校提供的時間外，要求課外學生利用自己可能擁有的計算機條件，完成更多的練習，不通過大量的實踐，能力和知識水平得不到有效得提高。 學生在上機做實驗前，應(yīng)事先將程序、調(diào)試數(shù)據(jù)、上機操作順序準備好，并提前使用這些調(diào)試數(shù)據(jù)人工執(zhí)行過。為此，安排一定的實驗上機學時。為達到自學的效果，除讀懂教科書中所講內(nèi)容外，還需大量做題。 自學與練習 自學是獲取知識的重要手段。面授輔導或答疑安排兩周一次為宜。 面授輔導或答疑 本課程教學過程中，面授輔導和答疑是必不可少的教學環(huán)節(jié)。為保證教學效果，采取電視集中授課方式。 六、課程實驗 實驗內(nèi)容和要求由省級電大作出具體規(guī)定，從 2024年春開始按該課程實驗教材規(guī)定進行。 掌握：要求學生能夠較好地理解和掌握，并且能夠做簡單的分析。 四、教學方法和教學形式建議 電視授課為主，結(jié)合面授輔導、面授或電子郵件答疑，進行必要的上機實驗。 二、先修課要求 面向?qū)ο蟪绦蛟O(shè)計、計算機數(shù)學 (離散數(shù)學 )。課程采用面向?qū)ο蟮挠^點討論數(shù)據(jù)結(jié)構(gòu)技術(shù)，并以兼有面向過程和面向?qū)ο箅p重特色的 C++語言作為算法的描述工具，強化數(shù)據(jù)結(jié)構(gòu)基本知識和面向?qū)ο蟪绦蛟O(shè)計基本能力的雙基訓練。本課程介紹如何組織各種數(shù)據(jù)在計算機中的存儲、傳遞和轉(zhuǎn)換。 由于本課程內(nèi)容較多，在實際教學中可根據(jù)大綱內(nèi)容，進行適當調(diào)整。 （二）實驗、實習部分 課程安排五個類別的實驗，實驗時數(shù)為 12 課時，其中： 實驗 一、線性鏈表及運算 2課時 實驗 二、棧和隊列 2課時 實驗 三、樹和二叉樹 4課時 實驗 四、圖及其應(yīng)用 2課時 實驗 五、查找與排序 2課時 四、課程考核方式 閉卷考試 70%、平時作業(yè)與實驗 30% 五、建議教材和教學參考書 參考教材： 《數(shù)據(jù)結(jié)構(gòu)》（ C語言描述）高等教育出版社 耿國華主編 《數(shù)據(jù)結(jié)構(gòu)》（ C語言版）清華大學出版社 嚴蔚敏，吳偉民編者 《數(shù)據(jù)結(jié)構(gòu)題集》（ C語言版）清華大學出版社 嚴蔚敏，吳偉民編者 《數(shù)據(jù)結(jié)構(gòu)》算法實現(xiàn)及解析（第二版）西安電子科技大學出版社 高一凡 六、說明 因課時安排少，教學內(nèi)容多。 掌握：基本掌握外排算法的基本思想，不同排序方法的比較。難點：哈希表查找算法。掌握哈希表查找算法。 第 8章 查找（ 8學時） 靜態(tài)查找表（順序表，有序表，靜態(tài)樹表，索引順序表） 動態(tài)查找表（二叉排序樹和平衡二叉樹， B_樹和 B+樹，鍵樹） 哈希表（定義，構(gòu)造方法，處理沖突的方法，查找及其分析） 基本要求： 了解： 各種查找法的基本概念及實現(xiàn)的基本 思想。 重點：圖的兩種主要存儲結(jié)構(gòu)及遍歷算法。 掌握：圖的兩種主要存儲結(jié)構(gòu)及遍歷算法。重點： 樹的存儲結(jié)構(gòu)和遍歷算法。 掌握：熟練掌握二叉樹性質(zhì)和遍歷算法，掌握樹與森林的孩子兄弟存儲表示和遍歷。 難點：廣義表的遞歸算法。 掌握：掌握基本概念和算法。認識到數(shù)組可以作為順序存儲結(jié)構(gòu)用于順序表、字符串和稀疏矩陣的實現(xiàn)。難點：模式匹配及串的應(yīng)用。掌握：掌握串的基本概念和運算。難點： 棧和隊列的算法實現(xiàn)。 掌握： 熟練掌握棧和隊列的特性和在不同存儲結(jié)構(gòu)前提下的算法實現(xiàn)。棧和隊列是表最基本和重要的數(shù)據(jù)結(jié)構(gòu)，是數(shù)據(jù)結(jié)構(gòu)課程的基礎(chǔ)。難點：鏈表的理解。為后繼章節(jié)的學習打基礎(chǔ)。 第 2章 線性表（ 8學時） 線性表的類型定義 線性表的順序表示和實現(xiàn) 線性表的鏈式表示和實現(xiàn)（線性鏈表，循環(huán)鏈表，雙向鏈表） 一元多項式的表示及相加 基本要求： 了解：兩種存儲結(jié)構(gòu)（順序