北京航空航天大學(xué)軟件工程碩士考試《數(shù)據(jù)結(jié)構(gòu)與C語(yǔ)言程序設(shè)計(jì)》復(fù)習(xí)大綱   

《數(shù)據(jù)結(jié)構(gòu)與C語(yǔ)言程序設(shè)計(jì)》包括“數(shù)據(jù)結(jié)構(gòu)”與“C語(yǔ)言程序設(shè)計(jì)”兩門課程的內(nèi)容，各占比例50%。  

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

指定參考書：  

《數(shù)據(jù)結(jié)構(gòu)教程（第二版）》唐發(fā)根 編著，北京航空航天大學(xué)出版社，2005  

（建議盡可能選用2007年12月第4次印刷，或者2009年3月第5次印刷的書）  

一、概述  

1、簡(jiǎn)要了解數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)的基本概念；  

2、了解算法的定義、算法的五個(gè)基本性質(zhì)以及算法分析最基本的概念，包括算法分析的前提、目的。  

二、線性表  

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í)施的基本操作，重點(diǎn)包括順序表的插入和刪除、鏈表的建立、插入和刪除、檢索等操作對(duì)應(yīng)的過(guò)程和算法的設(shè)計(jì)。  

三、堆棧與隊(duì)列  

1、了解堆棧與隊(duì)列(不含循環(huán)隊(duì)列)的基本概念、基本操作；  

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

3、掌握在不同存儲(chǔ)結(jié)構(gòu)的基礎(chǔ)上對(duì)堆棧與隊(duì)列實(shí)施插入與刪除等基本操作過(guò)程。  

四、樹(shù)與二叉樹(shù)  

1、了解樹(shù)型結(jié)構(gòu)的基本概念，基本特征、名詞術(shù)語(yǔ)；  

2、了解完全二叉樹(shù)、滿二叉樹(shù)的概念；二叉樹(shù)的基本性質(zhì)（至少要記住結(jié)論）；  

3、了解二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)與二叉鏈表存儲(chǔ)結(jié)構(gòu)的構(gòu)造原理及特點(diǎn)，重點(diǎn)是二叉鏈表存儲(chǔ)結(jié)構(gòu)；  

4、掌握二叉樹(shù)的前序遍歷、中序遍歷、后序遍歷和按層次遍歷算法(非遞歸算法)以及利用遍歷解決有關(guān)二叉樹(shù)的其它操作；  

5、掌握二叉排序樹(shù)的基本概念、建立(插入)和查找。  

五、圖  

1、了解圖結(jié)構(gòu)的基本概念、基本名詞術(shù)語(yǔ)；  

2、掌握?qǐng)D的鄰接矩陣存儲(chǔ)方法和鄰接表存儲(chǔ)方法的基本構(gòu)造原理與特點(diǎn)；  

3、圖的深度優(yōu)先搜索和廣度優(yōu)先搜索的基本過(guò)程，遍歷的基本作用；  

4、最小生成樹(shù)的求解過(guò)程，拓?fù)渑判蚣捌淠康摹? 

六、文件及查找  

1、掌握順序查找法、折半查找法的查找過(guò)程，了解折半查找方法的基本要求；  

2、了解散列(Hash)文件的基本特點(diǎn)，散列函數(shù)和散列沖突的概念，處理散列沖突的方法。  

七、內(nèi)排序  

了解插入排序法、選擇排序法、泡排序法、快速排序法以及堆積排序(大頂堆積)法等排序方法的排序原理、規(guī)律和特點(diǎn)。 

《C語(yǔ)言程序設(shè)計(jì)》部分  

指定參考書：  

《C程序設(shè)計(jì)》（第三版）譚浩強(qiáng) 著，清華大學(xué)出版社, 2005、7  

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

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

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

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

4、各類運(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的含義。  

二、語(yǔ)句  

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

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

三、數(shù)組  

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

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

四、函數(shù)  

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

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

3、命令行參數(shù)的概念（帶參數(shù)的主函數(shù)）。  

五、宏定義  

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

2、包含文件的處理。  

六、指針  

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

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

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

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

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

2、結(jié)構(gòu)體數(shù)組。  

八、文件  

1、文本文件的基本概念，文本文件的類型指針FILE以及文本文件的使用方式；  

2、文本文件的打開(kāi)(fopen函數(shù))、文本文件的關(guān)閉(fclose函數(shù))；  

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

4、文本文件的讀寫，包括fputc函數(shù)和fgetc函數(shù)、fgets函數(shù)和fputs函數(shù)等；  

5、文本文件的輸入函數(shù)fscanf和輸出函數(shù)fprintf。  

說(shuō)明  

未在本大綱里提到的內(nèi)容試卷中原則上不涉及。  

試題題型（不同試卷可以組合不同題型）  

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

1、概念題（包括是非判斷題、選擇題(四選一)、填空題、簡(jiǎn)答題）  

2、綜合題（包括問(wèn)題求解過(guò)程、證明結(jié)論）  

3、算法題（包括算法填空題、算法設(shè)計(jì)題）  

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

1、選擇題（四選一）  

2、程序閱讀題（寫出程序的功能，或者程序的運(yùn)行結(jié)果，或者補(bǔ)充填空）  

3、C語(yǔ)言程序設(shè)計(jì)題  

《網(wǎng)絡(luò)安全基礎(chǔ)》復(fù)習(xí)大綱  

參考資料：《計(jì)算機(jī)網(wǎng)絡(luò)安全——協(xié)議、技術(shù)與應(yīng)用》（2008年9月版）編著：黃河；清華大學(xué)出版社。一份卷，滿分100分。 在職研究生