數(shù)據(jù)結構教學大綱

1、XX師范學院大學本科專業(yè)教學大綱中文課程名稱：數(shù)據(jù)結構英文課程名稱：Data Structures適用專業(yè)：信息管理與信息系統(tǒng) 制定單位：商學院 執(zhí)筆人： 審核人： 單位負責人： 制定時間：2017-2-10XX師范學院教務處二一七年一月數(shù)據(jù)結構課程教學大綱一、課程基本信息（一）課程代碼及課程名稱1.課程代碼：2.課程名稱（中/英文）：數(shù)據(jù)結構/Data Structures （二）課程類別及課程性質專業(yè)教育必修課程（三）學時及學分： 總學時數(shù)：64；總學分數(shù)：3。其中，講授學時：32 ，實踐（實驗）學時：32。（四）適用專業(yè)及開設學期適用專業(yè)：信息管理與信息系統(tǒng)（本科）開設學期：第二學期（五

2、）先修課程與后續(xù)課程先修課程：大學計算機基礎、高等數(shù)學、C語言程序設計后續(xù)課程：數(shù)據(jù)庫原理與應用、管理信息系統(tǒng)分析與設計、管理信息系統(tǒng)、Java程序設計(高級)二、課程簡介“數(shù)據(jù)結構”是信息管理與信息系統(tǒng)專業(yè)一門重點專業(yè)基礎課程，也是學科專業(yè)核心專業(yè)基礎課程之一，屬于專業(yè)學位必修課程。本課程的教學任務是針對大量的信息處理對象，介紹對象信息與數(shù)據(jù)表示的各種抽象的、基本的邏輯結構及其上的基本運算操作。通過研究各種基本數(shù)據(jù)結構內在的邏輯關系和它們在計算機中的存儲表示方式，初步建立數(shù)據(jù)結構上基本運算操作的正確性概念，同時，結合各種典型問題討論其上的各種基本運算操作及其基本算法，講授各種數(shù)據(jù)結構的特點、

3、適用范圍，以及對一些基本算法效率的定性和定量分析方法，為后續(xù)課程提供必要的數(shù)據(jù)結構基礎。此外，配合實驗課程的教學中，學生應理論聯(lián)系實際，理論指導實踐，通過規(guī)范地完成一系列數(shù)據(jù)結構實驗進一步鞏固所學的相關書本知識，在知識、能力、素質上得到進一步的提高。三、教學目的與基本要求（一）該課程教學目的與專業(yè)培養(yǎng)要求對應關系矩陣 培養(yǎng)要求課程名稱培養(yǎng)要求1培養(yǎng)要求2培養(yǎng)要求3培養(yǎng)要求4培養(yǎng)要求5培養(yǎng)要求6培養(yǎng)要求7培養(yǎng)要求8培養(yǎng)要求9培養(yǎng)要求數(shù)據(jù)結構說明：表格要清晰展示該課程與每項培養(yǎng)要求達成的關聯(lián)度情況，關聯(lián)度強的用“”標識，關聯(lián)度中等的用“”標識，關聯(lián)度弱的用“”標識；每門課程與4-8項（底線為總培養(yǎng)

4、要求的50%）培養(yǎng)要求相關聯(lián)。（二）教學目的數(shù)據(jù)結構A在計算機科學中是一門綜合性的專業(yè)基礎課，不僅是一般程序設計的基礎，而且是設計和實現(xiàn)操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)、編譯程序及其它系統(tǒng)程序和大型應用程序的重要基礎。本課程討論各種數(shù)據(jù)組織中的數(shù)據(jù)的邏輯結構、存儲結構以及有關操作的算法。目的是使學生學會分析研究計算機所要加工處理的數(shù)據(jù)的特征，掌握組織數(shù)據(jù)、存儲數(shù)據(jù)和處理數(shù)據(jù)的基本方法，并加強在實際應用中選擇合適的數(shù)據(jù)結構和設計相應算法的訓練，課程的具體教學目的如下：數(shù)據(jù)結構與算法是計算機科學教育中的一門核心課程。數(shù)據(jù)結構與算法主要討論在應用計算機解決問題時，如何有效地組織數(shù)據(jù)、表示數(shù)據(jù)和處理數(shù)據(jù)， 以及如

