【正文】 時。難點：鏈?zhǔn)酱鎯Y(jié)構(gòu)及其常用算法；雙向循環(huán)鏈表。（二）教學(xué)內(nèi)容 本章知識點：(掌握)； (掌握)；，領(lǐng)會以三元組表示稀疏矩陣時進(jìn)行運算采用的處理方法(掌握)；，學(xué)會廣義表的表頭，表尾分析方法(掌握)； (掌握)。（三）重點與難點重點：圖的存儲結(jié)構(gòu)；圖的遍歷 難點：圖遍歷的算法；第八章動態(tài)存儲管理（一）目的要求了解邊界標(biāo)識法和伙伴系統(tǒng)；無用單元收集和緊縮；（二）教學(xué)內(nèi)容 本章知識點：（了解）；（了解）。（二）教學(xué)內(nèi)容 本章知識點：(理解)；(掌握)；(掌握)；(掌握)；(掌握)；（熟悉）；，外存讀/寫次數(shù)的計算方法(掌握)。（四）實驗設(shè)備和材料 計算機。實驗后學(xué)生提交實驗報告。待填入哈希表的人名共有30個，取平均查找長度的上限為2?？偝煽冇善綍r成績和考試成績組成。（二）線性表（6 學(xué)時）1．主要內(nèi)容：（1）線性表的抽象數(shù)據(jù)類型定義和相關(guān)概念：數(shù)據(jù)項、記錄、文件等；（2）線性表順序存儲表示和基本操作的實現(xiàn)；（3）線性表的鏈?zhǔn)酱鎯Ρ硎竞突静僮鞯膶崿F(xiàn)；（4）稀疏多項式的抽象數(shù)據(jù)類型定義、表示和加法的實現(xiàn)。（五）數(shù)組和廣義表（4 學(xué)時）1．主要內(nèi)容：（1）數(shù)組的抽象數(shù)據(jù)類型定義及其順序表示和實現(xiàn)；（2）特殊矩陣和稀疏矩陣的壓縮存儲；（3）廣義表的抽象數(shù)據(jù)類型定義和存儲結(jié)構(gòu)。3．自學(xué)內(nèi)容：樹的先根遍歷算法與圖的深度優(yōu)先遍歷算法比較；樹的層次遍歷算法與圖的廣度優(yōu)先遍歷算法比較。盡量選擇基礎(chǔ)的并且加注了標(biāo)記的題，應(yīng)注重于精，而不要求多。期末考試成績低于50分者，本課程成績按不及格論處。因此，數(shù)據(jù)結(jié)構(gòu)課程在信息與計算科學(xué)專業(yè)中具有舉足輕重的作用。掌握稀疏多項式在線性表的兩種存儲結(jié)構(gòu)上的實現(xiàn)方法。掌握串的堆存儲結(jié)構(gòu)以及在其上實現(xiàn)串操作的基本方法。第7章 圖（12學(xué)時，2個學(xué)時實驗上機）理解圖的基本概念及術(shù)語，掌握圖的兩種存儲結(jié)構(gòu)(鄰接矩陣和鄰接表)的表示方法；熟練掌握圖的兩種遍歷(深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷)的算法思想、步驟，并能列出在兩種存儲結(jié)構(gòu)上按上述兩種遍歷算法得到的序列；理解最小生成樹的概念，能按Prim算法構(gòu)造最小生成樹；了解并掌握拓?fù)渑判?、關(guān)鍵路徑、最短路徑的算法思想。在教學(xué)方法上采用課堂講授，課后自學(xué)，課堂討論等教學(xué)形式。（五）實驗用C語言或C++語言完成一些算法設(shè)計題。由于軟件的核心是算法，而算法實際上是對加工數(shù)據(jù)過程的描述，所以研究數(shù)據(jù)結(jié)構(gòu)對提高編程能力和設(shè)計高性能的算法是至關(guān)重要的。鏈表插入、刪除運算的算法?；疽螅赫莆諗?shù)據(jù)結(jié)構(gòu)的基本概念，了解抽象數(shù)據(jù)類型，掌握算法時間復(fù)雜度和空間復(fù)雜度的分析方法。能夠從時間和空間復(fù)雜度的角度比較兩種存儲結(jié)構(gòu)的不同特點及其適用場合。(5)隊列的應(yīng)用舉例，如打印楊暉三角形，模擬汽車加油站等問題。實驗要求：借助棧來解決某些實際應(yīng)用問題，如表達(dá)式求值、迷宮問題等。掌握數(shù)組的地址計算方法。(5)樹的應(yīng)用，哈夫曼樹及哈夫曼編碼。實驗要求：利用二叉鏈表方法建立二叉樹，實現(xiàn)二叉樹的前、中、后序三種遍歷算法，并運用遍歷算法實現(xiàn)二叉樹的其他操作，如計算二叉樹結(jié)點個數(shù)、葉子結(jié)點個數(shù)、二叉樹的高度等。熟練掌握圖的兩種搜索路徑的遍歷：深度優(yōu)先搜索和廣度優(yōu)先搜索的算法。(4)散列表：散列表的基本概念，散列函數(shù)的構(gòu)造方法、處理沖突的方法、散列表的查找與分析。(5)歸并排序：2路歸并排序。快速排序、堆排序和歸并排序等高效排序方法是本章的學(xué)習(xí)重點和難點?；疽螅耗軐?shù)據(jù)結(jié)構(gòu)課程中所學(xué)的基本知識融會貫通，綜合運用所學(xué)的知識解決相關(guān)的實際問題，能夠把所學(xué)知識（包括算法和結(jié)構(gòu)）在計算機上用編程語言加以實現(xiàn)，并且能夠根據(jù)實際需求創(chuàng)建自己的數(shù)據(jù)結(jié)構(gòu)和實現(xiàn)自己的算法。同時，本課程又是軟件開發(fā)與設(shè)計等方面課程的基礎(chǔ)，如數(shù)據(jù)庫、操作系統(tǒng)、編譯原理、軟件工程等課程。要求學(xué)生學(xué)會分析研究計算機加工的數(shù)據(jù)對象的特征，以便在實際應(yīng)用中選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)、存儲結(jié)構(gòu)和相應(yīng)算法，初步掌握算法的時間與空間性能分析技巧，并培養(yǎng)復(fù)雜程序設(shè)計的技能?？傇u成績由平時成績和期末成績組成，其中平時成績占30%40%，期末考試占70%60%。其中，課堂講授以教師講授為主，授課時將電子教案和板書相結(jié)合，充分發(fā)揮各自的優(yōu)點。實驗要求：選取一個合適的數(shù)據(jù)結(jié)構(gòu)存儲數(shù)據(jù)，能對數(shù)據(jù)進(jìn)行插入、刪除，用不同查找算法進(jìn)行查找、用不同的排序算法進(jìn)行排序等。(7)排序算法分析：各種排序算法的比較和移動次數(shù)，時間復(fù)雜度和空間復(fù)雜度的分析。熟練掌握散列表的構(gòu)造方法、處理沖突的方法，深刻理散列表與其他結(jié)構(gòu)的表的實質(zhì)性的差別，了解各種散列函數(shù)的特點。了解關(guān)鍵路徑的概念和求解方法，了解弗洛伊德算法。(2)圖的存儲結(jié)構(gòu)兩種存儲結(jié)構(gòu)：鄰接矩陣和鄰接表表示法。掌握二叉樹的概念、性質(zhì)及二叉樹的表示。了解廣義表的結(jié)構(gòu)特點及其存儲方法。古典的模式匹配算法。熟練掌握棧的順序棧和鏈棧的進(jìn)棧出棧算法，特別應(yīng)注意棧滿和?？盏臈l件。實驗：實驗內(nèi)容：單鏈表的基本操作。(2)線性表的順序表示和實現(xiàn)。教學(xué)目的：通過本課程的學(xué)習(xí)，一方面，使學(xué)生學(xué)會分析研究計算機加工的數(shù)據(jù)結(jié)構(gòu)的特性，以便為應(yīng)用涉及的數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲結(jié)構(gòu)及相應(yīng)的算法，并初步了解對算法的時間分析和空間分析技術(shù)。因此，簡單地說，數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題的學(xué)科，主要研究數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和算法。總評成績：平時作業(yè)占30%，閉卷考試占70%。在傳授知識原理的前提下，配合實際應(yīng)用例子，由淺入深善于誘導(dǎo)，使學(xué)生從被動吸收知識的狀態(tài)下，轉(zhuǎn)化到主動索取知識的狀態(tài)中來，并采用多媒體輔助教學(xué)，加大課堂授課的知識含量。第8章 查找（10學(xué)時，2個學(xué)時實驗上機）了解查找的基本思想及查找成功和不成功的概念，掌握在順序表、有序表、索引表、散列表等上的查找方法和算法，并能求出相應(yīng)的平均查找長度。掌握對特殊矩陣進(jìn)行壓縮存儲時的下標(biāo)變換公式。第3章 棧和隊列（6學(xué)時，2個學(xué)時實驗上機）理解棧和隊列的定義、特征及在其上所定義的基本運算。理解數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)的聯(lián)系與區(qū)別，以及在數(shù)據(jù)結(jié)構(gòu)上施加的運算及其實現(xiàn)。平時作業(yè)10%：根據(jù)上交次數(shù)及完成情況進(jìn)行評定?？蓞⒖歼x擇以下一些案例：（1）學(xué)生通訊錄管理系統(tǒng)，（2）表達(dá)式求值問題（3）交通咨詢系統(tǒng)，等。2．基本要求（1）了解查找的作用，熟悉相關(guān)術(shù)語；（2）熟練掌握順序查找、折半查找和索引順序表查找；（3）熟練掌握二叉排序樹的特性、構(gòu)造和查找方法；（4）熟練掌握哈希表的構(gòu)造方法，特別是哈希函數(shù)和處理沖突方法的選?。唬?）通過分析等概率下的平均查找長度來衡量各種查找方法的效率。3．自學(xué)內(nèi)容：采用十字鏈表存儲結(jié)構(gòu)創(chuàng)建稀疏矩陣。3．自學(xué)內(nèi)容：靜態(tài)鏈表。六、本課程與其它課程的聯(lián)系與分工先修課包括：集合論，圖論，高級語言（結(jié)構(gòu)或記錄，指針）；后續(xù)課包括：數(shù)據(jù)庫，編譯原理，操作系統(tǒng)等。（二）實驗過程 編程實現(xiàn)實驗內(nèi)容（三）實驗教學(xué)基本要求 掌握索引技術(shù)的使用。（五）實驗學(xué)時 2學(xué)時實驗三最小生成樹問題（一）實驗內(nèi)容利用克魯斯卡爾算法求最小生成樹。每個專業(yè)開設(shè)的課程都是確定的，而且課程在開設(shè)時間的安排必須滿足先修關(guān)系。實踐教學(xué)部分：上機實驗分4個專題，每個專題可提供2~4個難度不等的題目供選。（三）重點與難點重點：二叉排序樹的構(gòu)造方法、二叉平衡樹的建立方法；哈希表的構(gòu)造、應(yīng)用；難點：二叉排序樹的構(gòu)造及應(yīng)用；哈希表的構(gòu)造方法；查找的平均長度。難點：稀疏矩陣的三元組表示；廣義表的存儲定義、操作。（二）教學(xué)內(nèi)容 本章知識點： (掌握)；(掌握)； (熟練掌握)； (掌握)。理解數(shù)據(jù)結(jié)構(gòu)的基本概念；算法設(shè)計；掌握算法的時間和空間復(fù)雜度。其中，理論教學(xué)部分：第一章緒論（一）目的要求了解數(shù)據(jù)結(jié)構(gòu)的意義與發(fā)展過程、數(shù)據(jù)結(jié)構(gòu)在計算機科學(xué)中的作用、學(xué)習(xí)本課程的目的、任務(wù)及要求。第三章 棧和隊列（一）目的要求掌握棧的定義，表示及實現(xiàn)；表達(dá)式求值；棧與遞歸過程；隊列的定義、表示及實現(xiàn)。（三）重點與難點重點：多維數(shù)組元素存儲地址的計算；稀疏矩陣的三元組表示；廣義表的存儲定義、操作。（三）重點與難點存儲器分配策略和算法、無用單元收集時的標(biāo)志算法第九章查找（一）目的要求了解靜態(tài)查找表(順序表，有序表，索引順序表)；動態(tài)查找表(二叉排序樹，平衡二叉樹，B樹和B+樹)的建立和查找；掌握哈希表的建立，查找及分析；（二）教學(xué)內(nèi)容 本章知識點：、折半查