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

1、數(shù)據(jù)結(jié)構(gòu)教學(xué)大綱一、課程基本信息1課程中文名稱(chēng)：數(shù)據(jù)結(jié)構(gòu)2課程英文名稱(chēng)：Data Structures3課程類(lèi)別：必修4適用專(zhuān)業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)5總學(xué)時(shí)：72學(xué)時(shí)（其中理論54學(xué)時(shí)，上機(jī)18學(xué)時(shí)）6總學(xué)分：4二、本課程在教學(xué)計(jì)劃中的地位、作用和任務(wù)本課程是計(jì)算機(jī)專(zhuān)業(yè)的專(zhuān)業(yè)基礎(chǔ)課，是該專(zhuān)業(yè)的主干課之一，是研究數(shù)據(jù)之間的關(guān)系以及對(duì)數(shù)據(jù)如何進(jìn)行有效處理的學(xué)科。課程的任務(wù)是介紹一些最常用的數(shù)據(jù)結(jié)構(gòu)，闡明數(shù)據(jù)結(jié)構(gòu)內(nèi)在的邏輯關(guān)系，討論它們?cè)谟?jì)算機(jī)中的存儲(chǔ)表示，并結(jié)合各種典型應(yīng)用說(shuō)明它們?cè)谶M(jìn)行各種運(yùn)算（操作）時(shí)的動(dòng)態(tài)性質(zhì)及實(shí)際的執(zhí)行算法。三、理論教學(xué)內(nèi)容與教學(xué)基本要求1第一章 緒論（3學(xué)時(shí)）教學(xué)內(nèi)容：什么

2、是數(shù)據(jù)結(jié)構(gòu)；數(shù)據(jù)結(jié)構(gòu)的基本概念和常用的術(shù)語(yǔ)；數(shù)據(jù)結(jié)構(gòu)發(fā)展的歷史以及數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)科學(xué)中地位；算法描述和算法分析教學(xué)基本要求：了解數(shù)據(jù)結(jié)構(gòu)的發(fā)展和地位；了解各種算法描述方法和算法設(shè)計(jì)的基本要求；理解數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和抽象數(shù)據(jù)類(lèi)型的基本概念；掌握對(duì)算法的評(píng)價(jià)標(biāo)準(zhǔn)和算法效率的度量方法。教學(xué)重點(diǎn)：理解數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和抽象數(shù)據(jù)類(lèi)型的基本概念；掌握對(duì)算法的評(píng)價(jià)標(biāo)準(zhǔn)和算法效率的度量方法教學(xué)難點(diǎn)：算法的評(píng)價(jià)標(biāo)準(zhǔn)和算法效率的度量方法2第二章 線性表（9學(xué)時(shí)）教學(xué)內(nèi)容：線性表的邏輯結(jié)構(gòu)；線性表的順序存儲(chǔ)結(jié)構(gòu)；線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)；線性表應(yīng)用舉例教學(xué)基本要求：理解線性表的概念、邏輯結(jié)構(gòu)特

3、性以及兩種存儲(chǔ)結(jié)構(gòu)特性，針對(duì)實(shí)際應(yīng)用能從時(shí)間和空間復(fù)雜度的角度選用適當(dāng)?shù)拇鎯?chǔ)結(jié)構(gòu)；熟練掌握線性表的順序存儲(chǔ)結(jié)構(gòu)及其各種基本運(yùn)算；熟練掌握線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（單鏈表、循環(huán)鏈表、雙向鏈表）及其各種基本運(yùn)算，能在實(shí)際應(yīng)用中選用適當(dāng)?shù)逆湵斫Y(jié)構(gòu)。教學(xué)重點(diǎn)：線性表的概念、邏輯結(jié)構(gòu)特性以及兩種存儲(chǔ)結(jié)構(gòu)特性，線性表的順序存儲(chǔ)結(jié)構(gòu)及其各種基本運(yùn)算；線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（單鏈表、循環(huán)鏈表、雙向鏈表）及其各種基本運(yùn)算教學(xué)難點(diǎn)：線性表的各種基本運(yùn)算3第三章 字符串（3學(xué)時(shí)）教學(xué)內(nèi)容：串類(lèi)型的定義；串的表示和實(shí)現(xiàn)；串操作的應(yīng)用舉例教學(xué)基本要求：了解串的應(yīng)用；掌握串的基本概念、順序和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)；掌握串的各種基本運(yùn)算；

