北華航天工業學院研究生入學考試
數據結構（508）復試科目大綱
一、考試總體要求
本
考試大綱適用于報考我校航空宇航科學與技術專業-航天遙感技術與應用方向、電子信息專業-遙感與空間信息工程方向的碩士研究生入學考試。
《數據結構》課程考試目標：理解數據結構的基本概念、基本原理和方法；掌握數據的
邏輯結構、存儲結構及其差異，以及各種基本操作的實現。具備運用數據結構基本原理、基本方法進行分析和解決有關問題的能力，能夠對算法進行設計與分析，并運用數據結構對問題進行求解。
二、考試形式：待定。
三、考試內容及要求
（一）概述
2．理解算法定義、基本性質以及算法分析，包括時間復雜度和空間復雜度的計算。
（二）線性表
1．理解線性關系、線性表的定義和線性表的基本操作。
2．掌握線性表的順序存儲結構與鏈式存儲結構(包括單鏈表、循環鏈表和雙向鏈表)的構造原理。
3．熟練掌握在以上兩種存儲結構的基礎上對線性表實施的基本操作，包括順序表的插入、刪除、查找等以及鏈表的建立、插入、刪除、查找等操作對應的算法設計。
4．掌握鏈表的常用應用。
（三）棧和隊列
1．理解棧與隊列的基本概念與基本操作。
2．掌握棧與隊列的順序存儲結構與鏈式存儲結構的構造原理。
3．熟練掌握在不同存儲結構的基礎上對棧與隊列實施插入與刪除等基本操作的算法設計。
4．掌握棧和隊列在解決實際問題中應用。例如：遞歸過程、表達式求值、數制轉換、迷宮求解、排隊問題等。
（四）串、數組和廣義表
1．理解串的基本概念及其順序和鏈式存儲結構。
2．掌握串的模式匹配過程及算法設計。
3．掌握數組的順序存儲結構及地址計算。
4．理解特殊矩陣的壓縮存儲方法。
5．理解廣義表的基本概念、存儲結構。
（五）樹與二叉樹
1．理解樹與二叉樹的基本概念，名詞術語。
2．掌握二叉樹的基本性質和存儲結構。
3．掌握二叉樹與樹、森林之間的轉換。
4．熟練掌握二叉樹的遍歷，包括遞歸和非遞歸算法。
5．掌握以二叉鏈表形式存儲的二叉樹遍歷算法的應用。
6．掌握哈夫曼樹的基本概念，哈夫曼樹和哈夫曼編碼的構造和算法設計。
（六）圖
1．理解圖的基本概念和名詞術語。
2．掌握圖的鄰接矩陣和鄰接表（含逆鄰接表）存儲方法的構造原理及特點。
3．熟練掌握圖的深度優先搜索與廣度優先搜索過程和算法設計。
4．掌握最小生成樹和最短路徑的構造和算法設計。
5．掌握AOV網與拓撲排序基本概念與求解過程。
（七）查找
1．掌握順序查找、折半查找和分塊查找的查找算法的設計與算法復雜性的分析過程。
2．掌握二叉排序樹的概念、構造、基本操作及實現算法的設計。
3．掌握平衡二叉樹的概念、構造、插入和刪除過程。
4．掌握散列(Hash)表的構造、散列函數的構造、處理散列沖突的基本方法以及散列表的查找和平均查找長度的計算。
（八）內部排序
1．理解排序的基本概念，各種內排序方法的基本原理和特點，包括排序過程中進行的元素之間的比較次數，排序總趟數、排序穩定性以及時間復雜度與空間復雜度計算。
2．掌握直接插入排序、折半插入排序、選擇排序、起泡排序、希爾排序、快速排序、堆排序、二路歸并排序、基數排序的排序思想；
3．了解各種內部排序算法的應用。
四、參考書目
《數據結構(C語言版)》 嚴蔚敏 吳偉民主編 清華大學出版社
京公安網備11010802020593號
