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

1、編號(hào)：信息管理與信息系統(tǒng) 公共管理學(xué)院本科課程教學(xué)大綱數(shù)據(jù)結(jié)構(gòu) ()教學(xué)大綱一、課程基本信息課程名稱(chēng)： 數(shù)據(jù)結(jié)構(gòu) () data structure (ii)課程號(hào)： 40128830課程類(lèi)別： 專(zhuān)業(yè)課學(xué) 時(shí)： 48 學(xué) 分： 3二、教學(xué)目的及要求數(shù)據(jù)結(jié)構(gòu)概論，從抽象數(shù)據(jù)類(lèi)型的角度討論線(xiàn)性表、棧、隊(duì)列，串、數(shù)組、廣義表，樹(shù)、二叉樹(shù)和圖等基本類(lèi)型的數(shù)據(jù)結(jié)構(gòu)及其應(yīng)用，抽象數(shù)據(jù)類(lèi)型的常用表示方法,操作系統(tǒng)和編譯程序中涉及的動(dòng)態(tài)存儲(chǔ)管理的基本技術(shù)，查找、內(nèi)部排序，外部排序，置換選擇排序, 文件的概念，文件結(jié)構(gòu),索引順序存取方法。三、教學(xué)內(nèi)容第1章 緒論 （共3學(xué)時(shí)） 1.1 什么是數(shù)據(jù)結(jié)構(gòu) （0.5學(xué)

2、時(shí)）教學(xué)內(nèi)容：由數(shù)學(xué)方程無(wú)法描述的非數(shù)值計(jì)算問(wèn)題引出數(shù)據(jù)結(jié)構(gòu)表、圖、樹(shù)的3種實(shí)例，闡述數(shù)據(jù)結(jié)構(gòu)的概念，數(shù)據(jù)結(jié)構(gòu)的內(nèi)涵和特點(diǎn)，數(shù)據(jù)結(jié)構(gòu)所處的學(xué)科地位，數(shù)據(jù)結(jié)構(gòu)的學(xué)科背景、起源、發(fā)展和現(xiàn)狀；要求學(xué)生掌握數(shù)據(jù)結(jié)構(gòu)的概念，能辨別數(shù)學(xué)模型中數(shù)學(xué)方程和表、圖、樹(shù)等數(shù)據(jù)結(jié)構(gòu)的區(qū)別。 1.2 基本概念和術(shù)語(yǔ) （1學(xué)時(shí)）教學(xué)內(nèi)容：闡述本課使用的一些基本概念，包括數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)、數(shù)據(jù)對(duì)象、數(shù)據(jù)結(jié)構(gòu)、集合、結(jié)構(gòu)、線(xiàn)性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)、圖狀結(jié)構(gòu)、網(wǎng)狀結(jié)構(gòu)、邏輯結(jié)構(gòu)、物理結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、位、元素、結(jié)點(diǎn)、數(shù)據(jù)域、順序映像、非順序映像、順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)、指針、虛擬存儲(chǔ)結(jié)構(gòu)、數(shù)據(jù)類(lèi)型、原子類(lèi)型、結(jié)構(gòu)類(lèi)型、抽象

3、數(shù)據(jù)類(lèi)型、固定聚合類(lèi)型、可變聚合類(lèi)型、多形數(shù)據(jù)類(lèi)型；要求學(xué)生掌握包括數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)、數(shù)據(jù)對(duì)象、數(shù)據(jù)結(jié)構(gòu)、集合、結(jié)構(gòu)、線(xiàn)性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)、圖狀結(jié)構(gòu)、網(wǎng)狀結(jié)構(gòu)等在內(nèi)的所有基本概念。 1.3 抽象數(shù)據(jù)類(lèi)型的表示與實(shí)現(xiàn) （0.5學(xué)時(shí)）教學(xué)內(nèi)容：闡述在c語(yǔ)言中，抽象數(shù)據(jù)類(lèi)型的常用表示方法，包括預(yù)定義常量和類(lèi)型、數(shù)據(jù)結(jié)構(gòu)的表示用類(lèi)型定義（typedef）描述、函數(shù)表示法、各種賦值語(yǔ)句、選擇語(yǔ)句、結(jié)束語(yǔ)句、輸入和輸出語(yǔ)句、基本函數(shù)、邏輯運(yùn)算約定；要求學(xué)生了解抽象數(shù)據(jù)類(lèi)型的描述語(yǔ)言、構(gòu)成方法，掌握抽象數(shù)據(jù)類(lèi)型的類(lèi)c語(yǔ)言11種表示方法。 1.4 算法與算法分析 （1學(xué)時(shí)）1.4.1 算法教學(xué)內(nèi)容：闡述算

4、法的定義，算法的5個(gè)重要特征：有窮性、確定性、可行性、輸入、輸出；要求學(xué)生掌握算法的定義，理解算法的5個(gè)重要特征。1.4.2 算法設(shè)計(jì)要求教學(xué)內(nèi)容：闡述好算法設(shè)計(jì)的4個(gè)要求即正確性、可讀性、強(qiáng)壯性和效率與低存儲(chǔ)量需求；要求學(xué)生理解好算法設(shè)計(jì)的4個(gè)要求。 1.4.3 算法效率的度量教學(xué)內(nèi)容：闡述算法效率的2種度量方法：事前統(tǒng)計(jì)的方法和事后分析估算的方法，時(shí)間復(fù)雜度的概念，頻度的概念；要求學(xué)生掌握時(shí)間復(fù)雜度的概念，頻度的概念。1.4.4 算法的存儲(chǔ)空間需求教學(xué)內(nèi)容：闡述空間復(fù)雜度的概念，空間復(fù)雜度的表示法，算法原地工作的概念；要求學(xué)生掌握空間復(fù)雜度的概念，了解算法原地工作的概念。第2章 線(xiàn)性表 （

