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

1、數(shù)據(jù)結(jié)構(gòu)與算法課程教學(xué)大綱課程代碼：12281030適用專業(yè)：計(jì)算機(jī)應(yīng)用技術(shù)總學(xué)時(shí)數(shù)： 68學(xué)時(shí)，其中：理論教學(xué)34學(xué)時(shí)，實(shí)踐教學(xué)34學(xué)時(shí)。學(xué)分：4.5先修課程：C語(yǔ)言程序?qū)д?、程序設(shè)計(jì)導(dǎo)論考核方式：機(jī)試一、制訂大綱的依據(jù)本大綱根據(jù)2013年軟件技術(shù)專業(yè)教學(xué)計(jì)劃制訂。二、課程簡(jiǎn)介數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學(xué)、計(jì)算機(jī)硬件和計(jì)算機(jī)軟件之間的一門計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的核心課程，是高級(jí)程序設(shè)計(jì)語(yǔ)言、編譯原理、操作系統(tǒng)、數(shù)據(jù)庫(kù)等課程的基礎(chǔ)。同時(shí)，數(shù)據(jù)結(jié)構(gòu)技術(shù)也廣泛應(yīng)用于信息科學(xué)、系統(tǒng)工程、應(yīng)用數(shù)學(xué)以及各種工程技術(shù)領(lǐng)域。數(shù)據(jù)結(jié)構(gòu)課程集中討論軟件開發(fā)過程中的設(shè)計(jì)階段、同時(shí)設(shè)計(jì)編碼和分析階段的若干基本問題。此外，為了構(gòu)

2、造出好的數(shù)據(jù)結(jié)構(gòu)及其實(shí)現(xiàn)，還需考慮數(shù)據(jù)結(jié)構(gòu)及其實(shí)現(xiàn)的評(píng)價(jià)與選擇。因此，數(shù)據(jù)結(jié)構(gòu)的內(nèi)容包括抽象、實(shí)現(xiàn)和評(píng)價(jià)三個(gè)層次，從數(shù)據(jù)表示和數(shù)據(jù)處理上看有五個(gè)基本組成“要素”分別是邏輯結(jié)構(gòu)，存儲(chǔ)結(jié)構(gòu)、基本運(yùn)算、算法及不同數(shù)據(jù)結(jié)構(gòu)的比較與算法分析。三、課程性質(zhì)、教育目標(biāo)(一)性質(zhì)：本課程為計(jì)算機(jī)系軟件技術(shù)專業(yè)的專業(yè)課。（二）教育目標(biāo)：通過本課程的學(xué)習(xí)，使學(xué)生深透地理解數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)的基本概念以及有關(guān)算法，培養(yǎng)基本的、良好的程序設(shè)計(jì)技能，編制高效可靠的程序，為學(xué)習(xí)操作系統(tǒng)、編譯原理和數(shù)據(jù)庫(kù)等課程奠定基礎(chǔ)。四、課程教學(xué)內(nèi)容與基本要求第一部分 緒論 (一)教學(xué)內(nèi)容數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語(yǔ)；抽象數(shù)據(jù)類型

