一、考試要求
軟件工程學科專業基礎考試大綱適用于北京工業大學信息學部軟件學院（0835） 軟件工程、（0854）電子信息（專業學位）的碩士研究生招生考試?？荚噧热莅瑪祿Y構與算法和操作系統兩個部分，它們是軟件工程學科的重要基礎理論。數據結構與算法考試內容主要包括數據結構的基本概念和術語、線性表、棧和隊列、數組、串和廣義表、樹和二叉樹、集合與字典、搜索結構、圖和內部排序。要求考生對其中的基本概念有很深入的理解，掌握算法的設計及評價方法，具有綜合運用所學知識分析問題和解決問題的能力。操作系統的考試內容主要包括操作系統進程、內存、文件和I/O 管理的策略、算法、機制以及相互關系。要求考生掌握操作系統的基本概念、基本原理和基本功能，理解操作系統的整體運行過程。
二、考試內容
（一）數據結構與算法部分
1. 數據結構的基本概念和術語
（1） 掌握數據結構的基本概念和術語
（2） 掌握數據結構的邏輯結構、存儲結構
（3） 熟練掌握抽象數據類型的表示方法
（4） 熟練掌握算法的時間復雜度、空間復雜度的分析方法
2. 線性表
（1） 掌握線性表的邏輯結構
（2） 掌握線性表的順序存儲結構及插入刪除、查找、遍歷等操作的實現
（3） 掌握線性表的鏈式存儲結構及插入刪除、查找、遍歷等操作的實現
3. 棧和隊列
（1） 掌握棧的定義、棧的抽象數據類型及存貯表示
（2） 熟練掌握棧操作的實現
（3） 熟練掌握遞歸算法
（4） 掌握隊列的定義、隊列的抽象數據類型及存貯表示
（5） 熟練掌握隊列操作的實現及應用
4. 數組、串和廣義表
（1） 理解數組的定義、存貯表示及應用
（2） 理解串的定義、運算和存貯表示的特點
（3） 掌握串運算的算法
（4） 掌握廣義表的定義、ADT、存貯表示
（5） 掌握廣義表的遍歷算法
5. 樹
（1） 掌握樹結構的概念、術語和ADT
（2） 掌握二叉樹的性質和存貯表示
（3） 熟練掌握二叉樹遍歷算法及運用
（4） 掌握二叉樹線索化技術
（5） 掌握樹和森林的存貯表示、與二叉樹的轉化方法及樹的遍歷
（6） 熟練掌握樹的應用（Huffman 樹）
6. 集合與字典
（1） 掌握集合的概念、術語、ADT 及操作的實現
（2） 掌握字典的概念、術語、ADT 及操作的實現
7. 搜索結構
（1） 熟練掌握靜態查找技術
（2） 熟練掌握動態查找技術
（3） 掌握 B 樹及鏈樹的存貯表示與查找
（4） 熟練掌握哈希表技術
（5） 掌握查找技術的綜合分析評價方法
8. 圖
（1） 掌握圖的基本概念、術語和ADT
（2） 掌握圖的存貯方法
（3） 熟練掌握圖的 DFS 和 BFS 搜索算法及應用
（4） 熟練掌握最短路徑算法及應用
（5） 熟練掌握拓撲排序算法及應用
9. 內部排序
（1） 掌握排序的概念及術語
（2） 熟練掌握插入排序、冒泡排序、選擇排序、快速排序、歸并排序、堆排序及基數排序算法
（3） 掌握排序方法的最好、最壞情況分析