5、共4學(xué)時(shí)） 2.1 線(xiàn)性表的類(lèi)型定義 （0.5學(xué)時(shí)）教學(xué)內(nèi)容：闡述線(xiàn)性結(jié)構(gòu)的特點(diǎn)，線(xiàn)性表的抽象數(shù)據(jù)類(lèi)型定義，數(shù)據(jù)項(xiàng)、記錄、文件的定義，實(shí)例說(shuō)明線(xiàn)性表的插入、刪除、歸并等操作方式，并對(duì)算法做相應(yīng)的分析；要求學(xué)生掌握線(xiàn)性表的概念和抽象數(shù)據(jù)類(lèi)型定義。 2.2 線(xiàn)性表的順序表示和實(shí)現(xiàn)（重點(diǎn)） （1.5學(xué)時(shí)）教學(xué)內(nèi)容：闡述線(xiàn)性表的順序表示的概念，順序映像的方式，順序映像的隨機(jī)存取特性，實(shí)例描述線(xiàn)性表在順序存儲(chǔ)表示時(shí)進(jìn)行插入、刪除、合并操作的幾種算法；要求學(xué)生掌握線(xiàn)性表的順序表示的概念和順序映像的方式，理解線(xiàn)性表在順序存儲(chǔ)結(jié)構(gòu)時(shí)的插入、刪除、合并等操作方法。 2.3 線(xiàn)性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)（重點(diǎn)） （1.

6、5學(xué)時(shí)）2.3.1 線(xiàn)性鏈表教學(xué)內(nèi)容：闡述線(xiàn)性鏈表的概念、構(gòu)成方式，結(jié)點(diǎn)、數(shù)據(jù)域、指針域、指針、鏈、鏈表、頭指針、頭結(jié)點(diǎn)和靜態(tài)鏈表的概念，線(xiàn)性鏈的表示法，實(shí)例算法說(shuō)明單鏈表的插入、刪除、合并操作處理算法，靜態(tài)鏈表的算法；要求學(xué)生掌握線(xiàn)性有序鏈表的概念、與之相關(guān)的名詞概念，理解單鏈表的插入、刪除、合并操作算法過(guò)程。2.3.2 循環(huán)鏈表教學(xué)內(nèi)容：闡述循環(huán)鏈表的概念，循環(huán)鏈表的操作特點(diǎn)；要求學(xué)生掌握循環(huán)鏈表的概念。2.3.3 雙向鏈表教學(xué)內(nèi)容：闡述雙向鏈表的概念和特點(diǎn)，雙向鏈表的抽象數(shù)據(jù)類(lèi)型定義，雙向鏈表的幾種操作算法；要求學(xué)生掌握雙向鏈表的概念，理解雙向鏈表的抽象數(shù)據(jù)類(lèi)型定義，理解雙向鏈表的操作算

7、法。 2.4 一元多項(xiàng)式的表示及相加 （0.5學(xué)時(shí)）教學(xué)內(nèi)容：闡述存儲(chǔ)高次一元多項(xiàng)式的線(xiàn)性表可以采用每個(gè)元素包含2個(gè)數(shù)據(jù)項(xiàng)的方法，利用線(xiàn)性鏈表的基本操作來(lái)實(shí)現(xiàn)一元多項(xiàng)式的定義、相加和相乘運(yùn)算；要求學(xué)生掌握利用線(xiàn)性鏈表的基本操作來(lái)實(shí)現(xiàn)一元多項(xiàng)式的定義、相加和相乘運(yùn)算。第3章 棧和隊(duì)列 （共4學(xué)時(shí)） 3.1 棧 （0.5學(xué)時(shí)）3.1.1 抽象數(shù)據(jù)類(lèi)型棧的定義教學(xué)內(nèi)容：闡述棧、棧頂、棧底、后進(jìn)先出等概念，棧的抽象數(shù)據(jù)定義；要求學(xué)生掌握棧及棧的相關(guān)概念，理解棧的抽象數(shù)據(jù)定義。3.1.2 棧的表示和實(shí)現(xiàn)教學(xué)內(nèi)容：闡述棧的2種存儲(chǔ)表示法：順序棧和鏈棧的定義，順序棧的模塊說(shuō)明；要求學(xué)生掌握順序棧的定義。 3

8、.2 棧的應(yīng)用舉例 （1學(xué)時(shí)）3.2.1 數(shù)制轉(zhuǎn)換教學(xué)內(nèi)容：闡述應(yīng)用棧結(jié)構(gòu)的后進(jìn)先出特性，進(jìn)行十進(jìn)制n和其它d進(jìn)制數(shù)的轉(zhuǎn)換算法；要求學(xué)生理解應(yīng)用棧結(jié)構(gòu)的數(shù)制轉(zhuǎn)換算法。3.2.2 括號(hào)匹配的檢驗(yàn)教學(xué)內(nèi)容：闡述應(yīng)用棧結(jié)構(gòu)的后進(jìn)先出特性，進(jìn)行圓括號(hào)和方括號(hào)書(shū)寫(xiě)格式是否正確的檢查算法；要求學(xué)生理解應(yīng)用棧結(jié)構(gòu)的括號(hào)匹配檢驗(yàn)算法。3.2.3 行編輯程序教學(xué)內(nèi)容：闡述應(yīng)用棧結(jié)構(gòu)的文本行編輯算法；要求學(xué)生理解應(yīng)用棧結(jié)構(gòu)的文本行編輯算法。3.2.4 迷宮求解教學(xué)內(nèi)容：闡述應(yīng)用棧結(jié)構(gòu)的迷宮求解算法，即求出迷宮中從入口到出口的所有路徑；要求學(xué)生理解應(yīng)用棧結(jié)構(gòu)的迷宮求解算法。3.2.5 表達(dá)式求值教學(xué)內(nèi)容：闡述應(yīng)用棧

