2021西安郵電大學826數據結構研究生考試大綱 正文

西安郵電大學碩士研究生招生考試大綱
科目代碼：826
科目名稱：《數據結構》
一、課程性質和任務
數據結構是計算機各專業的專業基礎課。它是操作系統、數據庫、編譯原理等所有軟件專業基礎課和專業課的重要基礎；它還是進行程序設計，尤其是進行高水平的應用程序和系統程序必不可少的基礎。通過本課程的學習，使學生掌握數據組織、存儲和運算的基本原理和方法，培養學生對各類數據結構和相關算法的分析和設計的能力，使學生能夠編寫出正確、清晰和較高質量的算法和程序。
二、課程教學內容和要求
第一章 數據結構和算法
1. 了解數據結構、邏輯結構、存儲結構和抽象數據類型的基本概念。
2. 了解數據結構的發展和地位。
3. 了解各種算法描述方法和算法設計的基本要求。
4. 掌握對算法的評價標準和算法效率的度量方法。
第二章 線性表
1. 理解線性表的概念、定義、邏輯結構和存儲結構。
2. 熟練掌握線性表的順序結構及其各種基本運算。
3. 熟練掌握單鏈表、循環鏈表、雙向鏈表的存儲結構及其各種基本運算。
4. 理解鏈表的應用——稀疏多項式存儲和運算。
第三章 棧和隊列
1. 掌握棧的定義、表示、實現和應用。
2. 掌握遞歸的概念和遞歸的實現過程。
3. 掌握隊列的定義以及順序（循環隊列）和鏈式存儲結構的實現。
第四章 串
1. 了解串的基本概念及順序和鏈式存儲結構。
2. 掌握串的各種基本運算。
3. 了解串的模式匹配算法。
第五章 數組和廣義表
1. 掌握數組的順序存儲結構。
2. 理解稀疏數組的概念和壓縮存儲的方法。
3. 理解稀疏矩陣的三元組存儲結構和基本運算。
4. 了解稀疏矩陣的十字鏈表存儲結構。
5. 理解廣義表的基本概念，掌握廣義表的存儲結構。
第六章 樹
1. 理解樹的基本概念及其存儲結構。
2. 熟練掌握二叉樹的定義、性質以及各種存儲結構和遍歷算法。
3. 掌握線索二叉樹的概念、存儲結構及線索化算法。
4. 掌握樹和森林與二叉樹間的轉換，掌握樹和森林的遍歷算法。
5. 掌握哈夫曼樹的概念、存儲結構和應用。
第七章 圖
1. 理解圖的基本概念，掌握圖的鄰接矩陣和鄰接表的存儲結構。
2. 了解十字鏈表，鄰接多重表等存儲結構。
3. 熟練掌握圖的深度優先和廣度優先遍歷算法。
4. 理解圖的連通性、最小生成樹的概念。
5. 掌握求最小生成樹算法。
6. 理解有向無環圖的概念，掌握拓撲排序和關鍵路徑算法。
7. 理解帶權最短路徑的概念，掌握求最短路徑的算法。
第八章 查找
1. 理解查找的概念及其效率的評價方法。
2. 理解靜態查找表的概念，熟練掌握順序、折半和分塊查找算法。
3. 理解動態查找表和二叉排序樹的概念。
4. 了解平衡二叉樹的概念。
5. 理解哈希表的含義，掌握哈希函數的構造和處理沖突的基本方法。
第九章 內部排序
1. 掌握插入類排序的算法：直接插入排序、希爾排序。
2. 掌握交換類排序的算法：冒泡排序、快速排序。
3. 掌握選擇類排序的算法：簡單選擇排序、堆排序。
4. 了解歸并排序、基數排序的思想，了解外排序的概念。
三、參考書目
《數據結構與算法》，王曙燕，高等教育出版社

西安郵電大學

本文來源：http://m.btfokj.cn/xayddx/cksm_382751.html