4、 熟練掌握順序存儲(chǔ)結(jié)構(gòu)上串的各種操作。教學(xué)重點(diǎn)：串的基本概念、順序和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及各種基本運(yùn)算教學(xué)難點(diǎn)：串的各種基本運(yùn)算4第四章 棧和隊(duì)列（6學(xué)時(shí)）教學(xué)內(nèi)容：棧；棧的應(yīng)用；棧與遞歸過(guò)程；隊(duì)列教學(xué)基本要求：掌握棧和隊(duì)列的定義、表示、實(shí)現(xiàn)和應(yīng)用；掌握棧的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)以及相應(yīng)操作的實(shí)現(xiàn)；了解遞歸的概念和遞歸過(guò)程的實(shí)現(xiàn)；掌握隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)（循環(huán)隊(duì)列）和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的實(shí)現(xiàn)。教學(xué)重點(diǎn)：棧和隊(duì)列的定義、表示、實(shí)現(xiàn)和應(yīng)用；棧的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)以及相應(yīng)操作的實(shí)現(xiàn)；隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)（循環(huán)隊(duì)列）和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的實(shí)現(xiàn)教學(xué)難點(diǎn)：棧和隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)以及相應(yīng)操作的實(shí)現(xiàn)5第五章

5、 樹(shù)和二叉樹(shù)（9學(xué)時(shí)）教學(xué)內(nèi)容：樹(shù)的定義；二叉樹(shù)；遍歷二叉樹(shù)和線索二叉樹(shù)；樹(shù)和森林；哈夫曼樹(shù)及其應(yīng)用教學(xué)基本要求：熟練掌握二叉樹(shù)的定義、性質(zhì)、各種存儲(chǔ)結(jié)構(gòu)的特點(diǎn)及適用范圍；熟練掌握二叉樹(shù)的各種遍歷算法；理解線索二叉樹(shù)的概念、存儲(chǔ)結(jié)構(gòu)及線索化算法；掌握樹(shù)和森林與二叉樹(shù)間的轉(zhuǎn)換，掌握樹(shù)和森林的遍歷算法；掌握哈夫曼樹(shù)的概念、存儲(chǔ)結(jié)構(gòu)；掌握建立哈夫曼樹(shù)和哈夫曼編碼的方法及帶權(quán)路徑長(zhǎng)度的計(jì)算；理解樹(shù)的基本概念及其存儲(chǔ)結(jié)構(gòu)。教學(xué)重點(diǎn)：二叉樹(shù)的定義、性質(zhì)、各種存儲(chǔ)結(jié)構(gòu)的特點(diǎn)及適用范圍；二叉樹(shù)的各種遍歷算法；樹(shù)和森林與二叉樹(shù)間的轉(zhuǎn)換教學(xué)難點(diǎn)：二叉樹(shù)的各種遍歷算法，線索二叉樹(shù)線索化算法6第六章 集合與字典（9學(xué)

6、時(shí)）教學(xué)內(nèi)容：靜態(tài)查找表；動(dòng)態(tài)查找表；哈希表教學(xué)基本要求：理解查找及其算法的時(shí)間復(fù)雜度；理解靜態(tài)查找表的概念；理解二叉平衡樹(shù)，B樹(shù)的概念；理解哈希表的含義；掌握二叉排序樹(shù)查找算法；掌握哈希函數(shù)的構(gòu)造方法，哈希表的建立和查找以及處理沖突的基本方法；熟練掌握順序查找、折半查找和分塊查找算法，能對(duì)其性能進(jìn)行分析。教學(xué)重點(diǎn)：順序查找、折半查找和分塊查找算法，哈希函數(shù)的構(gòu)造方法，哈希表的建立和查找以及處理沖突的基本方法教學(xué)難點(diǎn)：哈希函數(shù)的構(gòu)造方法，哈希表的建立和查找以及處理沖突的基本方法，各種查找算法的性能進(jìn)行分析7第八章 內(nèi)部排序（6學(xué)時(shí)）教學(xué)內(nèi)容：基本概念；插入排序；快速排序；選擇排序；歸并排序；基