9、結(jié)構(gòu)進(jìn)行表達(dá)式求值的算符優(yōu)先法，算符優(yōu)先法中的算符優(yōu)先關(guān)系，要求學(xué)生理解應(yīng)用棧結(jié)構(gòu)進(jìn)行表達(dá)式求值的算符優(yōu)先法。 3.3 棧與遞歸的實(shí)現(xiàn) （0.75學(xué)時(shí)）教學(xué)內(nèi)容：闡述遞歸的概念、遞歸問(wèn)題的特性，棧在n階hanoi塔問(wèn)題等典型遞歸問(wèn)題中的應(yīng)用；要求學(xué)生理解棧在n階hanoi塔遞歸算法中的應(yīng)用。 3.4 隊(duì)列（重點(diǎn)） （1.5學(xué)時(shí)）3.4.1 抽象數(shù)據(jù)類(lèi)型隊(duì)列的定義教學(xué)內(nèi)容：闡述隊(duì)列、fifo的概念，隊(duì)列的特性，隊(duì)列的抽象數(shù)據(jù)定義，雙端隊(duì)列的概念；要求學(xué)生掌握隊(duì)列的概念，理解隊(duì)列的特性，隊(duì)列的抽象數(shù)據(jù)定義，雙端隊(duì)列的概念。3.4.2 鏈隊(duì)列隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)教學(xué)內(nèi)容：闡述鏈隊(duì)列的概念，鏈隊(duì)列類(lèi)型

10、的模塊說(shuō)明，隊(duì)列鏈?zhǔn)奖硎镜幕静僮骱瘮?shù)；要求學(xué)生掌握鏈隊(duì)列的概念，理解鏈隊(duì)列類(lèi)型的模塊說(shuō)明，隊(duì)列鏈?zhǔn)奖硎镜幕静僮骱瘮?shù)。3.4.3 循環(huán)隊(duì)列隊(duì)列的順序表示和實(shí)現(xiàn)教學(xué)內(nèi)容：闡述循環(huán)隊(duì)列的概念，循環(huán)隊(duì)列類(lèi)型的模塊說(shuō)明，隊(duì)列循環(huán)表示的基本操作函數(shù)；要求學(xué)生掌握循環(huán)隊(duì)列的概念，理解循環(huán)隊(duì)列類(lèi)型的模塊說(shuō)明，隊(duì)列循環(huán)表示的基本操作函數(shù)。 3.4 離散事件模擬 （0.25學(xué)時(shí)）教學(xué)內(nèi)容：闡述使用有序鏈表和隊(duì)列這兩種數(shù)據(jù)類(lèi)型做離散事件模擬的算法；要求學(xué)生理解包含有序鏈表和隊(duì)列的事件模擬程序。第4章 串 （共3學(xué)時(shí)） 4.1 串類(lèi)型的定義 （0.5學(xué)時(shí)）教學(xué)內(nèi)容：闡述串產(chǎn)生的背景，串的概念，串長(zhǎng)度、空串、子串、

11、主串、位置、空格串等概念，串的抽象數(shù)據(jù)類(lèi)型定義，串的基本操作集概念；要求學(xué)生掌握串及相關(guān)的概念，理解串的抽象數(shù)據(jù)類(lèi)型定義。 4.2 串的表示和實(shí)現(xiàn)（重點(diǎn)） （1.5學(xué)時(shí)）4.2.1 定長(zhǎng)順序存儲(chǔ)表示教學(xué)內(nèi)容：闡述串在機(jī)內(nèi)的定長(zhǎng)順序表示，在這種存儲(chǔ)結(jié)構(gòu)表示時(shí)如何實(shí)現(xiàn)串的連接操作和子串操作；要求學(xué)生掌握串的定長(zhǎng)順序存儲(chǔ)表示，理解在定長(zhǎng)順序存儲(chǔ)結(jié)構(gòu)表示時(shí)實(shí)現(xiàn)串的連接操作和子串操作的方法。4.2.2 堆分配存儲(chǔ)表示教學(xué)內(nèi)容：闡述串的堆分配存儲(chǔ)表示，在這種存儲(chǔ)結(jié)構(gòu)表示時(shí)如何實(shí)現(xiàn)串的插入操作；要求學(xué)生掌握串的堆分配存儲(chǔ)表示，理解在堆分配存儲(chǔ)結(jié)構(gòu)表示時(shí)實(shí)現(xiàn)串的插入操作4.2.3 串的塊鏈存儲(chǔ)表示教學(xué)內(nèi)容：闡

12、述串的塊鏈存儲(chǔ)表示；要求學(xué)生掌握串的塊鏈存儲(chǔ)表示。 4.3 串的模式匹配算法 （0.75學(xué)時(shí)）4.3.1 求子串位置的定位函數(shù)教學(xué)內(nèi)容：闡述定位操作、匹配、模式匹配、模式串等概念，求子串位置的定位函數(shù)；要求學(xué)生掌握模式匹配的概念，熟悉求子串位置的定位函數(shù)。4.3.2 模式匹配的一種改進(jìn)算法教學(xué)內(nèi)容：闡述克努特莫里斯普拉特（kmp）模式匹配算法；要求學(xué)生熟悉kmp模式匹配算法。 4.4 串操作應(yīng)用舉例 （0.25學(xué)時(shí)）4.4.1 文本編輯教學(xué)內(nèi)容：闡述文本編輯是修改字符數(shù)據(jù)的形式或格式，在文本編輯中使用串操作；要求學(xué)生理解文本編輯中串的用法。4.4.2 建立詞索引表教學(xué)內(nèi)容：闡述使用串建立詞索引

