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

1、數(shù)據(jù)結(jié)構(gòu)課程教學(xué)大綱【課程編JSZB0210碼】計(jì)算機(jī)科學(xué)與技術(shù)【適用專理論課時(shí)：72,實(shí)驗(yàn)課時(shí)：32業(yè)】【課時(shí)】目標(biāo)和要求】數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)科學(xué)與技術(shù)的一門專業(yè)核心課程，與計(jì)算機(jī)各門課程之間都有密切聯(lián)系，具有獨(dú)特的承上啟下的重要位置。同時(shí)數(shù)據(jù)結(jié)構(gòu)又是一門實(shí)踐性極強(qiáng)的技術(shù)基礎(chǔ)課，其內(nèi)容隨計(jì)算機(jī)科學(xué)與技術(shù)的飛速發(fā)展而不斷更新。本課程主要內(nèi)容有：數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計(jì)與分析的基本知識(shí)，各種基本數(shù)據(jù)結(jié)構(gòu)的定義，存儲(chǔ)結(jié)構(gòu)、相應(yīng)的算法以及應(yīng)用，了解基本的數(shù)據(jù)結(jié)構(gòu)與算法的關(guān)系。培養(yǎng)學(xué)生結(jié)合實(shí)際應(yīng)用，設(shè)計(jì)有效的算法和數(shù)據(jù)結(jié)構(gòu)的能力。通過教學(xué)達(dá)到以下目的：1 .熟悉各種基本數(shù)據(jù)結(jié)構(gòu)的定義，性質(zhì)和特點(diǎn)；2 .掌握各

2、種基本數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)及相應(yīng)算法；3 .初步掌握算法分析的基本技巧以及如何根據(jù)實(shí)際問題設(shè)計(jì)一個(gè)有效的算法?！窘虒W(xué)時(shí)間安排】本課程計(jì)4學(xué)分，72+32學(xué)時(shí)，學(xué)時(shí)分配如下:序號(hào)課程內(nèi)容/實(shí)驗(yàn)名稱實(shí)驗(yàn)類型課時(shí)備注（教學(xué)形式）1緒論4學(xué)時(shí)講授、作業(yè)、輔導(dǎo)2線性表/線性表的各種操作綜合6學(xué)時(shí)+4學(xué)時(shí)講授、實(shí)驗(yàn)、作業(yè)、輔導(dǎo)3棧和隊(duì)列/棧和隊(duì)列的各種操作綜合6學(xué)時(shí)+4學(xué)時(shí)講授、實(shí)驗(yàn)、作業(yè)、輔導(dǎo)4串/串的各種操作綜合4學(xué)時(shí)+4學(xué)時(shí)講授、實(shí)驗(yàn)、作業(yè)、輔導(dǎo)5數(shù)組和廣義表4學(xué)時(shí)講授、作業(yè)、輔導(dǎo)6樹和二叉樹/樹和二叉樹的各種操作綜合12學(xué)時(shí)+4學(xué)時(shí)講授、實(shí)驗(yàn)、作業(yè)、輔導(dǎo)7圖/圖的各種操作綜合12學(xué)時(shí)+4學(xué)

3、時(shí)講授、實(shí)驗(yàn)、作業(yè)、輔導(dǎo)8動(dòng)態(tài)存儲(chǔ)管理4學(xué)時(shí)講授、作業(yè)、輔導(dǎo)9查找/各種查找方法及其實(shí)現(xiàn)綜合6學(xué)時(shí)+4學(xué)時(shí)講授、實(shí)驗(yàn)、作業(yè)、輔導(dǎo)10內(nèi)部排序/各種排序方法及其實(shí)現(xiàn)綜合10學(xué)時(shí)+4學(xué)時(shí)講授、實(shí)驗(yàn)、作業(yè)、輔導(dǎo)11外部排序2學(xué)時(shí)講授、作業(yè)、輔導(dǎo)12文件/實(shí)驗(yàn)考核綜合2學(xué)時(shí)+4學(xué)時(shí)講授、實(shí)驗(yàn)、作業(yè)、輔導(dǎo)合計(jì)72學(xué)時(shí)+32學(xué)時(shí)【教學(xué)內(nèi)容要點(diǎn)】第一章緒論（4學(xué)時(shí)）一、學(xué)習(xí)目的要求掌握數(shù)據(jù)結(jié)構(gòu)的定義、內(nèi)容和方法，掌握算法的定義、描述和評(píng)價(jià)。二、主要教學(xué)內(nèi)容1、數(shù)據(jù)結(jié)構(gòu)的概念和術(shù)語2、基本數(shù)據(jù)類型3、抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)4、算法描述與分析第二章線性表（6學(xué)時(shí)）、學(xué)習(xí)目的要求掌握線性表的抽象數(shù)據(jù)類型定義和兩

