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

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

課程代碼：********。

課程負(fù)責(zé)人：********。

課程中文名稱：數(shù)據(jù)結(jié)構(gòu)。

課程英文名稱：DataStructures。

課程類別：專業(yè)基礎(chǔ)課必修.

課程學(xué)分?jǐn)?shù)：3。

課程學(xué)時數(shù)：講課32/48學(xué)時，上機(jī)32學(xué)時。

授課對象：計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)。

本課程的前導(dǎo)課程：高級語言程序設(shè)計(jì)。

本課程的后續(xù)課程：操作系統(tǒng)、數(shù)據(jù)庫應(yīng)用技術(shù)等?

一'教學(xué)目的

《數(shù)據(jù)結(jié)構(gòu)》是計(jì)算機(jī)專業(yè)一門重要的專業(yè)基礎(chǔ)課。通過本課程的學(xué)習(xí)，使得學(xué)生從數(shù)

據(jù)邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和基本運(yùn)算算法設(shè)計(jì)三個層面掌握基本的數(shù)據(jù)組織和數(shù)據(jù)處理方法，

能夠從問題出發(fā)設(shè)計(jì)面向數(shù)據(jù)結(jié)構(gòu)的求解算法，并能夠?qū)λ惴ㄟM(jìn)行時間復(fù)雜度與空間復(fù)雜度

分析。為后續(xù)課程如操作系統(tǒng)等課程學(xué)習(xí)打下基礎(chǔ)。

二、教學(xué)要求

通過講授和上機(jī)實(shí)驗(yàn)，使學(xué)生了解《數(shù)據(jù)結(jié)構(gòu)》的原理和特點(diǎn)。掌握線性表、棧和隊(duì)列、

串、數(shù)組和稀疏矩陣、樹和二叉樹、圖、查找和排序等基本數(shù)據(jù)結(jié)構(gòu)及其相關(guān)算法的設(shè)計(jì)。

具備一定的利用數(shù)據(jù)結(jié)構(gòu)方法求解實(shí)際問題的能力。

三、課程知識點(diǎn)

知識單元知識點(diǎn)名稱知識點(diǎn)內(nèi)容知識點(diǎn)類型備注

數(shù)據(jù)結(jié)構(gòu)的基認(rèn)識數(shù)據(jù)結(jié)構(gòu)的定義、包括數(shù)據(jù)邏輯結(jié)

一般知識點(diǎn)

本概念構(gòu)、存儲結(jié)構(gòu)和運(yùn)算的3個層次。

算法的基本概

認(rèn)識算法的定義和5個基本特性。重要知識點(diǎn)

念

數(shù)據(jù)結(jié)構(gòu)算法描述認(rèn)識用高級語言如C/C++描述算法的自我

一般知識點(diǎn)

概述基本方法。學(xué)習(xí)

算法分析掌握算法的時間復(fù)雜度和空間復(fù)雜度

重要知識點(diǎn)

分析方法。

數(shù)據(jù)結(jié)構(gòu)+算認(rèn)識從數(shù)據(jù)結(jié)構(gòu)角度求解問題的基本

重要知識點(diǎn)

法=程序步驟。

線性表及其邏認(rèn)識線性表的定義和線性表的基本運(yùn)

一般知識點(diǎn)

輯結(jié)構(gòu)算。

線性表的順序

掌握順序表的存儲結(jié)構(gòu)特點(diǎn)和順序表

存儲結(jié)構(gòu)一順重要知識點(diǎn)

基本運(yùn)算的實(shí)現(xiàn)。

序表

線性表的鏈?zhǔn)秸莆諉捂湵淼拇鎯Y(jié)構(gòu)特點(diǎn)、單鏈表的

存儲結(jié)構(gòu)一單插入和刪除節(jié)點(diǎn)操作、單鏈表的建表方重要知識點(diǎn)

鏈表法、以及單鏈表基本運(yùn)算的實(shí)現(xiàn)。