13、表的方法，詞索引表插入的實(shí)現(xiàn)算法；要求學(xué)生理解建立詞索引表中串的用法。第5章 數(shù)組和廣義表 （共5學(xué)時(shí)） 5.1 數(shù)組的定義 （0.5學(xué)時(shí)）教學(xué)內(nèi)容：闡述抽象數(shù)據(jù)類(lèi)型數(shù)組的定義；要求學(xué)生掌握抽象數(shù)據(jù)類(lèi)型數(shù)組的定義。 5.2數(shù)組的順序表示和實(shí)現(xiàn)（重點(diǎn)） （1.5學(xué)時(shí)）教學(xué)內(nèi)容：闡述數(shù)組的順序存儲(chǔ)結(jié)構(gòu)，以列序?yàn)橹餍虻亩S數(shù)組存儲(chǔ)方式，以行序?yàn)橹餍虻亩S數(shù)組存儲(chǔ)方式，n維數(shù)組的數(shù)據(jù)元素存儲(chǔ)位置的計(jì)算；要求學(xué)生掌握數(shù)組的順序表示法。 5.3 矩陣的壓縮存儲(chǔ)（重點(diǎn)） （1.5學(xué)時(shí)）5.3.1 特殊矩陣教學(xué)內(nèi)容：闡述矩陣、壓縮存儲(chǔ)、特殊矩陣的概念，特殊矩陣的壓縮存儲(chǔ)算法；要求學(xué)生掌握壓縮存儲(chǔ)、特殊矩陣的概

14、念，熟悉特殊矩陣的壓縮存儲(chǔ)算法。5.3.2 稀疏矩陣教學(xué)內(nèi)容：闡述稀疏矩陣的概念，稀疏矩陣的壓縮存儲(chǔ)算法，兩個(gè)稀疏矩陣相乘的算法；要求學(xué)生掌握稀疏矩陣的壓縮存儲(chǔ)算法。 5.4 廣義表的定義 （0.5學(xué)時(shí)）教學(xué)內(nèi)容：闡述抽象數(shù)據(jù)類(lèi)型廣義表的定義，列表的3個(gè)重要結(jié)論；要求學(xué)生掌握抽象數(shù)據(jù)類(lèi)型廣義表的定義。 5.5 廣義表的存儲(chǔ)結(jié)構(gòu) （0.5學(xué)時(shí)）教學(xué)內(nèi)容：闡述廣義表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，廣義表的頭尾鏈表存儲(chǔ)表示；要求學(xué)生熟悉廣義表的存儲(chǔ)結(jié)構(gòu)。 5.6 m元多項(xiàng)式的表示 （0.25學(xué)時(shí)）教學(xué)內(nèi)容：闡述廣義表的m元多項(xiàng)式表示，m元多項(xiàng)式的存儲(chǔ)結(jié)構(gòu)示意圖；要求學(xué)生了解廣義表的m元多項(xiàng)式表示。 5.7 廣義表的

15、遞歸算法 （0.25學(xué)時(shí)）5.7.1 求廣義表的深度教學(xué)內(nèi)容：闡述利用分治法進(jìn)行遞歸算法設(shè)計(jì)，求廣義表的深度算法；要求學(xué)生了解廣義表的遞歸算法。5.7.2 復(fù)制廣義表教學(xué)內(nèi)容：闡述復(fù)制廣義表算法；要求學(xué)生了解復(fù)制廣義表的遞歸算法。5.7.3建立廣義表的存儲(chǔ)結(jié)構(gòu)教學(xué)內(nèi)容：闡述建立廣義表的存儲(chǔ)結(jié)構(gòu)的2種分析方法；要求學(xué)生了解建立廣義表的存儲(chǔ)結(jié)構(gòu)的2種方法。第6章 樹(shù)和二叉樹(shù) （共6學(xué)時(shí)） 6.1 樹(shù)的定義和基本術(shù)語(yǔ) （0.5學(xué)時(shí)）教學(xué)內(nèi)容：闡述樹(shù)型結(jié)構(gòu)的背景，樹(shù)、子樹(shù)、結(jié)點(diǎn)、葉子、終端結(jié)點(diǎn)、分支結(jié)點(diǎn)、雙親、孩子、深度、有序樹(shù)、無(wú)序樹(shù)、森林抽象數(shù)據(jù)類(lèi)型樹(shù)的定義,樹(shù)的4種表示法；要求學(xué)生掌握樹(shù)的概念，

16、樹(shù)結(jié)構(gòu)中結(jié)點(diǎn)、葉子、深度等術(shù)語(yǔ)的概念。 6.2 二叉樹(shù)（重點(diǎn)） （1學(xué)時(shí)）6.2.1 二叉樹(shù)的定義教學(xué)內(nèi)容：闡述抽象數(shù)據(jù)類(lèi)型二叉樹(shù)的定義；要求學(xué)生掌握抽象數(shù)據(jù)類(lèi)型二叉樹(shù)的定義。6.2.2 二叉樹(shù)的性質(zhì)教學(xué)內(nèi)容：闡述二叉樹(shù)的5個(gè)重要性質(zhì)；要求學(xué)生掌握二叉樹(shù)的5個(gè)重要性質(zhì)。6.2.3 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)教學(xué)內(nèi)容：闡述二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)，二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)；要求學(xué)生掌握二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)，二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。 6.3 遍歷樹(shù)和線(xiàn)索二叉樹(shù)（重點(diǎn)） （1學(xué)時(shí)）6.3.1 遍歷二叉樹(shù)教學(xué)內(nèi)容：闡述遍歷和遍歷二叉樹(shù)的概念，先序遍歷二叉樹(shù)的操作定義，中序遍歷二叉樹(shù)的操作定義，后序遍歷二叉樹(shù)的操作定義，先