3、的表示；算法和算法分析。(二)重點(diǎn)、難點(diǎn)重點(diǎn)：數(shù)據(jù)結(jié)構(gòu)的基本概念及相關(guān)術(shù)語(yǔ)。難點(diǎn)：算法的時(shí)間復(fù)雜度分析。(三)教學(xué)基本要求知識(shí)要求：了解：抽象數(shù)據(jù)類型及面向?qū)ο蟾拍?；理解：算法的定義及算法的特性；掌握：數(shù)據(jù)結(jié)構(gòu)的基本概念、算法的性能分析與度量方法。第二部分 線性表 (一)教學(xué)內(nèi)容1線性表的定義及操作；2線性表的順序存儲(chǔ)定義及操作實(shí)現(xiàn)；3單鏈表的定義；單鏈表中的插入與刪除；帶表頭結(jié)點(diǎn)的單鏈表；靜態(tài)鏈表；4循環(huán)鏈表的類定義及運(yùn)算； 5雙向鏈表的類定義及運(yùn)算；6線性表的應(yīng)用：多項(xiàng)式及其相加。(二)重點(diǎn)、難點(diǎn)重點(diǎn)：順序表的數(shù)組定義方式及實(shí)現(xiàn)，單鏈表的定義及實(shí)現(xiàn)。難點(diǎn)：循環(huán)鏈表和雙向鏈表的定義及實(shí)現(xiàn)。(

4、三)教學(xué)基本要求知識(shí)要求：了解：靜態(tài)鏈表。理解：線性表的定義及操作。掌握：順序表的數(shù)組定義方式及實(shí)現(xiàn)，單鏈表、循環(huán)鏈表和雙向鏈表的定義及實(shí)現(xiàn)。第三部分 棧和隊(duì)列 (一)教學(xué)內(nèi)容1棧的抽象數(shù)據(jù)類型；棧的順序存儲(chǔ)表示；棧的鏈?zhǔn)酱鎯?chǔ)表示；棧的兩種存儲(chǔ)表示上的基本運(yùn)算；2棧的應(yīng)用；3隊(duì)列的抽象數(shù)據(jù)類型；隊(duì)列的順序存儲(chǔ)表示及基本運(yùn)算；隊(duì)列的鏈?zhǔn)酱鎯?chǔ)表示及基本運(yùn)算；4隊(duì)列的應(yīng)用舉例。(二)重點(diǎn)、難點(diǎn)重點(diǎn)：棧的定義及實(shí)現(xiàn)；隊(duì)列的定義及實(shí)現(xiàn)。難點(diǎn)：棧的應(yīng)用中的表達(dá)式求值；循環(huán)隊(duì)列（隊(duì)列的順序存儲(chǔ)）。(三)教學(xué)基本要求知識(shí)要求：了解：隊(duì)列的應(yīng)用。理解：棧的應(yīng)用中的遞歸算法。掌握：棧的定義及實(shí)現(xiàn)；隊(duì)列的定義及實(shí)現(xiàn)

5、。棧的應(yīng)用中的表達(dá)式求值；循環(huán)隊(duì)列（隊(duì)列的順序存儲(chǔ)）。第四部分 串、數(shù)組和廣義表(一)教學(xué)內(nèi)容1字符串的抽象數(shù)據(jù)類型；字符串操作的實(shí)現(xiàn)；字符串的模式匹配2數(shù)組的邏輯結(jié)構(gòu)定義和存儲(chǔ)方法；特殊矩陣和稀疏矩陣的壓縮存儲(chǔ)方法； 3廣義表的概念；廣義表的表示及操作；廣義表存儲(chǔ)結(jié)構(gòu)的實(shí)現(xiàn)；4廣義表的訪問算法；廣義表的遞歸算法。(二)重點(diǎn)、難點(diǎn)重點(diǎn)：串和數(shù)組的基本概念、存儲(chǔ)結(jié)構(gòu)。廣義表的概念和存儲(chǔ)結(jié)構(gòu)及其相關(guān)運(yùn)算的實(shí)現(xiàn)。難點(diǎn)：串的模式匹配算法，特殊矩陣和稀疏矩陣的壓縮存儲(chǔ)。(三)教學(xué)基本要求知識(shí)要求：了解：串的一些基本處理操作、矩陣的相關(guān)運(yùn)算。理解：廣義表的遞歸算法。 掌握：串和數(shù)組的基本概念、存儲(chǔ)結(jié)構(gòu)。廣

6、義表的概念和存儲(chǔ)結(jié)構(gòu)及其相關(guān)運(yùn)算的實(shí)現(xiàn)。串的模式匹配算法，特殊矩陣和稀疏矩陣的壓縮存儲(chǔ)。第五部分 樹和二叉樹(一)教學(xué)內(nèi)容1樹的基本概念； 2二叉樹的定義、性質(zhì)、存儲(chǔ)表示及相關(guān)運(yùn)算；二叉樹的遍歷；線索二叉樹； 3森林和二叉樹的相互轉(zhuǎn)換；4哈夫曼樹及哈夫曼編碼。(二)重點(diǎn)、難點(diǎn)重點(diǎn)：二叉樹的定義、性質(zhì)、存儲(chǔ)表示；二叉樹的遍歷；難點(diǎn)：二叉樹的相關(guān)運(yùn)算。(三)教學(xué)基本要求知識(shí)要求：了解：線索二叉樹上的復(fù)雜運(yùn)算實(shí)現(xiàn)。 理解：二叉樹的相關(guān)運(yùn)算。 掌握：二叉樹的定義、性質(zhì)、存儲(chǔ)表示；二叉樹的遍歷；森林和二叉樹的相互轉(zhuǎn)換；哈夫曼樹及哈夫曼編碼。第六部分 圖(一)教學(xué)內(nèi)容1圖的基本概念、存儲(chǔ)表示（鄰接矩陣、鄰

