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

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

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

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

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

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

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

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

8、查找方法（順序、折半）。7.掌握插入類排序（直接、折半、表、希爾等插入排序）、交換類排序（冒泡、快速排序）。四、教學(xué)內(nèi)容（一） 緒論（共4學(xué)時）（一）教學(xué)目的和要求介紹數(shù)據(jù)結(jié)構(gòu)課程的研究對象，基本術(shù)語，掌握算法的要領(lǐng)，描述算法的類語言。了解數(shù)據(jù)結(jié)構(gòu)的發(fā)展概況及其在計算機(jī)中的地位。（二）教學(xué)重點與難點教學(xué)重點：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、掌握計算語句頻度和估算算法時間復(fù)雜度的方法。教學(xué)難點：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、算法時間復(fù)雜度的計算。（三）教學(xué)內(nèi)容1、什么是數(shù)據(jù)結(jié)構(gòu) 2、基本概念和術(shù)語 3、抽象數(shù)據(jù)類型的表示與實現(xiàn) 4、算法和算法分析（二） 線性表（共8學(xué)時）（一）教學(xué)目的和要求掌握線性表的邏輯結(jié)構(gòu)、順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。掌握在線性表上實現(xiàn)基本運算的算法。（二）教學(xué)重點與難點教學(xué)重點：1、線性表的定義及邏輯上的特點；2、順序表上插入、刪除和定位運算的實現(xiàn)；3、單鏈表的結(jié)構(gòu)特點及類型說明；4、頭指

10、針和頭結(jié)點的作用及區(qū)別；指針操作；5、定位、刪除、插入運算在單鏈表上的實現(xiàn)；6、循環(huán)鏈表、雙鏈表的結(jié)構(gòu)特點；及其刪除與插入運算的實現(xiàn)。教學(xué)難點：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)運算。（三）教學(xué)內(nèi)容1、線性表的類型定義 2、線性表的順序表示和實現(xiàn) 3、線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn) 4、一元多項式的表示及相加 （三） 棧和隊列（共8學(xué)時）（一）教學(xué)目的和要求掌握棧和隊列的邏輯結(jié)構(gòu)定義，掌握在兩種存儲結(jié)構(gòu)

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

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

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

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

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

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

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

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