線性表線性表的鏈?zhǔn)秸莆针p鏈表的存儲結(jié)構(gòu)特點(diǎn)、雙鏈表的

存儲結(jié)構(gòu)一雙插入和刪除節(jié)點(diǎn)操作、雙鏈表的建表方重要知識點(diǎn)

鏈表法、以及雙鏈表基本運(yùn)算的實(shí)現(xiàn)。

掌握循環(huán)鏈表的存儲結(jié)構(gòu)特點(diǎn)、循環(huán)鏈

線性表的鏈?zhǔn)?/p>

表的插入和刪除節(jié)點(diǎn)操作、循環(huán)鏈表的

存儲結(jié)構(gòu)一循重要知識點(diǎn)

建表方法、以及循環(huán)鏈表基本運(yùn)算的實(shí)

環(huán)鏈表

現(xiàn)。

掌握從求解問題描述、數(shù)據(jù)組織到運(yùn)算

線性表的應(yīng)用難度知識點(diǎn)

算法設(shè)計(jì)完整過程。

了解棧的定義、棧的邏輯結(jié)構(gòu)特性和棧

棧的基本概念一般知識點(diǎn)

的基本運(yùn)算。

棧的順序存儲掌握順序棧的存儲結(jié)構(gòu)特點(diǎn)和順序棧

重要知識點(diǎn)

棧結(jié)構(gòu)-順序?；具\(yùn)算的實(shí)現(xiàn)。

棧的鏈?zhǔn)酱鎯φ莆真湕５拇鎯Y(jié)構(gòu)特點(diǎn)和鏈棧基本

重要知識點(diǎn)

結(jié)構(gòu)-鏈棧運(yùn)算的實(shí)現(xiàn)。

棧的應(yīng)用了解棧在表達(dá)式求值中的應(yīng)用。難度知識點(diǎn)

隊(duì)列的基本概了解隊(duì)列的定義、隊(duì)列的邏輯結(jié)構(gòu)特性

一般知識點(diǎn)

念和隊(duì)列的基本運(yùn)算。

隊(duì)列的順序存掌握順序隊(duì)的存儲結(jié)構(gòu)特點(diǎn)和順序隊(duì)

重要知識點(diǎn)

隊(duì)列儲結(jié)構(gòu)-順序隊(duì)基本運(yùn)算的實(shí)現(xiàn)。

隊(duì)列的鏈?zhǔn)酱嬲莆真滉?duì)的存儲結(jié)構(gòu)特點(diǎn)和鏈隊(duì)基本

重要知識點(diǎn)

儲結(jié)構(gòu)-鏈隊(duì)運(yùn)算的實(shí)現(xiàn)。

隊(duì)列的應(yīng)用了解隊(duì)列在病人看病問題中的應(yīng)用。難度知識點(diǎn)

了解串的定義、串的邏輯結(jié)構(gòu)特性和串

串的基本概念一般知識點(diǎn)

的基本運(yùn)算。

串的順序存儲掌握順序串的存儲結(jié)構(gòu)特點(diǎn)和順序串

串一般知識點(diǎn)

結(jié)構(gòu)一順序串基本運(yùn)算的實(shí)現(xiàn)。

串的鏈?zhǔn)酱鎯φ莆真湸拇鎯Y(jié)構(gòu)特點(diǎn)和鏈串基本

一般知識點(diǎn)

結(jié)構(gòu)-鏈串運(yùn)算的實(shí)現(xiàn)。

數(shù)組的基本概

了解數(shù)組的定義和數(shù)組的存儲結(jié)構(gòu)。一般知識點(diǎn)

念

數(shù)組和稀特殊矩陣的壓了解對稱矩陣、上下三角矩陣和對角矩

重要知識點(diǎn)

疏矩陣縮存儲陣的壓縮存儲。

了解稀疏矩陣的特點(diǎn)、稀疏矩陣的三元

稀疏矩陣一般知識點(diǎn)

組表示和十字鏈表表示。

