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

1、數(shù)據(jù)結(jié)構(gòu)（Data Structure）課程代碼：2131034學(xué)分：4學(xué)時：64（其中：課程教學(xué)學(xué)時：48，實(shí)驗(yàn)學(xué)時：16）先修課程：計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)導(dǎo)論、程序設(shè)計(jì)基礎(chǔ)適用專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)教材：數(shù)據(jù)結(jié)構(gòu)（C語言版），嚴(yán)蔚敏，吳偉民編著，清華大學(xué)出版社，2016年7月第 1 版第45次印刷開課學(xué)院：計(jì)算機(jī)與軟件學(xué)院一、課程性質(zhì)與課程目標(biāo)（一）課程性質(zhì)數(shù)據(jù)結(jié)構(gòu)是高等工科院校計(jì)算機(jī)類相關(guān)專業(yè)的一門重要學(xué)科基礎(chǔ)必修課。本課程主要研究各種數(shù)據(jù)的抽象表示、實(shí)現(xiàn)方法、算法的設(shè)計(jì)過程以及算法的分析，是計(jì)算機(jī)軟件設(shè)計(jì)的重要理論和實(shí)踐基礎(chǔ)課程。（二）課程目標(biāo)課程目標(biāo)包括知識目標(biāo)和能力目標(biāo)，具體如下：課

2、程目標(biāo)1：使學(xué)生掌握數(shù)據(jù)結(jié)構(gòu)的基本概念和基本理論，熟悉合理組織數(shù)據(jù)的基本方法，培養(yǎng)學(xué)生解決計(jì)算機(jī)領(lǐng)域復(fù)雜工程問題所需專業(yè)基礎(chǔ)知識，為本專業(yè)后續(xù)課程的學(xué)習(xí)以及進(jìn)一步的軟件開發(fā)打下良好的理論基礎(chǔ)；課程目標(biāo)2：能夠運(yùn)用計(jì)算思維分析問題和解決問題，針對計(jì)算機(jī)領(lǐng)域復(fù)雜工程問題，分析并抽象出涉及的數(shù)據(jù)元素以及它們內(nèi)在的邏輯關(guān)系；課程目標(biāo)3：能夠綜合運(yùn)用數(shù)據(jù)結(jié)構(gòu)的基本理論和設(shè)計(jì)方法，針對計(jì)算機(jī)領(lǐng)域復(fù)雜工程問題研究和設(shè)計(jì)可行的解決方案，并能對解決方案進(jìn)行分析和論證。（三）課程目標(biāo)與專業(yè)畢業(yè)要求指標(biāo)點(diǎn)的對應(yīng)關(guān)系本課程支撐專業(yè)培養(yǎng)計(jì)劃中的畢業(yè)要求指標(biāo)點(diǎn)1.2、2.2和3.2。畢業(yè)要求指標(biāo)點(diǎn)1.2：具備扎實(shí)的計(jì)算機(jī)

3、工程基礎(chǔ)知識，了解通過計(jì)算機(jī)解決復(fù)雜工程問題的基本方法，并遵循復(fù)雜系統(tǒng)開發(fā)的工程化基本要求；畢業(yè)要求指標(biāo)點(diǎn)2.2：應(yīng)用計(jì)算機(jī)領(lǐng)域?qū)I(yè)知識，能夠根據(jù)給出的實(shí)際工程案例，運(yùn)用草稿、圖表、流程表等工程方法發(fā)現(xiàn)問題、提出問題及分析問題；畢業(yè)要求指標(biāo)點(diǎn)3.2：能夠合理地組織數(shù)據(jù)，有效地存儲和處理數(shù)據(jù)，正確地進(jìn)行算法設(shè)計(jì)、分析和評價。課程目標(biāo)畢業(yè)要求指標(biāo)點(diǎn)課程目標(biāo)1課程目標(biāo)2課程目標(biāo)3畢業(yè)要求1.2畢業(yè)要求2.2畢業(yè)要求3.2二、課程內(nèi)容及教學(xué)要求本課程教學(xué)內(nèi)容包括：線性表、棧和隊(duì)列、數(shù)組、樹和二叉樹、圖等常見的數(shù)據(jù)結(jié)構(gòu)，討論各種典型查找算法、內(nèi)部排序算法以及算法分析的基本方法。本課程基本要求是：從數(shù)據(jù)的