4、種存儲(chǔ)方式，以及在相應(yīng)存儲(chǔ)結(jié)構(gòu)上的線性表運(yùn)算。、主要教學(xué)內(nèi)容1、線性數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)2、線性表的邏輯結(jié)構(gòu)3、線性表的順序存儲(chǔ)和實(shí)現(xiàn)4、線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)5、應(yīng)用舉例第三章棧和隊(duì)列（6學(xué)時(shí)）、學(xué)習(xí)目的要求掌握棧和隊(duì)列的結(jié)構(gòu)特征以及操作實(shí)現(xiàn)特點(diǎn)。、主要教學(xué)內(nèi)容1、棧的抽象數(shù)據(jù)類型2、棧的表示和實(shí)現(xiàn)3、棧的應(yīng)用舉例4、隊(duì)列的抽象數(shù)據(jù)類型及定義5、循環(huán)隊(duì)列和鏈隊(duì)列6、隊(duì)列的應(yīng)用第四章串（4學(xué)時(shí)）、學(xué)習(xí)目的要求掌握串的定義、基本存儲(chǔ)結(jié)構(gòu)和基本操作以及串的應(yīng)用。、主要教學(xué)內(nèi)容1、串的邏輯結(jié)構(gòu)和定義2、串的表示和實(shí)現(xiàn)3、串的模式匹配算法4、串的應(yīng)用第五章數(shù)組和廣義表（4學(xué)時(shí)）3、學(xué)習(xí)目的要求掌握數(shù)組和廣義

5、表的定義與實(shí)現(xiàn)，加深對(duì)這兩種特殊的線性結(jié)構(gòu)的理解。二、主要教學(xué)內(nèi)容1、數(shù)組的定義與運(yùn)算2、數(shù)組的順序存儲(chǔ)和實(shí)現(xiàn)3、特殊矩陣的壓縮存儲(chǔ)4、廣義表的定義5、廣義表的存儲(chǔ)結(jié)構(gòu)第六章樹和二叉樹（12學(xué)時(shí)）、學(xué)習(xí)目的要求掌握樹型結(jié)構(gòu)的特性、存儲(chǔ)及其操作實(shí)現(xiàn)。、主要教學(xué)內(nèi)容1、樹的定義和基本術(shù)語2、二叉樹3、二叉樹的遍歷和線索二叉樹4、樹和森林5、哈夫曼樹及其應(yīng)用6、樹的應(yīng)用舉例第七章圖（12學(xué)時(shí)）、學(xué)習(xí)目的要求掌握?qǐng)D在計(jì)算機(jī)中的存儲(chǔ)和實(shí)現(xiàn)，并且利用圖來解決實(shí)際問題。、主要教學(xué)內(nèi)容1圖的定義和術(shù)語圖的存儲(chǔ)結(jié)構(gòu)，圖的遍歷圖的連通性，最短路徑應(yīng)用舉例；第八章動(dòng)態(tài)存儲(chǔ)管理（2學(xué)時(shí)）3、學(xué)習(xí)目的要求4、5、掌握利