樹樹的基本概念了解樹的定義、樹的邏輯表示方法和樹一般知識點(diǎn)

的基本術(shù)語。

樹的性質(zhì)了解樹的4個性質(zhì)及其應(yīng)用。一般知識點(diǎn)

掌握樹的先根遍歷、后根遍歷和層次遍

樹的基本運(yùn)算一般知識點(diǎn)

歷過程。

掌握樹的雙親存儲結(jié)構(gòu)、孩子鏈存儲結(jié)

樹的存儲結(jié)構(gòu)一般知識點(diǎn)

構(gòu)和孩子兄弟鏈存儲結(jié)構(gòu)以及特點(diǎn)。

了解二叉樹、滿二叉樹和完全二叉樹的

二叉樹的基本

定義、二叉樹的邏輯表示方法和二叉樹一般知識點(diǎn)

概念

的基本術(shù)語。

二叉樹樹的性

了解二叉樹樹的5個性質(zhì)及其應(yīng)用。重要知識點(diǎn)

質(zhì)

二叉樹與樹、

了解森林、樹轉(zhuǎn)換為二叉樹以及二叉樹

森林之間的轉(zhuǎn)一般知識點(diǎn)

還原為森林、樹的過程。

換

二叉樹存儲結(jié)掌握二叉樹的順序存儲結(jié)構(gòu)和二叉樹

重要知識點(diǎn)

構(gòu)的鏈?zhǔn)酱鎯Y(jié)構(gòu)。

二叉樹的基本

掌握二叉樹的基本運(yùn)算及其實(shí)現(xiàn)過程。重要知識點(diǎn)

運(yùn)算及其實(shí)現(xiàn)

二叉樹掌握二叉樹的先序遍歷、中序遍歷、后

序遍歷和層次遍歷算法設(shè)計(jì)，了解先序

二叉樹的遍歷重要知識點(diǎn)

遍歷、中序遍歷和后序遍歷非遞歸算法

設(shè)計(jì)。

二叉樹遍歷應(yīng)掌握二叉樹的4種遍歷在二叉樹算法

難度知識點(diǎn)

用設(shè)計(jì)中的應(yīng)用。

掌握由先序遍歷、中序遍歷序列構(gòu)造二

二叉樹的構(gòu)造叉樹和由后序遍歷、中序遍歷序列構(gòu)造一般知識點(diǎn)

二叉樹的過程.

了解線索二叉樹的概念、線索二叉樹的

線索二叉樹一般知識點(diǎn)

構(gòu)造和遍歷過程。

掌握哈夫曼樹的概念、構(gòu)造哈夫曼樹和

哈夫曼樹一般知識點(diǎn)

產(chǎn)生哈夫曼編碼的過程。

圖的基本概念了解圖的定義和圖的基本術(shù)語。一般知識點(diǎn)

掌握圖的鄰接矩陣存儲方法和鄰接表

圖的存儲結(jié)構(gòu)重要知識點(diǎn)

表存儲方法。

掌握圖深度優(yōu)先搜索遍歷和廣度優(yōu)先

圖的遍歷重要知識點(diǎn)

搜索遍歷算法。

圖遍歷算法的掌握圖的兩種遍歷算法在圖算法設(shè)計(jì)

難度知識點(diǎn)

圖應(yīng)用中的應(yīng)用。

了解生成樹和最小生成樹的概念，掌握

生成樹和最小

構(gòu)造最小生成樹的普里姆算法和克魯重要知識點(diǎn)

生成樹

斯卡爾算法。

了解最短路徑的概念,掌握構(gòu)造最短路

最短路徑重要知識點(diǎn)

徑的狄克斯特拉算法和弗洛伊德算法。

拓?fù)渑判蛄私馔負(fù)渑判虻母拍詈屯負(fù)渑判蜻^程。一般知識點(diǎn)

AOE網(wǎng)與關(guān)鍵了解AOE網(wǎng)與關(guān)鍵路徑的概念、求解