4、邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和運(yùn)算三個方面理解并掌握線性表、棧、隊(duì)列、數(shù)組、樹和圖等常用的數(shù)據(jù)結(jié)構(gòu)；了解在各種常用的數(shù)據(jù)結(jié)構(gòu)上實(shí)現(xiàn)的排序和查找運(yùn)算；對算法的時間和空間復(fù)雜度有一定的分析能力；針對常見的應(yīng)用問題，能選擇合適的數(shù)據(jù)結(jié)構(gòu)及設(shè)計(jì)有效的算法解決問題。第1章緒論教學(xué)內(nèi)容1. 數(shù)據(jù)結(jié)構(gòu)的定義；2. 基本概念和術(shù)語（數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)、數(shù)據(jù)對象、數(shù)據(jù)結(jié)構(gòu)）；3. 抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)（ADT的三要素）；4.算法和算法分析（算法的定義及其五個特性；算法評價的標(biāo)準(zhǔn)；算法效率的度量）。（二）教學(xué)要求1.了解數(shù)據(jù)結(jié)構(gòu)的三個方面：邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、運(yùn)算；2. 理解抽象數(shù)據(jù)類型的概念；3. 理解算法的概念

5、和特性；4. 掌握算法的描述方法；5. 了解算法分析的內(nèi)容；6. 掌握算法時間復(fù)雜度的分析方法。（三）重點(diǎn)與難點(diǎn)1. 重點(diǎn)數(shù)據(jù)結(jié)構(gòu)三方面含義、算法的偽碼描述方法、簡單算法的時間復(fù)雜度分析。2. 難點(diǎn)算法的偽碼描述、算法的時間復(fù)雜度分析。第2章線性表（一）教學(xué)內(nèi)容線性表的定義、相關(guān)概念（前驅(qū)、后繼、表長、位序、空表等）、線性表的抽象數(shù)據(jù)結(jié)構(gòu)類型定義；線性表的順序表示和運(yùn)算實(shí)現(xiàn)；順序表的插入和刪除操作的實(shí)現(xiàn)方法；線性鏈表的有關(guān)概念：頭結(jié)點(diǎn)、結(jié)點(diǎn)、數(shù)據(jù)域、指針域、指針（鏈）；線性鏈表的存儲結(jié)構(gòu)、插入和刪除操作的實(shí)現(xiàn)方法及其時間復(fù)雜度分析；循環(huán)鏈表的存儲結(jié)構(gòu)以及插入和刪除操作的實(shí)現(xiàn)方法及其時間復(fù)雜度分

6、析。（二）教學(xué)要求 1. 理解線性表的基本概念，線性表有關(guān)的術(shù)語，線性表的特性；2. 熟悉線性表的抽象數(shù)據(jù)類型定義；3. 掌握線性表的順序存儲表示及實(shí)現(xiàn)；4. 掌握線性表的鏈接存儲表示及實(shí)現(xiàn)；5. 了解線性表的應(yīng)用。（三）重點(diǎn)與難點(diǎn)1.重點(diǎn)熟練掌握順序表和單鏈表上的各種基本算法及相關(guān)的時間復(fù)雜度分析。2.難點(diǎn)雙向循環(huán)鏈表的插入、刪除以及算法時間復(fù)雜度的分析。第3章棧和隊(duì)列教學(xué)內(nèi)容1. 棧的有關(guān)概念：棧、棧頂、棧底、空棧的定義；2. 棧的“后進(jìn)先出”特點(diǎn)；3. 棧的抽象數(shù)據(jù)類型定義；4. 棧的表示和實(shí)現(xiàn)：順序棧和鏈棧；5. 棧的應(yīng)用舉例：數(shù)制轉(zhuǎn)換、括號匹配的檢驗(yàn)、表達(dá)式求值（應(yīng)用棧實(shí)現(xiàn)表達(dá)式求值