6、用不同策略進(jìn)行動(dòng)態(tài)存儲(chǔ)管理的方法。二、主要教學(xué)內(nèi)容1概述可利用空間表及分配方法邊界標(biāo)識(shí)法伙伴系統(tǒng)4 、第九章查找（6學(xué)時(shí)）、學(xué)習(xí)目的要求掌握數(shù)據(jù)結(jié)構(gòu)中的查找技術(shù)的表示和實(shí)現(xiàn)方法。、主要教學(xué)內(nèi)容1、順序查找，有序表的查找2、索引順序查找，二分查找法3、哈希表4、B樹及B+樹5、應(yīng)用舉例4、第十章內(nèi)部排序（10學(xué)時(shí)）、學(xué)習(xí)目的要求掌握數(shù)據(jù)結(jié)構(gòu)中排序的基本概念和五類重要的排序方法。、主要教學(xué)內(nèi)容1、插入排序2、交換排序3、選擇排序4、歸并排序5、基數(shù)排序6、各種內(nèi)部排序方法的比較第十一章外部排序（4學(xué)時(shí)）、學(xué)習(xí)目的要求了解對(duì)外存信息進(jìn)行存取的特點(diǎn)，掌握外部排序的方法及實(shí)現(xiàn)。二、主要教學(xué)內(nèi)容1、外存信

7、息的存取2、外部排序的方法第十二章文件（2學(xué)時(shí)）、學(xué)習(xí)目的要求掌握文件在外存儲(chǔ)器中的表示方法及其各種運(yùn)算的實(shí)現(xiàn)方法。二、主要教學(xué)內(nèi)容1、文件組織：順序、隨機(jī)和直接存取文件2、索引文件3、ISAM及VSAM技術(shù)4、多關(guān)鍵字文件5、應(yīng)用舉例實(shí)驗(yàn)教學(xué)內(nèi)容要點(diǎn)】、線性表的各種操作1、實(shí)驗(yàn)?zāi)康囊笳莆站€性表的兩種存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)方式熟練掌握順序表和鏈表的建立、插入和刪除的算法編寫順序表和鏈表的建立、插入和刪除算法的實(shí)現(xiàn)程序分析算法的時(shí)間復(fù)雜度2、實(shí)驗(yàn)主要內(nèi)容編程實(shí)現(xiàn)順序表的建立、插入、刪除及輸出操作編程實(shí)現(xiàn)鏈表的建立、插入、刪除及輸出操作編程實(shí)現(xiàn)一元多項(xiàng)式的表示及相加3、實(shí)驗(yàn)儀器設(shè)備微機(jī)若干臺(tái)二、棧和隊(duì)列

8、的各種操作1、實(shí)驗(yàn)?zāi)康囊笳莆諚：完?duì)列的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)方式掌握棧和循環(huán)隊(duì)列的基本運(yùn)算掌握棧在實(shí)現(xiàn)遞歸過程中的作用2、實(shí)驗(yàn)主要內(nèi)容編程實(shí)現(xiàn)棧的進(jìn)棧、出棧及元素輸出操作編程實(shí)現(xiàn)循環(huán)隊(duì)列的基本運(yùn)算編程實(shí)現(xiàn)遞歸過程，并理解棧在實(shí)現(xiàn)遞歸過程中的作用3、實(shí)驗(yàn)儀器設(shè)備微機(jī)若干臺(tái)、串的各種操作1、實(shí)驗(yàn)?zāi)康囊笳莆兆址母拍罴按鎯?chǔ)方式掌握串的基本運(yùn)算掌握串的模式匹配算法2、實(shí)驗(yàn)主要內(nèi)容編程實(shí)現(xiàn)串的基本運(yùn)算編程實(shí)現(xiàn)串的模式匹配算法3、實(shí)驗(yàn)儀器設(shè)備微機(jī)若干臺(tái)四、樹和二叉樹的各種操作1、實(shí)驗(yàn)?zāi)康囊笳莆斩鏄涞男再|(zhì)、順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)方式掌握二叉樹的遍歷算法及其執(zhí)行過程掌握二叉樹的線索化過程掌握哈夫曼樹及其應(yīng)用2、