一般知識點(diǎn)

路徑關(guān)鍵路徑的過程。

查找的基本概

查找表和平均查找長度ASL的定義。一般知識點(diǎn)

念

掌握順序查找、折半查找和分塊查找算

線性表的查找重要知識點(diǎn)

法設(shè)計(jì)和算法分析。

掌握二叉排序樹的算法設(shè)計(jì)。重要知識點(diǎn)

查找

樹表的查找了解平衡二叉樹、B和B+樹的組織和

一般知識點(diǎn)

查找過程。

掌握哈希表的基本概念、哈希函數(shù)構(gòu)造

哈希表查找方法、哈希沖突解決方法和哈希查找過重要知識點(diǎn)

程。

排序的基本概了解排序算法的穩(wěn)定性、排序算法的分

一般知識點(diǎn)

念類。

掌握直接插入排序算法的思路、排序算

法和算法分析，折半插入排序算法的思

插入排序重要知識點(diǎn)

路、排序算法和算法分析，希爾排序算

法的思路、排序算法和算法分析。

掌握冒泡排序算法的思路、排序算法和

交換排序算法分析，快速排序算法的思路、排序重要知識點(diǎn)

算法和算法分析。

掌握直接選擇排序算法的思路、排序算

選擇排序法和算法分析，堆排序算法的思路、排重要知識點(diǎn)

排序序算法和算法分析。

掌握歸并排序算法的思路，二路歸并算

歸并排序重要知識點(diǎn)

法和算法分析。

掌握基數(shù)排序算法的思路、排序算法和

基數(shù)排序重要知識點(diǎn)

算法分析。

各種內(nèi)排序方

掌握各種內(nèi)排序方法時間和空間因素

法的比較和選難度知識點(diǎn)

的比較和分析。

擇

外排序的基本

了解外排序概念和外排序的一般過程。一般知識點(diǎn)

概念

掌握磁盤排序中生成初始?xì)w并段、多路

磁盤排序重要知識點(diǎn)

平衡歸并和構(gòu)造最佳歸并樹的過程。

四'課程能力點(diǎn)

能力單元能力點(diǎn)名稱能力點(diǎn)要求能力點(diǎn)類型備注

掌握從數(shù)據(jù)邏輯結(jié)構(gòu)到存儲結(jié)構(gòu)的

映射關(guān)系，算法的時間復(fù)雜度和空

面向數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)算法

間復(fù)雜度分析，使學(xué)生能夠從數(shù)據(jù)思維能力點(diǎn)

的算法設(shè)計(jì)設(shè)計(jì)流程

結(jié)構(gòu)角度出發(fā)，掌握從邏輯結(jié)構(gòu)一

存儲結(jié)構(gòu)f基本運(yùn)算算法設(shè)計(jì)的流

程，并通過設(shè)計(jì)合理的存儲結(jié)構(gòu)來

設(shè)計(jì)出好算法的過程。

掌握線性表的順序存儲結(jié)構(gòu)和鏈?zhǔn)?/p>

線性表算法設(shè)

存儲結(jié)構(gòu)中線性表基本運(yùn)算算法設(shè)設(shè)計(jì)能力點(diǎn)

計(jì)

計(jì)方法。

線性表

掌握線性表的邏輯結(jié)構(gòu)f存儲結(jié)構(gòu)

線性表應(yīng)用一運(yùn)算算法設(shè)計(jì)的主線，利用線性設(shè)計(jì)能力點(diǎn)

表求解實(shí)際應(yīng)用問題。

掌握棧的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯?/p>

棧算法設(shè)計(jì)設(shè)計(jì)能力點(diǎn)

結(jié)構(gòu)中?；具\(yùn)算算法設(shè)計(jì)方法。

掌握隊(duì)列的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱?/p>

隊(duì)列算法設(shè)計(jì)儲結(jié)構(gòu)中隊(duì)列基本運(yùn)算算法設(shè)計(jì)方設(shè)計(jì)能力點(diǎn)