7、的過程）；6. 隊(duì)列的定義及有關(guān)概念，隊(duì)列的“先進(jìn)先出”特點(diǎn)，隊(duì)列的抽象數(shù)據(jù)類型定義；7. 鏈隊(duì)列隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)；8. 循環(huán)隊(duì)列隊(duì)列的順序表示和實(shí)現(xiàn)：循環(huán)隊(duì)列的存儲結(jié)構(gòu)，循環(huán)隊(duì)列的插入和刪除操作實(shí)現(xiàn)。（二）教學(xué)要求1. 理解棧的基本概念，棧有關(guān)的術(shù)語，棧的特性；2. 熟悉棧的抽象數(shù)據(jù)類型定義；3. 掌握棧的順序存儲表示及實(shí)現(xiàn)和棧的鏈接存儲表示及實(shí)現(xiàn)；4. 掌握棧的應(yīng)用；5. 理解隊(duì)列的基本概念，隊(duì)列有關(guān)的術(shù)語，隊(duì)列的特性；6.熟悉隊(duì)列的抽象數(shù)據(jù)類型定義；7.掌握隊(duì)列的順序存儲表示及實(shí)現(xiàn)和隊(duì)列的鏈接存儲表示及實(shí)現(xiàn)；8.了解隊(duì)列的應(yīng)用（三）重點(diǎn)與難點(diǎn)1.重點(diǎn)順序棧及其運(yùn)算的實(shí)現(xiàn)、棧的簡單應(yīng)用

8、、循環(huán)隊(duì)列的插入和刪除實(shí)現(xiàn)。2.難點(diǎn)循環(huán)隊(duì)列的概念以及循環(huán)隊(duì)列的插入和刪除實(shí)現(xiàn)。第4章字符串（一）教學(xué)內(nèi)容1. 串的定義，串長、空串、子串、主串、位置、相等、空格串等概念。常用串運(yùn)算，串的抽象數(shù)據(jù)類型定義；2. 串的表示和實(shí)現(xiàn)；（1）定長順序存儲表示（2）堆分配存儲表示（3）串的塊鏈存儲表示3. 串的模式匹配算法。（二）教學(xué)要求1. 理解串的基本概念，串有關(guān)的術(shù)語，串的特性；2. 熟悉串的抽象數(shù)據(jù)類型定義；3. 掌握串的存儲表示及實(shí)現(xiàn)；4. 理解串的模式匹配運(yùn)算；5. 掌握樸素的模式匹配算法。（三）重點(diǎn)與難點(diǎn)1.重點(diǎn)串的常用運(yùn)算含義、串的順序存儲表示。2.難點(diǎn)串的模式匹配運(yùn)算。第5章數(shù)組和廣義

9、表（一）教學(xué)內(nèi)容1. 數(shù)組的抽象數(shù)據(jù)結(jié)構(gòu)類型定義；2. 一維數(shù)組的順序存儲表示，二維數(shù)組的順序存儲表示：以行序存儲和以列序存儲；數(shù)組中存儲元素和修改元素值的操作；3. 矩陣的壓縮存儲：對稱矩陣的壓縮存儲；稀疏矩陣的抽象數(shù)據(jù)類型定義，稀疏因子的定義，稀疏矩陣壓縮存儲的實(shí)現(xiàn)方法：三元組順序表；十字鏈表。（二）教學(xué)要求1. 理解數(shù)組的定義，數(shù)組的順序表示和實(shí)現(xiàn)；2. 了解對稱矩陣、三角矩陣、稀疏矩陣的壓縮存儲；3. 了解廣義表的定義，廣義表的鏈?zhǔn)酱鎯Y(jié)構(gòu)。（三）重點(diǎn)與難點(diǎn)1.重點(diǎn)數(shù)組的存儲表示、對稱矩陣和稀疏矩陣的壓縮存儲。2.難點(diǎn)稀疏矩陣的壓縮存儲。第6章樹和二叉樹（一）教學(xué)內(nèi)容樹的抽象數(shù)據(jù)類型定

