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

1、數(shù)據(jù)結(jié)構(gòu)與算法課程教學大綱課程代碼課程名稱數(shù)據(jù)結(jié)構(gòu)與算法Data Structure課程基本情況1、學分： 4.5 學時：80 （理論學時：64 實驗學時：16）2、課程性質(zhì)：學科專業(yè)基礎(chǔ)課3、適用專業(yè)：計算機科學與技術(shù)專業(yè)、計算機軟件工程專業(yè) 4、適用對象：本科5、先修課程：計算機語言(C) 6、教材與參考書目：數(shù)據(jù)結(jié)構(gòu)(C語言版)，嚴蔚敏 吳偉民，清華大學出版社，1997數(shù)據(jù)結(jié)構(gòu)(用面向?qū)ο蠓椒ㄅcC+描述) ，殷人昆，清華大學出版社，1998C+數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 （美）Robert L.Kruse/Alexander J.Ryba著/錢麗萍譯， 清華大學出版社，2004 算機算法設(shè)計與分

2、析（第2版），王曉東， 電子工業(yè)出版社， 20047、考核方式：考試、閉卷 平時成績3040、期終考試6070 8、教學環(huán)境：課堂、多媒體，實驗室課程教學目的數(shù)據(jù)結(jié)構(gòu)是計算機程序設(shè)計的重要理論基礎(chǔ)。也是計算機專業(yè)教學中的核心專業(yè)基礎(chǔ)課程。它所討論的知識內(nèi)容和提倡的技術(shù)方法，對進一步學習計算機領(lǐng)域的其他課程、從事軟件工程的開發(fā)，都有著不可替代的作用。是從事計算機科學研究及應(yīng)用的科技人員必須具備的重要基礎(chǔ)知識。課程內(nèi)容、學時分配及教學基本要求1 緒論 （4學時）1.1什么是數(shù)據(jù)結(jié)構(gòu) （理解）1.2基本概念和術(shù)語 （掌握）1.3抽象數(shù)據(jù)類型的表示與實現(xiàn) （了解）1.4算法和算法分析 1.4.1算法

3、（掌握）1.4.2算法設(shè)計的要求 （掌握）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雙向鏈表（掌握）課程內(nèi)容、學時分配及教學基本要求2.4一元多項式的表示及相加（理解）3 棧和隊列 （6+2學時）3.1棧 （掌握）3.1.l抽象數(shù)據(jù)類型棧的定義 3.1.2棧的表示和實現(xiàn) 3.2棧的應(yīng)用舉例（了解）3.2.1數(shù)制轉(zhuǎn)換 3.2.2括號匹配的檢驗 3.2.3行編輯程序 3.2.4迷宮求解

4、 3.2.5表達式求值 3.3棧與遞歸的實現(xiàn) （了解）3.4隊列 3.4.1抽象數(shù)據(jù)類型隊列的定義 （掌握）3.4.2鏈隊列-隊列的鏈式表示和實現(xiàn) （掌握）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ù)Index（S,T,pos） 4.3.2模式匹配的一種改進算法 4.4串操作應(yīng)用舉例 （理解）4.4.1文本編輯 4.4.2建

5、立詞索引表5 數(shù)組和廣義表（4學時）5.1數(shù)組的定義 （掌握）5.2數(shù)組的順序表示和實現(xiàn) （掌握）5.3矩陣的壓縮存儲 （理解）5.3.l特殊矩陣 （理解）5.3.2稀疏矩陣 （理解）5.4廣義表的定義 （掌握）5.5廣義表的存儲結(jié)構(gòu) （理解）5.6 m元多項式的表示（了解）5.7廣義表的遞歸算法 （了解）5.7.1求廣義表的深度 5.7.2復(fù)制廣義表 課程內(nèi)容、學時分配及教學基本要求5.7.3建立廣義表的存儲結(jié)構(gòu) 6 樹和二叉樹 （10+2學時）6.1樹的定義和基本術(shù)語 （掌握）6.2二叉樹 （掌握）6.2.1二叉樹的定義 6.2.2二叉樹的性質(zhì) 6.2.3二叉樹的存儲結(jié)構(gòu) 6.3遍歷二叉樹