17、序遍歷二叉樹(shù)基本操作的遞歸算法在二叉鏈表上的實(shí)現(xiàn)；要求學(xué)生掌握遍歷和遍歷二叉樹(shù)的概念，熟悉序遍歷二叉樹(shù)基本操作的遞歸算法在二叉鏈表上的實(shí)現(xiàn)。6.3.2 線(xiàn)索二叉樹(shù)教學(xué)內(nèi)容：闡述線(xiàn)索鏈表、線(xiàn)索、線(xiàn)索二叉樹(shù)、線(xiàn)索化的概念，線(xiàn)索二叉樹(shù)及其存儲(chǔ)結(jié)構(gòu)，后序后繼線(xiàn)索二叉樹(shù)；要求學(xué)生掌握線(xiàn)索、線(xiàn)索二叉樹(shù)的概念，熟悉中序線(xiàn)索二叉樹(shù)，中序線(xiàn)索鏈表。 6.4 樹(shù)和森林 （1學(xué)時(shí)）6.4.1 樹(shù)的存儲(chǔ)結(jié)構(gòu)教學(xué)內(nèi)容：闡述樹(shù)的3種常用的鏈表存儲(chǔ)結(jié)構(gòu)，即雙親表示法、二叉樹(shù)表示法、孩子表示法；要求學(xué)生掌握樹(shù)的3種常用的鏈表存儲(chǔ)結(jié)構(gòu)。6.4.2 森林與二叉樹(shù)的轉(zhuǎn)換教學(xué)內(nèi)容：闡述森林與二叉樹(shù)的轉(zhuǎn)換，森林轉(zhuǎn)換成二叉樹(shù)的定義，二叉

18、樹(shù)轉(zhuǎn)換成森林的定義；要求學(xué)生掌握森林轉(zhuǎn)換成二叉樹(shù)的定義，二叉樹(shù)轉(zhuǎn)換成森林的定義。6.4.3 樹(shù)和森林的遍歷教學(xué)內(nèi)容：闡述森林的2種遍歷方法：先序遍歷森林、中序遍歷森林；要求學(xué)生了解森林的2種遍歷方法。 6.5 樹(shù)與等價(jià)問(wèn)題 （0.25學(xué)時(shí)）教學(xué)內(nèi)容：闡述等價(jià)關(guān)系和等價(jià)類(lèi)的定義，等價(jià)問(wèn)題，確定等價(jià)類(lèi)的算法，劃分等價(jià)類(lèi)需對(duì)集合進(jìn)行的3種操作；要求學(xué)生理解等價(jià)關(guān)系和等價(jià)類(lèi)的定義，了解雙親表示法做存儲(chǔ)結(jié)構(gòu)時(shí)查找函數(shù)和歸并操作的實(shí)現(xiàn)算法。 6.6 赫夫曼樹(shù)及其應(yīng)用（重點(diǎn)） （1學(xué)時(shí)）6.6.1 最優(yōu)二叉樹(shù)教學(xué)內(nèi)容：闡述最優(yōu)二叉樹(shù)的概念，構(gòu)造赫夫曼樹(shù)的算法；要求學(xué)生掌握最優(yōu)二叉樹(shù)的概念，構(gòu)造赫夫曼樹(shù)的算法

19、。6.6.2 赫夫曼編碼教學(xué)內(nèi)容：闡述赫夫曼編碼的定義，赫夫曼和赫夫曼編碼的存儲(chǔ)表示；要求學(xué)生掌握赫夫曼編碼的定義，赫夫曼和赫夫曼編碼的存儲(chǔ)表示。 6.7 回溯法與樹(shù)的遍歷 （1學(xué)時(shí)）教學(xué)內(nèi)容：闡述回溯法的定義，遍歷狀態(tài)樹(shù)的算法；要求學(xué)生理解回溯法的定義和遍歷狀態(tài)樹(shù)的算法。 6.8 樹(shù)的計(jì)數(shù) （0.25學(xué)時(shí)）教學(xué)內(nèi)容：闡述二叉樹(shù)相似和等價(jià)的概念，二叉樹(shù)的計(jì)數(shù)問(wèn)題定義，由前序和中序序列構(gòu)造一棵二叉樹(shù)的過(guò)程；要求學(xué)生熟悉二叉樹(shù)相似和等價(jià)的概念，二叉樹(shù)的計(jì)數(shù)問(wèn)題定義。第7章 圖 （共5學(xué)時(shí)） 7.1 圖的定義和術(shù)語(yǔ) （1學(xué)時(shí)）教學(xué)內(nèi)容：闡述圖的概念，抽象數(shù)據(jù)類(lèi)型圖的定義，頂點(diǎn)、弧、有向圖、無(wú)向圖、完

20、全圖、有向完全圖、稀疏圖、稠密圖、權(quán)、網(wǎng)、子圖、鄰接點(diǎn)、入度、出度、路徑、回路、簡(jiǎn)單路徑、連通、連通圖、連通分量、強(qiáng)連通圖、生成樹(shù)、生成森林等概念；要求學(xué)生掌握?qǐng)D以及與圖有關(guān)名詞的定義、掌握抽象數(shù)據(jù)類(lèi)型圖的定義。 7.2 圖的存儲(chǔ)結(jié)構(gòu)（重點(diǎn)） （1學(xué)時(shí)）7.2.1 數(shù)組表示法教學(xué)內(nèi)容：闡述圖的多重鏈表，圖的數(shù)組表示法，網(wǎng)及其鄰接矩陣；要求學(xué)生掌握?qǐng)D的多重鏈表，熟悉圖的數(shù)組表示法。7.2.2 鄰接表教學(xué)內(nèi)容：闡述圖的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鄰接表、逆鄰接表；要求學(xué)生掌握?qǐng)D的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鄰接表。7.2.3 十字鏈表教學(xué)內(nèi)容：闡述有向圖的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)十字鏈表；要求學(xué)生掌握有向圖的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)十字鏈表。7.2.4