10、義。結(jié)點(diǎn)、結(jié)點(diǎn)的度、葉子（終端結(jié)點(diǎn)）、分支結(jié)點(diǎn)（非終端結(jié)點(diǎn)）、樹的度、雙親、孩子、兄弟、祖先、子孫、深度、有序樹、無序樹和森林等術(shù)語的定義；二叉樹的抽象數(shù)據(jù)類型定義；二叉樹的5個性質(zhì)；滿二叉樹和完全二叉樹的概念；二叉樹的存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu)；遍歷二叉樹：先序遍歷、中序遍歷、后序遍歷的概念及遞歸算法；樹的存儲結(jié)構(gòu)：雙親表示法、孩子表示法、孩子兄弟表示法；森林與二叉樹的轉(zhuǎn)換；赫夫曼樹及其應(yīng)用：路徑長度、樹的路徑長度、樹的帶權(quán)路徑長度、最優(yōu)二叉樹（赫夫曼樹）的定義；赫夫曼編碼算法。（二）教學(xué)要求1. 理解樹的基本概念，樹有關(guān)的術(shù)語，樹的特性；2. 熟悉樹的抽象數(shù)據(jù)類型定義；3. 熟悉

11、樹的抽象數(shù)據(jù)類型定義；4. 理解二叉樹的基本概念，二叉樹有關(guān)的術(shù)語，二叉樹的特性；5. 熟悉二叉樹的抽象數(shù)據(jù)類型定義；6. 掌握二叉樹的順序與鏈接存儲表示；7. 掌握二叉樹的遍歷運(yùn)算及實(shí)現(xiàn)；8. 了解線索二叉樹；9掌握赫夫曼（Huffman）樹及其應(yīng)用；10. 了解森林與二叉樹的轉(zhuǎn)換；11. 了解樹和森林的遍歷。（三）重點(diǎn)與難點(diǎn)1.重點(diǎn)二叉樹的存儲表示、二叉樹的遍歷算法、赫夫曼算法、赫夫曼編碼。2.難點(diǎn)赫夫曼算法、赫夫曼編碼。第7章圖（一）教學(xué)內(nèi)容1. 基本概念及術(shù)語：頂點(diǎn)、?。ɑ☆^、弧尾）、有向圖、無向圖、完全圖、網(wǎng)、子圖、度（出度、入度）、路徑、回路（環(huán)）、簡單回路、連通圖（強(qiáng)連通圖）、連

12、通分量（強(qiáng)連通分量）等；2. 圖的存儲結(jié)構(gòu)：數(shù)組表示法（鄰接矩陣）；鄰接表；3. 圖的遍歷：深度優(yōu)先、廣度優(yōu)先；4. 圖的連通性問題：最小生成樹的定義；構(gòu)造最小生成樹的算法（Prim算法和Kruskal算法）。5. 有向無環(huán)圖及其應(yīng)用：拓?fù)渑判?、關(guān)鍵路徑；6. 最短路徑：從某個源點(diǎn)到其余各頂點(diǎn)的最短路徑（Dijkstra算法）。（二）教學(xué)要求1. 理解圖的基本概念，圖有關(guān)的術(shù)語，圖的特性；2. 熟悉圖的抽象數(shù)據(jù)類型定義；3. 掌握圖的鄰接矩陣、鄰接表存儲表示；4. 掌握圖的深度優(yōu)先遍歷、廣度優(yōu)先遍歷算法；5. 掌握以下圖的基本應(yīng)用及其復(fù)雜度分析：最小（代價）生成樹、最短路徑、拓?fù)渑判颉㈥P(guān)鍵路徑

