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

1、數(shù)據(jù)結(jié)構(gòu)一、課程簡介數(shù)據(jù)結(jié)構(gòu)是生物技術(shù)專業(yè)基礎(chǔ)課程之一，學(xué)習(xí)本課程能使學(xué)生掌握數(shù)據(jù)在計算機中的表示、 存儲和處理。為以后學(xué)習(xí)編譯程序、操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)打下基礎(chǔ)，進而服務(wù)于本專業(yè)。通過 本課程的學(xué)習(xí)，使學(xué)生獲得計算機學(xué)科各領(lǐng)域的數(shù)據(jù)結(jié)構(gòu)知識，及有關(guān)的應(yīng)用軟件所要用到的各 種數(shù)據(jù)結(jié)構(gòu)知識。掌握常用的數(shù)據(jù)結(jié)構(gòu)及內(nèi)在的邏輯關(guān)系，掌握計算機軟件設(shè)計中的算法知識。 提高軟件設(shè)計和編程技能。學(xué)會初步對不同的存儲結(jié)構(gòu)和相應(yīng)算法進行比照，有一定的算法改進 能力，掌握應(yīng)用數(shù)據(jù)結(jié)構(gòu)知識對本專業(yè)生物信息進行檢測與處理，為計算機技術(shù)在醫(yī)學(xué)和臨床中 的應(yīng)用提供基礎(chǔ)，使學(xué)生具有生物技術(shù)領(lǐng)域軟件研究和開發(fā)的基本能力。二、

2、理論教學(xué)內(nèi)容.緒論掌握內(nèi)容：數(shù)據(jù)結(jié)構(gòu)的基本概念；基本術(shù)語；數(shù)據(jù)結(jié)構(gòu)課程的研究對象；算法的特性，描述 算法的類語言。了解內(nèi)容：數(shù)據(jù)結(jié)構(gòu)的開展概況及其在生物信息學(xué)相關(guān)專業(yè)中的應(yīng)用。.線性表掌握內(nèi)容：線性表的定義；線性表的邏輯結(jié)構(gòu)、順序存儲結(jié)構(gòu)，鏈式存儲結(jié)構(gòu)；順序表的基 本操作及運算；單鏈表的基本操作及相應(yīng)算法；雙鏈表的概念及算法。了解內(nèi)容：性表上實現(xiàn)基本運算的算法及線性表在生物信息學(xué)上的應(yīng)用。.棧與隊列掌握內(nèi)容：棧和隊列的邏輯結(jié)構(gòu)定義，棧和隊列的基本運算。棧和隊列在程序設(shè)計中的應(yīng)用。了解 內(nèi)容：棧和隊列在解決本專業(yè)問題中的應(yīng)用實例。.串掌握內(nèi)容：串類型的定義、串的表示和實現(xiàn)、串的模式匹配算法、字符

3、串的存儲結(jié)構(gòu)，字符 串的操作算法。了解內(nèi)容：串操作在生物技術(shù)專業(yè)中的應(yīng)用舉例。.數(shù)組和廣義表掌握內(nèi)容：數(shù)組的基礎(chǔ)知識；數(shù)組的順序存儲和特殊矩陣的壓縮存儲；稀疏矩陣的壓縮存儲；三元 組表，十字鏈表，矩陣的快速轉(zhuǎn)置。了解內(nèi)容：廣義表的概念及應(yīng)用。.樹和二叉樹掌握內(nèi)容：樹的基本概念和術(shù)語，掌握二叉樹的基本性質(zhì)和特點；遍歷二叉樹的定義和遍歷 方法；最優(yōu)二叉樹（哈夫曼樹）的特點及建立；樹和森林的轉(zhuǎn)化與遍歷；哈夫曼編碼與譯碼。了解內(nèi)容：樹和二叉樹在本專業(yè)的應(yīng)用舉例。.查找掌握內(nèi)容：查找的基本概念、基于線性表的查找方法（順序、折半），靜態(tài)表查找（順序表 的查找、有序表的查找、靜態(tài)樹表的查找）。動態(tài)表查找方法

