隴東學院2019年專升本計算機科學與技術專業(yè)《數據結構與算法》考試大綱

一、考試目的

考核普通高等學校專科（含高職）應屆畢業(yè)生對于《數據結構與算法》課程基本知識掌握是否達到教學大綱所規(guī)定的要求。

二、考試要求及內容

第1章 緒論

1、掌握數據、數據元素、數據項、數據結構等基本概念。

2、掌握數據結構的邏輯結構、存儲結構及數據運算的含義及其相互關系。

3、掌握數據結構的兩大類邏輯結構和四種常用的存儲表示方法。

4、理解算法、算法的時間復雜度和空間復雜度、最壞的和平均的時間復雜度等概念。

5、掌握算法描述和算法分析的方法，對于一般算法能分析出時間復雜度。   

第2章 線性表

1、理解線性表的邏輯結構特征。

2、理解線性表上定義的基本運算，并能利用基本運算構造出較復雜的運算。

線性表的順序存儲結構，要求達到“綜合利用”層次。 

3、 理解順序表的含義及特點，即順序表如何反映線性表中元素之間的邏輯關系。

4、掌握順序表上的插入、刪除操作及其平均時間性能分析。 

5、理解利用順序表設計算法解決簡單的應用問題。  

6、掌握鏈表如何表示線性表中元素之間的邏輯關系。  

7、掌握鏈表中頭指針和頭結點的使用。 

8、理解單鏈表、雙鏈表、循環(huán)鏈表鏈接方式上的區(qū)別。 

9、 掌握單鏈表上實現(xiàn)的建表、查找、插入和刪除等基本算法，并分析其時間復雜度。   

10、理解循環(huán)鏈表上尾指針取代頭指針的作用，以及單循環(huán)鏈表上的算法與單鏈表上相應算法的異同點。   

11、理解雙鏈表的定義及其相關的算法。  

12、掌握利用鏈表設計算法解決簡單的應用問題。 

13、理解順序表和鏈表的主要優(yōu)缺點。

14、掌握針對線性表上所需要執(zhí)行的主要操作，知道選擇順序表還是鏈表作為其存儲結構才能取得較優(yōu)的時空性能。

第3章 棧和隊列

 1、理解棧的邏輯結構特點，棧與線性表的異同。

 2、掌握順序棧和鏈棧上實現(xiàn)的進棧、退棧等基本算法。

 3、理解棧的“上溢”和“下溢”的概念及其判別條件。

 4、掌握利用棧設計算法解決簡單的應用問題。

 5、理解隊列的邏輯結構特點，隊列與線性表的異同。

 6、掌握順序隊列（主要是循環(huán)隊列）和鏈隊列上實現(xiàn)的入隊、出隊等基本算法。

 7、理解隊列的“上溢”和“下溢”的概念及其判別條件。

 8、了解使用數組實現(xiàn)的循環(huán)隊列取代普通的順序隊列的原因。

 9、掌握循環(huán)隊列中對邊界條件的處理方法。

 10、掌握利用隊列設計算法解決簡單的應用問題。

第4章 串

1、掌握串的有關概念及基本運算。

2、理解串與線性表的關系。

3、掌握串的兩種存儲表示。

4、掌握使用C語言提供的串操作函數構造與串相關的算法解決簡單的應用問題。

第5章 數組和廣義表

 1、掌握數組的邏輯結構特征。

 2、掌握數組的順序存儲結構及地址計算方式。

 3、掌握數組是一種隨機存取結構的原因。

 4、理解特殊矩陣和稀疏矩陣的概念。

 5、理解特殊矩陣和壓縮存儲時的下標變換方法。

 6、理解稀疏矩陣的三元組表表示方法及有關算法。

 7、掌握廣義表的有關概念及其與線性表的關系。

 8、掌握廣義表的括號表示和圖形表示之間的轉換。

第6章  樹

 1、掌握樹的邏輯結構特征。

 2、掌握樹的不同表示方法。

 3、掌握樹的常用術語及含義。

 4、二叉樹的遞歸定義及樹與二叉樹的差別。

5、掌握二叉樹的性質，了解相應的證明方法。

 6、掌握二叉樹的兩種存儲方法、特點及適用范圍。

 7、掌握二叉樹的三種遍歷算法，理解其執(zhí)行過程。

 8、掌握確定三種遍歷所得到的相應的結點訪問序列。

 9、理解以遍歷算法為基礎，設計有關算法解決簡單的應用問題。

 10、理解二叉樹線索化的目的及實質。

11、理解在中序線索樹中查找給定結點的中序前趨和中序后繼的方法。

 12、掌握樹和森林與二叉樹之間的轉換方法。

 13、掌握樹的各種存儲結構及其特點。

 14、掌握樹的兩種遍歷方法。

 15、掌握最優(yōu)二叉樹和最優(yōu)前綴碼的概念及特點。

 16、掌握哈夫曼算法的思想。

 17、掌握根據給定的葉結點及其權值構造出相應的最優(yōu)二叉樹。

 18、掌握根據最優(yōu)二叉樹構造對應的哈夫曼編碼。