13、。（三）重點(diǎn)與難點(diǎn)1.重點(diǎn)圖的存儲表示、圖的遍歷算法、最小生成樹算法、關(guān)鍵路徑算法。2.難點(diǎn)最小生成樹算法，最短路徑算法。第8章查找（一）教學(xué)內(nèi)容1. 順序查找的過程、算法以及性能分析；平均查找長度的定義；2. 有序表的折半查找過程、算法以及性能分析；3. 索引順序表的查找過程、算法以及性能分析；4. 二叉排序樹的定義及查找過程；二叉排序樹的插入和刪除；二叉排序樹的查找分析；平衡二叉樹（AVL樹）、平衡因子的定義及平衡二叉樹的構(gòu)造過程；平衡樹查找的分析；5. B-樹的定義；6. 哈希表：基本概念：哈希（Hash）函數(shù)、沖突、同義詞、哈希表、散列、哈希地址（散列地址）等；哈希函數(shù)的構(gòu)造要求、除留

14、余數(shù)法；處理沖突的方法：開放地址法、鏈地址法；哈希表的查找及其分析。（二）教學(xué)要求1. 理解查找的定義及相關(guān)概念；2. 掌握靜態(tài)查找表：順序表的查找，有序表的查找，索引順序表的查找；3. 掌握動態(tài)查找表：二叉排序樹，平衡二叉樹；4. 了解B-樹；5.掌握哈希表及其查找。（三）重點(diǎn)與難點(diǎn)1.重點(diǎn)順序查找、折半查找、二叉排序樹及其建立、二叉排序樹查找、AVL樹建立過程分析、AVL樹的查找及ASL分析、哈希表的建立、哈希表查找及ASL分析。2.難點(diǎn)AVL樹建立過程。第9章內(nèi)部排序（一）教學(xué)內(nèi)容1. 排序的定義；排序方法的時間和空間特性、穩(wěn)定性；2. 插入排序：直接插入排序、希爾排序；3. 快速排序；

15、4. 選擇排序：堆排序；5. 歸并排序；6. 各種內(nèi)部排序方法的比較。（二）教學(xué)要求1. 理解排序的定義及相關(guān)概念；2. 掌握常用的排序方法：直接插入排序，二分法插入排序，直接選擇排序，冒泡排序，希爾排序，快速排序，堆排序，歸并排序，基數(shù)排序；3. 理解各類內(nèi)部排序方法的特點(diǎn)：時間復(fù)雜度，空間復(fù)雜度，穩(wěn)定性。（三）重點(diǎn)與難點(diǎn)1.重點(diǎn)希爾排序、快速排序、堆排序和歸并排序。2.難點(diǎn)快速排序、堆排序以及各類內(nèi)部排序方法的比較。三、本課程開設(shè)的實(shí)驗(yàn)項(xiàng)目編號實(shí)驗(yàn)項(xiàng)目名稱學(xué)時類型要求支撐的課程目標(biāo)1線性表的存儲表示及實(shí)現(xiàn)2驗(yàn)證性必做課程目標(biāo)12棧的應(yīng)用(數(shù)制轉(zhuǎn)換及回文判斷)2驗(yàn)證性必做課程目標(biāo)13串的應(yīng)用

