一、考試要求
計算機學科專業基礎考試大綱適用于北京工業大學信息學部(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.