第7章  圖

1、理解圖的邏輯結構特征。

2、理解圖的常用術語及含義。

3、掌握鄰接矩陣和鄰接表這兩種存儲結構的特點及適用范圍。

4、掌握根據應用問題的特點和要求選擇合適的存儲結構。

5、理解連通圖及非連通圖的深度優(yōu)先搜索和廣度優(yōu)先搜索兩種遍歷算法,其執(zhí)行過程以及時間分析。

6、掌握確定兩種遍歷所得到的頂點訪問序列。

7、掌握圖的兩種遍歷與樹的遍歷之間的關系。

8、 理解兩種遍歷所使用的輔助數據結構（?；蜿犃校┰诒闅v過程中所起的作用。

9、理解利用圖的兩種遍歷設計算法解決簡單的應用問題。

10、掌握生成樹和最小生成樹的概念。

11、掌握對遍歷給定的圖，畫出深度優(yōu)先和廣度優(yōu)先生成樹或生成森林。

12、掌握Prim和Kruskal算法的基本思想、時間性能及這兩種算法各自的特點。

13、掌握要求對給定的連通圖，根據Prim和Kruskal算法構造出最小生成樹。

14、了解最短路徑的含義。

15、掌握拓撲排序的基本思想和步驟。

16、了解對給定的有向圖，若拓撲序列存在，則要求寫出拓撲序列。

第8章  查找

1、了解查找在數據處理中的重要性。

2、理解查找算法效率的評判標準。

3、掌握順序查找、二分查找、分塊查找的基本思想、算法實現(xiàn)和查找效率分析。

4、理解順序查找中哨兵的作用。

5、理解二分查找對存儲結構及關鍵字的要求。

6、理解通過比較線性表上三種查找方法的優(yōu)缺點，能根據實際問題的要求和特點，選擇出合適的查找方法。

7、掌握二叉查找樹的定義和特點以及用途。

8、掌握二叉查找樹的插入、刪除、建樹和查找算法及時間性能。

9、掌握建立一棵二叉查找樹的過程實質上是對輸入實例的排序過程，輸入實例對所建立的二叉查找樹形態(tài)的影響。

10、掌握散列表、散列函數、散列地址和裝填因子等有關概念。

11、掌握散列函數的選取原則及產生沖突的原因。

12、掌握幾種常用的散列函數構造方法。

13、理解兩類解決沖突的方法及其優(yōu)缺點。

14、理解采用線性探測法和拉鏈法解決沖突時，散列表的建表方法、查找過程以及算法實現(xiàn)和時間分析。

第9章  排序

1、了解排序在數據處理中的重要性。

2、掌握排序方法的“穩(wěn)定”性含義。

3、理解排序方法的分類及算法好壞的評判標準。

4、掌握直接插入排序的基本思想和算法實現(xiàn)，以及在最好、最壞和平均情況下的時間性能分析。

5、理解直接插入排序中哨兵的作用。

6、掌握針對給定的輸入實例，要能寫出直接插入排序的排序過程。

7、掌握針對給定的輸入實例，要能寫出shell排序的排序過程。

8、掌握冒泡排序的基本思想。

9、掌握快速排序的基本思想和算法實現(xiàn)，以及在最壞和平均情況下的時間性能分析，了解算法的穩(wěn)定性。

10、掌握針對給定的輸入實例，能寫出快速排序的排序過程。

11、理解堆、小根堆、大根堆、堆項等有關概念和定義。

12、理解堆性質及堆與完全二叉樹的關系。

13、掌握直接選擇排序和堆排序的基本思想和算法實現(xiàn)，以及時間性能分析。

14、掌握針對給定的輸入實例，寫出堆排序的排序過程。

15、掌握歸并排序的基本思想和算法實現(xiàn)，以及時間性能分析。

16、掌握針對給定的輸入實例，能寫出歸并排序的排序過程。

17、掌握通過對被排序的記錄數目、記錄信息量的大小、關鍵字的結構及初始狀態(tài)、穩(wěn)定性要求、輔助空間的大小、各種時間性能等方面的比較掌握各種排序的優(yōu)缺點。

第10章  文件

1、理解文件的有關概念。

2、理解文件的邏輯結構及其操作。

3、理解文件的存儲結構（組織方式）分類。

4、理解順序文件的特點及外存種類的適應性。

5、理解索引文件的組織方式和特點。

6、了解索引文件的查詢和更新操作的基本思想。

7、理解 兩種最常用的索引順序文件（ISAM文件和VSAM文件）的組織方式和特點。

8、了解在ISAM文件和VSAM文件上查詢和更新操作的基本思想。

 參考教材：

《數據結構》（用C語言描述），耿國華主編，高等教育出版社，2015年7月第1版。