21、 鄰接多重表教學(xué)內(nèi)容：闡述無(wú)向圖的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鄰接多重表；要求學(xué)生掌握無(wú)向圖的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鄰接多重表。 7.3 圖的遍歷（重點(diǎn)） （1學(xué)時(shí)）7.3.1 深度優(yōu)先搜索教學(xué)內(nèi)容：闡述圖的遍歷概念，遍歷圖的路徑深度優(yōu)先搜索；要求學(xué)生掌握深度優(yōu)先搜索過(guò)程。7.3.2 廣度優(yōu)先搜索教學(xué)內(nèi)容：闡述遍歷圖的路徑廣度優(yōu)先搜索；要求學(xué)生掌握廣度優(yōu)先搜索過(guò)程。 7.4 圖的連通問(wèn)題 （1學(xué)時(shí)）7.4.1 無(wú)向圖的連通分量和生成樹(shù)教學(xué)內(nèi)容：闡述利用遍歷圖的算法求解連通和非連通無(wú)向圖的連通性問(wèn)題，無(wú)向圖的連通分量和生成樹(shù)的構(gòu)成方式；要求學(xué)生熟悉無(wú)向圖的連通分量和生成樹(shù)的構(gòu)成方式。7.4.2 有向圖的強(qiáng)連通分量教學(xué)內(nèi)容

22、：闡述求解有向圖的強(qiáng)連通分量的步驟；要求學(xué)生熟悉求解有向圖的強(qiáng)連通分量的步驟。7.4.3 最小生成樹(shù)教學(xué)內(nèi)容：闡述最小生成樹(shù)問(wèn)題的概念，構(gòu)造最小生成樹(shù)的普里姆算法、克魯斯卡爾算法；要求學(xué)生熟悉構(gòu)造最小生成樹(shù)的普里姆算法。7.4.4 關(guān)節(jié)點(diǎn)和重連通分量教學(xué)內(nèi)容：闡述關(guān)節(jié)點(diǎn)、重連通圖和重連通分量的概念，由深度優(yōu)先生成樹(shù)得出2類(lèi)關(guān)節(jié)點(diǎn)的特性；要求學(xué)生熟悉關(guān)節(jié)點(diǎn)、重連通圖和重連通分量的概念，了解2類(lèi)關(guān)節(jié)點(diǎn)的特性。 7.5 有向無(wú)環(huán)圖及其應(yīng)用 （0.5學(xué)時(shí)）7.5.1 拓?fù)渑判蚪虒W(xué)內(nèi)容：闡述有向無(wú)環(huán)dag圖的定義，在描述表達(dá)式時(shí)與二叉樹(shù)的區(qū)別，拓?fù)渑判?、偏序、全序、拓?fù)溆行虻母拍睿負(fù)渑判虻乃惴?；要求學(xué)

23、生掌握有向無(wú)環(huán)dag圖的定義，熟悉拓?fù)渑判?、偏序、全序、拓?fù)溆行虻母拍睢?.5.2 關(guān)鍵路徑教學(xué)內(nèi)容：闡述aoe網(wǎng)，關(guān)鍵路徑的算法；要求學(xué)生熟悉aoe網(wǎng)的概念，了解關(guān)鍵路徑的算法。 7.6 最短路徑 （0.5學(xué)時(shí)）7.6.1 從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑教學(xué)內(nèi)容：闡述源點(diǎn)、終點(diǎn)的概念，分析帶權(quán)有向圖中從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑問(wèn)題，講解針對(duì)此問(wèn)題的用c語(yǔ)言描述的迪杰斯特拉算法；要求學(xué)生了解從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑問(wèn)題，了解迪杰斯特拉算法。7.6.2 每一對(duì)頂點(diǎn)之間的最短路徑教學(xué)內(nèi)容：分析帶權(quán)有向圖中每一對(duì)頂點(diǎn)之間的最短路徑問(wèn)題，講解針對(duì)此問(wèn)題的弗洛伊德算法；要求學(xué)生了解帶權(quán)有

24、向圖中每一對(duì)頂點(diǎn)之間的最短路徑問(wèn)題，了解弗洛伊德算法。第8章 動(dòng)態(tài)存儲(chǔ)管理 （共3學(xué)時(shí)） 8.1 概述 （0.25學(xué)時(shí)）教學(xué)內(nèi)容：闡述動(dòng)態(tài)存儲(chǔ)管理的基本問(wèn)題是系統(tǒng)如何應(yīng)用戶(hù)提出的請(qǐng)求分配內(nèi)存；要求學(xué)生理解動(dòng)態(tài)存儲(chǔ)管理的基本問(wèn)題。 8.2 可利用空間表及分配方法 （0.25學(xué)時(shí)）教學(xué)內(nèi)容：闡述使用可利用空間表進(jìn)行動(dòng)態(tài)存儲(chǔ)分配的方法，可利用空間表的3種不同的結(jié)構(gòu)形式，即系統(tǒng)運(yùn)行期間所有用戶(hù)請(qǐng)求分配的存儲(chǔ)量大小相同、存儲(chǔ)量有若干種規(guī)格、分配給用戶(hù)的內(nèi)存塊的大小不固定可以隨請(qǐng)求而變，空間表中空閑塊的3種分配策略，即首次擬合法、最佳擬合法、最差擬合法；要求學(xué)生了解使用可利用空間表進(jìn)行動(dòng)態(tài)存儲(chǔ)分配的方法的

