數(shù)據(jù)結(jié)構(gòu)課程復(fù)習(xí)提綱

1、數(shù)據(jù)結(jié)構(gòu)課程復(fù)習(xí)提綱一、課程性質(zhì)與設(shè)置目的【課程性質(zhì)和特點】數(shù)據(jù)結(jié)構(gòu)是計算機科學(xué)與技術(shù)專業(yè)本科階段中一門專業(yè)基礎(chǔ)課，在計算機的各個領(lǐng)域中均會使用到該課程的有關(guān)知識。本課程的目的和任務(wù)是學(xué)生較全面地掌握各種常用的數(shù)據(jù)結(jié)構(gòu)、相關(guān)的算法以及實現(xiàn)，為學(xué)習(xí)后續(xù)專業(yè)課程提供必要的支持，提高運用數(shù)據(jù)結(jié)構(gòu)解決實際問題的能力。【課程的基本要求】1、從數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和數(shù)據(jù)的運算三個方面去掌握串、向量、線性表、棧、隊列、樹、圖、散列和文件等常用的數(shù)據(jù)結(jié)構(gòu)。2、掌握在各種常用的數(shù)據(jù)結(jié)構(gòu)上實現(xiàn)的排序和查找運算。3、對算法的時間和空間復(fù)雜性有一定的分析能力。4、針對簡單的應(yīng)用問題，應(yīng)能選擇合適的數(shù)據(jù)結(jié)構(gòu)及設(shè)

2、計有效的算法解決之?！鞠嚓P(guān)課程的聯(lián)系】本課程的先修課程為離散數(shù)學(xué)和高級語言程序設(shè)計（C+語言），后續(xù)課程為操作系統(tǒng)、數(shù)據(jù)庫原理、算法分析與設(shè)計等。數(shù)據(jù)結(jié)構(gòu)中存儲結(jié)構(gòu)及基本運算的實現(xiàn)需要程序設(shè)計的基本知識和編程的經(jīng)驗及能力，本課程的大部分實例均是用C+語言實現(xiàn)的，故要求較熟練地掌握C+語言?！菊n程修讀對象】 本科計算機科學(xué)與技術(shù)專業(yè)，屬專業(yè)基礎(chǔ)課?！菊n時安排】 總學(xué)時：64 學(xué)時 講課：48學(xué)時 實驗 ：16學(xué)時 總學(xué)分：4學(xué)分 講課：3學(xué)分 實驗： 1學(xué)分二、課程理論部分內(nèi)容與考核目標(biāo)第1章 概論【課程內(nèi)容】1.1 基本概念和術(shù)語1.2 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的意義1.3 算法的描述和分析【學(xué)習(xí)目的與要

3、求】本章的目的是介紹數(shù)據(jù)結(jié)構(gòu)中常用的基本概念和術(shù)語以及學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的意義，要求了解本章介紹的各種基本概念和術(shù)語，掌握算法描述和分析的方法。本章重點是了解數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及數(shù)據(jù)的運算三方面的概念及相互關(guān)系，難點是算法復(fù)雜度的分析方法?！究己酥R點與考核要求】理解數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項、數(shù)據(jù)結(jié)構(gòu)等基本概念。理解數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及數(shù)據(jù)運算的含義及其相互關(guān)系。 了解抽象數(shù)據(jù)類型描述。掌握算法、算法的時間復(fù)雜度和空間復(fù)雜度、最壞的和平均的時間復(fù)雜度等概念。掌握算法時間復(fù)雜度大0表示法。掌握算法描述和算法分析的方法，對于一般算法能分析出時間復(fù)雜度。第2章 字符串【課程內(nèi)容

