《數(shù)據(jù)結(jié)構(gòu)Ⅰ》課程教學(xué)大綱

1、數(shù)據(jù)結(jié)構(gòu)Data Structure 一、課程基本情況課程類別：學(xué)科基礎(chǔ)課課程學(xué)分： 4 學(xué)分課程總學(xué)時： 64 學(xué)時，其中講課：44 學(xué)時，實(shí)驗(yàn)（含上機(jī)）：20 學(xué)時，課外0學(xué)時課程性質(zhì)：必修開課學(xué)期：第3學(xué)期先修課程：計(jì)算機(jī)基礎(chǔ)，C語言程序設(shè)計(jì)適用專業(yè)： 信息管理與信息系統(tǒng)教 材：數(shù)據(jù)結(jié)構(gòu)，清華大學(xué)出版社，嚴(yán)蔚敏，2011年，C語言版。開課單位：經(jīng)濟(jì)管理學(xué)院 信息管理系二、課程性質(zhì)、教學(xué)目標(biāo)和任務(wù)本課程是專業(yè)必修基礎(chǔ)課，是重要的計(jì)算機(jī)基礎(chǔ)課程。數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)程序設(shè)計(jì)的基礎(chǔ)，本課程的學(xué)習(xí)目的是要使學(xué)生學(xué)會分析研究所要解決的問題中涉及的數(shù)據(jù)結(jié)構(gòu)的特性，并為應(yīng)用涉及的數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存

2、儲結(jié)構(gòu)及其相應(yīng)的算法，培養(yǎng)數(shù)據(jù)抽象能力；掌握數(shù)據(jù)組織、存儲和處理的常用方法；使學(xué)生掌握了解數(shù)據(jù)結(jié)構(gòu)的研究內(nèi)容及其重要性，掌握常用數(shù)據(jù)結(jié)構(gòu)，主要包括線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖形結(jié)構(gòu)，并能靈活運(yùn)用；掌握順序存儲方法、鏈?zhǔn)酱鎯Ψ椒?、常用基本算法（初始化、銷毀、求長度、判空、判滿、插入、刪除、查找、遍歷、排序等）設(shè)計(jì)與評價；掌握常用的數(shù)據(jù)處理各種算法，并能靈活運(yùn)用；逐步掌握算法的時間分析和空間分析的技術(shù)；訓(xùn)練復(fù)雜程序設(shè)計(jì)的技能；并能夠編寫出結(jié)構(gòu)清楚和正確易讀的程序，養(yǎng)成良好的程序設(shè)計(jì)習(xí)慣。數(shù)據(jù)結(jié)構(gòu)是一門實(shí)踐性很強(qiáng)的課程，必須通過上機(jī)操作才能掌握所學(xué)的知識，所以要特別強(qiáng)調(diào)講授與上機(jī)操作相結(jié)合，要保證學(xué)生有充

3、分的上機(jī)條件。根據(jù)實(shí)際情況安排內(nèi)容，須依據(jù)師生之間共同配合與努力情況來決定。在課程實(shí)驗(yàn)中不僅要訓(xùn)練計(jì)算機(jī)實(shí)驗(yàn)技能和操作能力，更應(yīng)包括設(shè)計(jì)算法的創(chuàng)造性實(shí)驗(yàn)?zāi)芰?。三、教學(xué)內(nèi)容和要求第1章 數(shù)據(jù)結(jié)構(gòu)緒論（9學(xué)時）1.1數(shù)據(jù)結(jié)構(gòu)的概念（2學(xué)時）（1）了解數(shù)據(jù)結(jié)構(gòu)的概念；（2）理解計(jì)算機(jī)能解決的問題中存在不同的數(shù)據(jù)結(jié)構(gòu)；（3）掌握為不同的問題選擇不同的數(shù)據(jù)結(jié)構(gòu)進(jìn)行問題的分析和解決；重點(diǎn)：數(shù)據(jù)結(jié)構(gòu)的概念；難點(diǎn)：為應(yīng)用涉及的數(shù)據(jù)選擇適當(dāng)?shù)慕Y(jié)構(gòu)；1.2常見的數(shù)據(jù)結(jié)構(gòu)類型（1學(xué)時）（1）了解數(shù)據(jù)結(jié)構(gòu)的常見類型；（2）理解不同數(shù)據(jù)結(jié)構(gòu)類型的區(qū)別；（3）掌握不同數(shù)據(jù)結(jié)構(gòu)類型的特點(diǎn)。重點(diǎn)：數(shù)據(jù)結(jié)構(gòu)的類型；難點(diǎn)：區(qū)分不