棧和隊(duì)列法。

掌握棧在實(shí)際求解問題中的應(yīng)用方

棧的應(yīng)用設(shè)計(jì)能力點(diǎn)

法。

掌握隊(duì)列在實(shí)際求解問題中的應(yīng)用

隊(duì)列的應(yīng)用設(shè)計(jì)能力點(diǎn)

方法。

掌握二叉樹、滿二叉樹和完全二叉

二叉樹結(jié)構(gòu)思維能力點(diǎn)

樹的性質(zhì)和結(jié)點(diǎn)計(jì)算。

二叉樹遍歷算掌握二叉樹4種遍歷算法設(shè)計(jì)

二叉樹設(shè)計(jì)能力點(diǎn)

法設(shè)計(jì)

二叉樹遍歷算掌握基于二叉樹遍歷的二叉樹遞歸

設(shè)計(jì)能力點(diǎn)

法的應(yīng)用算法設(shè)計(jì)

圖遍歷算法設(shè)

掌握基于兩種圖遍歷的圖算法設(shè)計(jì)設(shè)計(jì)能力點(diǎn)

il-

圖掌握求最小生成樹的Prim和

圖的應(yīng)用Kruskal算法和求最短路徑的設(shè)計(jì)能力點(diǎn)

Dijkstra和Flody算法。

掌握順序查找、折半查找、二叉排

查找算法設(shè)計(jì)思維能力點(diǎn)

序樹和哈希表查找算法。

查找

基于不同的數(shù)據(jù)結(jié)構(gòu)選擇合適的查

查找的應(yīng)用設(shè)計(jì)能力點(diǎn)

找算法求解問題。

掌握直接插入排序、折半插入排序、

內(nèi)排序算法設(shè)希爾排序、冒泡排序、快速排序、

思維能力點(diǎn)

計(jì)簡單選擇排序、堆排序、二路歸并

排序

排序和基數(shù)排序算法。

基于不同的要求選擇合適的內(nèi)排序

內(nèi)排序的應(yīng)用設(shè)計(jì)能力點(diǎn)

算法求解問題。

五、授課課時安排（32/48課時）

授課

知識單元涵蓋知識點(diǎn)情況授課目標(biāo)重難點(diǎn)要求備注

課時

目標(biāo)：①數(shù)據(jù)結(jié)構(gòu)的基本概念，②數(shù)

據(jù)邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)的映射關(guān)系，

③數(shù)據(jù)類型和數(shù)據(jù)結(jié)構(gòu)的區(qū)別和聯(lián)

系，④利用抽象數(shù)據(jù)類型表述求解問

題的方法，⑤算法的特性和采用

數(shù)據(jù)結(jié)構(gòu)的基本概念；

C/C++語言描述算法的方法，⑥算法

算法的基本概念；算法

1、緒論2/2設(shè)計(jì)目標(biāo)和分析方法，包括時間復(fù)雜

描述；算法分析；數(shù)據(jù)

度和空間復(fù)雜度分析，⑦從數(shù)據(jù)結(jié)構(gòu)

結(jié)構(gòu)+算法=程序

的角度設(shè)計(jì)好算法的過程。

重點(diǎn)和難點(diǎn)：①算法的時間和空間復(fù)

雜度分析，特別是遞歸算法的時間和

空間復(fù)雜度分析，②如何設(shè)計(jì)好的算

法。

線性表及其邏輯結(jié)構(gòu)；目標(biāo)：①線性表的邏輯結(jié)構(gòu)特點(diǎn)和線

線性表的順序存儲結(jié)性表抽象數(shù)據(jù)類型的描述方法，②線

構(gòu)一順序表；線性表的性表的兩類存儲結(jié)構(gòu)設(shè)計(jì)方法以及

鏈?zhǔn)酱鎯Y(jié)構(gòu)一單鏈各自的優(yōu)缺點(diǎn)，③順序表算法設(shè)計(jì)方