5、何設計正確的算法和評價算法的效率。課程介紹常見的數(shù)據(jù)結構及其應用，常用的數(shù)據(jù)處理技術和算法，以及算法效率估算的基本技術。通過本課程的學習， 學生應該掌握常用的數(shù)據(jù)結構，掌握合理地組織數(shù)據(jù)結構和表示數(shù)據(jù)的方法，掌握有效地處理數(shù)據(jù)的方法，掌握評價算法性能的基本方法。通過本課程的訓練，進一步提高學生的數(shù)據(jù)抽象能力；提高學生設計高質量程序的能力。本課程也為學生學習操作系統(tǒng)、編譯原理和數(shù)據(jù)庫等后續(xù)課程奠定基礎。1. 知識方面 1.1理解數(shù)據(jù)結構的一些基本概念、理解并掌握算法的描述方法，理解并掌握算法的時間復雜度和空間復雜度的概念以及分析方法。1.2理解各種數(shù)據(jù)結構的基本概念，深刻理解各種數(shù)據(jù)結構的邏輯特

6、性，理解并熟練掌握各種數(shù)據(jù)結構的存儲表示方法，理解并掌握在各種數(shù)據(jù)結構基礎上的算法設計與描述，并理解和掌握對算法性能進行分析的方法以及分析結果。1.3理解查找、排序的基本概念，掌握各種查找、排序方法及其算法描述和性能分析方法和分析結果。2. 能力與素質方面2.1 具備依據(jù)工程實際問題的需求合理地組織數(shù)據(jù)，并在計算機中有效地存儲數(shù)據(jù)的能力。2.2 具備為解決工程實際問題進行算法設計與分析的能力。2.3 具備將算法通過具體的編程語言加以實現(xiàn)的能力。（三）教學要求：通過本課程的學習，在基礎方面，要求學生能夠掌握常用數(shù)據(jù)結構的基本概念及其不同的實現(xiàn)方法；在技能方面，通過系統(tǒng)學習能夠在不同存儲結構上實現(xiàn)

7、不同的運算，并對算法設計的方式和技巧有所體會?？傃灾?，使應用者較全面的掌握各種常用的數(shù)據(jù)結構，提高運用數(shù)據(jù)結構解決實際問題的能力。1.掌握數(shù)據(jù)結構的概念及術語。2.掌握線性表（棧、隊列）的存儲結構（順序和鏈式存儲）、算法描述及應用。3.掌握數(shù)組的順序存儲和特殊矩陣的壓縮存儲。4.掌握樹的基本概念和術語，掌握二叉樹的基本性質和特點、存儲結構及算法描述、二叉樹的遍歷、樹、森林與二叉樹的轉換。掌握最優(yōu)二叉樹（哈夫曼樹）的特點及應用。5.掌握圖的基本概念和術語、存儲結構（鄰接矩陣、鄰接表、十字鏈表、鄰接多重表）、圖的遍歷、圖的連通性（最小生成樹）。 6.掌握查找的基本概念、基于線性表的查找方法（順序、

8、折半）。7.掌握插入類排序（直接、折半、表、希爾等插入排序）、交換類排序（冒泡、快速排序）。四、教學內容（一） 緒論（共4學時）（一）教學目的和要求介紹數(shù)據(jù)結構課程的研究對象，基本術語，掌握算法的要領，描述算法的類語言。了解數(shù)據(jù)結構的發(fā)展概況及其在計算機中的地位。（二）教學重點與難點教學重點：1、熟悉各名詞、術語的含義，特別是數(shù)據(jù)的邏輯結構和存儲結構之間的關系。分清哪些是邏輯結構的性質，哪些是存儲結構的性質；2、了解抽象數(shù)據(jù)類型的定義、表示和實現(xiàn)方法；3、理解算法五個要素的確切含義：動態(tài)有窮性（能執(zhí)行結束）；確定性（對于相同的輸入執(zhí)行相同的路徑）；有輸入；有輸出；可行性（用以描述算法的操作都是

9、足夠基本的）；4、掌握計算語句頻度和估算算法時間復雜度的方法。教學難點：1、掌握數(shù)據(jù)結構的意義及數(shù)據(jù)結構的基本內容；2、掌握數(shù)據(jù)結構及數(shù)據(jù)、數(shù)據(jù)元素等相關概念；3、掌握算法描述的方法；4、算法時間復雜度的計算。（三）教學內容1、什么是數(shù)據(jù)結構 2、基本概念和術語 3、抽象數(shù)據(jù)類型的表示與實現(xiàn) 4、算法和算法分析（二） 線性表（共8學時）（一）教學目的和要求掌握線性表的邏輯結構、順序存儲結構和鏈式存儲結構。掌握在線性表上實現(xiàn)基本運算的算法。（二）教學重點與難點教學重點：1、線性表的定義及邏輯上的特點；2、順序表上插入、刪除和定位運算的實現(xiàn)；3、單鏈表的結構特點及類型說明；4、頭指針和頭結點的作用