4、同的數(shù)據(jù)結(jié)構(gòu)類型；1.3抽象數(shù)據(jù)類型ADT（3學(xué)時）（1）了解抽象數(shù)據(jù)類型的概念；（2）理解ADT的含義；（3）掌握不同問題的ADT定義及實(shí)現(xiàn)；重點(diǎn)：ADT的概念；難點(diǎn)：為具體問題定義ADT并實(shí)現(xiàn)；1.4算法分析（3學(xué)時）（1）了解算法、時間復(fù)雜度等的含義； （2）理解算法的效率度量方法； （3）掌握算法的特征，算法的描述；算法的時間復(fù)雜度，包括最壞和平均時間復(fù)雜度的含義；重點(diǎn)：算法基本概念；難點(diǎn)：算法的時間復(fù)雜度；第2章 線性表（10學(xué)時）2.1線性表的定義（3學(xué)時）（1）了解線性結(jié)構(gòu)的特點(diǎn)； （2）理解線性表的ADT定義； （3）掌握線性表的實(shí)際應(yīng)用實(shí)例；重點(diǎn)：線性表的基本概念；難點(diǎn)：線性

5、表的復(fù)雜操作，如合并排序等； 2.2線性表的順序表示和實(shí)現(xiàn)（3學(xué)時）（1）了解線性結(jié)構(gòu)的兩種存儲方法的含義； （2）理解線性表順序存儲方式的優(yōu)缺點(diǎn)； （3）掌握線性表順序存儲方式的具體實(shí)現(xiàn)、順序表的元素查找、插入和刪除操作及時間復(fù)雜度分析；重點(diǎn)：線性表順序存儲方式的基本概念；難點(diǎn)：線性表順序存儲方式的實(shí)現(xiàn)；2.3 線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)（4學(xué)時）（1）了解線性表鏈?zhǔn)酱鎯Ψ绞健⒀h(huán)鏈表、雙向鏈表的含義； （2）理解線性表鏈?zhǔn)酱鎯Ψ绞降膬?yōu)缺點(diǎn)； （3）掌握線性表鏈?zhǔn)酱鎯Ψ绞降木唧w實(shí)現(xiàn)、單鏈表上的查找、插入和刪除等基本運(yùn)算的實(shí)現(xiàn)及時間復(fù)雜度分析；重點(diǎn)：線性表鏈?zhǔn)酱鎯Ψ绞降幕靖拍?；難點(diǎn)：線性表鏈?zhǔn)酱?/p>

6、儲方式的實(shí)現(xiàn)；第3章 棧和隊(duì)列（7學(xué)時）3.1棧的定義（1學(xué)時）（1）了解棧結(jié)構(gòu)的特點(diǎn)； （2）理解棧結(jié)構(gòu)的定義； （3）掌握棧結(jié)構(gòu)的具體實(shí)現(xiàn)；重點(diǎn)：棧的基本概念；難點(diǎn)：棧的具體實(shí)現(xiàn)；3.2棧的應(yīng)用舉例（3學(xué)時）（1）了解棧結(jié)構(gòu)的具體應(yīng)用場合； （2）理解棧結(jié)構(gòu)的后進(jìn)先出特性； （3）掌握棧結(jié)構(gòu)的具體應(yīng)用實(shí)現(xiàn)，如數(shù)制轉(zhuǎn)換、括號匹配、迷宮求解和表達(dá)式求值等；重點(diǎn)：棧結(jié)構(gòu)的應(yīng)用特點(diǎn)；難點(diǎn)：棧結(jié)構(gòu)的具體應(yīng)用實(shí)現(xiàn)；3.3隊(duì)列（3學(xué)時）（1）了解隊(duì)列、循環(huán)隊(duì)列的定義； （2）理解隊(duì)列的ADT定義； （3）掌握鏈隊(duì)列、循環(huán)隊(duì)列的表示和實(shí)現(xiàn)，熟練掌握入棧和出棧運(yùn)算的實(shí)現(xiàn)；重點(diǎn)：隊(duì)列和棧的定義及基本運(yùn)算；難點(diǎn)

