【正文】 找和索引查找的方法、應用(掌握)；(掌握)；(掌握)；，B+樹和鍵樹的特點以及它們的建立過程（理解）；(掌握)；；(掌握)。（三）重點與難點重點：外部排序過程和實現(xiàn)方法；多路并歸算法及其實現(xiàn)； 難點：最佳并歸樹的構造方法及其應用。（五）實驗學時 4學時實驗二教學計劃編制問題（一）實驗內容假設任何專業(yè)都有固定的學習年限，每學年含兩學期，每學期的時間長度和學分上限值均相等。（四）實驗設備和材料 計算機。哈希函數(shù)用除留余數(shù)法構造，用偽隨機探測再散列法處理沖突。平時成績占30%，考試成績占70%。2．基本要求（1）掌握線性表的定義和特點；（2）熟練掌握線性表的順序存儲表示和插入、刪除、查找等實現(xiàn)算法；（3）熟練掌握單鏈表、循環(huán)鏈表、雙向鏈表三種鏈表的表示，以及單鏈表的查找、插入、刪除、創(chuàng)建等實現(xiàn)算法。2．基本要求（1）了解數(shù)組的兩種存儲表示方法，并掌握數(shù)組在以行為主的存儲結構中的地址計算方法；（2）掌握對特殊矩陣進行壓縮存儲時的下標變換公式；（3）熟悉稀疏矩陣的三元組順序表存儲結構下的一般轉置和快速轉置算法；了解十字鏈表等存儲結構；（4）掌握廣義表的結構特點、取表頭表尾操作，及其存儲表示方法。（八）查找（4 學時）1．主要內容：（1）查找的基本概念和相關術語；（2）靜態(tài)查找表：順序查找、折半查找和索引順序表查找；（3）動態(tài)查找表：二叉排序樹的查找、插入和刪除；（4）哈希表。要求積極獨立完成所布置的習題，建議安排至少六次。課堂表現(xiàn)10%：包括課堂考勤和課堂提問，如果缺課課時達到本課程教學時數(shù)的1/3，則取消考試資格。課程性質：專業(yè)基礎理論課/必修 開課學期：5 總學分數(shù)： 修訂年月：2007年7月二、課程教學內容及學時分配第1章 緒論（4學時）理解數(shù)據(jù)、數(shù)據(jù)元素和數(shù)據(jù)項的概念及其相互間的關系。本章知識點為：線性表的邏輯結構定義、抽象數(shù)據(jù)類型定義和各種存儲結構的描述方法；在線性表的兩類存儲結構(順序的和鏈式的)上實現(xiàn)基本操作；稀疏多項式的抽象數(shù)據(jù)類型定義、表示和加法的實現(xiàn)。本章知識點為：串的數(shù)據(jù)類型定義；串的三種存儲表示：定長順序存儲結構、塊鏈存儲結構和堆分配存儲結構；串的各種基本操作的實現(xiàn)及其應用；第5章 數(shù)組和廣義表（6學時，2個學時實驗上機）了解數(shù)組的兩種存儲表示方法，并掌握數(shù)組在以行為主的存儲結構中的地址計算方法。本章知識點為：圖的定義和術語；圖的四種存儲結構：數(shù)組表示法、鄰接表、十字鏈表和鄰接多重表；圖的兩種遍歷策略：深度優(yōu)先搜索和廣度優(yōu)先搜索；圖的連通性：連通分量和最小生成樹；拓撲排序和關鍵路徑；兩類求最短路徑問題的解法。(一)課堂講授本課程屬于基礎理論課程。培養(yǎng)學生的算法設計能力和程序設計能力。非數(shù)值計算問題的數(shù)學模型不再是傳統(tǒng)的數(shù)學方程問題，而是諸如表、樹、圖之類的數(shù)據(jù)結構。算法時間復雜度后綴表達式的算法，數(shù)制的換算利用本章的基本知識設計相關的應用問題循環(huán)隊列的特點及判斷溢出的條件利用隊列的特點設計相關的應用問題串的模式匹配運算算法二叉樹遍歷算法的設計利用二叉樹遍歷算法，解決簡單應用問題 哈夫曼樹的算法圖的遍歷最小生成樹最短路徑二叉排序樹查找平衡樹二叉樹堆排序快速排序 歸并排序三、教學方法與手段充分利用多媒體教學工具，配合黑板上的教學內容較難部分的算法實現(xiàn)過程演義四、教學內容、目標與學時分配教學內容 教學目標 課時分配緒論數(shù)據(jù)結構的內容邏輯結構與存儲結構算法和算法分析線性表線性表的定義與運算線性表的順序存儲線性表的鏈式存儲棧棧的定義與運算棧存儲和實現(xiàn)棧的應用舉例隊列隊列的定義與基本運算隊列的存儲與實現(xiàn)隊列的應用舉例串串的定義與基本運算串的表示與實現(xiàn)串的基本運算樹和二叉樹樹的定義和術語二叉樹樹的基本概念和術語 遍歷二叉數(shù)和線索二叉樹二叉樹的轉換二叉樹的應用哈夫曼樹及其應用圖圖的定義和術語圖的存儲結構圖的遍歷算法圖的連通性查找查找的基本概念與靜態(tài)查找 動態(tài)查找哈希表了解了解掌握熟練掌握順序表存儲地址的計算掌握單鏈表的結構特點和基本運算掌握雙鏈表的結構特點和基本運算掌握棧的定義與運算掌握棧的存儲與實現(xiàn)熟練掌握棧的各種實際應用掌握隊列的定義與基本運算熟練掌握隊列的存儲與實現(xiàn)掌握循環(huán)隊列的特征和基本運算了解串的邏輯結構掌握串的存儲結構熟練掌握串的基本運算了解了解二叉樹熟練掌握二叉樹定義和存儲結構了解二叉樹的遍歷算法掌握掌握哈夫曼的建立及編碼了解了解熟練掌握熟練掌握了解熟練掌握了解哈希表與哈希方法4學時1學時1學時2學時8學時2學時2學時4學時8學時2學時2學時4學時6學時2學時2學時2學時6學時2學時2學時2學時12學時2學時2學時2學時2學時2學時2學時8學時2學時2學時2學時2學時8學時4學時2學時2學時排序12學時 插入排序熟練掌握基本思想3學時 快速排序了解各種內部排序方法和特點3學時 選擇排序掌握2學時 各種排序方法比較掌握2學時實驗內容 實驗目標 課時分配 算法編程實驗：用指針方式編寫程序 復習C（C++）語言指針、結構體等的用法對單鏈表進行遍歷鏈表的描述與操作實現(xiàn)棧及其操作描述方法及操作編寫串子系統(tǒng)1 串的特點及順序定長存儲、操作、查找編寫串子系統(tǒng) 2 串的特點及順序定長存儲、操作、查找編寫樹子系統(tǒng)1 二叉樹的特點及存儲方式、創(chuàng)建、顯示、遍歷等編寫樹子系統(tǒng)2 二叉樹的特點及存儲方式、創(chuàng)建、顯示、遍歷等圖子系統(tǒng)圖的鄰接矩陣的存儲、遍歷、廣度/深度優(yōu)先搜索查找子系統(tǒng)理解查找基本算法、平均查找長度、靜態(tài)、動態(tài)查找等五、考試范圍與題型考試范圍與分數(shù)比例1)緒論12% 2)線性表17% 3)棧7% 4)隊列6% 5)串4% 6)樹和二叉樹14% 7)圖15% 8)查找4% 9)排序21%考試題型與分數(shù)比例1)名詞解釋18% 2)判斷對錯16% 3)填空16% 4)單項選擇18% 5)應用32%六、教材與參考資料教材： 實用數(shù)據(jù)結構基礎（譚浩強）中國鐵道出版社參考資料： 數(shù)據(jù)結構（嚴蔚敏）清華大學出版社數(shù)據(jù)結構實用教程（徐孝凱）清華大學出版社（撰寫人：，審核人： 2學時 2學時 2學時 2學時 2學時 2學時 2學時 2學時 2學時）第五篇：數(shù)據(jù)結構教學大綱(參考)數(shù)據(jù)結構 Data Structure 課程代碼：學 時 數(shù)：64（講課50 實驗14 研討0 實習實踐1周）學 分 數(shù)：4 課程類別：學科基礎課開課學期：4 主講教師：編寫日期： 2011年7月1日一、課程性質和目的課程性質：數(shù)據(jù)結構A是計算機科學與技術、數(shù)字媒體藝術、信息管理與信息系統(tǒng)專業(yè)的一門重要學科基礎課，是必修課。（理論8學時，實驗4學時）教學內容：(1)線性表的類型定義。掌握無序表和有序表的合并算法，了解多項式的加法運算?；疽螅赫莆諚：完犃械奶攸c，并能在相應的應用問題中正確選用。、數(shù)組和廣義表（理論2學時）教學內容：(1)串的表示和實現(xiàn)，包括順序存儲和鏈式存儲表示。了解稀疏矩陣的兩種壓縮存儲方法的特點和適用范圍?；疽螅毫私鈽浜蜕值母拍睿涞亩x、樹的術語。（理論8學時，實驗2學時）教學內容：(1)圖的定義和術語。掌握構造最小生成樹的兩種算法及拓撲排序算法的思想，掌握迪杰斯特拉算法?；疽螅菏炀氄莆枕樞虮砗陀行虮淼牟檎曳椒捌鋵崿F(xiàn)，掌握二叉排序樹的插入和查找算法及其實現(xiàn)，了解平衡二叉樹、B樹和B+樹的各種操作。(6)基數(shù)排序：多關鍵字的排序和鏈數(shù)基數(shù)排序。實驗：實驗內容：綜合性實驗。本課程的教學環(huán)節(jié)包括：課堂講授、實驗、實習、作業(yè)、答疑、小測驗等。四、本課程的考核方式期末考試采用筆試形式，考試題型為：選擇、填空、判斷、應用題和算法設計題。執(zhí)筆人：審核人：教學院長：院學術委員會：院長：