【正文】 索系統(tǒng)，（3）內(nèi)部排序算法比較，等。掌握簡單的算法分析方法。了解稀疏矩陣的兩種壓縮存儲方法的特點(diǎn)和適用范圍，領(lǐng)會以三元組表示稀疏矩陣時進(jìn)行矩陣運(yùn)算采用的處理方法。注重培養(yǎng)學(xué)生的學(xué)習(xí)興趣，提高學(xué)生的基本素質(zhì)。一、教學(xué)目的與要求了解數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)；教學(xué)要求在每章教學(xué)內(nèi)容給出，大體上為三個層次：了解、掌握和熟練掌握。(3)線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)。掌握利用棧實現(xiàn)表達(dá)式求值的算法，了解迷宮求解算法。（理論8學(xué)時，實驗2學(xué)時）教學(xué)內(nèi)容：(1)二叉樹的定義和術(shù)語，二叉樹的性質(zhì)，特殊的二叉樹。(3)圖的兩種遍歷策略：深度優(yōu)先搜索和廣度優(yōu)先搜索。掌握描述折半查找過程的判定樹的構(gòu)造方法，以及按定義計算各種查找方法在等概率情況下查找成功時的平均查找長度。（1周）教學(xué)內(nèi)容：(1)設(shè)計準(zhǔn)備：理解實習(xí)任務(wù)，明確相關(guān)算法，搜集可用資源，熟悉實習(xí)環(huán)境。課程實習(xí)的成績由平時成績和實習(xí)作業(yè)兩部分組成，其中平時成績占30%，實習(xí)作業(yè)占70%。三、本課程與其它課程的聯(lián)系和分工本課程的先修課為程序設(shè)計基礎(chǔ)和離散數(shù)學(xué)，本課程可以C/C++或Java語言作為算法描述和上機(jī)實踐的工具。理解排序方法“穩(wěn)定”或“不穩(wěn)定”的含義，弄清楚在什么情況下要求應(yīng)用的排序方法必須是穩(wěn)定的。(3)基于樹表的查找：二叉排序樹、平衡二叉樹、B樹和B+樹。實驗：實驗內(nèi)容：二叉樹的基本算法。掌握串的古典的模式匹配算法。(4)隊列的類型，隊列的順序存儲(循環(huán)隊)和鏈接存儲的表示和實現(xiàn)。(4)算法時間復(fù)雜度和空間復(fù)雜度的分析。隨著計算機(jī)硬件的發(fā)展，對計算機(jī)軟件的發(fā)展也提出了越來越高的要求。三、課程教學(xué)的基本要求本課程是信息與計算科學(xué)專業(yè)的重要專業(yè)基礎(chǔ)課，計算機(jī)科學(xué)各領(lǐng)域及有關(guān)的系統(tǒng)和應(yīng)用軟件都要用到各種數(shù)據(jù)結(jié)構(gòu)。熟練掌握在串的定長順序存儲結(jié)構(gòu)上實現(xiàn)串的各種操作的方法。當(dāng)用計算機(jī)來解決實際問題時，就要涉及到數(shù)據(jù)的表示及數(shù)據(jù)的處理，而數(shù)據(jù)表示及數(shù)據(jù)處理正是數(shù)據(jù)結(jié)構(gòu)課程的主要研究對象，通過這兩方面內(nèi)容的學(xué)習(xí)，為后續(xù)課程，特別是軟件方面的課程打下了厚實的知識基礎(chǔ)，同時也提供了必要的技能訓(xùn)練。四、教學(xué)安排建議 完成每章的教學(xué)后進(jìn)行布置習(xí)題，使用教材配套的《數(shù)據(jù)結(jié)構(gòu)題集（C語言版）》。3．自學(xué)內(nèi)容：串操作的應(yīng)用實例?？荚嚥捎瞄]卷方式。（三）實驗教學(xué)基本要求通過實例，使學(xué)生熟悉圖的各種存儲結(jié)構(gòu)的特性，掌握如何應(yīng)用圖結(jié)構(gòu)解決具體問題。十一章外部排序（一）目的要求理解外部排序的基本方法；掌握敗者樹和多路平衡歸并的實現(xiàn)；置換選擇排序；最佳歸并樹。（三）重點(diǎn)與難點(diǎn) 重點(diǎn)：串定義和存儲方法；串的操作 難點(diǎn)：串操作實現(xiàn)方法第五章 數(shù)組和廣義表（一）目的要求掌握數(shù)組的存儲結(jié)構(gòu)；稀疏矩陣的表示及操作的實現(xiàn)；廣義表的定義和存儲結(jié)構(gòu)；廣義表的遞歸算法。通過課堂教學(xué)、課外練習(xí)和上機(jī)實習(xí)，使學(xué)生了解數(shù)據(jù)對象的特性，數(shù)據(jù)組織的基本方法，并初步具備分析和解決現(xiàn)實世界問題在計算機(jī)中如何表示和處理的能力以及培養(yǎng)良好的程序設(shè)計技能，為后續(xù)課程的學(xué)習(xí)和科研工作的參與打下良好的基礎(chǔ)。難點(diǎn)：遞歸的編程實現(xiàn)；循環(huán)隊列和鏈隊列的基本運(yùn)算。（二）教學(xué)內(nèi)容 本章知識點(diǎn)：(掌握)； (掌握)；(掌握)。每門課恰好占一個學(xué)期。條件允許可采用CAI、電子教案、幻燈片、參觀等進(jìn)行輔助教學(xué)。2．基本要求（1）掌握棧和隊列兩種抽象數(shù)據(jù)類型的特點(diǎn)；（2）掌握棧的兩種存儲表示和實現(xiàn)，特別注意棧滿?？盏臈l件；（3）掌握隊列的兩種存儲表示和實現(xiàn)，特別注意隊滿隊空的條件；（4）了解遞歸算法與棧的關(guān)系。（九）內(nèi)部排序（4 學(xué)時）1．主要內(nèi)容：（1）排序的基本概念和相關(guān)術(shù)語；（2）插入排序：直接插入排序、折半插入排序和希爾排序；（3）交換排序：起泡排序和快速排序；（4）選擇排序：簡單選擇排序和堆排序；（5）歸并排序：二路歸并排序；（6）基數(shù)排序：鏈?zhǔn)交鶖?shù)排序；（7）各種內(nèi)部排序方法的比較討論。期末考試60%：本課程的期末考試考核內(nèi)容主要包括線性表、棧與隊列、串、數(shù)組與廣義表、樹與二叉樹、圖、查找和內(nèi)部排序。熟練掌握循環(huán)隊列和鏈隊列的基本操作實現(xiàn)算法，尤其是隊滿和隊空的描述方法。第9章 內(nèi)部排序（8學(xué)時，2個學(xué)時實驗上機(jī)）了解排序的基本思想和基本概念，理解和掌握插入排序、冒泡排序、快速排序、直接選擇排序、堆排序、歸并排序和基數(shù)排序的基本思想、步驟及算法。后續(xù)課程：操作系統(tǒng)，數(shù)據(jù)庫原理等。二、課程教學(xué)內(nèi)容、學(xué)時分配和課程教學(xué)基本要求（理論2學(xué)時）教學(xué)內(nèi)容：(1)數(shù)據(jù)結(jié)構(gòu)的一些基本概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)的邏輯結(jié)構(gòu)、物理結(jié)構(gòu)等。（理論6學(xué)時，實驗4學(xué)時）教學(xué)內(nèi)容：(1)棧的類型定義，棧的順序存儲和鏈接存儲的表示和實現(xiàn)。(3)特殊矩陣和稀疏矩陣的壓縮存儲，稀疏矩陣的轉(zhuǎn)置運(yùn)算。掌握線索化二叉樹的特性及尋找某結(jié)點(diǎn)的前驅(qū)和后繼的方法。實驗要求：使用鄰接矩陣或鄰接表表示法存儲一個圖，實現(xiàn)圖的深度優(yōu)先搜索和廣度優(yōu)先搜索的算法。深刻理解排序算法的過程、特點(diǎn)及其依據(jù)的原則，并能加以靈活應(yīng)用。實驗針對相應(yīng)單元所學(xué)的內(nèi)容，能夠采取合適的數(shù)據(jù)結(jié)構(gòu)和算法解決有關(guān)問題。數(shù)據(jù)結(jié)構(gòu)研究數(shù)據(jù)的組織方式，內(nèi)容豐富、學(xué)習(xí)量大，隱含在各部分內(nèi)容中的方法和技術(shù)多，旨在讓學(xué)生掌握計算機(jī)軟件系統(tǒng)所必需的數(shù)據(jù)結(jié)構(gòu)的算法。(4)代碼測試：模塊組裝，整體測試。(3)交換排序：冒泡排序和快速排序。(6)兩類求最短路徑問題的算法，迪杰斯特拉算法和弗洛伊德算法。線索化二叉樹。了解隊列的應(yīng)用。熟練掌握這兩類存儲結(jié)構(gòu)的描述方法，掌握鏈表中的頭結(jié)點(diǎn)、頭指針和首元結(jié)點(diǎn)的區(qū)別及循環(huán)鏈表、雙向鏈表的特點(diǎn)等。了解算法分析方法。教師應(yīng)認(rèn)真組織，安排重點(diǎn)發(fā)言，充分調(diào)動每一名同學(xué)的學(xué)習(xí)積極性，做好總結(jié)。第6章 樹和二叉樹（12學(xué)時，2個學(xué)時實驗上機(jī)）深刻理解樹的定義、性質(zhì)及其存儲方法，熟練掌握二叉樹的二叉鏈表存儲方式、結(jié)點(diǎn)結(jié)構(gòu)和類型定義，并能畫出給定二叉樹的二叉鏈表的結(jié)構(gòu)示意圖；理解并掌握二叉樹的三種遍歷方法，并能寫出該三種遍歷的算法；會完成樹、森林與二叉樹間的相互轉(zhuǎn)換；理解哈夫曼樹的構(gòu)造方法，并能對給定的數(shù)據(jù)集合構(gòu)造出哈夫曼樹。理解順序表和鏈表的定義、組織形式、結(jié)構(gòu)特征和類型說明，掌握在這兩種表上實現(xiàn)的插入、刪除和按值查找的算法。五、課程考核本課程考核形式為：平時成績占40%，期末考試成績占60%。（七）圖（9 學(xué)時）1．主要內(nèi)容：（1）圖的定義和術(shù)語；（2）圖的四種存儲結(jié)構(gòu)：數(shù)組表示法（鄰接矩陣）、鄰接表、十字鏈表和鄰接多重表；（3）圖的兩種遍歷策略：深度優(yōu)先遍歷和廣度優(yōu)先遍歷；（4）圖的連通性和最小生成樹；（5）有向無環(huán)圖及其應(yīng)用：拓?fù)渑判蚝完P(guān)鍵路徑；（6）最短路徑問題。2．基本要求（1）了解學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的重要性；（2）掌握數(shù)據(jù)結(jié)構(gòu)的定義及相關(guān)概念和術(shù)語；（3）了解抽象數(shù)據(jù)類型的定義、表示與實現(xiàn)方法；（4）理解算法的概念、特點(diǎn)并掌握度量其效率的基本方法。（四）實驗設(shè)備和材料 計算機(jī)。（三）實驗教學(xué)基本要求通過實例，使學(xué)生掌握棧和隊列兩種特殊的線性結(jié)構(gòu)，掌握棧和隊列的特點(diǎn)。第七章 圖（一）目的要求理解圖的基本概念；圖的存儲結(jié)構(gòu)；掌握圖的遍歷及應(yīng)用{最小生成樹，最短路徑等}；拓?fù)渑判蚝完P(guān)鍵路徑。第二章線性表（一）目的要求掌握線性表的邏輯結(jié)構(gòu)；線性表的存儲結(jié)構(gòu)及操作的實現(xiàn)；理解一元多項式的表示；（二）教學(xué)內(nèi)容 本章知識點(diǎn)：(掌握)；(掌握)；(掌握)；(掌握)。難點(diǎn)：數(shù)據(jù)結(jié)構(gòu)的定義；算法與程序的區(qū)別；時間復(fù)雜度及其計算。難點(diǎn)：二叉樹的遍歷方式；二叉排序樹的構(gòu)造方法；二叉樹的線索化。（二）實驗過程 編程實現(xiàn)實驗內(nèi)容。實驗后學(xué)生提交實驗報告。三、課程教學(xué)內(nèi)容與基本要求（一）緒論（3 學(xué)時）1．主要內(nèi)容：（1）介紹什么是數(shù)據(jù)結(jié)構(gòu)；（2）基本概念和術(shù)語: 數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對象，以及數(shù)據(jù)結(jié)構(gòu)的定義、邏輯結(jié)構(gòu)、物理結(jié)構(gòu)（理解）數(shù)據(jù)類型、抽象數(shù)據(jù)類型；（3）抽象數(shù)據(jù)類型的表示與實現(xiàn)；（4）算法和算法分析: 算法的概念、算法設(shè)計的要求以及算法效率的度量。3．自學(xué)內(nèi)容：先序、后序遍歷二叉樹非遞歸算法，層次遍歷二叉樹算法。建議實驗安排為八次，共16學(xué)時，分別如下：實驗1 線性表的順序存儲結(jié)構(gòu)的實現(xiàn)(2學(xué)時)實驗2 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)的實現(xiàn)(2學(xué)時)實驗3 棧的算法實現(xiàn)(2學(xué)時)實驗4 隊列的算法實現(xiàn)(2學(xué)時)實驗5 串類型及操作(2學(xué)時)實驗6 二叉樹的建立與遍歷(2