7、：循環(huán)隊(duì)列的具體實(shí)現(xiàn)；第4章 數(shù)和二叉樹（9學(xué)時）4.1樹的定義和術(shù)語（1學(xué)時）（1）了解非線性結(jié)構(gòu)的特點(diǎn)； （2）理解樹的遞歸定義、常見術(shù)語； （3）掌握樹結(jié)構(gòu)的ADT定義；重點(diǎn)：樹的基本概念；難點(diǎn)：樹的ADT實(shí)現(xiàn)；4.2 二叉樹（2學(xué)時）（1）了解二叉樹的定義； （2）理解二叉樹的性質(zhì)； （3）掌握二叉樹的二叉鏈表存儲表示；重點(diǎn)：二叉樹的基本概念；難點(diǎn)：二叉樹的存儲結(jié)構(gòu)；4.3 遍歷二叉樹和線索二叉樹（2學(xué)時）（1）了解遍歷二叉樹、線索二叉樹的概念； （2）理解二叉樹的先序、中序、后序、層序遍歷的含義； （3）掌握二叉樹的先序、中序、后序、層序遍歷過程及相應(yīng)的遍歷算法、線索二叉樹的存儲結(jié)構(gòu)

8、；重點(diǎn)：遍歷二叉樹、線索二叉樹的基本概念；難點(diǎn)：遍歷二叉樹的遍歷過程實(shí)現(xiàn)、二叉樹的線索化處理過程；4.4 樹和森林（3學(xué)時）（1）了解樹的孩子表示法和雙親表示法； （2）理解樹的孩子兄弟表示法； （3）掌握樹與二叉樹的相互轉(zhuǎn)化方法、樹和森林的遍歷；重點(diǎn)：樹的存儲實(shí)現(xiàn)；難點(diǎn)：樹與二叉樹的相互轉(zhuǎn)化；4.5 赫夫曼樹及其應(yīng)用（1學(xué)時）（1）了解赫夫曼樹的定義； （2）理解赫夫曼樹的應(yīng)用； （3）掌握赫夫曼樹的構(gòu)造；重點(diǎn)：赫夫曼樹的基本概念；難點(diǎn)：赫夫曼樹的構(gòu)造；第5章 圖（4學(xué)時）5.1圖的基本概念（1學(xué)時）（1）了解圖的定義；（2）理解圖常見的術(shù)語；（3）掌握路徑與連通的概念；重點(diǎn)：圖的基本概念；

9、難點(diǎn)：各種術(shù)語的含義；5.2圖的存儲結(jié)構(gòu)（2學(xué)時）（1）了解圖的存儲結(jié)構(gòu)類型；（2）理解圖的鄰接表、十字鏈表等結(jié)構(gòu)的含義；（3）掌握圖的鄰接表、十字鏈表等結(jié)構(gòu)的具體實(shí)現(xiàn)；重點(diǎn)：圖的各種存儲結(jié)構(gòu)的區(qū)別；難點(diǎn)：圖的各種存儲結(jié)構(gòu)的實(shí)現(xiàn)；5.3圖的遍歷（1學(xué)時）（1）了解圖的遍歷含義；（2）理解圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷的含義；（3）掌握圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷算法的具體實(shí)現(xiàn)；重點(diǎn)：圖的各種遍歷的區(qū)別；難點(diǎn)：圖的各種遍歷算法的具體實(shí)現(xiàn)；第6章 查找（5學(xué)時）6.1靜態(tài)查找表（3學(xué)時）（1）了解查找、查找成功的概念； （2）理解順序查找的過程、索引順序表的查找； （3）掌握有序表的查找，如折半查找、斐波那契查找和插值查找等方法，并進(jìn)行性能分析。重點(diǎn)：順序查找的基本概念；難點(diǎn)：各種有序表查找方法的實(shí)現(xiàn)過程；6.2 動態(tài)查找表（2學(xué)時）（1）了解二叉排序樹、平衡二叉樹、哈希表等的概念； （2）理解B樹的定義及查找過程； （3）掌握靜態(tài)查找、動態(tài)查找的定義及平均查找長度的定義；重點(diǎn)：動態(tài)查找表的含義；難點(diǎn)：動態(tài)查找表和哈希表的應(yīng)用。四、課程考核（1）作業(yè)等：作業(yè)：5 次，課程論文：0 篇；（2）考核方式：閉卷考試；（3）總評成績計(jì)算方式：平時及實(shí)驗(yàn)成績占20%、期中考試成績占2