16、（串的聯(lián)接和模式匹配）2驗(yàn)證性必做課程目標(biāo)14二叉樹的遍歷2驗(yàn)證性必做課程目標(biāo)1，25赫夫曼樹及其應(yīng)用2設(shè)計(jì)性必做課程目標(biāo)1，2，36圖的建立與遍歷2驗(yàn)證性必做課程目標(biāo)1，27順序查找與二分法查找的實(shí)現(xiàn)與比較2驗(yàn)證性必做課程目標(biāo)2，38快速排序算法2驗(yàn)證性必做課程目標(biāo)2，3實(shí)驗(yàn)1：線性表的存儲表示及實(shí)現(xiàn)1. 實(shí)驗(yàn)?zāi)康募耙?）掌握線性表的順序存儲表示及實(shí)現(xiàn)；2）掌握線性表的鏈接存儲表示及實(shí)現(xiàn)；3）理解線性表的邏輯結(jié)構(gòu)和兩種存儲結(jié)構(gòu)；4）能夠應(yīng)用線性表解決實(shí)際問題，并能分析其時間復(fù)雜度。2. 實(shí)驗(yàn)主要內(nèi)容1）自行建立兩個有序的順序表，然后將其合并成一個新的有序表；2）自行建立兩個有序的單鏈表，然

17、后將其合并成一個新的有序單鏈表；3）分別分析有序的順序表合并和有序的單鏈表合并的算法時間復(fù)雜度。3. 重難點(diǎn)有序單鏈表的創(chuàng)建與合并，合并算法復(fù)雜度的分析。實(shí)驗(yàn)2：棧的應(yīng)用1. 實(shí)驗(yàn)?zāi)康募耙?) 了解棧的定義及特點(diǎn)；2）掌握順序棧的實(shí)現(xiàn)；3）掌握棧的簡單應(yīng)用。2. 實(shí)驗(yàn)主要內(nèi)容1）建立能夠存放十進(jìn)制整數(shù)的順序棧空棧；2）利用棧的特性完成數(shù)制轉(zhuǎn)換（十進(jìn)制數(shù)轉(zhuǎn)成二進(jìn)制數(shù)、八進(jìn)制數(shù)和十六進(jìn)制數(shù)）；3）建立能夠存放字符的順序?？諚＃?）利用棧的特性對輸入的字符串完成是否為回文的判斷；5）分別對上述兩個算法完成算法時間復(fù)雜度的分析。3. 重難點(diǎn)利用棧的特性對輸入的字符串完成是否為回文的判斷。實(shí)驗(yàn)3：串的

18、應(yīng)用（字符串的聯(lián)接和字符串的模式匹配）1. 實(shí)驗(yàn)?zāi)康募耙?) 了解串的三種存儲結(jié)構(gòu)；2）掌握串的定長順序存儲結(jié)構(gòu)；3）掌握串的簡單模式匹配算法并分析該算法的時間復(fù)雜度。2. 實(shí)驗(yàn)主要內(nèi)容1）采用定長順序存儲結(jié)構(gòu)存儲兩個長度不超過255的字符串；2）將上述兩個字符串聯(lián)接起來作為主串S；3）采用定長順序存儲結(jié)構(gòu)存儲一個長度不超過255的字符串作為模式子串T；4）采用簡單模式匹配算法，對主串S，從它的第pos個字符起和模式串T比較，如果模式串中的每個字符都和主串S中的字符序列匹配成功，則返回主串的pos；5）分別對上述兩個算法（串的聯(lián)接和串的模式匹配）完成算法時間復(fù)雜度的分析。3. 重難點(diǎn)定長順序

19、存儲的兩個串聯(lián)接時的各種情況分析；匹配不成功時主串應(yīng)回溯到的位置分析。實(shí)驗(yàn)4：二叉樹的遍歷1. 實(shí)驗(yàn)?zāi)康募耙?) 了解二叉樹的定義和遞歸的思想；2）掌握二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)：二叉鏈表；3）掌握二叉樹的5個基本性質(zhì)；4）掌握建立二叉樹的基本算法；5）掌握二叉樹的三種遍歷算法。2. 實(shí)驗(yàn)主要內(nèi)容1）對給定的二叉樹補(bǔ)足空結(jié)點(diǎn)（度為1的結(jié)點(diǎn)只需補(bǔ)1個空結(jié)點(diǎn)；度為0的結(jié)點(diǎn)需要補(bǔ)2個結(jié)點(diǎn)；度為2的結(jié)點(diǎn)不需要補(bǔ)空結(jié)點(diǎn)）；2）對補(bǔ)充過空結(jié)點(diǎn)的二叉樹進(jìn)行先序遍歷（空結(jié)點(diǎn)用#表示）；3）根據(jù)先序遍歷的結(jié)果，遞歸建立二叉樹；4）分別用遞歸和非遞歸的算法中序遍歷該二叉樹，輸出中序遍歷的結(jié)果（不包含空結(jié)點(diǎn)）；5）分別