25、方法。 8.3 邊界標(biāo)識(shí)法 （1學(xué)時(shí)）8.3.1 可利用空間表的結(jié)構(gòu)教學(xué)內(nèi)容：闡述邊界標(biāo)識(shí)法的定義，可利用空間表的結(jié)構(gòu)；要求學(xué)生了解邊界標(biāo)識(shí)法的定義，可利用空間表的結(jié)構(gòu)。8.3.2 分配算法教學(xué)內(nèi)容：闡述可利用空間表的分配算法；要求學(xué)生了解可利用空間表的分配算法。8.3.3 回收算法教學(xué)內(nèi)容：闡述可利用空間表的回收算法；要求學(xué)生了解可利用空間表的回收算法。 8.4 伙伴系統(tǒng) （1學(xué)時(shí)）8.4.1 可利用空間表的結(jié)構(gòu)教學(xué)內(nèi)容：闡述動(dòng)態(tài)存儲(chǔ)管理方法伙伴系統(tǒng)，伙伴關(guān)系下的可利用空間表的結(jié)構(gòu)；要求學(xué)生了解動(dòng)態(tài)存儲(chǔ)管理方法伙伴系統(tǒng)、伙伴關(guān)系下的可利用空間表的結(jié)構(gòu)。8.4.2 分配算法教學(xué)內(nèi)容：闡述可利用

26、空間表的分配算法；要求學(xué)生了解可利用空間表的分配算法。8.4.3 回收算法教學(xué)內(nèi)容：闡述伙伴關(guān)系下回收算法；要求學(xué)生了解伙伴關(guān)系下回收算法。 8.5 無(wú)用單元收集 （0.25學(xué)時(shí)）教學(xué)內(nèi)容：闡述無(wú)用單元的概念，無(wú)用單元收集的2條途徑，即收集訪(fǎng)問(wèn)計(jì)數(shù)器、收集無(wú)用單元，3種標(biāo)志算法，即遞歸算法、非遞歸算法、利用表結(jié)點(diǎn)本身的指針域標(biāo)記遍歷路徑的算法；要求學(xué)生建立無(wú)用單元收集的概念。 8.6 存儲(chǔ)緊縮 （0.25學(xué)時(shí)）教學(xué)內(nèi)容：闡述存儲(chǔ)緊縮的概念，2種回收緊縮的方式；要求學(xué)生了解存儲(chǔ)緊縮的概念和2種回收緊縮的方式。第9章 查找 （共4學(xué)時(shí)） 9.1 靜態(tài)查找表（重點(diǎn)） （1.5學(xué)時(shí)）9.1.1 順序表

27、的查找教學(xué)內(nèi)容：闡述查找表的概念，動(dòng)態(tài)查找表、關(guān)鍵字、查找的概念，抽象數(shù)據(jù)類(lèi)型靜態(tài)查找表的定義，順序表的查找實(shí)現(xiàn)；要求學(xué)生掌握查找表的概念，動(dòng)態(tài)查找表、關(guān)鍵字、查找的概念，順序表的查找實(shí)現(xiàn)。9.1.2 有序表的查找教學(xué)內(nèi)容：闡述有序表的折半查找實(shí)現(xiàn)，查找操作的性能分析，折半查找的性能分析；要求學(xué)生掌握有序表的折半查找實(shí)現(xiàn)。9.1.3 靜態(tài)樹(shù)表的查找教學(xué)內(nèi)容：闡述靜態(tài)樹(shù)表的查找，靜態(tài)最優(yōu)查找樹(shù)的概念；要求學(xué)生掌握靜態(tài)最優(yōu)查找樹(shù)的概念。9.1.4 索引順序表的查找教學(xué)內(nèi)容：闡述索引順序表的分塊查找算法；要求學(xué)生了解索引順序表的分塊查找算法。 9.2 動(dòng)態(tài)查找表（重點(diǎn)） （1學(xué)時(shí)）9.2.1 二叉排

28、序樹(shù)和平衡二叉樹(shù)教學(xué)內(nèi)容：闡述動(dòng)態(tài)查找表的特點(diǎn)，抽象數(shù)據(jù)類(lèi)型動(dòng)態(tài)查找表的定義，二叉排序樹(shù)的概念，二叉排序樹(shù)的查找過(guò)程，二叉排序樹(shù)的插入和刪除，平衡二叉樹(shù)（avl）的概念，平衡樹(shù)的生成過(guò)程，二叉排序樹(shù)的平衡旋轉(zhuǎn)圖例；要求學(xué)生掌握抽象數(shù)據(jù)類(lèi)型動(dòng)態(tài)查找表的定義，二叉排序樹(shù)的概念，二叉排序樹(shù)的查找過(guò)程，平衡二叉樹(shù)（avl）的概念。9.2.2 b樹(shù)和b樹(shù)教學(xué)內(nèi)容：闡述b樹(shù)的概念，b樹(shù)查找分析，b樹(shù)的插入和刪除，b+樹(shù)的概念；要求學(xué)生掌握抽象數(shù)據(jù)類(lèi)型動(dòng)態(tài)查找表的定義，二叉排序樹(shù)的概念，二叉排序樹(shù)的查找過(guò)程，平衡二叉樹(shù)（avl）的概念，b樹(shù)的概念，b樹(shù)查找分析，b+樹(shù)的概念。9.2.3 鍵樹(shù)教學(xué)內(nèi)容：闡述數(shù)