2、線性表6/8表：線性表的鏈?zhǔn)酱鎯Ψ?，④單鏈表、雙鏈表和循環(huán)鏈表算

結(jié)構(gòu)一雙鏈表；線性表法設(shè)計(jì)方法。

的鏈?zhǔn)酱鎯Y(jié)構(gòu)一循重點(diǎn)：順序表、單鏈表、雙鏈表和循

環(huán)鏈表；線性表的應(yīng)環(huán)鏈表算法設(shè)計(jì)方法。

用；有序表。難點(diǎn)：利用線性表求解復(fù)雜問題。

目標(biāo)：①棧的邏輯結(jié)構(gòu)特性和棧抽象

數(shù)據(jù)類型的描述方法，②棧的先進(jìn)后

出特點(diǎn)，③?；具\(yùn)算在兩類存儲結(jié)

棧的基本概念；棧的順構(gòu)下的實(shí)現(xiàn)算法，④棧在實(shí)際求解問

序存儲結(jié)構(gòu)-順序棧；題中的應(yīng)用方法，⑤隊(duì)列的邏輯結(jié)構(gòu)

棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)-鏈特性和隊(duì)列抽象數(shù)據(jù)類型的描述方

3、棧和隊(duì)棧；棧的應(yīng)用；隊(duì)列的法，⑥隊(duì)列的先進(jìn)后出特點(diǎn)，⑦隊(duì)列

4/6

列基本概念；隊(duì)列的順序基本運(yùn)算在兩類存儲結(jié)構(gòu)下的實(shí)現(xiàn)

存儲結(jié)構(gòu)-順序隊(duì)；隊(duì)算法，⑧隊(duì)列在實(shí)際求解問題中的應(yīng)

列的鏈?zhǔn)酱鎯Y(jié)構(gòu)-鏈用方法。

隊(duì)；隊(duì)列的應(yīng)用。重點(diǎn)：①棧算法設(shè)計(jì)，②隊(duì)列算法設(shè)

計(jì)。

難點(diǎn)：棧和隊(duì)列在求解復(fù)雜問題中的

應(yīng)用。

目標(biāo)：①串的邏輯結(jié)構(gòu)特性和串抽象

數(shù)據(jù)類型的描述方法，②串的兩類存

串的基本概念；串的順

儲結(jié)構(gòu)設(shè)計(jì)方法以及各自的優(yōu)缺點(diǎn)，

序存儲結(jié)構(gòu)-順序串；

4、串2/2③順序串算法設(shè)計(jì)方法，④鏈串算法

串的鏈?zhǔn)酱鎯Y(jié)構(gòu)-鏈

設(shè)計(jì)方法。

串。

重點(diǎn)：①順序串運(yùn)算算法設(shè)計(jì)，②鏈

串運(yùn)算算法設(shè)計(jì)、

5、數(shù)組和2/2數(shù)組的基本概念；特殊目標(biāo)：①數(shù)組的邏輯結(jié)構(gòu)特性和數(shù)組

稀疏矩陣矩陣的壓縮存儲；稀疏抽象數(shù)據(jù)類型的描述方法，②數(shù)組的

矩陣。順序存儲結(jié)構(gòu)及其特點(diǎn)，③對稱矩

陣、上三角矩陣、下三角矩陣和三對

角矩陣的壓縮存儲，④稀疏矩陣的兩

種壓縮存儲方法。

重點(diǎn)：各種特殊矩陣的壓縮存儲方

法。

目標(biāo)：①樹的定義及其邏輯結(jié)構(gòu)特

性，②樹的邏輯結(jié)構(gòu)表示方法和樹的

樹的基本概念；樹的性性質(zhì)，③樹的遍歷方法和樹的存儲結(jié)

質(zhì)；樹的基本運(yùn)算；樹構(gòu)，④二叉樹的定義及其性質(zhì)，⑤二

