2016北京航空航天大學(xué)軟件學(xué)院考研大綱

• 2025考研復(fù)試標(biāo)準(zhǔn)班
• 26考研全科上岸規(guī)劃營「擇校▪規(guī)劃▪備考」
• 北京航空航天大學(xué)2026考研專業(yè)課復(fù)習(xí)資料「真題▪筆記▪講義▪題庫」

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

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

2016年“數(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)”部分

一、概述

1．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)的基本概念；

2．算法的定義、基本性質(zhì)以及算法分析的基本概念，包括采用大O形式表示時(shí)間復(fù)雜度和空間復(fù)雜度。

二、線性表

1．線性關(guān)系、線性表的定義，線性表的基本操作；

2．線性表的順序存儲(chǔ)結(jié)構(gòu)與鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)(包括單(向)鏈表、循環(huán)鏈表和雙向鏈表)的構(gòu)造原理；

3．在以上兩種存儲(chǔ)結(jié)構(gòu)的基礎(chǔ)上對(duì)線性表實(shí)施的基本操作，包括順序表的插入與刪除、鏈表的建立、插入與刪除、查找等操作對(duì)應(yīng)的算法設(shè)計(jì)(含遞歸算法的設(shè)計(jì))。

三、堆棧與隊(duì)列

1．堆棧與隊(duì)列的基本概念與基本操作；

2．堆棧與隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)與鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的構(gòu)造原理；

3．在不同存儲(chǔ)結(jié)構(gòu)的基礎(chǔ)上對(duì)堆棧與隊(duì)列實(shí)施插入與刪除等基本操作的算法設(shè)計(jì)；

4.循環(huán)隊(duì)列的基本概念；

5．堆棧和隊(duì)列在解決實(shí)際問題中應(yīng)用。

四、樹與二叉樹

1．樹與二叉樹的基本概念，基本特征、名詞術(shù)語；

2．完全二叉樹與滿二叉樹的基本概念，二叉樹的基本性質(zhì)及其應(yīng)用；

3．二叉樹的順序存儲(chǔ)結(jié)構(gòu)與二叉鏈表存儲(chǔ)結(jié)的基本原理；

4．二叉樹的前序遍歷、中序遍歷、后序遍歷和按層次遍歷，重點(diǎn)是二叉樹在以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)基礎(chǔ)上各種遍歷算法(包括非遞歸算法)的設(shè)計(jì)與應(yīng)用；

5．二叉排序樹的基本概念、建立(插入)、查找以及平均查找長度ASL的計(jì)算。

五、圖

1．圖的基本概念、名詞術(shù)語；

2．圖的鄰接矩陣存儲(chǔ)方法和鄰接表(含逆鄰接表)存儲(chǔ)方法的構(gòu)造原理及特點(diǎn)；

3．圖的深度優(yōu)先搜索與廣度優(yōu)先搜索；

4．最小(代價(jià))生成樹、最短路徑、AOV網(wǎng)與拓?fù)渑判蛞约癆OE網(wǎng)與關(guān)鍵路徑的基本概念與求解過程。

六、文件及查找

1．順序查找法以及平均查找長度(ASL)的計(jì)算；

2．折半查找法以及平均查找長度(ASL)的計(jì)算，包括查找過程對(duì)應(yīng)的“判定樹”的構(gòu)造；

3．B-樹和B+樹的基本概念，B-樹的插入與查找；

4．散列(Hash)表的構(gòu)造、散列函數(shù)的構(gòu)造，散列沖突的基本概念、處理散列沖突的基本方法以及散列表的查找和平均查找長度的計(jì)算。

七、內(nèi)排序

1．排序的基本概念，各種內(nèi)排序方法的基本原理和特點(diǎn)，包括排序過程中進(jìn)行的元素之間的比較次數(shù)，排序總趟數(shù)、排序穩(wěn)定性以及時(shí)間復(fù)雜度與空間復(fù)雜度計(jì)算；

2．插入排序法(含折半插入排序法)；

3．選擇排序法；

4．(起)泡排序法；

5．快速排序法；

6．堆積(Heap)排序法，包括堆積的定義與構(gòu)造；

7．二路歸并排序法。

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

一、C語言基本知識(shí)

1．C語言的特點(diǎn)以及C語言程序的組成；

2．?dāng)?shù)據(jù)類型，包括整型、實(shí)型、字符型等常量與變量和變量的賦值；用typedef定義類型；

3．各種類型數(shù)據(jù)之間的混合運(yùn)算；

4．各類運(yùn)算符(包括自增、自減運(yùn)算符)的運(yùn)算規(guī)則與優(yōu)先級(jí)，條件運(yùn)算符；

5．算術(shù)表達(dá)式、關(guān)系表達(dá)式和邏輯表達(dá)式，逗號(hào)運(yùn)算符和逗號(hào)表達(dá)式，表達(dá)式sizeof的含義。

二、基本語句

1．賦值語句(含條件賦值語句)、條件語句(含if、if-else、switch)、循環(huán)語句(含while、do-while、for語句，包括循環(huán)嵌套和break語句與continue語句)；

2．輸入/輸出語句，包括整型、實(shí)型、字符型(含字符串)等類型數(shù)據(jù)的格式輸入函數(shù)scanf和格式輸出函數(shù)printf。

三、數(shù)組

1．一維數(shù)組和二維數(shù)組的定義、引用與初始化；

2．字符數(shù)組的定義、引用與初始化，字符數(shù)組的輸入與輸出，字符串和字符串處理函數(shù)的應(yīng)用。

四、函數(shù)

1．函數(shù)的定義，函數(shù)參數(shù)(形參和實(shí)參)與函數(shù)的返回值；

2．函數(shù)的調(diào)用，包括函數(shù)的嵌套調(diào)用和函數(shù)的遞歸調(diào)用；

3．命令行參數(shù)的基本概念，帶參數(shù)的主函數(shù)的概念和應(yīng)用。

五、指針

1．指針的基本概念，變量的指針與指向變量的指針變量，包括定義、引用以及指針變量作為函數(shù)參數(shù)；

2．?dāng)?shù)組與指針，包括指向數(shù)組的指針變量的定義與賦值、通過指針引用數(shù)組元素、數(shù)組名作為函數(shù)參數(shù)；

3．字符串與指針，指向字符串的指針變量。

六、宏定義

1．帶參數(shù)的宏定義；

2．“包含文件”處理的基本概念。

七、結(jié)構(gòu)體與共用體

1．結(jié)構(gòu)體的基本概念和特點(diǎn)，結(jié)構(gòu)體變量的初始化與引用；

2．結(jié)構(gòu)體數(shù)組，包括結(jié)構(gòu)體數(shù)組的定義、初始化及應(yīng)用；

3．共用體的基本概念，共用體變量的引用。

八、位運(yùn)算

1．位運(yùn)算和位運(yùn)算符；

2．位運(yùn)算的應(yīng)用。

九、文件

1．文件的基本概念，包括文件類型指針FILE與文件的使用方式；

2．文件的打開函數(shù)fopen與關(guān)閉函數(shù)fclose；

3．文件的狀態(tài)，包括feof函數(shù)和ferror函數(shù)；

4．文件的讀/寫，包括fread和fwrite函數(shù)、fputc和fgetc函數(shù)、fgets與fputs函數(shù)的應(yīng)用；

5．文件的輸入函數(shù)fscanf和輸出函數(shù)fprintf的應(yīng)用；

6．文件的定位，包括rewind函數(shù)和fseek函數(shù)以及ftell函數(shù)的應(yīng)用。