29、字查找樹(shù)的概念，數(shù)字查找樹(shù)的2種存儲(chǔ)結(jié)構(gòu)，在雙鏈樹(shù)中查找記錄的操作算法，trie樹(shù)的查找算法；要求學(xué)生掌握數(shù)字查找樹(shù)的概念，了解鍵樹(shù)的2種存儲(chǔ)結(jié)構(gòu)，了解trie樹(shù)的查找算法。 9.3 哈希表（重點(diǎn)） （1.5學(xué)時(shí)）9.3.1 什么是哈希表教學(xué)內(nèi)容：闡述哈希表、哈希函數(shù)的概念；要求學(xué)生掌握哈希表、哈希函數(shù)的概念。9.3.2 哈希函數(shù)的構(gòu)造方法教學(xué)內(nèi)容：闡述哈希函數(shù)的6種構(gòu)造方法：即直接定址法、數(shù)字分析法、平方取中法、折疊法、除留余數(shù)法和隨機(jī)數(shù)法；要求學(xué)生熟悉哈希函數(shù)的6種構(gòu)造方法，即直接定址法、數(shù)字分析法、平方取中法、折疊法、除留余數(shù)法和隨機(jī)數(shù)法。9.3.3 處理沖突的方法教學(xué)內(nèi)容：闡述哈希造表

30、處理沖突的4種方法，即開(kāi)放地址法、再哈希法、鏈地址法和建立一個(gè)公共溢出區(qū)；要求學(xué)生哈希造表處理沖突的4種方法，即開(kāi)放地址法、再哈希法、鏈地址法和建立一個(gè)公共溢出區(qū)。9.3.4 哈希表的查找及其分析教學(xué)內(nèi)容：闡述以開(kāi)放定址等方法處理沖突的哈希表的查找算法，哈希表查找的分析；要求學(xué)生熟悉以開(kāi)放定址等方法處理沖突的哈希表的查找算法。第10章 內(nèi)部排序 （共6學(xué)時(shí)） 10.1 概述 （0.5學(xué)時(shí)）教學(xué)內(nèi)容：闡述排序的概念，內(nèi)部排序和外部排序的概念；要求學(xué)生建立排序的概念。 10.2 插入排序（重點(diǎn)） （1.5學(xué)時(shí)）10.2.1 直接插入排序教學(xué)內(nèi)容：闡述直接插入排序的概念，直接插入排序的算法；要求學(xué)生

31、掌握直接插入排序的改建，了解直接插入排序的算法。10.2.2 其它插入排序教學(xué)內(nèi)容：闡述折半插入排序的概念和算法，2路插入排序的概念和算法；要求學(xué)生了解折半插入排序的概念和算法，2路插入排序的概念和算法。10.2.3 希爾排序教學(xué)內(nèi)容：闡述希爾排序的概念和算法，縮小增量排序的序列特點(diǎn)；要求學(xué)生了解希爾排序的概念和算法，了解縮小增量排序的序列特點(diǎn)。 10.3 快速排序 （1學(xué)時(shí)）教學(xué)內(nèi)容：闡述起泡排序的概念和算法，快速排序的概念和算法；要求學(xué)生掌握起泡排序的概念和算法，了解快速排序的概念和算法。 10.4 選擇排序（重點(diǎn)） （1.5學(xué)時(shí)）10.4.1 簡(jiǎn)單排序選擇教學(xué)內(nèi)容：闡述選擇排序的的基本思

32、想，簡(jiǎn)單選擇排序算法；要求學(xué)生掌握選擇排序的的基本思想，了解簡(jiǎn)單選擇排序算法。10.4.2 樹(shù)形選擇排序教學(xué)內(nèi)容：闡述樹(shù)形選擇排序示例；要求學(xué)生了解樹(shù)形選擇排序。10.4.3 堆排序教學(xué)內(nèi)容：闡述堆排序的概念，堆的定義，堆排序的算法；要求學(xué)生了解堆排序的概念，堆的定義，堆排序的算法。 10.5 歸并排序 （0.5學(xué)時(shí)）教學(xué)內(nèi)容：闡述歸并排序的概念和算法；要求學(xué)生了解歸并排序的概念和算法。 10.6 基數(shù)排序 （0.5學(xué)時(shí)）10.6.1 多關(guān)鍵字排序教學(xué)內(nèi)容：闡述基數(shù)排序的概念，多關(guān)鍵字排序問(wèn)題；要求學(xué)生了解基數(shù)排序的概念，多關(guān)鍵字排序問(wèn)題。10.6.2 鏈?zhǔn)交鶖?shù)排序教學(xué)內(nèi)容：闡述鏈?zhǔn)交鶖?shù)排序方

33、法；要求學(xué)生了解鏈?zhǔn)交鶖?shù)排序方法。 10.7 各種內(nèi)部排序方法的比較討論 （0.5學(xué)時(shí)）教學(xué)內(nèi)容：闡述各種內(nèi)部排序方法的優(yōu)劣；要求學(xué)生了解各種內(nèi)部排序方法的優(yōu)劣。第11章 外部排序 （共2學(xué)時(shí)） 11.1 外存信息的存取 （0.5學(xué)時(shí)）教學(xué)內(nèi)容：闡述磁帶信息的存取方式，磁盤(pán)信息的存取方法；要求學(xué)生了解磁帶信息的存取方式，磁盤(pán)信息的存取方法。 11.2 外部排序的方法 （0.75學(xué)時(shí)）教學(xué)內(nèi)容：闡述2路平衡歸并的外部排序法；令學(xué)生了解2路平衡歸并的外部排序法。 11.3 多路平衡歸并的實(shí)現(xiàn) （0.25學(xué)時(shí)）教學(xué)內(nèi)容：描述多路平衡歸并的敗者樹(shù)圖；要求學(xué)生了解多路平衡歸并的敗者樹(shù)圖。 11.4 置換選擇排序 （0.25學(xué)時(shí)）教學(xué)內(nèi)容：闡述置