7、數(shù)排序；各種內(nèi)部排序方法的比較討論教學(xué)基本要求：了解內(nèi)部排序的概念；了解歸并排序、基數(shù)排序的算法；掌握插入類(lèi)排序的算法，直接插入排序、希爾排序； 掌握交換類(lèi)排序的算法，冒泡排序、快速排序； 掌握選擇類(lèi)排序的算法，簡(jiǎn)單選擇排序、堆排序；掌握各種排序方法的特點(diǎn)，能夠?qū)Ω鞣N排序算法進(jìn)行評(píng)價(jià)，并能加以靈活應(yīng)用。教學(xué)重點(diǎn)：插入類(lèi)排序的算法，直接插入排序、希爾排序；掌握交換類(lèi)排序的算法，冒泡排序、快速排序，掌握選擇類(lèi)排序的算法，簡(jiǎn)單選擇排序、堆排序教學(xué)難點(diǎn)：各種排序方法的特點(diǎn)，能夠?qū)Ω鞣N排序算法進(jìn)行評(píng)價(jià)，并能加以靈活應(yīng)用8第九章 圖（9學(xué)時(shí)）教學(xué)內(nèi)容：圖的定義和術(shù)語(yǔ)；圖的存儲(chǔ)結(jié)構(gòu)；圖的遍歷；圖的連通性問(wèn)題

8、；有向無(wú)環(huán)圖及其應(yīng)用；最短路徑教學(xué)基本要求：理解圖的基本概念，掌握?qǐng)D的鄰接矩陣和鄰接表的存儲(chǔ)結(jié)構(gòu)；理解帶權(quán)最短路徑的概念，掌握用Dijkstra方法求最短路徑的算法；掌握構(gòu)造最小生成樹(shù)的方法及其算法；掌握求拓?fù)渑判蚝完P(guān)鍵路徑的方法，理解其算法；熟練掌握?qǐng)D的深度優(yōu)先和廣度優(yōu)先遍歷算法。教學(xué)重點(diǎn)：圖的基本概念，掌握?qǐng)D的鄰接矩陣和鄰接表的存儲(chǔ)結(jié)構(gòu)，圖的深度優(yōu)先和廣度優(yōu)先遍歷算法，用Dijkstra方法求最短路徑的算法；構(gòu)造最小生成樹(shù)的方法及其算法；求拓?fù)渑判蚝完P(guān)鍵路徑的方法教學(xué)難點(diǎn)：用Dijkstra方法求最短路徑的算法；構(gòu)造最小生成樹(shù)的方法及其算法；求拓?fù)渑判蚝完P(guān)鍵路徑的方法四、實(shí)驗(yàn)教學(xué)內(nèi)容與要求

9、（簡(jiǎn)要說(shuō)明，詳見(jiàn)實(shí)驗(yàn)課大綱）根據(jù)實(shí)驗(yàn)大綱和要求進(jìn)行。詳見(jiàn)實(shí)驗(yàn)大綱。五、考核方式考試六、成績(jī)?cè)u(píng)定期末考試成績(jī)占70%，平時(shí)成績(jī)和實(shí)驗(yàn)成績(jī)占30%七、本課程對(duì)學(xué)生創(chuàng)新能力培養(yǎng)的措施選擇一些算法作為作業(yè)讓學(xué)生獨(dú)立去實(shí)現(xiàn)，采用激勵(lì)與督促手段，隨后加以檢查和評(píng)講。八、教材與參考書(shū)教 材：張乃孝算法與數(shù)據(jù)結(jié)構(gòu)北京：高等教育出版社，2006年（面向21世紀(jì)課程教材）參考書(shū)：1 嚴(yán)蔚敏，吳偉民數(shù)據(jù)結(jié)構(gòu)（第二版）北京：清華大學(xué)出版社，1992年2 張乃孝數(shù)據(jù)結(jié)構(gòu)與算法學(xué)習(xí)輔導(dǎo)及習(xí)題詳解北京：電子工業(yè)出版社，2004年九、其它必要的說(shuō)明1本課程教學(xué)大綱是按照計(jì)算機(jī)科學(xué)與技術(shù)（四年制）本科培養(yǎng)方案及課程基本要求并結(jié)合我校計(jì)算機(jī)科學(xué)與技術(shù)專(zhuān)業(yè)的學(xué)科建設(shè)情況與教學(xué)計(jì)劃制定的。