的存儲結(jié)構(gòu)；二叉樹的叉樹與樹、森林之間的轉(zhuǎn)換，⑥二叉

基本概念；二叉樹樹的樹的兩種存儲結(jié)構(gòu)和二叉樹的基本

性質(zhì)；二叉樹與樹、森運(yùn)算算法設(shè)計(jì)。⑦二叉樹的遍歷過

6、樹和二林之間的轉(zhuǎn)換；二叉樹程、算法設(shè)計(jì)及其應(yīng)用。⑧二叉樹的

6/8

叉樹存儲結(jié)構(gòu)；二叉樹的基構(gòu)造過程，⑨線索二叉樹的特點(diǎn)及其

本運(yùn)算及其實(shí)現(xiàn)；二叉構(gòu)造過程，⑩哈夫曼樹和哈夫曼編碼

樹的遍歷；二叉樹遍歷的構(gòu)造過程。

應(yīng)用；二叉樹的構(gòu)造；重點(diǎn)：①二叉樹性質(zhì)和二叉樹結(jié)點(diǎn)計(jì)

線索二叉樹；哈夫曼算，②二叉樹的遍歷過程、算法設(shè)

樹。計(jì)及其應(yīng)用。

難點(diǎn)：靈活利用二叉樹的遍歷思路進(jìn)

行較復(fù)雜二叉樹算法設(shè)計(jì)。

目標(biāo)：①圖的定義及其邏輯結(jié)構(gòu)特

性，圖抽象數(shù)據(jù)類型的描述方法，②

圖的基本術(shù)語及其含義，③圖的鄰接

矩陣和鄰接表兩種主要的存儲結(jié)構(gòu)

及其特點(diǎn)，④圖的深度優(yōu)先和廣度優(yōu)

先遍歷算法，⑤圖遍歷算法的應(yīng)用，

圖的基本概念；圖的存⑥生成樹和最小生成樹的定義和求

儲結(jié)構(gòu)；圖的遍歷；圖最小生成樹的Prim和Kruskal算法，

遍歷算法的應(yīng)用；生成⑦最短路徑的概念和求最短路徑的

7、圖4/8

樹和最小生成樹；最短Dijkstra和Flody算法,⑧拓?fù)渑判蜻^

路徑；拓?fù)渑判颍籄OE程，⑨關(guān)鍵路徑的定義及其構(gòu)造過

網(wǎng)與關(guān)鍵路徑。程。

重點(diǎn)：①圖的鄰接矩陣和鄰接表兩種

主要的存儲結(jié)構(gòu)及其特點(diǎn)，②圖的深

度優(yōu)先和廣度優(yōu)先遍歷算法，③Prim

和Kruskal算法，④Dijkstra和Flody

算法。

難點(diǎn)：圖遍歷算法的應(yīng)用。

查找的基本概念；線性目標(biāo)：①掌握查找的概念，②線性表

8、查找3/6表的查找；樹表的查的順序查找和折半查找算法，索引存

找；哈希表查找。儲結(jié)構(gòu)和分塊查找方法，③二叉排序

樹的定義、查找和插入算法、刪除過

程，④平衡二叉樹的特點(diǎn)及其調(diào)整方

法，⑤B-樹的定義和基本操作過程，

B+的定義，⑥哈希表的定義及其特

點(diǎn)，⑦哈希函數(shù)構(gòu)造方法和解決沖突

的方法，⑧各種查找方法的性能分

析。

重點(diǎn)：各種查找算法的實(shí)現(xiàn)。

難點(diǎn)：各種查找方法的性能分析。

目標(biāo)：①排序的定義和相關(guān)概念，②

插入排序算法，包括直接插入排序、

折半插入排序和希爾排序，③交換排

序算法，包括冒泡排序和快速排序，

排序的基本概念；插入④選擇排序算法，包括簡單選擇排序

排序；交換排序；選擇和堆排序，⑤歸并排序算法，包括二