6、和線索二叉樹 6.3.1遍歷二叉樹 （掌握）6.3.2線索二叉樹 （理解）6.4樹和森林 （理解）6.4.1樹的存儲結(jié)構(gòu) 6.4.2森林與二叉樹的轉(zhuǎn)換 6.4.3樹和森林的遍歷 6.5樹與等價問題（理解）6.6赫夫曼樹及其應(yīng)用 （掌握）6.6.1最優(yōu)二叉樹（赫夫曼樹） 6.6.2赫夫曼編碼 6.7回溯法與樹的遍歷 （理解）6.8樹的計數(shù) （了解）7 圖（10+2學時）7.1圖的定義和術(shù)語 （掌握）7.2圖的存儲結(jié)構(gòu) （掌握）7.2.1數(shù)組表示法 （掌握）7.2.2鄰接表 （掌握）7.2.3十字鏈表 （理解）7.2.4鄰接多重表 （理解）7.3圖的遍歷 7.3.l深度優(yōu)先搜索 （掌握）7.3.2

7、廣度優(yōu)先搜索 （掌握）7.4圖的連通性問題 7.4.1無向圖的連通分量和生成樹（理解）7.4.2有向圖的強連通分量（理解）7.4.3最小生成樹 （掌握）7.4.4關(guān)節(jié)點和重連通分量 （了解）7.5有向無環(huán)圖及其應(yīng)用 （了解）7.5.1拓撲排序 7.5.2關(guān)鍵路徑 7.6最短路徑（掌握）7.6.1從某個源點到其余各項點的最短路徑 7.6.2每一對頂點之間的最短路徑 課程內(nèi)容、學時分配及教學基本要求8 查找（10+2學時）8.1靜態(tài)查找表 （掌握）8.1.l順序表的查找 （掌握）8.1.2有序表的查找 （掌握）8.1.3靜態(tài)樹表的查找（掌握）8.1.4索引順序表的查找（掌握）8.2動態(tài)查找表 （了

8、解）8.2.1二叉排序樹和平衡二叉樹 8.2.2 B- 樹和B+樹8.2.3鍵樹 8.3哈希表 （理解）8.3.1什么是哈希表 8.3.2哈希函數(shù)的構(gòu)造方法 8.3.3處理沖突的方法 8.3.4哈希表的查找及其分析 9 內(nèi)部排序（10+2學時）9.1概述 （掌握）9.2插入排序 9.2.1直接插入排序 （掌握）9.2.2其他插入排序（理解）9.2.3希爾排序（理解）9.3快速排序 （掌握）9.4選擇排序 9.4.1簡單選擇排序 （掌握）9.4.2樹形選擇排序（理解）9.4.3堆排序（理解）9.5歸并排序（理解）9.6基數(shù)排序 （了解）9.6.1多關(guān)鍵字的排序 9.6.2鏈式基數(shù)排序 9.7各種

9、內(nèi)部排序方法的比較討論（掌握）課內(nèi)實驗序號 實驗名稱 實驗學時 每組人數(shù) 實驗性質(zhì) 開出要求實驗一 順序表 2 1 驗證 必做 實驗二 鏈表 2 1驗證 必做實驗三 棧和隊列 2 1 驗證 必做實驗四 串的匹配 2 1 驗證 必做實驗五 二叉樹的遍歷 2 1 綜合 必做實驗六 圖的深度和廣度遍歷 2 1 驗證 必做實驗七 查找 2 1 驗證 必做實驗八 排序 2 1 驗證 必做實驗內(nèi)容序號內(nèi)容提要實驗一1、 順序表的建立、插入、刪除和查找等算法的設(shè)計與編制2、 程序調(diào)試實驗二1、 單鏈表的建立、插入、刪除和查找等算法的設(shè)計與編制2、JOSEPHUS問題實驗三1、 堆棧的建立、入棧、出棧等算法的設(shè)計與編制2、隊列的建立、入隊、出隊等算法的設(shè)計與編制實驗四1、 BF算法的設(shè)計與編制2、矩陣三元表算法實驗五1、 二叉樹的建立算法的設(shè)計與編制2、 二叉樹的遞歸遍歷算法的設(shè)計與編制3、二叉樹的非遞歸遍歷算法的設(shè)計與編制實驗六1、 圖的建立算法的設(shè)計與編制2、圖的深度和廣度遍歷算法的設(shè)計與編制實驗七1、 前哨法查找的設(shè)計與編制2、二分法查找的設(shè)計與編制實驗八1、 插入排序算法的設(shè)計與編制2