《數(shù)據結構》課程教學大綱

《數(shù)據結構》課程教學大綱一、課程基本信息課程編號：B022314課程名稱：數(shù)據結構英文名稱：DataStructure先修課程：高等數(shù)學、C語言程序設計適用專業(yè)：通信工程課程類別：專業(yè)教育選修課程/拓展課程課程總學時/學分：48/3（其中理論38學時，實驗10學時）二、課程目標通過本課程的學習，使學生具備下列能力：1．掌握數(shù)據結構的基本概念，了解數(shù)據結構及其分類、數(shù)據結構與算法的密切關系；熟悉各種基本數(shù)據結構及其操作；掌握設計算法的步驟和算法分析方法；掌握數(shù)據結構在排序和查找等常用算法中的應用。2．學會分析研究數(shù)據結構的特性，能為應用問題涉及的數(shù)據選擇適當?shù)倪壿嫿Y構、存儲結構和操作，培養(yǎng)對給定實際問題選擇和構造合適數(shù)據結構及設計有效算法的能力。3．初步掌握算法的時間分析和空間分析技術，提高理論水平，增強抽象和設計的能力，為以后進行軟件開發(fā)和學習后續(xù)課程打下一個堅實的基礎。三、課程目標與畢業(yè)要求的關系畢業(yè)要求指標點課程目標3.設計/開發(fā)解決方案：能夠針對信息通信領域的復雜工程問題提出有效的解決方案，設計滿足功能需求、性能指標的軟硬件系統(tǒng)或功能單元，并能夠在設計環(huán)節(jié)中體現(xiàn)創(chuàng)新意識，考慮社會、健康、安全、法律、文化以及環(huán)境等因素。3-4能夠對通信系統(tǒng)進行測試和評價、優(yōu)化和改進；課程目標2課程目標34.研究：能夠基于科學原理并采用科學方法對信息通信領域復雜工程問題進行研究，包括設計實驗、分析與解釋數(shù)據，并通過信息綜合得到合理有效的結論。4-1針對信息通信領域復雜工程問題的關鍵因素，基于科學原理制定實驗目標和方法，設計實驗方案；課程目標1課程目標2課程目標3四、教學內容、要求及重難點第一章緒論（2學時）教學要求：1.熟悉數(shù)據、數(shù)據元素、數(shù)據項、數(shù)據對象、數(shù)據結構、邏輯結構、存儲結構和數(shù)據類型等概念術語的含義，掌握基本概念，特別是數(shù)據的邏輯結構和存儲結構之間的關系。2.了解邏輯結構和存儲結構的性質，抽象數(shù)據類型的定義及表示方法。3.理解算法五個特性的確切含義。4.掌握計算語句頻度和估算算法時間復雜度的方法。5.熟悉算法描述規(guī)范與設計風格。教學重點：各概念術語的確切含義，算法的概念、評價標準及從時間和空間角度分析算法的方法。教學難點：數(shù)據結構的基本概念，數(shù)據的邏輯結構、存儲結構及其差異，算法的時間復雜度分析。第二章線性表（10學時）教學要求：1.了解線性表的邏輯結構特性。2.熟練掌握順序存儲結構和鏈式存儲結構的描述方法。3.熟練掌握在順序存儲結構中線性表的查找、插入、刪除和合并操作。4.熟練掌握在單鏈表存儲結構中線性表的查找、插入、刪除和合并操作。5.了解在循環(huán)鏈表、雙向鏈表存儲結構中實現(xiàn)線性表操作的基本方法。6.了解靜態(tài)鏈表。7.掌握線性表兩種存儲結構的不同特點及其使用場合。教學重點：順序表的存儲結構的描述方法，線性表在順序存儲結構上的基本操作，鏈式存儲結構的描述方法，線性表在鏈式存儲結構上的基本操作。教學難點：各種鏈表的特點及在其上實現(xiàn)線性表基本操作的方法。[實驗名稱]鏈表[實驗類型]設計性[實驗要求]1.編寫程序實現(xiàn)鏈表的創(chuàng)建、插入、查找、刪除操作。2.通過本實驗加深對鏈表的理解，掌握鏈表的創(chuàng)建、插入、查找、刪除操作。[實驗學時]2學時第三章棧和隊列（6學時）教學要求：1.掌握棧和隊列的操作特性，并能在相應的應用問題中正確選用它們。2.熟練掌握棧類型的兩種實現(xiàn)方法。3.掌握棧滿和?？盏臈l件以及它們的描述方法。4.掌握循環(huán)隊列和鏈隊列的基本操作實現(xiàn)算法。5.掌握隊滿和隊空的條件以及它們的描述方法。教學重點：棧和隊列這兩種結構的特點，棧和隊列在兩種存儲結構中的實現(xiàn)。教學難點：隊滿和隊空的條件以及它們的描述方法，循環(huán)隊列的基本操作實現(xiàn)算法。[實驗名稱]棧及其運算[實驗類型]設計性[實驗要求]1.編寫程序實現(xiàn)棧的進棧、出棧和判?？盏冗\算。2.通過本實驗加深對棧的理解，掌握棧的進棧、出棧和判?？盏冗\算。[實驗學時]2學時第四章串（2學時）教學要求：1.熟悉串的七種基本操作的定義，并能利用這些基本操作實現(xiàn)串的其它各種操作的方法。2.熟練掌握在串的定長順序存儲結構上實現(xiàn)串的各種操作的方法。3.掌握堆串存儲結構以及在其上實現(xiàn)串操作的基本方法。4.了解串匹配的KMP算法。5.了解塊鏈串的結構定義。教學重點：串的基本操作和存儲方法。教學難點：在串的存儲結構上實現(xiàn)基本操作，KMP算法。第五章數(shù)組和廣義表（2學時）教學要求：1.掌握數(shù)組的兩種存儲表示方法，并掌握數(shù)組在以行為主的存儲結構中的地址計算方法。2.理解掌握對特殊矩陣進行壓縮存儲的下標變換公式。3.了解稀疏矩陣的兩種存儲方法的特點和適用范圍，領會以三元組表示稀疏矩陣時進行矩陣運算采用的處理方法。4.掌握廣義表的結構特點及其存儲表示方法。5.了解對非空廣義表進行分解的兩種分析方法：即可將一個非空廣義表分解為表頭和表尾兩部分或者分解為n個子表。教學重點：數(shù)組的順序存儲，矩陣的壓縮存儲。教學難點：稀疏矩陣的兩種壓縮存儲方法。第六章樹和二叉樹（8學時）教學要求：1.熟練掌握二叉樹的結構特性，了解相應的證明方法。2.熟悉二叉樹的各種存儲結構的特點及適用范圍。3.熟練掌握二叉樹各種遍歷策略的遞歸算法。4.理解二叉樹線索化的實質。5.了解二叉樹的線索化過程以及在中序線索化樹上找給定結點的前驅和后繼的方法。6.熟悉樹的各種存儲結構及其特點，了解樹和森林與二叉樹的轉換方法。7.掌握建立哈夫曼樹和構造哈夫曼編碼的方法。教學重點：二叉樹的定義、性質和存儲結構，二叉樹的遍歷，哈夫曼樹的基本概念及哈夫曼算法。教學難點：理解二叉樹的性質及其證明，各種二叉樹遍歷策略的遞歸算法及應用，哈夫曼算法的實現(xiàn)。[實驗名稱]二叉樹的建立及輸出[實驗類型]設計性[實驗要求]1.編寫程序實現(xiàn)的二叉樹的創(chuàng)建和遍歷。2.通過本實驗加深對二叉樹的二叉鏈表存儲結構的理解，掌握二叉樹的三種遍歷算法。[實驗學時]2學時第七章圖（8學時）教學要求：1.熟悉圖的各種存儲結構及其構造算法。2.熟練掌握圖的兩種搜索路徑的遍歷：深度優(yōu)先搜索和廣度優(yōu)先搜索的算法。3.掌握應用圖的遍歷算法求解各種簡單路徑問題的方法。4.掌握圖的最小生成樹算法及最短路徑的求法。5.理解拓撲排序及關鍵路徑的的推導方法。教學重點：圖的鄰接矩陣表示法和鄰接表表示法，圖的深度優(yōu)先和廣度優(yōu)先遍歷算法，最小生成樹的概念及構造方法，拓撲排序，最短路徑的求解思路。教學難點：圖的鄰接表表示法，深度優(yōu)先和廣度優(yōu)先遍歷算法，最小生成樹的構造方法，求解最短路徑的思路及算法。[實驗名稱]圖及其遍歷[實驗類型]綜合性[實驗要求]1.編寫程序實現(xiàn)圖的存儲和圖的深度優(yōu)先搜索算法以及廣度優(yōu)先搜索算法。2.通過本實驗加深對圖的鄰接矩陣和鄰接表的存儲結構的理解，掌握圖的深度優(yōu)先搜索算法以及廣度優(yōu)先搜索算法。[實驗學時]2學時第八章查找（6學時）教學要求：1.熟練掌握順序查找法和折半查找法，熟悉分塊查找法。2.熟練掌握二叉排序樹的構造和查找方法。3.了解平衡二叉排序樹的維護平衡方法。4.掌握哈希表的構造方法，深刻理解哈希表與其他表的實質性差別。5.掌握哈希表處理沖突的方法。6.熟悉求等概率情況下查找成功時的平均查找長度的方法。教學重點：順序查找、折半查找、索引順序查找各自的思路與特點，二叉排序樹的插入、刪除算法和查找方法，哈希表處理沖突的方法，哈希表的查找及其分析。教學難點：各種查找算法的思路和算法實現(xiàn)，平衡二叉排序樹的維護平衡方法，哈希表處理沖突的方法及其分析。[實驗名稱]樹表的查找[實驗類型]設計性[實驗要求]1.編寫程序實現(xiàn)樹表的查找。2.通過本實驗加深對二叉排序樹的理解，掌握二叉排序樹的插入、查找等操作。[實驗學時]2學時第九章內部排序（4學時）教學要求：1.深刻理解排序的定義，理解插入排序、交換排序、選擇排序、歸并排序、基數(shù)排序各種方法的基本思想。2.了解各種方法的排序過程及其依據的原則。3.掌握各種排序算法及時間復雜度的分析方法。4.理解排序方法的“穩(wěn)定”或“不穩(wěn)定”的含義。5.了解各種內部排序方法的應用。教學重點：各種排序的基本思想、算法特點、穩(wěn)定性及算法時間復雜度的分析。教學難點：希爾排序、快速排序、堆排序及基數(shù)排序的基本思想和算法實現(xiàn)，各種排序算法時間復雜度的分析方法。五、課程教學內容、教學方式對課程目標的支撐序號課程內容框架教學內容教學方式學時支撐課程目標1緒論數(shù)據結構的基本概念；邏輯結構和存儲結構的性質，抽象數(shù)據類型的定義及表示方法；算法的五個特性；計算語句頻度和估算算法時間復雜度的方法；算法描述規(guī)范與設計風格。講授、課堂討論、課堂引導與啟發(fā)下的課堂訓練和課外作業(yè)布置2課程目標12線性表線性表的邏輯結構特性;順序存儲結構和鏈式存儲結構的描述方法；在順序存儲結構中線性表的查找、插入、刪除和合并操作；在單鏈表存儲結構中線性表的查找、插入、刪除和合并操作；在循環(huán)鏈表、雙向鏈表存儲結構中實現(xiàn)線性表操作的基本方法；靜態(tài)鏈表；線性表兩種存儲結構的不同特點及其使用場合。講授、課堂討論、課堂引導與啟發(fā)下的課堂訓練和課外作業(yè)布置、學生動手實驗和課后撰寫實驗報告10課程目標1課程目標2課程目標33棧和隊列棧和隊列的操作特性；棧類型的兩種實現(xiàn)方法；棧滿和?？盏臈l件以及它們的描述方法；循環(huán)隊列和鏈隊列的基本操作實現(xiàn)算法；隊滿和隊空的條件以及它們的描述方法。講授、課堂討論、課堂引導與啟發(fā)下的課堂訓練和課外作業(yè)布置、學生動手實驗和課后撰寫實驗報告6課程目標1課程目標2課程目標34串串的七種基本操作的定義，利用這些基本操作實現(xiàn)串的其它各種操作的方法；在串的定長順序存儲結構上實現(xiàn)串的各種操作的方法；堆串存儲結構以及在其上實現(xiàn)串操作的基本方法；串匹配的KMP算法；塊鏈串的結構定義。講授、課堂討論、課堂引導與啟發(fā)下的課堂訓練和課外作業(yè)布置、學生動手實驗和課后撰寫實驗報告2課程目標1課程目標2課程目標35數(shù)組和廣義表數(shù)組的兩種存儲表示方法；數(shù)組在以行為主的存儲結構中的地址計算方法；對特殊矩陣進行壓縮存儲的下標變換公式；稀疏矩陣的兩種存儲方法的特點和適用范圍；以三元組表示稀疏矩陣時進行矩陣運算采用的處理方法；廣義表的結構特點及其存儲表示方法；非空廣義表進行分解的兩種分析方法。講授、課堂討論、課堂引導與啟發(fā)下的課堂訓練和課外作業(yè)布置、學生動手實驗和課后撰寫實驗報告2課程目標1課程目標2課程目標36樹和二叉樹二叉樹的結構特性及相應的證明方法；二叉樹的各種存儲結構的特點及適用范圍；二叉樹各種遍歷策略的遞歸和非遞歸算法；二叉樹線索化的實質；二叉樹的線索化過程以及在中序線索化樹上找給定結點的前驅和后繼的方法；樹的各種存儲結構及其特點；樹和森林與二叉樹的轉換方法；實現(xiàn)樹的各種操作；哈夫曼樹和構造哈夫曼編碼的方法。講授、課堂討論、課堂引導與啟發(fā)下的課堂訓練和課外作業(yè)布置、學生動手實驗和課后撰寫實驗報告8課程目標1課程目標2課程目標37圖圖的各種存儲結構及其構造算法；圖的深度優(yōu)先搜索算法和廣度優(yōu)先搜索算法；應用圖的遍歷算法求解各種簡單路徑問題的方法；圖的最小生成樹算法及最短路徑的求法；拓撲排序及關鍵路徑的的推導方法。講授、課堂討論、課堂引導與啟發(fā)下的課堂訓練和課外作業(yè)布置、學生動手實驗和課后撰寫實驗報告8課程目標1課程目標2課程目標38查找順序查找法、折半查找法和分塊查找法；二叉排序樹的構造和查找方法；平衡二叉排序樹的維護平衡方法；B樹的特點以及它的建樹過程；哈希表的構造方法；哈希表與其他表的實質性差別；哈希表處理沖突的方法；求等概率情況下查找成功時的平均查找長度的方法；講授、課堂討論、課堂引導與啟發(fā)下的課堂訓練和課外作業(yè)布置、學生動手實驗和課后撰寫實驗報告6課程目標1課程目標39內部排序排序的定義；插入類排序的基本思想；直接插入排序、折半插入排序、希爾排序的算法、排序過程、時間復雜度及穩(wěn)定性；交換類排序的基本思想；冒泡排序、快速排序的算法、排序過程、時間復雜度及穩(wěn)定性；選擇類排序的基本思想；簡單選擇排序、樹形選擇排序、堆排序的算法、排序過程、時間復雜度及穩(wěn)定性；歸并排序的基本思想；歸并排序的算法、排序過程、時間復雜度及穩(wěn)定性；分配類排序的基本思想；基數(shù)排序的算法、排序過程、時間復雜度及穩(wěn)定性。講授、課堂討論、課堂引導與啟發(fā)下的課堂訓練和課外作業(yè)布置、學生動手實驗和課后撰寫實驗報告4課程目標1課程目標3六、課程目標與考核內容課程目標考核內容課程目標1：掌握數(shù)據結構的基本概念，了解數(shù)據結構及其分類、數(shù)據結構與算法的密切關系；熟悉各種基本數(shù)據結構及其操作；掌握設計算法的步驟和算法分析方法；掌握數(shù)據結構在排序和查找等常用算法中的應用。1.數(shù)據結構和算法的基本概念，線性表、棧和隊列、串、數(shù)組和廣義表、樹和二叉樹以及圖的基礎知識和相關操作，查找和排序的算法。2.出勤和平時作業(yè)的完成情況。3.期末考試成績。課程目標2：學會分析研究數(shù)據結構的特性，能為應用問題涉及的數(shù)據選擇適當?shù)倪壿嫿Y構、存儲結構和操作，培養(yǎng)對給定實際問題選擇和構造合適數(shù)據結構及設計有效算法的能力。1.利用四種邏輯結構和兩種存儲結構的知識分析實際的問題，選擇適當?shù)倪壿嫿Y構和存儲結構，并分析問題所涉及的操作，編寫出算法，解決問題。2.出勤和平時作業(yè)的完成情況。3.期末考試成績。課程目標3：初步掌握算法的時間分析和空間分析技術，提高理論水平，增強抽象和設計的能力，為以后進行軟件開發(fā)和學習后續(xù)課程打下一個堅實的基礎。1.對給定算法分析其時間和空間復雜度并根據分析優(yōu)化算法。2.出勤和平時作業(yè)的完成情況。3.期末考試成績。七、考核方式與評價細則考核方式比例考核/評價細則平時成績出勤10%1.全勤100分；2.曠課一次扣5分；3.遲到、早退、事假一次扣3分；4.上課時玩手機一次扣3分；5.上課睡覺一次扣3分；6.病