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

1、數(shù)據(jù)結(jié)構(gòu)教學大綱一、課程基本信息1課程中文名稱：數(shù)據(jù)結(jié)構(gòu)2課程英文名稱：Data Structures3課程類別：必修4適用專業(yè)：計算機科學與技術(shù)5總學時：72學時（其中理論54學時，上機18學時）6總學分：4二、本課程在教學計劃中的地位、作用和任務(wù)本課程是計算機專業(yè)的專業(yè)基礎(chǔ)課，是該專業(yè)的主干課之一，是研究數(shù)據(jù)之間的關(guān)系以及對數(shù)據(jù)如何進行有效處理的學科。課程的任務(wù)是介紹一些最常用的數(shù)據(jù)結(jié)構(gòu)，闡明數(shù)據(jù)結(jié)構(gòu)內(nèi)在的邏輯關(guān)系，討論它們在計算機中的存儲表示，并結(jié)合各種典型應(yīng)用說明它們在進行各種運算（操作）時的動態(tài)性質(zhì)及實際的執(zhí)行算法。三、理論教學內(nèi)容與教學基本要求1第一章 緒論（3學時）教學內(nèi)容：什么

2、是數(shù)據(jù)結(jié)構(gòu)；數(shù)據(jù)結(jié)構(gòu)的基本概念和常用的術(shù)語；數(shù)據(jù)結(jié)構(gòu)發(fā)展的歷史以及數(shù)據(jù)結(jié)構(gòu)在計算機科學中地位；算法描述和算法分析教學基本要求：了解數(shù)據(jù)結(jié)構(gòu)的發(fā)展和地位；了解各種算法描述方法和算法設(shè)計的基本要求；理解數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和抽象數(shù)據(jù)類型的基本概念；掌握對算法的評價標準和算法效率的度量方法。教學重點：理解數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和抽象數(shù)據(jù)類型的基本概念；掌握對算法的評價標準和算法效率的度量方法教學難點：算法的評價標準和算法效率的度量方法2第二章 線性表（9學時）教學內(nèi)容：線性表的邏輯結(jié)構(gòu)；線性表的順序存儲結(jié)構(gòu)；線性表的鏈式存儲結(jié)構(gòu)；線性表應(yīng)用舉例教學基本要求：理解線性表的概念、邏輯結(jié)構(gòu)特

3、性以及兩種存儲結(jié)構(gòu)特性，針對實際應(yīng)用能從時間和空間復雜度的角度選用適當?shù)拇鎯Y(jié)構(gòu)；熟練掌握線性表的順序存儲結(jié)構(gòu)及其各種基本運算；熟練掌握線性表的鏈式存儲結(jié)構(gòu)（單鏈表、循環(huán)鏈表、雙向鏈表）及其各種基本運算，能在實際應(yīng)用中選用適當?shù)逆湵斫Y(jié)構(gòu)。教學重點：線性表的概念、邏輯結(jié)構(gòu)特性以及兩種存儲結(jié)構(gòu)特性，線性表的順序存儲結(jié)構(gòu)及其各種基本運算；線性表的鏈式存儲結(jié)構(gòu)（單鏈表、循環(huán)鏈表、雙向鏈表）及其各種基本運算教學難點：線性表的各種基本運算3第三章 字符串（3學時）教學內(nèi)容：串類型的定義；串的表示和實現(xiàn)；串操作的應(yīng)用舉例教學基本要求：了解串的應(yīng)用；掌握串的基本概念、順序和鏈式存儲結(jié)構(gòu)；掌握串的各種基本運算；

4、 熟練掌握順序存儲結(jié)構(gòu)上串的各種操作。教學重點：串的基本概念、順序和鏈式存儲結(jié)構(gòu)及各種基本運算教學難點：串的各種基本運算4第四章 棧和隊列（6學時）教學內(nèi)容：棧；棧的應(yīng)用；棧與遞歸過程；隊列教學基本要求：掌握棧和隊列的定義、表示、實現(xiàn)和應(yīng)用；掌握棧的順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)以及相應(yīng)操作的實現(xiàn)；了解遞歸的概念和遞歸過程的實現(xiàn)；掌握隊列的順序存儲結(jié)構(gòu)（循環(huán)隊列）和鏈式存儲結(jié)構(gòu)的實現(xiàn)。教學重點：棧和隊列的定義、表示、實現(xiàn)和應(yīng)用；棧的順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)以及相應(yīng)操作的實現(xiàn)；隊列的順序存儲結(jié)構(gòu)（循環(huán)隊列）和鏈式存儲結(jié)構(gòu)的實現(xiàn)教學難點：棧和隊列的順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)以及相應(yīng)操作的實現(xiàn)5第五章