10、及區(qū)別；指針操作；5、定位、刪除、插入運算在單鏈表上的實現(xiàn)；6、循環(huán)鏈表、雙鏈表的結構特點；及其刪除與插入運算的實現(xiàn)。教學難點：1、線性表與線性結構的聯(lián)系與區(qū)別；2、線性表的順序存儲結構及其運算； 3、頭結點在鏈表中的作用和指針的操作；4、單鏈表存儲結構定義，刪除、插入運算中的指針操作順序；5、單鏈表的基本運算的實現(xiàn)；6、循環(huán)鏈表、雙鏈表上指針的操作順序及其相關運算。（三）教學內容1、線性表的類型定義 2、線性表的順序表示和實現(xiàn) 3、線性表的鏈式表示和實現(xiàn) 4、一元多項式的表示及相加 （三） 棧和隊列（共8學時）（一）教學目的和要求掌握棧和隊列的邏輯結構定義，掌握在兩種存儲結構上如何實現(xiàn)棧和隊

11、列的基本運算，掌握棧在程序設計中的應用。（二）教學重點與難點教學重點：1、棧的定義及邏輯特點；棧上的基本運算；2、棧的順序存儲結構及運算實現(xiàn)；鏈式存儲結構；3、入棧、出棧等運算在鏈棧上的實現(xiàn)；4、隊列的定義及邏輯特點；隊列上的基本運算；5、隊列的順序存儲結構及其上的運算實現(xiàn)；6、隊列的鏈式存儲結構；7、入隊、出隊等運算在鏈隊列上的實現(xiàn)。教學難點：1、順序?；具\算的實現(xiàn)；2、順序棧的溢出判斷條件； 3、棧的應用；4、循環(huán)隊列的隊空、隊滿判斷條件；循環(huán)隊列上的插入、刪除操作。（三）教學內容1、棧的類型定義2、棧的應用舉例3、棧與遞歸的實現(xiàn)4、隊列的類型定義 （四） 串和數(shù)組（共8學時）（一）教學

12、目的和要求掌握字符串的存儲結構，以及字符串的操作算法，掌握數(shù)組的順序存儲和特殊矩陣的壓縮存儲。（二）教學重點與難點教學重點：1、熟悉串的定義及串的基本操作；2、串的兩種存儲方式；3、字符串的運算；4、串的模式匹配算法。5、多維組的邏輯結構，兩種順序存儲方式；6、計算給定元素在存儲區(qū)中的地址；7、對稱矩陣、三角矩陣的壓縮存儲方式；8、計算給定元素在存儲區(qū)中的地址；9、稀疏矩陣的三元組表表示方法；教學難點：1、串的基本運算的綜合應用；2、串的模式匹配算法。3、了解數(shù)組的兩種存儲表示方法，并掌握數(shù)組在以行為主的存儲結構中的地址計算方法；4、稀疏矩陣的壓縮存儲表示下的運算的實現(xiàn)；5、了解稀疏矩陣的三類

13、壓縮存儲方法的特點和適用范圍，領會以三元組表示稀疏矩陣時進行矩陣運算采用的處理方法；（三）教學內容1、棧的類型定義2、棧的應用舉例3、棧與遞歸的實現(xiàn)4、隊列的類型定義5、數(shù)組的定義6、數(shù)組的順序表示和實現(xiàn)7、矩陣的壓縮存儲（五） 樹和二叉樹（共12學時）（一）教學目的和要求 掌握樹的基本概念和術語，掌握二叉樹的基本性質和特點、存儲結構及算法描述、二叉樹的遍歷、樹、森林與二叉樹的轉換。掌握最優(yōu)二叉樹（哈夫曼樹）的特點及應用。（二）教學重點與難點教學重點：1、二叉樹的定義、性質、邏輯特點及五種基本形態(tài)、基本運算； 2、二叉樹的鏈式存儲結構、順序存儲結構及其類型說明； 3、二叉樹鏈式存儲結構的組織方

14、式； 4、二叉樹的三種遍歷方法及其算法，以遍歷為基礎在二叉樹上實現(xiàn)的幾種運算； 5、哈夫曼樹和哈夫曼算法；森林與二叉樹的轉換。教學難點：1、二叉樹的遞歸定義；2、二叉樹鏈式存儲結構的組織方式；3、三種遍歷的主要區(qū)別；二叉樹上的復雜運算4、森林與二叉樹的轉換；5、哈夫曼算法及其應用。（三）教學內容1、樹的定義和基本術語2、二叉樹3、遍歷二叉樹和線索二叉樹4、樹和森林5、回溯法與樹的遍歷6、赫夫曼樹及其應用（六） 圖（共8學時）（一）教學目的和要求 掌握圖的基本概念和術語、存儲結構（鄰接矩陣、鄰接表、十字鏈表、鄰接多重表）、圖的遍歷、圖的連通性（最小生成樹）。理解拓撲排序及關鍵路徑和最短路徑的應用