4、】2.1 串及其運算2.2 串的存儲結(jié)構(gòu)及其實現(xiàn)2.3 簡單字符串模式匹配【學(xué)習(xí)目的與要求】本章目的是介紹串的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其實現(xiàn)，簡單模式匹配，難點是串模式匹配算法。【考核知識與考核要求】 掌握串的有關(guān)概念及基本運算。 了解模式匹配算法及其時間性能分析。第3章 向量【課程內(nèi)容】2.1 模板類2.2 向量的存儲結(jié)構(gòu)及其實現(xiàn)2.3 向量遍歷器2.4 向量的應(yīng)用-四個排序算法【學(xué)習(xí)目的與要求】本章目的是介紹一種靜態(tài)表的數(shù)據(jù)結(jié)構(gòu)-向量，要求掌握模板類，因為本書中所有的數(shù)據(jù)結(jié)構(gòu)實現(xiàn)均用到模板類，本章介紹了向量的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其實現(xiàn)，向量遍歷器，向量的應(yīng)用-四個排序算法，難點是模板類和四個排

5、序算法?！究己酥R與考核要求】 掌握向量的有關(guān)概念及基本操作。 掌握向量的應(yīng)用-四個排序算法。第4章 鏈表【課程內(nèi)容】4.1 線性表的概念4.2 動態(tài)線性表-單鏈表的邏輯結(jié)構(gòu) 4.3 單鏈表的實現(xiàn)  4.4 單鏈表應(yīng)用-插入排序，排序表  4.5 其它鏈表-雙端鏈表、循環(huán)鏈表【學(xué)習(xí)目的與要求】本章目的是介紹鏈表的邏輯結(jié)構(gòu)，以及定義在邏輯結(jié)構(gòu)上的幾種基本運算及其采用單鏈表上如何實現(xiàn)這些基本運算。要求在熟悉這些內(nèi)容的基礎(chǔ)上，能夠針對具體應(yīng)用問題的要求和性質(zhì)，選擇用單鏈表數(shù)據(jù)結(jié)構(gòu)來設(shè)計出相應(yīng)的有效算法，解決與鏈表相關(guān)的實際問題。本章重點是熟練掌握單鏈表上實現(xiàn)的各種基本算

6、法及相關(guān)的時間性能分析。【考核知識與考核要求】掌握單鏈表上實現(xiàn)的建表、查找、插入和刪除等基本算法，并分析其時間復(fù)雜度。 利用單鏈表設(shè)計算法解決簡單的應(yīng)用問題。    掌握單鏈表的應(yīng)用-排序鏈表和插入排序。 了解雙端鏈表、循環(huán)鏈表鏈接方式上的區(qū)別。第5章 棧和隊列【課程內(nèi)容】5.1 棧5.2 隊列5.3 棧的應(yīng)用-表達(dá)式求值【學(xué)習(xí)目的與要求】本章目的是介紹棧和隊列的邏輯結(jié)構(gòu)定義及在兩種存儲結(jié)構(gòu)上的基本運算。要求在掌握棧和隊列的特點的基礎(chǔ)上，懂得在什么樣的情況下能夠使用棧或隊列。本章重點是掌握棧的應(yīng)用-表達(dá)式中后綴轉(zhuǎn)換、中綴表達(dá)式求值?！究己酥R與考核要求】 掌握棧的

7、邏輯結(jié)構(gòu)特點。 掌握順序棧和鏈棧上實現(xiàn)的進(jìn)棧、退棧等基本算法。 掌握利用棧設(shè)計算法解決簡單的應(yīng)用問題-表達(dá)式求值。 掌握隊列的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其相關(guān)算法。 掌握隊列的邏輯結(jié)構(gòu)特點，隊列與線性表的異同。 掌握順序隊列（主要是循環(huán)隊列）和鏈隊列上實現(xiàn)的入隊、出隊等基本算法。 掌握隊列的“上溢”和“下溢”的概念及其判別條件。 掌握循環(huán)隊列中對邊界條件的處理方法。了解隊列的應(yīng)用。第6章 樹和二叉樹【課程內(nèi)容】6.1 樹及其相關(guān)概念6.2 二叉樹和森林、樹的轉(zhuǎn)換6.3 二叉樹的抽象數(shù)據(jù)類型描述及兩種表示(向量和鏈?zhǔn)奖硎?6.4 二叉樹的遍歷6.5 二叉樹的遍歷器先序遍歷器6.6 二叉排序樹的抽象數(shù)據(jù)

