北京航空航天大學(xué)

991“數(shù)據(jù)結(jié)構(gòu)與C語言程序設(shè)計(jì)”考試大綱(2021版)

2021年“數(shù)據(jù)結(jié)構(gòu)與C語言程序設(shè)計(jì)”考試內(nèi)容包括“數(shù)據(jù)結(jié)構(gòu)”與“C語言程序設(shè)計(jì)”兩門課程的內(nèi)容，各占比例50%。試卷滿分為150分。

“數(shù)據(jù)結(jié)構(gòu)”部分

一、緒論

包括但不限于數(shù)據(jù)結(jié)構(gòu)和算法的基本概念，主要內(nèi)容有：數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)的基本概念;算法的定義、基本性質(zhì)以及算法分析的基本概念，包括采用大O形式表示時(shí)間復(fù)雜度和空間復(fù)雜度。

二、線性表

包括但不限于線性表的概念、各種存儲(chǔ)結(jié)構(gòu)、操作和應(yīng)用，主要內(nèi)容有：線性關(guān)系、線性表的定義，線性表的基本操作;線性表的順序存儲(chǔ)結(jié)構(gòu)和操作的實(shí)現(xiàn);線性鏈表及其操作;循環(huán)鏈表及其操作;雙向鏈表及其操作;鏈表的應(yīng)用。

三、數(shù)組

包括但不限于數(shù)組的存儲(chǔ)結(jié)構(gòu)和操作，主要內(nèi)容有：.一維數(shù)組和二維數(shù)組的存儲(chǔ);矩陣的壓縮存儲(chǔ)的基本概念;對(duì)稱矩陣、對(duì)角矩陣以及三角矩陣的壓縮存儲(chǔ)。

四、堆棧與隊(duì)列

包括但不限于堆棧與隊(duì)列的基本概念、操作和應(yīng)用，主要內(nèi)容有：堆棧與隊(duì)列的基本概念與基本操作;堆棧與隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)與鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的構(gòu)造原理;在不同存儲(chǔ)結(jié)構(gòu)的基礎(chǔ)上對(duì)堆棧與隊(duì)列實(shí)施插入與刪除等基本操作的算法設(shè)計(jì);堆棧和隊(duì)列在解決各類實(shí)際問題中應(yīng)用。

五、樹與二叉樹

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

六、圖

包括但不限于圖的基本概念和操作，主要內(nèi)容有：圖的基本概念、名詞術(shù)語;圖的鄰接矩陣存儲(chǔ)方法和鄰接表(含逆鄰接表)存儲(chǔ)方法的構(gòu)造原理及特點(diǎn);圖的深度優(yōu)先搜索與廣度優(yōu)先搜索，連通分量;最小(代價(jià))生成樹、最短路徑、AOV網(wǎng)與拓?fù)渑判�、AOE網(wǎng)與關(guān)鍵路徑的基本概念和算法原理。

七、文件及查找

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

八、內(nèi)排序

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

“C語言程序設(shè)計(jì)”部分

一、C程序的基本結(jié)構(gòu)

包括但不限于C語言程序的基本組成、編譯運(yùn)行過程等內(nèi)容。

二、常量、變量和表達(dá)式

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

三、條件語句和開關(guān)語句

包括但不限于條件語句和開關(guān)語句的基本概念和使用，主要內(nèi)容有：關(guān)系運(yùn)算符和邏輯運(yùn)算符;運(yùn)算符的優(yōu)先級(jí);邏輯表達(dá)式;條件語句：條件、復(fù)合語句、條件語句的嵌套和級(jí)聯(lián)、條件運(yùn)算符和條件表達(dá)式;switch開關(guān)語句。

四、循環(huán)語句

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

五、函數(shù)

包括但不限于函數(shù)的基本概念和使用，主要內(nèi)容有：函數(shù)的基本概念;函數(shù)的調(diào)用、結(jié)構(gòu)和定義;函數(shù)的調(diào)用關(guān)系和返回值;局部變量、全局變量和靜態(tài)變量;函數(shù)參數(shù)的傳遞;常見標(biāo)準(zhǔn)庫(kù)函數(shù)的使用;遞歸函數(shù)。

六、數(shù)組

包括但不限于數(shù)組的基本概念和使用，主要內(nèi)容有：一維數(shù)組：定義和初始化、復(fù)制、數(shù)組參數(shù);字符串和字符數(shù)組;標(biāo)準(zhǔn)字符串函數(shù);二維數(shù)組：定義、引用、訪問、數(shù)組參數(shù)。

七、指針

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

八、結(jié)構(gòu)和聯(lián)合

包括但不限于結(jié)構(gòu)和聯(lián)合的基本概念和使用，主要內(nèi)容有：結(jié)構(gòu)：結(jié)構(gòu)類型的定義和訪問、包含結(jié)構(gòu)的結(jié)構(gòu);聯(lián)合：聯(lián)合類型的定義和訪問;類型定義語句(typedef);復(fù)雜類型的解讀。

九、輸入/輸出和文件

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