15、及意義。（二）教學重點與難點教學重點：1、理解圖的定義、術語及其含義，各種圖的鄰接矩陣表示法及其類型說明；2、理解并掌握圖的按深度優(yōu)先搜索遍歷方法和按廣度優(yōu)先搜索遍歷方法；3、領會生成樹和最小生成樹的概念；4、掌握由Prim算法思想構造最小生成樹按Prim算法思想；5、掌握拓撲序列和拓撲排序的概念，拓撲排序、關鍵路徑、最短路徑的算法思想。教學難點：1、正確理解與區(qū)別圖的常用術語；2、區(qū)別圖的兩種存儲結構的不同點及其應用場合；3、關鍵路徑的算法思想；最短路徑的算法思想。（三）教學內容1、圖的定義和術語2、圖的存儲結構3、圖的遍歷4、圖的連通性問題5、有向無環(huán)圖及其應用6、最短路徑（七） 查找（共

16、8學時）（一）教學目的和要求 掌握查找的基本概念、基于線性表的查找方法（順序、折半）。理解基于樹的查找方法（二叉排序樹、平衡二排序叉樹）。（二）教學重點與難點教學重點：1、查找表的基本概念及查找原理；順序存儲結構、順序表及其類型說明；2、查找運算在查找表和有序表上的實現(xiàn)；3、二叉排序樹的定義、性質及各結點間的鍵值關系，查找算法和基本思想；4、平衡二叉排序樹的概念；B-樹和B+樹的概念；5、散列表及散列存儲和散列查找的基本思想；各種散列表的組織、解決沖突的方法；教學難點：1、理解查找表的邏輯結構是集合，它的運算以查找為核心；2、二叉排序樹上的插入算法；平衡二叉樹的旋轉平衡算法；3、散列表上的有關

17、算法。（三）教學內容1、靜態(tài)查找表2、動態(tài)查找表3、哈希表（八） 排序（共8學時）（一）教學目的和要求 掌握插入類排序（直接、折半、表、希爾等插入排序）、交換類排序（冒泡、快速排序）。理解選擇類排序、歸并類排序和基數(shù)類排序。（二）教學重點與難點教學重點：1、排序基本概念及內排序和外排序、穩(wěn)定排序和非穩(wěn)定排序的區(qū)別；2、插入排序、冒泡排序、快速排序、直接選擇排序、堆排序的基本思想、基本步驟和算法；3、歸并排序的思想；兩個有序文件合并的方法和算法；4、二路歸并排序的算法和時空性能；教學難點：1、快速排序算法；2、堆排序方法。（三）教學內容1、插入排序2、快速排序3、選擇排序4、歸并排序5、基數(shù)排序

18、6、各種內部排序方法的比較討論五、教學時數(shù)分配數(shù)據(jù)結構課程教學時數(shù)分配表總學時：64 學分：3 章次章標題名稱學時小計講授學時實驗學時實踐學時討論、習題課等學時第一章緒論422第二章線性表8341第三章棧和隊列8341第四章串和數(shù)組844第五章樹和二叉樹12462第六章圖8341第七章查找8341第八章排序8341六、實驗內容與學時分配數(shù)據(jù)結構課程實驗教學一覽表 序號項目名稱內容提要學時實驗類型（演示、驗證、綜合、設計等）開放1一元二次方程求解復習函數(shù)定義，函數(shù)調用和參數(shù)傳遞及相關知識。2驗證否2線性表的操作建立順序表及鏈表，并完成查找、插入、刪除操作。4驗證否3棧與隊列的應用利用棧完成括號匹配，利用隊列模擬病人看病。4設計否4二叉樹的遍歷及應用利用二叉鏈表方法建立二叉樹，實現(xiàn)二叉樹的前、中、后序三種遍歷算法。并運用遍歷算法實現(xiàn)二叉樹的其他操作，如計算二叉樹結點個數(shù)、葉子結點個數(shù)、二叉樹的高度等。10驗證否5查找算法設計與實現(xiàn)選擇兩種查找算法實現(xiàn)查找并比較。6驗證否6排序算法設計與實現(xiàn)選擇兩種排序算法實現(xiàn)排序并比較。6驗證否七、本課程的實踐環(huán)節(jié)八、主要的教學方法與教學手段1.課程與教學方法、教學手段對應關系矩陣課程名稱對應的教學方式方法講授法啟發(fā)式討論法案例法項目教學實驗室實驗技能