8、類型及相關(guān)運算（操作）實現(xiàn)6.7 AVL樹6.8 哈夫曼樹及其應(yīng)用【學(xué)習(xí)目的與需求】本章目的是介紹二叉樹的定義、性質(zhì)、存儲結(jié)構(gòu)、遍歷、遍歷器，樹的定義、樹和森林與二叉樹的轉(zhuǎn)換、排序樹、AVL樹、哈夫曼樹及哈夫曼編碼等內(nèi)容。要求在熟悉這些內(nèi)容的基礎(chǔ)上，重點掌握二叉樹的遍歷算法及其相關(guān)應(yīng)用、排序樹、AVL樹，難點是使用本章所學(xué)到的有關(guān)知識設(shè)計出有效算法，解決與樹或二叉樹相關(guān)的應(yīng)用問題?！究己酥R點與考核要求】 了解樹的常用術(shù)語。 掌握二叉樹的遞歸定義。 掌握二叉樹的性質(zhì)，了解相應(yīng)的證明方法。 掌握二叉樹的兩種存儲方法、特點及適用范圍。 掌握二叉樹的四種遍歷算法，理解其執(zhí)行過程。 了解二叉樹先序遍歷

9、器。 掌握樹和森林與二叉樹之間的轉(zhuǎn)換方法。 掌握二叉排序樹的抽象數(shù)據(jù)類型描述及插入刪除的實現(xiàn)。 掌握AVL樹的插入和刪除的過程模擬。 掌握哈夫曼算法的思想。 掌握哈夫曼編碼。第7章 散列結(jié)構(gòu)【課程內(nèi)容】7.1 基本概念7.2 散列函數(shù)7.3 開地址散列7.4 桶散列【學(xué)習(xí)目的與要求】本章目的是介紹散列表的查找方法以及各種查找方法的時間性能（平均查找長度）比較。要求在熟悉這些內(nèi)容的基礎(chǔ)上，重點散列函數(shù)以及解決沖突的兩種方法。【考核知識點與考核要求】 掌握散列函數(shù)-除余法。 掌握開地址散列的算法模擬-線性探測法。掌握桶散列的算法模擬。第8章 優(yōu)先隊列【課程內(nèi)容 】 8.1 優(yōu)先隊列的基本

10、概念8.2 堆的數(shù)據(jù)結(jié)構(gòu)8.3 堆排序【學(xué)習(xí)目的與要求】本章目的是介紹優(yōu)先隊列,最小堆結(jié)構(gòu)、推排序。要求在熟悉這些內(nèi)容的基礎(chǔ)上，重點掌握堆排序的基本思想及排序過程，本章難點是堆排序的算法實現(xiàn)。【考核知識點與考核要求】 了解優(yōu)先隊列的概念。 掌握堆結(jié)構(gòu)及插入和刪除算法實現(xiàn)。 掌握用堆結(jié)構(gòu)來實現(xiàn)排序的基本思想和算法實現(xiàn)，以及平均情況下的時間性能分析。    與前面的四個算法進(jìn)行比較，比較時間性能分析，穩(wěn)定性分析。第9章 圖【課程內(nèi)容】9.1 圖的概念9.2 圖的兩種存儲結(jié)構(gòu)表示9.3 圖的兩種遍歷9.4 圖的可達(dá)性問題-Warshall算法9.5 生成樹和兩種最小生成