9、實(shí)驗(yàn)主要內(nèi)容編程實(shí)現(xiàn)在順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)方式時(shí)，二叉樹的遍歷算法及其執(zhí)行過程編程實(shí)現(xiàn)二叉樹的線索化過程及在線索樹上找前驅(qū)和后繼結(jié)點(diǎn)的方法編程實(shí)現(xiàn)哈夫曼樹的構(gòu)造及其應(yīng)用過程3、實(shí)驗(yàn)儀器設(shè)備微機(jī)若干臺(tái)五、圖的各種操作1、實(shí)驗(yàn)?zāi)康囊笳莆請(qǐng)D的存儲(chǔ)結(jié)構(gòu)及其構(gòu)造方法掌握?qǐng)D的兩種遍歷算法及其執(zhí)行過程掌握?qǐng)D的最小生成樹算法掌握?qǐng)D的單源最短路徑算法2、實(shí)驗(yàn)主要內(nèi)容編程實(shí)現(xiàn)圖的存儲(chǔ)結(jié)構(gòu)及其構(gòu)造方法編程實(shí)現(xiàn)圖的兩種遍歷算法及其執(zhí)行過程編程實(shí)現(xiàn)圖的最小生成樹算法編程實(shí)現(xiàn)圖的單源最短路徑算法3、實(shí)驗(yàn)儀器設(shè)備微機(jī)若干臺(tái)六、各種查找方法及其實(shí)現(xiàn)1、實(shí)驗(yàn)?zāi)康囊笳莆枕樞虮砗陀行虮淼牟檎曳椒ㄕ莆斩媾判驑涞臉?gòu)造和查找方法掌握

10、哈希表的構(gòu)造方法、沖突及其解決方法2、實(shí)驗(yàn)主要內(nèi)容編程實(shí)現(xiàn)順序表和有序表的查找方法編程實(shí)現(xiàn)二叉排序樹的構(gòu)造和查找方法編程實(shí)現(xiàn)哈希表的構(gòu)造方法、沖突及其解決方法3、實(shí)驗(yàn)儀器設(shè)備微機(jī)若干臺(tái)七、各種排序方法及其實(shí)現(xiàn)1、實(shí)驗(yàn)?zāi)康囊笊羁汤斫馀判虻亩x和各種排序方法的特點(diǎn)掌握各種排序方法的排序過程及其依據(jù)的原則掌握各種排序方法的時(shí)間復(fù)雜度的分析方法2、實(shí)驗(yàn)主要內(nèi)容編程實(shí)現(xiàn)插入排序方法的排序過程編程實(shí)現(xiàn)選擇排序方法的排序過程編程實(shí)現(xiàn)快速排序方法的排序過程編程實(shí)現(xiàn)歸并排序方法的排序過程編程實(shí)現(xiàn)基數(shù)排序方法的排序過程3、實(shí)驗(yàn)儀器設(shè)備微機(jī)若干臺(tái)八、實(shí)驗(yàn)考核1、實(shí)驗(yàn)?zāi)康囊髮?duì)數(shù)據(jù)結(jié)構(gòu)中的各種運(yùn)算和算法的掌握作全面的考察2、實(shí)驗(yàn)主要內(nèi)容編程實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)中的各種運(yùn)算和算法3、實(shí)驗(yàn)儀器設(shè)備微機(jī)若干臺(tái)成績(jī)考核方式】1、成績(jī)?cè)u(píng)定總則全面考核學(xué)生在課程學(xué)習(xí)各個(gè)環(huán)節(jié)的理解、掌握和參與情況2、平時(shí)成績(jī)?cè)u(píng)定平時(shí)成績(jī)=考勤成績(jī)+作業(yè)成績(jī)3、期末考核評(píng)定（1）有中期考試：課程成績(jī)二平時(shí)成績(jī)（10%）+中期成績(jī)（20%）+實(shí)驗(yàn)成績(jī)（28%）+期末成績(jī)（42%）（2）無中期考試：課程成績(jī)二平時(shí)成績(jī)（20%）+實(shí)驗(yàn)成績(jī)（32%）+期末成績(jī)（48%）教材與參考書目】指定教材：數(shù)據(jù)結(jié)構(gòu)（C語言版）嚴(yán)蔚敏、吳偉民編著清華大學(xué)出版社數(shù)據(jù)結(jié)構(gòu)題集（C語言版）嚴(yán)蔚敏、吳偉民編著清華大學(xué)出版社參考書目：1、Robert.Kruse