北京航空航天大學

991“數據結構與C語言程序設計”考試大綱(2021版)

2021年“數據結構與C語言程序設計”考試內容包括“數據結構”與“C語言程序設計”兩門課程的內容，各占比例50%。試卷滿分為150分。

“數據結構”部分

一、緒論

包括但不限于數據結構和算法的基本概念，主要內容有：數據的邏輯結構與存儲結構的基本概念;算法的定義、基本性質以及算法分析的基本概念，包括采用大O形式表示時間復雜度和空間復雜度。

二、線性表

包括但不限于線性表的概念、各種存儲結構、操作和應用，主要內容有：線性關系、線性表的定義，線性表的基本操作;線性表的順序存儲結構和操作的實現;線性鏈表及其操作;循環鏈表及其操作;雙向鏈表及其操作;鏈表的應用。

三、數組

包括但不限于數組的存儲結構和操作，主要內容有：.一維數組和二維數組的存儲;矩陣的壓縮存儲的基本概念;對稱矩陣、對角矩陣以及三角矩陣的壓縮存儲。

四、堆棧與隊列

包括但不限于堆棧與隊列的基本概念、操作和應用，主要內容有：堆棧與隊列的基本概念與基本操作;堆棧與隊列的順序存儲結構與鏈式存儲結構的構造原理;在不同存儲結構的基礎上對堆棧與隊列實施插入與刪除等基本操作的算法設計;堆棧和隊列在解決各類實際問題中應用。

五、樹與二叉樹

包括但不限于樹的基本概念和操作，二叉樹的基本概念、操作和應用，主要內容有：樹與二叉樹的基本概念、基本特征和名詞術語;完全二叉樹與滿二叉樹的基本概念，二叉樹的基本性質及其應用;二叉樹的順序存儲結構與二叉鏈表存儲結構的基本原理;二叉樹的前序遍歷、中序遍歷、后序遍歷和按層次遍歷，重點是二叉樹在以二叉鏈表作為存儲結構基礎上各種遍歷算法(包括遞歸和非遞歸算法)的設計與應用;線索二叉樹的基本概念;二叉排序樹的基本概念、建立(插入)、刪除結點、查找以及平均查找長度(ASL)的計算;哈夫曼樹的基本概念和簡單應用。

六、圖

包括但不限于圖的基本概念和操作，主要內容有：圖的基本概念、名詞術語;圖的鄰接矩陣存儲方法和鄰接表(含逆鄰接表)存儲方法的構造原理及特點;圖的深度優先搜索與廣度優先搜索，連通分量;最小(代價)生成樹、最短路徑、AOV網與拓撲排序、AOE網與關鍵路徑的基本概念和算法原理。

七、文件及查找

包括但不限于文件及查找的基本概念、操作和應用，主要內容有：順序查找法以及平均查找長度(ASL)的計算;折半查找法以及平均查找長度(ASL)的計算，包括查找過程對應的“判定樹”的構造;B-樹和B+樹的基本概念;散列(Hash)表的構造、散列函數的構造，散列沖突的基本概念、處理散列沖突的基本方法以及散列表的查找和平均查找長度的計算。

八、內排序

包括但不限于內排序的基本概念、各類算法實現原理和應用，主要內容有：排序的基本概念，各種內排序方法的基本原理和特點，包括排序過程中進行的元素之間的比較次數，排序總趟數、排序穩定性以及時間復雜度與空間復雜度計算;插入排序法(含折半插入排序法);選擇排序法;泡排序法;謝爾(Shell)排序法;快速排序法;堆積(Heap)排序法;二路歸并排序法。

“C語言程序設計”部分

一、C程序的基本結構

包括但不限于C語言程序的基本組成、編譯運行過程等內容。

二、常量、變量和表達式

包括但不限于C語言常量、變量和表達式的基本概念和使用，主要內容有：常量：數字常量、字符常量和字符串字面量;變量：變量名和變量類型，變量的賦值和類型轉換;算術表達式：算術運算符、增量(自增)和減量(自減)運算符、位運算和復合賦值運算符;強制類型轉換;數據輸入/輸出函數;常量的符號表示方法：常量宏、枚舉常量。

三、條件語句和開關語句

包括但不限于條件語句和開關語句的基本概念和使用，主要內容有：關系運算符和邏輯運算符;運算符的優先級;邏輯表達式;條件語句：條件、復合語句、條件語句的嵌套和級聯、條件運算符和條件表達式;switch開關語句。

四、循環語句

包括但不限于循環語句的基本概念和使用，主要內容有：while語句、for語句和do while語句;循環語句的選擇和使用;逗號表達式;循環語句的嵌套;循環中的非常規控制(break和continue)、goto語句。

五、函數

包括但不限于函數的基本概念和使用，主要內容有：函數的基本概念;函數的調用、結構和定義;函數的調用關系和返回值;局部變量、全局變量和靜態變量;函數參數的傳遞;常見標準庫函數的使用;遞歸函數。

六、數組

包括但不限于數組的基本概念和使用，主要內容有：一維數組：定義和初始化、復制、數組參數;字符串和字符數組;標準字符串函數;二維數組：定義、引用、訪問、數組參數。

七、指針

包括但不限于指針的基本概念和使用，主要內容有：地址與指針;指針變量：定義和賦值、訪問、參數和返回值;指針運算：指針與整數的加減、指針相減和比較、強制類型轉換和void*指針、不合法的指針運算、指針類型與數組類型的差異;指針與數組;指向二維數組的指針、多重指針和指針數組;函數指針。

八、結構和聯合

包括但不限于結構和聯合的基本概念和使用，主要內容有：結構：結構類型的定義和訪問、包含結構的結構;聯合：聯合類型的定義和訪問;類型定義語句(typedef);復雜類型的解讀。

九、輸入/輸出和文件

包括但不限于輸入/輸出和文件的基本概念和使用，主要內容有：輸入/輸出的基本過程和文件類型;文件的打開、創建和關閉;文件數據的正文(文本)格式讀寫;讀寫操作中的定位;文件數據的二進制格式讀寫