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

1、XX師范學院大學本科專業(yè)教學大綱中文課程名稱：數(shù)據(jù)結(jié)構(gòu)英文課程名稱：Data Structures適用專業(yè)：信息管理與信息系統(tǒng)制定單位：商學院執(zhí)筆人：審核人：單位負責人：制定時間：2017-2-10XX師范學院教務處二0一七年一月數(shù)據(jù)結(jié)構(gòu)課程教學大綱一、課程基本信息（一）課程代碼及課程名稱1 .課程代碼：061510902 .課程名稱（中/英文）:數(shù)據(jù)結(jié)構(gòu)/Data Structures（二）課程類別及課程性質(zhì)專業(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ù)結(jié)構(gòu)”是信息管理與信息系統(tǒng)專業(yè)一門重點專業(yè)基礎課程，也是學科 專業(yè)核心專業(yè)基礎課程之一，屬于專業(yè)學位必修課程。本課程的教學任務是針對 大量的信息處理對象，介紹對象信息與數(shù)據(jù)表示的各種抽象的、 基本的邏輯結(jié)構(gòu) 及其上的基本運算操作。通過研究各種基本數(shù)據(jù)結(jié)構(gòu)內(nèi)在的邏輯關(guān)系和它們在計 算機中的存儲表示方式，初步建立數(shù)據(jù)結(jié)構(gòu)上基本運算操作的正確性概念，同時,結(jié)合各種典型問題討論其上的各種基本運算操作及其基本算法，講授各

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

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

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

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

7、系統(tǒng)學習能夠在不同存儲結(jié)構(gòu)上實現(xiàn) 不同的運算，并對算法設計的方式和技巧有所體會?？傃灾箲谜咻^全面的 掌握各種常用的數(shù)據(jù)結(jié)構(gòu)，提高運用數(shù)據(jù)結(jié)構(gòu)解決實際問題的能力。1 .掌握數(shù)據(jù)結(jié)構(gòu)的概念及術(shù)語。2 .掌握線性表（棧、隊列）的存儲結(jié)構(gòu)（順序和鏈式存儲）、算法描述及應用。3 .掌握數(shù)組的順序存儲和特殊矩陣的壓縮存儲。4 .掌握樹的基本概念和術(shù)語，掌握二叉樹的基本性質(zhì)和特點、存儲結(jié)構(gòu)及算 法描述、二叉樹的遍歷、樹、森林與二叉樹的轉(zhuǎn)換。掌握最優(yōu)二叉樹（哈夫曼樹） 的特點及應用。5 .掌握圖的基本概念和術(shù)語、存儲結(jié)構(gòu)（鄰接矩陣、鄰接表、十字鏈表、鄰 接多重表）、圖的遍歷、圖的連通性（最小生成樹）6

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

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

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

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

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

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

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

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

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

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

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