《數(shù)據(jù)結構與算法》課程教學大綱

《數(shù)據(jù)結構與算法》課程教學大綱課程 課代碼 名

數(shù)據(jù)結構與算法DataStructure1、學分：4.5 學時（理論學時實驗學時：16）2、課程性質(zhì)：學科專業(yè)基礎課3、適用專業(yè)：計算機科學與技術專業(yè)、計算機軟件工程專業(yè)4、適用對象：本科課5、先修課程：計算機語言(C)程6、教材與參考書目：基《數(shù)據(jù)結構(C語言版)》，嚴蔚敏吳偉民，清華大學出版社，1997本《數(shù)據(jù)結構(用面向?qū)ο蠓椒ㄅcC++描述)》，殷人昆，清華大學出版社，1998情《C++數(shù)據(jù)結構與程序設計（美）RobertL.Kruse/AlexanderJ.Ryba著/錢麗萍譯》，況清華大學出版社，2004《算機算法設計與分析（2版730~4060~70％8、教學環(huán)境：課堂、多媒體，實驗室課程數(shù)據(jù)結構是計算機程序設計的重要理論基礎。也是計算機專業(yè)教學中的核心專業(yè)基礎教課程。它所討論的知識內(nèi)容和提倡的技術方法，對進一步學習計算機領域的其他課程、從學事軟件工程的開發(fā)，都有著不可替代的作用。是從事計算機科學研究及應用的科技人員必目須具備的重要基礎知識。的1緒論（4學時）課 1.1什么是數(shù)據(jù)結構（理解程 1.2基本概念和術語（掌握內(nèi) 1.3抽象數(shù)據(jù)類型的表示與實現(xiàn)（了解容 1.4算法和算法分析、 1.4.1算法（掌握）學 1.4.2算法設計的要求（掌握）時 1.4.3算法效率的度量（掌握分 1.4.4算法的存儲空間需求（理解）配及 2線性表（6+4學時）教 2.l線性表的類型定義（掌握）學 2.2線性表的順序表示和實現(xiàn)（掌握基 2.3線性表的鏈式表示和實現(xiàn)本2.3.1線性鏈表（掌握要2.3.2循環(huán)鏈表（掌握求2.3.3雙向鏈表（掌握2.4一元多項式的表示及相加（理解）（6+2學時）（掌握）3.1.l抽象數(shù)據(jù)類型棧的定義3.1.2棧的表示和實現(xiàn)棧的應用舉例（了解）數(shù)制轉換括號匹配的檢驗行編輯程序迷宮求解表達式求值（了解）隊列課 3.4.1抽象數(shù)據(jù)類型隊列的定義（掌握）程 3.4.2鏈隊隊列的鏈式表示和實現(xiàn)（掌握）內(nèi) 3.4.3循環(huán)隊隊列的順序表示和實現(xiàn)（掌握容 3.5離散事件模擬（了解）、學 4串（4+2學時）時 4.1串類型的定義（掌握分 4.2串的表示和實現(xiàn)配 4.2.1定長順序存儲表示（掌握及 4.2.2堆分配存儲表示（了解）教 4.2.3串的塊鏈存儲表示（了解學 4.3串的模式匹配算法（理解）基 4.3.l求子串位置的定位函數(shù)本 4.3.2模式匹配的一種改進算法要 4.4串操作應用舉例（理解求 4.4.1文本編輯4.4.2建立詞索引表數(shù)組和廣義表學時）（掌握）（掌握）（理解）5.3.l特殊矩陣（理解）5.3.2稀疏矩陣（理解）（掌握）（理解）m元多項式的表示（了解）（了解）求廣義表的深度復制廣義表建立廣義表的存儲結構樹和二叉樹（10+2學時）（掌握）二叉樹（掌握）二叉樹的定義二叉樹的性質(zhì)二叉樹的存儲結構遍歷二叉樹和線索二叉樹遍歷二叉樹（掌握）線索二叉樹（理解）（理解）樹的存儲結構森林與二叉樹的轉換課 6.4.3樹和森林的遍歷程 6.5樹與等價問題（理解）內(nèi) 6.6赫夫曼樹及其應用（掌握容 6.6.1最優(yōu)二叉樹（赫夫曼樹）、 6.6.2赫夫曼編碼學 6.7回溯法與樹的遍歷（理解時 6.8樹的計數(shù)（了解）分配 7圖（10+2學時）及 7.1圖的定義和術語（掌握教 7.2圖的存儲結構（掌握）學 7.2.1數(shù)組表示法（掌握）基 7.2.2鄰接表（掌握）本 7.2.3十字鏈表（理解）要 7.2.4鄰接多重表（理解求 7.3圖的遍歷7.3.l深度優(yōu)先搜索（掌握）7.3.2廣度優(yōu)先搜索（掌握）圖的連通性問題無向圖的連通分量和生成樹（理解）有向圖的強連通分量（理解）（掌握）（了解）（了解）拓撲排序關鍵路徑最短路徑（掌握）從某個源點到其余各項點的最短路徑每一對頂點之間的最短路徑8查找（10+2學時）（掌握）8.1.l順序表的查找（掌握）（掌握）靜態(tài)樹表的查找（掌握）索引順序表的查找（掌握）（了解）二叉排序樹和平衡二叉樹課 8.2.2B-樹和B+樹程 8.2.3鍵樹內(nèi) 8.3哈希表（理解）容 8.3.1什么是哈希表、 8.3.2哈希函數(shù)的構造方學 8.3.3處理沖突的方法時 8.3.4哈希表的查找及其分分配 9內(nèi)部排序（10+2學時及 9.1概述（掌握）教 9.2插入排序?qū)W 9.2.1直接插入排序（掌握基 9.2.2其他插入排序（理解）本 9.2.3希爾排序（理解）要 9.3快速排序（掌握）求 9.4選擇排序（掌握）樹形選擇排序（理解）堆排序（理解）歸并排序（理解）基數(shù)排序（了解）多關鍵字的排序鏈式基數(shù)排序各種內(nèi)部排序方法的比較討論（掌握）序號實驗名稱序號實驗名稱實驗學時每組人數(shù)實驗性質(zhì)開出要求實驗一順序表21驗證必做實驗二鏈表21驗證必做實驗三棧和隊列21驗證必做實驗四串的匹配21驗證必做實驗五二叉樹的遍歷21綜合必做實驗六圖的深度和廣度遍歷21驗證必做實驗七查找21驗證必做實驗八 排序 2 1 驗證 必做序號實驗四實驗內(nèi)容實驗五實驗八

內(nèi)容提要1、順序表的建立、插入、刪除和查找等算法的設計與編制2、程序調(diào)試1、單鏈表的建立、插入、刪除和查找等算法的設計與編制2、JOSEPHUS問題1、堆棧的建立、入棧、出棧等算法的設計與編制2、隊列的建立、入隊、出隊等算法的設計與編制1、BF算法的設計與編制2、矩陣三元表算法1、二叉樹的建立算法的設計與編制2、二叉樹的遞歸遍歷算法的設計與編制3、二叉樹的非遞歸遍歷算法的設計與編制1、圖的建立算法的設計與編制2、圖的深度和廣度遍歷算法的設計與編制1、前哨法查找的設計與編制2、二分法查找的設計與編制1、插入排序算法的設計與編制2、交換排序算法的設計與編制3、選擇排序算法的設計與編制備注大綱編寫應