9、排序3/6排序；歸并排序；基數(shù)路歸并排序，⑥基數(shù)排序算法，包括

排序；各種內(nèi)排序方法最低位優(yōu)先和最高位優(yōu)先排序，⑦各

的比較和選擇。種內(nèi)排序方法的性能分析和比較。⑧

外排序的基本過程。

重點(diǎn)：各種排序算法的實(shí)現(xiàn)。

難點(diǎn)：各種內(nèi)排序方法的性能分析和

比較。

六、上機(jī)課時安排（32課時）

課時課

內(nèi)容對應(yīng)能力點(diǎn)要求備注

類型時

設(shè)計(jì)順序表各種基本運(yùn)

上機(jī)實(shí)驗(yàn)項(xiàng)目1一線性表線性表算法

算的算法，設(shè)計(jì)單鏈表2

基本運(yùn)算算法設(shè)計(jì)。設(shè)計(jì)

各種基本運(yùn)算的算法。

設(shè)計(jì)順序棧各種基本運(yùn)

上機(jī)實(shí)驗(yàn)項(xiàng)目2—?；?/p>

棧算法設(shè)計(jì)算的算法，設(shè)計(jì)鏈棧各2

運(yùn)算算法設(shè)計(jì)。

種基本運(yùn)算的算法。

設(shè)計(jì)順序隊(duì)各種基本運(yùn)

上機(jī)實(shí)驗(yàn)項(xiàng)目3一隊(duì)列基隊(duì)列算法設(shè)

上機(jī)算的算法，設(shè)計(jì)鏈隊(duì)各2

本運(yùn)算算法設(shè)計(jì)。計(jì)

實(shí)驗(yàn)種基本運(yùn)算的算法。

題上機(jī)實(shí)驗(yàn)項(xiàng)目4一求解〃遞歸算法設(shè)掌握遞歸算法設(shè)計(jì)方

2

皇后問題。計(jì)法。

上機(jī)實(shí)驗(yàn)項(xiàng)目5一二叉樹二叉樹遍歷掌握二叉樹4種遍歷算

2

4種遍歷算法設(shè)計(jì)算法設(shè)計(jì)法的特點(diǎn)和實(shí)現(xiàn)過程。

上機(jī)實(shí)驗(yàn)項(xiàng)目6—圖遍歷圖遍歷算法掌握圖的DFS和BFS遍

2

算法設(shè)計(jì)設(shè)計(jì)歷算法設(shè)計(jì)。

上機(jī)實(shí)驗(yàn)項(xiàng)目7—圖中帶圖遍歷算法掌握圖的DFS遍歷算法

2

條件的路徑查找設(shè)計(jì)設(shè)計(jì)。

上機(jī)實(shí)驗(yàn)項(xiàng)目8—線性表查找算法設(shè)掌握順序查找和折半查

2

的查找算法設(shè)計(jì)計(jì)找算法設(shè)計(jì)。

上機(jī)實(shí)驗(yàn)項(xiàng)目9—樹表的查找算法設(shè)掌握二叉排序樹算法設(shè)

2

查找算法設(shè)計(jì)計(jì)，il'o

上機(jī)實(shí)驗(yàn)項(xiàng)目10―哈希表查找算法設(shè)掌握哈希表查找算法設(shè)

2

的查找算法設(shè)計(jì)計(jì)il'o

掌握直接插入排序、折

上機(jī)實(shí)驗(yàn)項(xiàng)目11一插入排內(nèi)排序算法

半插入排序、希爾排序1

序算法設(shè)計(jì)設(shè)計(jì)

算法設(shè)計(jì)。

上機(jī)實(shí)驗(yàn)項(xiàng)目12一交換排內(nèi)排序算法掌握冒泡排序、快速排

1

序算法設(shè)計(jì)設(shè)計(jì)序算法設(shè)計(jì)。

上機(jī)實(shí)驗(yàn)項(xiàng)目13一選擇排內(nèi)排序算法掌握簡單選擇排序和堆