ADDINCNKISM.UserStyle《數(shù)據(jù)結(jié)構(gòu)》課程教學(xué)大綱（學(xué)科專業(yè)類-理論課程）一、課程基本信息課程號3023S04002開課單位國際學(xué)院課程名稱（中文）數(shù)據(jù)結(jié)構(gòu)（英文）DataStructure課程性質(zhì)必修考核類型考試課程學(xué)分3課程學(xué)時(shí)51課程類別專業(yè)核心課適用專業(yè)（類）信息管理與信息系統(tǒng)二、課程描述及目標(biāo)（一）課程簡介《數(shù)據(jù)結(jié)構(gòu)》是計(jì)算機(jī)及相關(guān)專業(yè)的一門重要的專業(yè)基礎(chǔ)課，是介于數(shù)學(xué)、計(jì)算機(jī)硬件和計(jì)算機(jī)軟件之間的一門計(jì)算機(jī)科學(xué)與技術(shù)領(lǐng)域的核心課程，同時(shí)數(shù)據(jù)結(jié)構(gòu)技術(shù)也被廣泛應(yīng)用于信息科學(xué)、系統(tǒng)工程、應(yīng)用數(shù)學(xué)以及各種工程技術(shù)領(lǐng)域。本課程主要介紹如何合理地組織和表示數(shù)據(jù)、如何有效地存儲和處理數(shù)據(jù)、如何正確地設(shè)計(jì)算法以及對算法的優(yōu)劣做出分析和評價(jià)。（二）教學(xué)目標(biāo)通過本課程的學(xué)習(xí)，使學(xué)生透徹理解各種常用數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及相關(guān)算法的實(shí)現(xiàn)，全面掌握處理數(shù)據(jù)的理論和方法；培養(yǎng)學(xué)生具備較深入的選用合適的數(shù)據(jù)結(jié)構(gòu)、編寫規(guī)范的高質(zhì)量程序以及評價(jià)算法優(yōu)劣的能力；使學(xué)生接受系統(tǒng)的、科學(xué)的分析問題和解決問題的訓(xùn)練，提高運(yùn)用數(shù)據(jù)結(jié)構(gòu)解決實(shí)際問題的能力，為學(xué)習(xí)后續(xù)的軟件課程奠定良好的基礎(chǔ)。課程目標(biāo)1：透徹理解各種常用數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及相關(guān)算法的實(shí)現(xiàn)，全面掌握處理數(shù)據(jù)的理論和方法課程目標(biāo)2：培養(yǎng)學(xué)生具備較深入的選用合適的數(shù)據(jù)結(jié)構(gòu)、編寫規(guī)范的高質(zhì)量程序以及評價(jià)算法優(yōu)劣的能力；課程目標(biāo)3：使學(xué)生接受系統(tǒng)的、科學(xué)的分析問題和解決問題的訓(xùn)練，提高運(yùn)用數(shù)據(jù)結(jié)構(gòu)解決實(shí)際問題的能力，為學(xué)習(xí)后續(xù)的軟件課程奠定良好的基礎(chǔ)。三、教學(xué)方式與方法教學(xué)方式：課堂講授為主，輔以適當(dāng)?shù)恼n堂提問、討論和課堂練習(xí)。教學(xué)方法：啟發(fā)式教學(xué)、探討式教學(xué)、理論與實(shí)踐相結(jié)合。四、教學(xué)重點(diǎn)與難點(diǎn)（一）教學(xué)重點(diǎn)從數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、數(shù)據(jù)的運(yùn)算三個(gè)方面去掌握線性表、棧、隊(duì)列、串、數(shù)組、樹、圖等常用的數(shù)據(jù)結(jié)構(gòu)；掌握常用的各種查找方法和排序算法；能夠?qū)λ惴ǖ臅r(shí)間復(fù)雜性和空間復(fù)雜性的進(jìn)行分析。（二）教學(xué)難點(diǎn)邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)的關(guān)系；順序表和鏈表的區(qū)別與聯(lián)系；棧和隊(duì)列的特點(diǎn)；模式匹配；矩陣的壓縮存儲；二叉樹的性質(zhì)；二叉樹的非遞歸遍歷算法；哈夫曼樹的應(yīng)用；圖的遍歷算法；最小生成樹、最短路徑、關(guān)鍵路徑等圖的應(yīng)用及算法實(shí)現(xiàn)；二叉排序樹、平衡二叉樹和B樹的建立、查找、插入和刪除的方法及算法實(shí)現(xiàn)；哈希表的建立及性能分析；希爾排序、快速排序、堆排序和歸并排序的算法實(shí)現(xiàn)及性能分析。五、教學(xué)內(nèi)容、基本要求與學(xué)時(shí)分配序號教學(xué)內(nèi)容基本要求學(xué)時(shí)教學(xué)方式對應(yīng)課程目標(biāo)1第1章緒論掌握數(shù)據(jù)結(jié)構(gòu)中常用的基本概念和術(shù)語；理解學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的意義；了解數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)內(nèi)容；掌握算法描述和分析的方法。2講授課程目標(biāo)12第2章線性表掌握線性表的邏輯結(jié)構(gòu)和各種存儲表示方法，以及定義在邏輯結(jié)構(gòu)上的各種基本運(yùn)算在相應(yīng)的存儲結(jié)構(gòu)上的實(shí)現(xiàn)；理解順序表和鏈表的優(yōu)缺點(diǎn)；能夠針對具體的應(yīng)用問題的要求，選擇合適的存儲結(jié)構(gòu)設(shè)計(jì)出相應(yīng)的算法，解決與線性表相關(guān)的實(shí)際問題。8講授課程目標(biāo)23第3章棧和隊(duì)列掌握棧和隊(duì)列的邏輯結(jié)構(gòu)定義及在兩種存儲結(jié)構(gòu)上棧和隊(duì)列基本運(yùn)算的實(shí)現(xiàn)；理解棧和隊(duì)列的特點(diǎn)，懂得在什么樣的情況下使用?；蜿?duì)列。4講授課程目標(biāo)24第4章串掌握串的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及字符串上常用的基本運(yùn)算及模式匹配算法。4講授課程目標(biāo)35第5章數(shù)組和廣義表掌握多維數(shù)組的邏輯結(jié)構(gòu)特征及存儲方式；掌握特殊矩陣和稀疏矩陣的壓縮存儲方法；理解廣義表的概念及存儲實(shí)現(xiàn)方法4講授課程目標(biāo)36第6章二叉樹掌握二叉樹的性質(zhì)、二叉樹的存儲結(jié)構(gòu)、二叉樹的各種遍歷算法及其應(yīng)用；了解線索二叉樹的構(gòu)成和遍歷方法；掌握哈夫曼樹的建立和哈夫曼編碼的方法。10講授7第7章樹和森林掌握樹和森林的定義、樹和森林的存儲結(jié)構(gòu)、樹和森林與二叉樹之間的相互轉(zhuǎn)換、樹和森林的遍歷及樹的應(yīng)用。4講授8第8章圖掌握圖的基本概念、圖的存儲結(jié)構(gòu)、遍歷算法、生成樹算法；理解圖的應(yīng)用算法思想。14講授9第9章查找掌握各種存儲方式下的靜態(tài)查找表、動態(tài)查找表和哈希表的查找方法；能夠分析各種查找方法的時(shí)間性能。10講授課程目標(biāo)310第10章排序掌握各種內(nèi)排序方法的基本思想、排序過程、算法實(shí)現(xiàn)；能夠分析各種內(nèi)排序方法的時(shí)間和空間性能；理解各種排序方法的適用情況，并能夠根據(jù)具體要求進(jìn)行選擇；了解外排序的思想。8講授課程目標(biāo)4六、實(shí)驗(yàn)內(nèi)容、基本要求與學(xué)時(shí)分配序號實(shí)驗(yàn)項(xiàng)目名稱實(shí)驗(yàn)內(nèi)容與要求學(xué)時(shí)類型對應(yīng)課程目標(biāo)1簡單程序設(shè)計(jì)實(shí)踐1.建立一個(gè)學(xué)生成績表，人數(shù)不低于30人，完成對該表的查詢、求平均分、統(tǒng)計(jì)各分?jǐn)?shù)段的人數(shù)等基本操作；2.隨機(jī)輸入若干整數(shù)（不低于15個(gè)），選擇任意方法對其排序并輸出排序結(jié)果。2演示性課程目標(biāo)12線性表的基本操作1.約瑟夫環(huán)問題問題描述：約瑟夫(Joseph)問題的一種描述是：編號為1,2,…，n的n個(gè)人按順時(shí)針方向圍坐一圈，每人持有一個(gè)密碼（正整數(shù)）。一開始任選一個(gè)正整數(shù)作為報(bào)數(shù)上限值m，從第一個(gè)人開始按順時(shí)針方向自1開始順序報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)。報(bào)m的人出列，將他的密碼作為新的m值，從他在順時(shí)針方向上的下一個(gè)人開始重新從1報(bào)數(shù)，如此下去，直到所有人全部出列為止。試設(shè)計(jì)一個(gè)程序求出出列順序。2.一元多項(xiàng)式運(yùn)算問題描述：輸入并建立多項(xiàng)式；輸出多項(xiàng)式；完成多項(xiàng)式間的加減法運(yùn)算。4驗(yàn)證性課程目標(biāo)13棧與隊(duì)列的應(yīng)用模擬停車場管理問題描述：設(shè)停車廠只有一個(gè)可停放幾輛汽車的狹長通道，且只有一個(gè)大門可供汽車進(jìn)出。汽車在停車場內(nèi)按車輛到達(dá)的先后順序依次排列，若車場內(nèi)已停滿幾輛汽車，則后來的汽車只能在門外的便道上等候，一旦停車場內(nèi)有車開走，則排在便道上的第一輛車即可進(jìn)入;當(dāng)停車場內(nèi)某輛車要離開時(shí)，由于停車場是狹長的通道，在它之后開入的車輛必須先退出車場為它讓路，待該輛車開出大門后，為它讓路的車輛再按原次序進(jìn)入車場。在這里假設(shè)汽車不能從便道上開走。4設(shè)計(jì)性課程目標(biāo)14串和矩陣的操作實(shí)現(xiàn)KMP算法和改進(jìn)KMP算法；2設(shè)計(jì)性課程目標(biāo)15樹形結(jié)構(gòu)的操作1.二叉樹的建立與先中后序遍歷的實(shí)現(xiàn)（根據(jù)數(shù)據(jù)結(jié)構(gòu)課程內(nèi)容完成即可）；2.哈夫曼編/譯碼問題描述：根據(jù)數(shù)據(jù)結(jié)構(gòu)課程中所講解的哈夫曼編碼原理構(gòu)建哈夫曼樹，并根據(jù)用戶的輸入完成編碼或譯碼的過程。4設(shè)計(jì)性課程目標(biāo)16圖形結(jié)構(gòu)的操作拓?fù)渑判蚝完P(guān)鍵路徑的實(shí)現(xiàn)（根據(jù)數(shù)據(jù)結(jié)構(gòu)課程內(nèi)容完成即可）。6設(shè)計(jì)性課程目標(biāo)17查找實(shí)驗(yàn)1.實(shí)現(xiàn)順序查找、折半查找等靜態(tài)查找算法（根據(jù)數(shù)據(jù)結(jié)構(gòu)課程內(nèi)容完成即可）；2.哈希表設(shè)計(jì)問題描述：針對某個(gè)集體（比如你所在的班級）中的“人名”設(shè)計(jì)一個(gè)哈希表，使得平均查找長度不超過R，完成相應(yīng)的建表和查表程序6探究性課程目標(biāo)1課程目標(biāo)2課程目標(biāo)38內(nèi)排序算法的實(shí)現(xiàn)各種內(nèi)部排序方法的比較問題描述：在教材中，各種內(nèi)部排序算法（起泡排序、直接插入排序、簡單選擇排序、快速排序、希爾排序、堆排序）的時(shí)間復(fù)雜度分析結(jié)果只給出了算法執(zhí)行時(shí)間的階，或大概執(zhí)行時(shí)間。試通過隨機(jī)數(shù)據(jù)比較各算法的關(guān)鍵字比較次數(shù)和關(guān)鍵字移動次數(shù)，以得到真感受。6探究性課程目標(biāo)1課程目標(biāo)2課程目標(biāo)3合計(jì)34注：實(shí)驗(yàn)要求包括必修、選修；實(shí)驗(yàn)類型包括“演示性”、“驗(yàn)證性”、“設(shè)計(jì)性”、“探究性”、“其它”等。七、學(xué)業(yè)評價(jià)和課程考核（一）考核類型：t考試考查（二）考核方式：開卷考試t閉卷考試課程論文課程報(bào)告其它：（三）成績評定：考核依據(jù)建議分值（百分比）考核/評價(jià)細(xì)則對應(yīng)課程目標(biāo)平時(shí)考核50出勤30課程目標(biāo)1作業(yè)30