5、 樹和二叉樹（9學時）教學內(nèi)容：樹的定義；二叉樹；遍歷二叉樹和線索二叉樹；樹和森林；哈夫曼樹及其應(yīng)用教學基本要求：熟練掌握二叉樹的定義、性質(zhì)、各種存儲結(jié)構(gòu)的特點及適用范圍；熟練掌握二叉樹的各種遍歷算法；理解線索二叉樹的概念、存儲結(jié)構(gòu)及線索化算法；掌握樹和森林與二叉樹間的轉(zhuǎn)換，掌握樹和森林的遍歷算法；掌握哈夫曼樹的概念、存儲結(jié)構(gòu)；掌握建立哈夫曼樹和哈夫曼編碼的方法及帶權(quán)路徑長度的計算；理解樹的基本概念及其存儲結(jié)構(gòu)。教學重點：二叉樹的定義、性質(zhì)、各種存儲結(jié)構(gòu)的特點及適用范圍；二叉樹的各種遍歷算法；樹和森林與二叉樹間的轉(zhuǎn)換教學難點：二叉樹的各種遍歷算法，線索二叉樹線索化算法6第六章 集合與字典（9學

6、時）教學內(nèi)容：靜態(tài)查找表；動態(tài)查找表；哈希表教學基本要求：理解查找及其算法的時間復雜度；理解靜態(tài)查找表的概念；理解二叉平衡樹，B樹的概念；理解哈希表的含義；掌握二叉排序樹查找算法；掌握哈希函數(shù)的構(gòu)造方法，哈希表的建立和查找以及處理沖突的基本方法；熟練掌握順序查找、折半查找和分塊查找算法，能對其性能進行分析。教學重點：順序查找、折半查找和分塊查找算法，哈希函數(shù)的構(gòu)造方法，哈希表的建立和查找以及處理沖突的基本方法教學難點：哈希函數(shù)的構(gòu)造方法，哈希表的建立和查找以及處理沖突的基本方法，各種查找算法的性能進行分析7第八章 內(nèi)部排序（6學時）教學內(nèi)容：基本概念；插入排序；快速排序；選擇排序；歸并排序；基

7、數(shù)排序；各種內(nèi)部排序方法的比較討論教學基本要求：了解內(nèi)部排序的概念；了解歸并排序、基數(shù)排序的算法；掌握插入類排序的算法，直接插入排序、希爾排序； 掌握交換類排序的算法，冒泡排序、快速排序； 掌握選擇類排序的算法，簡單選擇排序、堆排序；掌握各種排序方法的特點，能夠?qū)Ω鞣N排序算法進行評價，并能加以靈活應(yīng)用。教學重點：插入類排序的算法，直接插入排序、希爾排序；掌握交換類排序的算法，冒泡排序、快速排序，掌握選擇類排序的算法，簡單選擇排序、堆排序教學難點：各種排序方法的特點，能夠?qū)Ω鞣N排序算法進行評價，并能加以靈活應(yīng)用8第九章 圖（9學時）教學內(nèi)容：圖的定義和術(shù)語；圖的存儲結(jié)構(gòu)；圖的遍歷；圖的連通性問題

8、；有向無環(huán)圖及其應(yīng)用；最短路徑教學基本要求：理解圖的基本概念，掌握圖的鄰接矩陣和鄰接表的存儲結(jié)構(gòu)；理解帶權(quán)最短路徑的概念，掌握用Dijkstra方法求最短路徑的算法；掌握構(gòu)造最小生成樹的方法及其算法；掌握求拓撲排序和關(guān)鍵路徑的方法，理解其算法；熟練掌握圖的深度優(yōu)先和廣度優(yōu)先遍歷算法。教學重點：圖的基本概念，掌握圖的鄰接矩陣和鄰接表的存儲結(jié)構(gòu)，圖的深度優(yōu)先和廣度優(yōu)先遍歷算法，用Dijkstra方法求最短路徑的算法；構(gòu)造最小生成樹的方法及其算法；求拓撲排序和關(guān)鍵路徑的方法教學難點：用Dijkstra方法求最短路徑的算法；構(gòu)造最小生成樹的方法及其算法；求拓撲排序和關(guān)鍵路徑的方法四、實驗教學內(nèi)容與要求

9、（簡要說明，詳見實驗課大綱）根據(jù)實驗大綱和要求進行。詳見實驗大綱。五、考核方式考試六、成績評定期末考試成績占70%，平時成績和實驗成績占30%七、本課程對學生創(chuàng)新能力培養(yǎng)的措施選擇一些算法作為作業(yè)讓學生獨立去實現(xiàn)，采用激勵與督促手段，隨后加以檢查和評講。八、教材與參考書教 材：張乃孝算法與數(shù)據(jù)結(jié)構(gòu)北京：高等教育出版社，2006年（面向21世紀課程教材）參考書：1 嚴蔚敏，吳偉民數(shù)據(jù)結(jié)構(gòu)（第二版）北京：清華大學出版社，1992年2 張乃孝數(shù)據(jù)結(jié)構(gòu)與算法學習輔導及習題詳解北京：電子工業(yè)出版社，2004年九、其它必要的說明1本課程教學大綱是按照計算機科學與技術(shù)（四年制）本科培養(yǎng)方案及課程基本要求并結(jié)合我校計算機科學與技術(shù)專業(yè)的學科建設(shè)情況與教學計劃制定的。