7、接表、十字鏈表，鄰接多重表）； 2圖的遍歷與連通性：深度優(yōu)先搜索；廣度優(yōu)先搜索；連通分量；重連通分量；3最小生成樹：克魯斯卡爾算法；普里姆算法；4最短路徑；5拓?fù)渑判?、關(guān)鍵路徑。(二)重點(diǎn)、難點(diǎn)重點(diǎn)：圖的存儲(chǔ)表示；圖的遍歷；最小生成樹；最短路徑；難點(diǎn)：關(guān)鍵路徑的求解。(三)教學(xué)基本要求知識(shí)要求：了解：圖的存儲(chǔ)結(jié)構(gòu)中的鄰接多重表。 理解：圖的遍歷算法。 掌握：圖的存儲(chǔ)表示（鄰接矩陣、鄰接表）；圖的遍歷；最小生成樹；最短路徑；拓?fù)渑判颉㈥P(guān)鍵路徑。第七部分 查找(一)教學(xué)內(nèi)容1靜態(tài)查找（順序查找、折半查找、分塊查找）；2動(dòng)態(tài)查找（二叉排序樹）； 3哈希查找。(二)重點(diǎn)、難點(diǎn)重點(diǎn)：靜態(tài)查找；二叉排序樹

8、的建立。難點(diǎn)：二叉排序樹的刪除；平衡二叉樹的調(diào)整。(三)教學(xué)基本要求知識(shí)要求：了解：查找的相關(guān)概念、作用。 理解：哈希函數(shù)的構(gòu)造。 掌握：靜態(tài)查找；二叉排序樹的相關(guān)知識(shí)；哈希查找法和解決沖突的方法。 第八部分 排序(一)教學(xué)內(nèi)容1排序概念；2插入排序、交換排序、選擇排序、歸并排序、基數(shù)排序；3各種排序方法的比較。(二)重點(diǎn)、難點(diǎn)重點(diǎn)：交換排序、選擇排序。難點(diǎn)：堆排序。(三)教學(xué)基本要求知識(shí)要求：了解：各種排序方法的時(shí)間復(fù)雜度的分析方法。 理解：排序方法“穩(wěn)定”或“不穩(wěn)定”的含義。 掌握：各種方法的排序過程及其依據(jù)的原則。 第九部分 文件(一)教學(xué)內(nèi)容1基本概念；2文件組織；3順序文件、隨機(jī)文件

9、、索引文件、倒排文件。 (二)重點(diǎn)、難點(diǎn)重點(diǎn)：基本概念；順序文件；索引文件。難點(diǎn)：文件的使用。能力要求：即通過本課程的學(xué)習(xí)，學(xué)生具備基本的、良好的程序設(shè)計(jì)技能，能夠編制高效可靠的程序。素質(zhì)要求：具備良好的編程習(xí)慣和能力。五、學(xué)時(shí)（理論和實(shí)踐）分配表序號(hào)教學(xué)內(nèi)容課時(shí)分配理論教學(xué)實(shí)踐教學(xué)考核權(quán)重1緒論225%2線性表4422%3棧和隊(duì)列555%4串、數(shù)組和廣義表43%5樹和二叉樹5625%6圖4420%7查找4410%8排序448%9文件222%總 計(jì)3434100%六、學(xué)習(xí)教學(xué)場(chǎng)地、設(shè)施要求（課程中的實(shí)踐部分）序號(hào)項(xiàng)目（實(shí)驗(yàn)）名稱學(xué)習(xí)教學(xué)場(chǎng)地、設(shè)施要求1線性表的應(yīng)用實(shí)踐教學(xué)在機(jī)房進(jìn)行，機(jī)器需要安裝有C語(yǔ)言環(huán)境。2棧和隊(duì)列的應(yīng)用3串的簡(jiǎn)單操作4二叉樹的算法實(shí)現(xiàn)5圖的遍歷6分塊查找7冒泡排序說明：分實(shí)踐項(xiàng)目列出場(chǎng)地、設(shè)施要求，如每個(gè)實(shí)踐項(xiàng)目的場(chǎng)地和設(shè)施基本相同，也可以一次性描述。七、考核及評(píng)分辦法考核的原則：閉卷考試?？己朔绞剑嚎荚?；期末考試；筆試（閉卷）；各教學(xué)環(huán)節(jié)占總分的比例：實(shí)驗(yàn)、作業(yè)占30%，期末考試占70%。八、學(xué)習(xí)資源的選用建議