北京工業大學計算機學院專業型碩士2011年考研大綱

考試內容及范圍說明

896 數據結構

1、數據結構的相關概念、算法概念、算法性質及算法分析（時間復雜度與空間復雜度）；

1. 線性表邏輯定義、存儲結構的表示，以及在特定存儲結構下線性表基本運算的算法實現；
2. 棧與隊列的邏輯定義、存儲結構的表示，基本操作特點，棧與隊列的基本應用；
3. 串的邏輯定義，基本操作含義與實現；
4. 數組定義、順序存儲，矩陣的壓縮存儲，廣義表定義及存儲結構；
5. 樹的定義與存儲結構、二叉樹定義與性質、存儲結構，二叉樹遍歷算法（三序遍歷與按層遍歷），赫夫曼樹與赫夫曼編碼以及二叉樹基本算法的實現與應用；
6. 圖的定義與術語，圖的存儲結構，圖的遍歷（深度優先搜索與廣度優先搜索），比較小生成樹、拓撲排序與從某個源點到其余各頂點的比較短路徑；
7. 查找的相關概念，靜態查找表（順序表的查找與有序表的查找），動態查找表（二叉排序樹），哈希表的相關概念
8. 排序的相關概念，掌握直接插入排序、冒泡排序、快速排序、簡單選擇排序、堆排序、歸并排序算法的執行過程、時空復雜度、穩定性以及使用場合。