20、對上述算法完成算法時間復(fù)雜度的分析。3. 重難點(diǎn)根據(jù)先序遍歷的結(jié)果，遞歸建立二叉樹。實(shí)驗(yàn)5：赫夫曼樹及其應(yīng)用1. 實(shí)驗(yàn)?zāi)康募耙?) 了解最優(yōu)二叉樹的定義及特點(diǎn)；2）掌握赫夫曼樹的構(gòu)造過程；3）掌握赫夫曼編碼。2. 實(shí)驗(yàn)主要內(nèi)容1）根據(jù)輸入的一串電文字符，分別統(tǒng)計(jì)各個字符在電文中出現(xiàn)的頻率；2）根據(jù)各個字符在電文中出現(xiàn)的頻率建立赫夫曼樹；3）為赫夫曼樹上的每個葉子結(jié)點(diǎn)實(shí)現(xiàn)赫夫曼編碼，并輸出該編碼；4）對Huffman編碼生成的代碼串進(jìn)行譯碼，輸出電文字符串。3. 重難點(diǎn)建立赫夫曼樹，求每個字符的赫夫曼編碼。實(shí)驗(yàn)6：圖的建立與遍歷1. 實(shí)驗(yàn)?zāi)康募耙?) 理解并掌握圖的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)鄰接矩陣

21、、鄰接表；2）以鄰接表為存儲結(jié)構(gòu)，掌握無向圖的基本操作和實(shí)現(xiàn)方法；3）掌握圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷算法；4）能夠?qū)ι鲜鏊惴ㄟM(jìn)行時間復(fù)雜度分析。2. 實(shí)驗(yàn)主要內(nèi)容1）以鄰接表為存儲結(jié)構(gòu)，根據(jù)輸入的頂點(diǎn)數(shù)、邊數(shù)、頂點(diǎn)信息、邊的權(quán)值等信息構(gòu)造一個無向圖G；2）深度優(yōu)先遍歷圖G，將從鍵盤輸入的頂點(diǎn)作為起始點(diǎn)，輸出深度優(yōu)先遍歷的頂點(diǎn)序列；3）廣度優(yōu)先遍歷圖G，將從鍵盤輸入的頂點(diǎn)作為起始點(diǎn)，輸出廣度優(yōu)先遍歷的頂點(diǎn)序列；4）分別對深度優(yōu)先遍歷和廣度優(yōu)先遍歷兩個算法完成算法時間復(fù)雜度的分析；3. 重難點(diǎn)用鄰接表的存儲結(jié)構(gòu)完成圖的構(gòu)造。實(shí)驗(yàn)7：順序查找與二分法查找的實(shí)現(xiàn)與比較1. 實(shí)驗(yàn)?zāi)康募耙?）掌握順

22、序查找的過程、算法以及性能分析；2）了解平均查找長度的定義，掌握平均查找長度的計(jì)算方法；3）掌握二分法查找的過程、算法以及性能分析。2. 實(shí)驗(yàn)主要內(nèi)容1）采用順序表結(jié)構(gòu)存放查找數(shù)據(jù)，關(guān)鍵字類型為整型；2）采用哨兵法完成順序查找，計(jì)算平均查找長度；3）對上述順序表中的數(shù)據(jù)進(jìn)行排序；4）利用二分查找法完成查找，計(jì)算平均查找長度；5）分別對上述兩個算法完成算法時間復(fù)雜度的分析，對比二者的查找效率。3. 重難點(diǎn)計(jì)算二分法查找的平均查找長度。實(shí)驗(yàn)8：快速排序算法1. 實(shí)驗(yàn)?zāi)康募耙?）理解內(nèi)部排序的定義及相關(guān)概念；2）掌握常用的排序算法快速排序的實(shí)現(xiàn)；3）掌握排序算法的時間復(fù)雜度分析過程以及穩(wěn)定性分析。

