北京航空航天大學(xué)《數(shù)據(jù)結(jié)構(gòu)與C語言程序設(shè)計》2011年考研大綱

　991數(shù)據(jù)結(jié)構(gòu)與C語言程序設(shè)計考試大綱（2011版）
　　2011年《數(shù)據(jù)結(jié)構(gòu)與C語言程序設(shè)計》考試內(nèi)容包括“數(shù)據(jù)結(jié)構(gòu)”與“C語言程序設(shè)計”兩門課程的內(nèi)容，各占比例50%，試卷滿分總分為150分。
　　《數(shù)據(jù)結(jié)構(gòu)》部分
　　指定參考書：《數(shù)據(jù)結(jié)構(gòu)教程（第二版）》 唐發(fā)根編著 北京航空航天大學(xué)出版社 2005
　　（建議選用2010年7月第6次印刷的書）
　　一、概述
　　1．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)的基本概念；
　　2．算法的定義、基本性質(zhì)以及算法分析的基本概念，包括采用大形式表示時間和空間復(fù)雜度。
　　二、線性表
　　1．線性關(guān)系、線性表的定義，線性表的基本操作；
　　2．線性表的順序存儲結(jié)構(gòu)與鏈?zhǔn)酱鎯�結(jié)構(gòu)(包括單(向)鏈表、循環(huán)鏈表和雙向鏈表)的構(gòu)造原理；
　　3．在以上兩種存儲結(jié)構(gòu)的基礎(chǔ)上對線性表實施的基本操作，包括順序表的插入與刪除、鏈表的建立、插入與刪除、檢索等操作對應(yīng)的算法設(shè)計(含遞歸算法的設(shè)計)。
　　三、堆棧與隊列
　　1．堆棧與隊列的基本概念與基本操作；
　　2．堆棧與隊列的順序存儲結(jié)構(gòu)與鏈?zhǔn)酱鎯�結(jié)構(gòu)的構(gòu)造原理；
　　3．在不同存儲結(jié)構(gòu)的基礎(chǔ)上對堆棧與隊列實施插入與刪除等基本操作的算法設(shè)計；
　　4．堆棧和隊列在解決實際問題中應(yīng)用。
　　四、樹與二叉樹
　　1．樹與二叉樹的基本概念，基本特征、名詞術(shù)語；
　　2．完全二叉樹與滿二叉樹的基本概念，二叉樹的基本性質(zhì)；
　　3．二叉樹與樹、樹林之間的轉(zhuǎn)換；
　　4．二叉樹的順序存儲結(jié)構(gòu)與二叉鏈表存儲結(jié)構(gòu)；
　　5．二叉樹的前序遍歷、中序遍歷、后序遍歷和按層次遍歷，以及在二叉鏈表基礎(chǔ)上各種遍歷算法(重點為非遞歸算法)的設(shè)計與應(yīng)用；
　　6．線索二叉樹的基本概念與構(gòu)造；
　　7．二叉排序樹的基本概念、建立(插入)、查找與平均查找長度ASL的計算；
　　8．哈夫曼(Huffman)樹的基本概念，哈夫曼樹的構(gòu)造與帶權(quán)路徑長度(WPL)的計算。
　　五、圖
　　1．圖的基本概念、名詞術(shù)語；
　　2．圖的鄰接矩陣存儲方法和鄰接表存儲方法的基本構(gòu)造原理及特點；
　　3．圖的深度優(yōu)先搜索與廣度優(yōu)先搜索；
　　4．最小(代價)生成樹、最短路徑、AOV網(wǎng)與拓?fù)渑判蛞约癆OE網(wǎng)與關(guān)鍵路徑的基本概念與求解過程。
　　六、文件及查找
　　1．順序查找法、折半查找法以及查找過程對應(yīng)的“判定樹”的構(gòu)造；
　　2．B-樹和B+樹的基本概念，B-樹的插入與查找；
　　3．散列(Hash)表的構(gòu)造、散列函數(shù)的構(gòu)造，散列沖突的基本概念與處理散列沖突的基本方法。
　　七、內(nèi)排序
　　1．排序的基本概念，包括各種內(nèi)排序方法的排序原理及特點，在排序過程中進(jìn)行的元素之間比較次數(shù)，排序的總趟數(shù)、穩(wěn)定性問題及時間與空間復(fù)雜度計算；
　　2．插入排序法(含折半插入排序法)；
　　3．選擇排序法；
　　4．(起)泡排序法；
　　5．謝爾(shell)排序法；
　　6．快速排序法；
　　7．堆(積)排序法，包括堆積的定義與構(gòu)造；
　　8．二路歸并排序法。

　《C語言程序設(shè)計》部分
　　指定參考書：《C程序設(shè)計 第三版》 譚浩強著，清華大學(xué)出版社 2005
　　一、C語言基本知識
　　1．C語言的特點以及C語言程序的組成；
　　2．?dāng)?shù)據(jù)類型，包括整型、實型、字符型等常量與變量和變量的賦值；用typedef定義類型；
　　3．各種類型數(shù)據(jù)之間的混合運算；
　　4．各類運算符(包括自增、自減運算符)的運算規(guī)則與優(yōu)先級，條件運算符；
　　5．算術(shù)表達(dá)式、關(guān)系表達(dá)式和邏輯表達(dá)式，逗號運算符和逗號表達(dá)式，表達(dá)式sizeof的含義。
　　二、語句
　　1．賦值語句(含條件賦值語句)、條件語句(含if、if-else、switch)、循環(huán)語句(含while、do-while、for語句，包括循環(huán)嵌套和break語句與continue語句)；
　　2．輸入/輸出語句，包括整型、實型、字符型(含字符串)等類型數(shù)據(jù)的格式輸入函數(shù)scanf和格式輸出函數(shù)printf。
　　三、數(shù)組
　　1．一維數(shù)組和二維數(shù)組的定義、引用與初始化；
　　2．字符數(shù)組的定義、引用與初始化，字符數(shù)組的輸入與輸出，字符串和字符串處理函數(shù)。
　　四、函數(shù)
　　1．函數(shù)的定義，函數(shù)參數(shù)(形參和實參)與函數(shù)的返回值；
　　2．函數(shù)的調(diào)用，包括函數(shù)的嵌套調(diào)用和遞歸函數(shù)的調(diào)用；
　　3．命令行參數(shù)的基本概念，帶參數(shù)的主函數(shù)的概念和應(yīng)用。
　　五、宏定義
　　帶參數(shù)的宏定義；
　　包含文件的處理。
　　六、指針
　　1．指針的基本概念，變量的指針與指向變量的指針變量，包括定義、引用以及指針變量作為函數(shù)參數(shù)；
　　2．?dāng)?shù)組與指針，包括指向數(shù)組的指針變量的定義與賦值、通過指針引用數(shù)組元素、數(shù)組名作為函數(shù)參數(shù)；
　　3．字符串與指針，指向字符串的指針變量。
　　七、結(jié)構(gòu)體
　　1．結(jié)構(gòu)體的基本概念和特點，結(jié)構(gòu)體變量的初始化與引用；
　　2．結(jié)構(gòu)體數(shù)組。
　　八、文件
　　1．C文件的基本概念，文本文件的類型指針FILE與文本文件的使用方式；
　　2．文本文件的打開(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。