一、考試要求
計算機學科專業基礎考試大綱適用于北京工業大學信息學部（0812）計算機科學與技術學科、（0839）網絡空間安全、北京未來網絡科技高精尖創新中心（085211）計算機技術（專業學位）的碩士研究生招生考試?？荚噧热葜饕▋刹糠郑簲祿Y構與語言程序設計，這兩門課程是計算機科學與技術學科的重要基礎課程。數據結構的考試內容主要包括基本數據結構、排序、索引、檢索、高級數據結構等內容，從邏輯結構的角度包括線性表、棧、隊列、二叉樹、樹和圖等各種基本數據結構；從算法的角度包括各類排序、檢索和索引算法。要求考生對其中的基本概念有很深入的理解，掌握數據結構與算法的基本概念、合理組織數據的基本方法、高效處理數據的基本算法、并具備面對實際問題選擇恰當數據結構與相應算法的能力。C 語言程序設計部分的考試內容主要包括 C 語言程序設計的基礎概念、方法和技巧。要求考生熟練掌握高級語言的基本控制結構、數據組織和程序組織形式。熟練使用 C 語言的結構體、指針、文件等。具有基本的計算思維能力，熟悉簡單算法，能夠構建實際問題的模塊化解決方案。
二、考試內容
數據結構部分：
1．數據結構的相關概念、算法概念、算法性質及算法分析（時間復雜度與空間復雜度）；
2．線性表邏輯結構定義、存儲結構的表示，以及在特定存儲結構下線性表基本運算的算法實現；
3．棧與隊列的邏輯結構定義、存儲結構的表示，基本操作特點，棧與隊列的基本應用；
4．串的邏輯結構定義，基本操作的含義與實現；
5．數組定義及其順序存儲，矩陣的壓縮存儲，廣義表定義及存儲結構；
6．樹的定義與存儲結構，二叉樹的定義與性質、存儲結構，二叉樹遍歷算法（三序遍歷與按層遍歷），赫夫曼樹與赫夫曼編碼以及二叉樹基本算法的實現與應用；
7．圖的定義與術語，圖的存儲結構，圖的遍歷（深度優先搜索與廣度優先搜索），最小生成樹、拓撲排序以及最短路徑的求解；
8．查找的相關概念，靜態查找表（順序表的查找與有序表的查找），動態查找表（二叉排序樹），B-樹，B+樹，AVL 樹，哈希表的相關概念；
9．排序的相關概念，掌握插入排序、冒泡排序、快速排序、簡單選擇排序、堆排序、歸并排序、基數排序算法的執行過程、時空復雜度、穩定性以及使用場合。
C語言程序設計部分：
1、控制結構
2、算法設計初步
3、數據組織的設計與實現
4、程序組織的設計與實現
5、結構體/指針/文件的應用
三、參考書目
1、嚴蔚敏,吳偉民.《數據結構》(C 語言版). 清華大學出版社
, 2011.
2、廖湖聲等著《C 語言程序設計案例教程》第2 版).人民郵電出版社2010.