23、2. 實(shí)驗(yàn)主要內(nèi)容1）建立能夠存放n個十進(jìn)制整數(shù)的順序表；2）隨機(jī)選定其中一個元素作為樞軸；3）根據(jù)樞軸，進(jìn)行一趟快速排序，將原數(shù)列劃分成兩個待排序序列；4）分別遞歸對兩個子序列進(jìn)行快速排序；5）對快速排序算法完成算法時間復(fù)雜度和穩(wěn)定性分析；3. 重難點(diǎn)快速排序的思想和算法時間復(fù)雜度分析。注：本課程為專業(yè)課，授課對象為大二學(xué)生，實(shí)驗(yàn)類型主要包括驗(yàn)證性和設(shè)計(jì)性實(shí)驗(yàn)，均需要提交實(shí)驗(yàn)報(bào)告，實(shí)驗(yàn)報(bào)告主要包括實(shí)驗(yàn)?zāi)康?、?shí)驗(yàn)內(nèi)容、預(yù)習(xí)內(nèi)容、實(shí)驗(yàn)步驟、算法的時間復(fù)雜度分析以及總結(jié)。實(shí)驗(yàn)評價內(nèi)容和評分細(xì)則參見附錄1。四、學(xué)時分配及教學(xué)方法章教學(xué)形式及學(xué)時分配主要教學(xué)方法支撐的課程目標(biāo)課堂教學(xué)實(shí)驗(yàn)上機(jī)課程實(shí)踐小

24、計(jì)第一章緒論44講授、案例、演示課程目標(biāo)1， 2第二章線性表628講授、案例、自學(xué)、實(shí)驗(yàn)課程目標(biāo)1， 2第三章棧和隊(duì)列628講授、對比、自學(xué)、討論、實(shí)驗(yàn)課程目標(biāo)1， 2， 3第四章串224講授、演示、自學(xué)、實(shí)驗(yàn)課程目標(biāo)1， 2第五章數(shù)組22講授、自學(xué)課程目標(biāo)1， 2第六章樹和二叉樹8412講授、案例、演示、討論、自學(xué)、實(shí)驗(yàn)課程目標(biāo)1， 2， 3第七章圖8210講授、案例、演示、討論、自學(xué)、實(shí)驗(yàn)課程目標(biāo)1， 2， 3第八章查找628講授、案例、演示、實(shí)驗(yàn)課程目標(biāo)1， 2， 3第九章內(nèi)部排序628講授、案例、演示、實(shí)驗(yàn)課程目標(biāo)1， 2， 3合計(jì)481664注：1.課程實(shí)踐學(xué)時按相關(guān)專業(yè)培養(yǎng)計(jì)劃列入表格； 2.主要教學(xué)方法包括講授法、討論法、演示法、研究型教學(xué)方法（基于問題、項(xiàng)目、案例等教學(xué)方法）等。五、課程考核 1. 課程考核方式包括期末考試、平時作業(yè)和實(shí)驗(yàn)情況考核?？己诵问娇己艘罂己藱?quán)重備注平時作業(yè)及階段測試課后完成1015個習(xí)題，主要考核學(xué)生對每節(jié)課知識點(diǎn)的復(fù)習(xí)、理解和掌握度，計(jì)算全部作業(yè)的平均成績再按15%計(jì)入總成績；可讓學(xué)生查閱資料，了解本課程相關(guān)技術(shù)發(fā)展情況，自主學(xué)習(xí)并完成。15%根據(jù)平時作業(yè)得分取平均值或結(jié)