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

數(shù)據(jù)結(jié)構(gòu)課程教學大綱(DataStructure)學時數(shù)：72其中：實驗學時：10課外學時：0學分數(shù)：4.5適用專業(yè)：網(wǎng)絡工程一、課程的性質(zhì)、目的和任務數(shù)據(jù)結(jié)構(gòu)是計算機、網(wǎng)絡工程專業(yè)的必修學科基礎(chǔ)課程，主要介紹：線性表、棧、隊列、數(shù)組、串、樹、二叉樹、圖等基本數(shù)據(jù)結(jié)構(gòu)及其應用；排序及查找的原理與方法；數(shù)據(jù)的存儲結(jié)構(gòu)。通過本課程的學習使學生掌握基本數(shù)據(jù)結(jié)構(gòu)的概念、特征、存貯結(jié)構(gòu)及算法和算法分析的手段。熟悉基本結(jié)構(gòu)在計算機學科的應用，，訓練學習使用高級語言編寫合理算法的能力。二、課程教學的基本要求（一）了解典型數(shù)據(jù)結(jié)構(gòu)的邏輯關(guān)系，存貯結(jié)構(gòu)，操作及算法的關(guān)系。（二）熟練掌握各種基本數(shù)據(jù)結(jié)構(gòu)的概念、特點、存貯方式、算法及分析評估。（三）掌握基本算法分析方法。（四）熟悉查找及排序的典型算法。（五）針對實際問題，選擇合理的數(shù)據(jù)結(jié)構(gòu)及實現(xiàn)相應的操作。三、課程的教學內(nèi)容、重點和難點第一章概論（2學時）一、基本內(nèi)容：（一）數(shù)據(jù)、數(shù)據(jù)元類、數(shù)據(jù)類型、數(shù)據(jù)結(jié)構(gòu)。（二）算法與數(shù)據(jù)結(jié)構(gòu)的關(guān)系。（三）算法的描述，評價標準及評估。第一節(jié)：基本概念和術(shù)語第二節(jié)：抽象數(shù)據(jù)類型第三節(jié)：算法分析第四節(jié)：性能分析與度量二、基本要求：（一）熟悉數(shù)據(jù)結(jié)構(gòu)基本概念（二）了解數(shù)據(jù)結(jié)構(gòu)要解決的問題重點：數(shù)據(jù)結(jié)構(gòu)的三個要點。難點：區(qū)分數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)類型，數(shù)據(jù)元素的差別。第二章線性表（8學時）一、基本內(nèi)容：（一）線性表的定義及抽象操作。（二）線性表的兩種存貯結(jié)構(gòu)及算法。（三）鏈表的應用舉例。第一節(jié)：線性表第二節(jié)：線性表的順序表示與實現(xiàn)第三節(jié)：線性表的鏈式表示與實現(xiàn)鏈表第四節(jié)：一元多項式的表示與實現(xiàn)二、基本要求：（一）掌握線性表的基本概念（二）掌握線性表的各種算法重點：線性表的基本操作。難點：線性表的抽象操作，鏈表應用。第三章棧和隊列（8學時）一、基本內(nèi)容：（一）隊列、棧的定義及抽象操作。（二）隊列、棧的順序存貯結(jié)構(gòu)及相關(guān)算法。（三）隊列、棧的鏈式存貯結(jié)構(gòu)及相關(guān)算法。（四）多隊列、棧的順序存貯。（五）棧的應用舉例、棧與遞歸過程的關(guān)系。第一節(jié)：棧第二節(jié)：隊列第三節(jié)：棧與隊列的實現(xiàn)第四節(jié)：棧與隊列的應用舉例二、基本要求：（一）掌握隊列、棧的基本概念（二）掌握隊列、棧的各種算法（三）熟悉隊列、棧的各種應用重點：隊列、棧的各種算法。難點：循環(huán)隊列的概念與操作。第四章數(shù)組、廣義表（4學時）一、基本內(nèi)容：（一）數(shù)組的定義及操作。（二）數(shù)組的順序存貯及規(guī)律。（三）矩陣的壓縮存貯。（四）廣義表簡介。第一節(jié)：數(shù)組的定義第二節(jié)：數(shù)組的順序表示和實現(xiàn)第三節(jié)：矩陣的壓縮存儲第四節(jié)：廣義表簡介二、基本要求：（一）掌握數(shù)組的基本概念（二）掌握矩陣的壓縮存貯的各種算法重點：矩陣的各種壓縮存貯。難點：十字鏈表的結(jié)構(gòu)與操作。第五章串（4學時）一、基本內(nèi)容：（一）串的基本概念和抽象操作。（二）串的存貯方式介紹。（三）串的操作的實現(xiàn)。第一節(jié)：串類型的定義第二節(jié)：串的表示和實現(xiàn)第三節(jié)：串的模式匹配算法二、基本要求：（一）掌握串的基本概念（二）掌握串的各種算法（三）熟悉求子串的序號算法的實現(xiàn)原理重點：串的存貯方式比較。難點：子串定位算法實現(xiàn)。第六章樹和二叉樹（10學時）一、基本內(nèi)容：（一）樹的定義及抽象操作。（二）二叉樹的性質(zhì)及存貯方式（順序、鏈式）。（三）二叉樹的遍歷：前序、中序、后序、線索二叉樹。（四）樹的存貯結(jié)構(gòu)：雙親表示法、孩子表示法、孩子兄弟表示法等。（五）樹、森林、二叉樹的轉(zhuǎn)換、樹的遍歷。（六）Huffman樹及其應用。第一節(jié)：樹的定義和基本術(shù)語第二節(jié)：二叉樹第三節(jié)：二叉樹的存儲結(jié)構(gòu)第四節(jié)：遍歷二叉樹第五節(jié)：線索化二叉樹第六節(jié)：樹與森林第七節(jié)：赫夫曼樹二、基本要求：（一）掌握樹、二叉樹的基本概念（二）掌握二叉樹存儲結(jié)構(gòu)及各種算法（三）熟悉樹的存儲結(jié)構(gòu)及相關(guān)操作的實現(xiàn)重點：二叉樹的概念與操作。難點：二叉樹的遍歷算法與Huffman樹。第七章圖（10學時）一、基本內(nèi)容：（一）圖的定義及基本操作。（二）圖的存貯結(jié)構(gòu)：（鄰接矩陳，鄰接表存貯方法，十字鏈表法）。（三）圖的遍歷：深度優(yōu)先搜索與廣度優(yōu)先搜索算法。（四）連通分量，生成樹，最小生成樹。（五）拓撲排序，關(guān)鏈路徑。（六）最短路徑。第一節(jié)：圖的定義和術(shù)語第二節(jié)：圖的存儲結(jié)構(gòu)第三節(jié)：圖的遍歷與連通性第四節(jié)：最小生成樹第五節(jié)：活動網(wǎng)絡第六節(jié)：最短路徑二、基本要求：（一）掌握圖的基本概念（二）掌握圖遍歷的DFS和BFS算法（三）熟悉圖的實現(xiàn)與應用重點：圖的DFS與BFS算法，拓撲排序。難點：最小生成樹，拓撲排序。第八章內(nèi)部排序（10學時）一、基本內(nèi)容：（一）概述。（二）插入排序：直接插入排序，希爾排序。（三）選擇排序：直接選擇排序，堆排序。（四）交換排序：冒泡排序，快速排序。（五）歸并排序：（六）排序各種方法比較。第一節(jié)：概述第二節(jié)：插入排序（直接插入、折半插入、表插入排序、希爾排序）第三節(jié)：交換排序（起泡排序、快速排序）第四節(jié)：選擇排序（簡單選擇排序、樹形選擇排序、堆排序）第五節(jié)：歸并排序二、基本要求：（一）掌握排序的基本概念（二）掌握排序的各種算法（三）熟悉排序算法的比較與應用。重點：插入排序、交換排序。難點：堆排序、快速排序。第九章查找（8學時）一、基本內(nèi)容：（一）概述。（二）順序查找算法：順序查找、折半查找、分塊查找。（三）樹表的查找、二叉排序樹，平衡二叉樹。（四）哈希（Hash）表：概念，構(gòu)造方法，沖突與沖突處理方法。第一節(jié)：靜態(tài)查找表第二節(jié)：動態(tài)查找樹表第三節(jié)：哈希表二、基本要求：（一）掌握查找的基本概念（二）掌握查找的各種算法（三）熟悉HASH表的實現(xiàn)與應用重點：順序查找算法難點：二叉排序樹，哈希（Hash）表 第十章外部排序（4學時）一、基本內(nèi)容：（一）概述（外存貯器的特點，外部排序的特點）（二）K—路歸并排序。（三）初始歸并的產(chǎn)生。（四）最佳歸并樹。第一節(jié)：概述第二節(jié)：歸并排序第三節(jié)：最佳歸并樹二、基本要求：（一）掌握外部排序的基本概念（二）掌握外部排序的各種算法（三）熟悉歸并算法的實現(xiàn)。重點：K—路歸并排序難點：最佳歸并樹第十一章文件（2學時）一、基本內(nèi)容：（一）基本概念。（二）文件組織：順序文件，索引順序文件、哈希文件、鏈接文件、倒排文件。第一節(jié)：概述第二節(jié)：文件組織二、基本要求：（一）掌握文件的基本概念（二）掌握文件的組織結(jié)構(gòu)重點：文件基本概念，順序文件。難點：哈希文件。四、課程各教學環(huán)節(jié)要求本課程教學環(huán)節(jié)除講課外，還有實驗課等，實驗課是培養(yǎng)工科學生實驗技能的主要手段，是本課程的實踐環(huán)節(jié)，通過實驗訓練使學生能達到如下要求：（一）實驗要求：1、實現(xiàn)隊列、棧的各種算法及操作。2、用Huffman樹進行加密抽樣與解密算法。3、實現(xiàn)深度優(yōu)先搜索與廣度優(yōu)先搜索算法。4、實現(xiàn)典型的排序算法。5、實現(xiàn)典型的查找算法。（二）考試環(huán)節(jié)要求：1、本課程的命題考試將根據(jù)本大綱所規(guī)定的內(nèi)容和目標來確定考試范圍和考核要求?？荚嚸}會覆蓋各章，并適當突出重點章節(jié)，體現(xiàn)本課程的內(nèi)容重點。2、本課程在試題中對不同能力層次要求的分數(shù)比例一般為：基礎(chǔ)題占20%，簡答與計算題占60%-70%，綜合運用與編成題占10%-20%。3、本課程采取期末考試與平時作業(yè)考查相結(jié)合的方法，期末考試成績占70%，平時作業(yè)成績（含實驗）占30%。期末考試閉卷筆試，根據(jù)教學大綱命題，考試時間為120分鐘，卷面分值100分。五、學時分配章號主要內(nèi)容各教學環(huán)節(jié)學時分配作業(yè)量（題）備注講授實驗討論習題課外其它小計一概論222二線性表883三棧與隊列6284四數(shù)組與廣義表442五串443六樹與二叉樹82108七圖82108八內(nèi)部排序82106九查找6284十外部排序442十一文件222期中測驗、期末復習、機動22合計62107244六、課程與其它課程的聯(lián)系本課程一般應在學完《語言》、《離散數(shù)學》之后開課。而本課程又是后續(xù)的《編譯原理》、《操作系統(tǒng)原理》、《數(shù)