11、樹算法9.6 最短路徑9.7 拓?fù)渑判颉緦W(xué)習(xí)目的與要求】本章目的是介紹圖的基本概念、兩種常用的存儲結(jié)構(gòu)表示、兩種遍歷算法以及圖的應(yīng)用算法，要求考生在熟悉這些內(nèi)容的基礎(chǔ)上，重點掌握在圖的兩種存儲結(jié)構(gòu)上實現(xiàn)的遍歷算法、理解可達(dá)問題、最短路徑、最小生成樹、拓?fù)渑判虻乃惴M。本章難點是圖的應(yīng)用算法：求最小生成樹的兩種算法模擬，結(jié)點可達(dá)的算法模擬，求最短路徑以及拓?fù)渑判虻乃惴M，只要求考生掌握這些算法的基本思想及時間性能。【考核知識與考核要求】 了解圖的常用術(shù)語及含義。 掌握鄰接矩陣和鄰接表這兩種存儲結(jié)構(gòu)的特點及適用范圍。 掌握 連通圖及非連通圖的深度優(yōu)先搜索和廣度優(yōu)先搜索兩種遍歷算法。

12、了解圖的兩種遍歷與樹的遍歷之間的關(guān)系。 能夠利用圖的兩種遍歷設(shè)計算法解決簡單的應(yīng)用問題。 掌握 Warshall算法的基本思想。 掌握 最小生成樹的兩個算法-Prim和Kruskal算法的基本思想。 掌握單源最短路徑的Dijkstra算法的基本思想。 掌握多源最短路徑Floyd-Warshall算法的基本思想。 掌握拓?fù)渑判虻幕舅枷牒筒襟E。第10章 排序【課程內(nèi)容 】 7.1 基本概念7.2 插入排序7.3 交換排序7.4 選擇排序7.5 歸并排序7.6 分配排序7.7 各種排序方法的比較和選擇【學(xué)習(xí)目的與要求】本章目的是介紹五類內(nèi)部排序方法的基本思想、排序過程

13、、算法實現(xiàn)、時間和空間性能的分析以及各種排序方法的比較和選擇。要求在熟悉這些內(nèi)容的基礎(chǔ)上，重點掌握快速排序、堆排序、歸并排序和基數(shù)排序的基本思想及排序過程，本章難點是這四個排序算法的實現(xiàn)。【考核知識點與考核要求】 了解排序在數(shù)據(jù)處理中的重要性以及排序方法的“穩(wěn)定”性含義。 掌握排序方法的分類及算法好壞的評判標(biāo)準(zhǔn)。 掌握直接插入排序的基本思想和算法實現(xiàn)，以及在最好、最壞和平均情況下的時間性能分析。    掌握冒泡排序的基本思想。 掌握快速排序的基本思想和算法實現(xiàn)，以及在最壞和平均情況下的時間性能分析，了解算法的穩(wěn)定性，并能夠根據(jù)給定的輸入實例，能寫出快速排序的排序過

14、程。 了解堆、小根堆、大根堆、堆項等有關(guān)概念和定義。 掌握堆性質(zhì)及堆與完全二叉樹的關(guān)系，并能夠針對給定的輸入實例，寫出堆排序的排序過程。 掌握歸并排序的基本思想和算法實現(xiàn)，以及時間性能分析，并能夠針對給定的輸入實例，能寫出歸并排序的排序過程。 掌握基數(shù)排序的基本思想和算法實現(xiàn)，以及時間性能分析。并能夠?qū)o定的輸入實例，能寫出基數(shù)排序的排序過程。 掌握各種排序方法的比較和選擇并能夠?qū)Ρ慌判虻挠涗洈?shù)目、記錄信息量的大小、關(guān)鍵字的結(jié)構(gòu)及初始狀態(tài)、穩(wěn)定性要求、輔助空間的大小、各種時間性能等方面的比較掌握各種排序的優(yōu)缺點。第11章 文件【課程內(nèi)容】10.1 文件的基本概念10.2 歸并排序10.3分配排序(基數(shù)排序)【學(xué)習(xí)目的與要求】本章目的是介紹存儲在外存上的數(shù)據(jù)結(jié)構(gòu)(即文件)的有關(guān)概念、各種文件的特點、組織方法及查詢和更新操作，要求對這些內(nèi)容做一般性的了解。重點掌握兩種排序，并與前面的