4、（二叉排序樹、平衡二排序叉樹）， 哈希表的概念，基本性質(zhì)，哈希函數(shù)的構(gòu)造方法、哈希表處理沖突的方法。了解內(nèi)容：相關(guān)查找算法在解決本專業(yè)實際問題中的應(yīng)用。.內(nèi)部排序掌握內(nèi)容：內(nèi)部排序的概念，穩(wěn)定性；選擇類排序的概念及方法；插入類排序（直接、折半、 表、希爾等插入排序）、交換類排序（冒泡、快速排序）。歸并類排序和基數(shù)類排序、堆排序的 概念及方法，交換類排序（冒泡、快速排序）。60了解內(nèi)容：各種內(nèi)部排序方法的比擬。三、實驗教學(xué)內(nèi)容.線性表基本內(nèi)容：線性表的各種操作（建立、插入、刪除，兩個有序單鏈表的合并等）的實現(xiàn)；線 性表的基本運算在兩種存儲結(jié)構(gòu)（順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)）上的實現(xiàn)?；疽螅壕帉?/p>

5、算法實現(xiàn)順序表與鏈表的建立、插入元素、刪除表中某元素等操作。并對相 應(yīng)算法進行時間復(fù)雜度分析。.棧和隊列基本內(nèi)容：掌握棧和隊列的基本操作：初始化棧（隊列）、判棧（隊列）為空、出棧（隊）、 入棧（隊）等運算?；疽螅壕帉憲：完犃羞@兩種特殊線性表的基本運算算法，運用棧和隊列解決實際問題。.樹基本內(nèi)容：樹的基本概念、二叉樹性質(zhì)、基本操作及在鏈式存儲結(jié)構(gòu)上的實現(xiàn)；二叉樹的生 成、遍歷及求深度等算法；二叉樹的線索化及線索二叉樹的遍歷算法；線索二叉樹與雙向循環(huán)鏈 表之間的聯(lián)系；哈夫曼樹的含義及其應(yīng)用?；疽螅壕帉懞蜕峙c二叉樹的轉(zhuǎn)換方法。對樹的存儲結(jié)構(gòu)及各種操作編寫算法實現(xiàn)；二 叉樹的存儲結(jié)構(gòu)；應(yīng)用二

6、叉樹的相關(guān)操作；解決實際問題。.查找基本內(nèi)容：各種靜態(tài)查找表的查找方法（順序查找法、折半查找法、索引順序表查找）；二 叉排序樹的構(gòu)造方法和查找算法；哈希表的構(gòu)造方法；理解哈希表與其它結(jié)構(gòu)表的實質(zhì)性差異； 描述查找過程的判定樹構(gòu)造方法，以及按定義計算各種查找方法在等概率情況下查找成功時的平均 查找長度；穩(wěn)定性?；疽螅壕帉懗绦?qū)崿F(xiàn)各種靜態(tài)查找表的查找方法和二叉平衡樹的建立和維護平衡的方 法。.排序基本內(nèi)容：熟練掌握各種排序的算法思想、方法及穩(wěn)定性；掌握快速排序、堆、排序、歸并 排序的方法實現(xiàn)；對一組數(shù)據(jù)，能寫出其具體的排序過程、算法及完整程序，并上機調(diào)試； 了解每一種排序的時間及空間復(fù)雜度?；?/p>

7、本要求：編寫程序?qū)崿F(xiàn)快速排序、堆、排序、歸并排序的方法實現(xiàn)；對一組數(shù)據(jù)，能 寫出其具體的排序過程、算法及完整程序，并上機調(diào)試；對每一種排序的時間及空間復(fù)雜度進行 分析。四、參考資料.參考書數(shù)據(jù)結(jié)構(gòu)JAVA語言描述.劉小晶、杜選主編.清華大學(xué)出版社.2011年出版數(shù)據(jù)結(jié)構(gòu)（C語言版）.嚴蔚敏、吳偉民編著,清華大學(xué)出版社.2004年出版數(shù)據(jù)結(jié)構(gòu)JAVA語言描述第二版.劉小晶，杜選，朱蓉，杜衛(wèi)鋒主編.清華大學(xué)出版社.2015 年3月出版.網(wǎng)絡(luò)資源數(shù)據(jù)結(jié)構(gòu)-中國大學(xué)MOOC （163.org/course/zju0901 -93001）數(shù)據(jù)結(jié)構(gòu)-極客學(xué)院數(shù)據(jù)結(jié)構(gòu)視頻教程（ :/ jikexueyuan /course