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

1、編程技術(shù)精品！ 991 數(shù)據(jù)結(jié)構(gòu)與 C 語言程序設(shè)計(jì)考試大綱（2013 版）2013 年數(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)教程（第二版）唐發(fā)根編著北京航空航天大學(xué)出版社一、概述 1 數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)的基本概念；2 算法的定義、基本性質(zhì)以及算法分析的基本概念，包括采用大？形式表示時間復(fù)雜度和空間復(fù)雜度。二、 線性表 1 線性關(guān)系、線性表的定義，線性表的基本操作；2 線性表的順序存儲結(jié)構(gòu)與鏈?zhǔn)酱鎯Y(jié)構(gòu)（包括單（向鏈表、循環(huán)鏈表和雙向鏈表的構(gòu)造原理；3.在以上兩種存儲結(jié)

2、構(gòu)的基礎(chǔ)上對線性表實(shí)施的基本操作，包括順序表的插入與刪除、鏈 表的建立、插入與刪除、查找等操作對應(yīng)的算法設(shè)計(jì)（含遞歸算法的設(shè)計(jì)。三、堆 棧與隊(duì)列 1.堆棧與隊(duì)列的基本概念與基本操作；2.堆棧與隊(duì)列的順序存儲結(jié)構(gòu)與鏈?zhǔn)酱鎯Y(jié)構(gòu)的構(gòu)造原理；3 .在不同存儲結(jié)構(gòu)的基礎(chǔ)上對堆棧與隊(duì)列實(shí)施插入 與刪除等基本操作的算法設(shè)計(jì)； 4.堆棧和隊(duì)列在解決實(shí)際問題中應(yīng)用。四、樹與二叉樹 1.樹與二叉樹的基本概念，基本特征、名詞術(shù)語；2.完全二叉樹與滿二叉樹的基本概念，二叉樹的基本性質(zhì)；3.二叉樹與樹、樹林之間的轉(zhuǎn)換；4.二叉樹的順序存儲結(jié)構(gòu)與二叉鏈表存儲結(jié)構(gòu)；5.二叉樹的前序遍歷、中序遍歷、后序遍歷和按層次遍歷，以

3、及在二叉鏈表基礎(chǔ)上各種遍歷算法（重點(diǎn)為非遞歸算法的 設(shè)計(jì)與應(yīng)用；6.二叉排序樹的基本概念、建立（插入、查找與平均查找長度 ASL 的計(jì)算；7.哈夫曼（Huffman 樹的基本概念，哈夫曼樹的構(gòu)造與帶權(quán)路徑長度 （WPL 的計(jì)算。五、圖 1.圖的基本概念、名詞術(shù)語；2.圖的鄰接矩陣存儲方法 和鄰接表（含逆鄰接表存儲方法的構(gòu)造原理及特點(diǎn)；3.圖的深度優(yōu)先搜索與廣度優(yōu)先搜索；4.最?。ù鷥r生成樹、最短路徑、AOV 網(wǎng)與拓?fù)渑判蛞约?AOE 網(wǎng)與關(guān) 鍵路徑的基本概念與求 解過程。六、文件及查找 1.順序查找法以及平均查找長 度（ASL 的計(jì)算；2.折半查找法以及平均查找長度（ASL 的計(jì)算，包括查找過

4、程對 應(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)定性以及時間復(fù)雜度與空間復(fù)雜度計(jì)算；2插入排序法（含折半插入排序法；3 選擇排序法；4.（起泡排序法；5 謝爾（Shell 排序法；6 快速排序法；7 堆積（Heap 排序法，包括堆積的定義與構(gòu)造；8 二路歸并排序法。C 語言程序設(shè)計(jì)部分 指定參考書：C 程序設(shè)計(jì)第三

5、版譚浩強(qiáng) 著，清華大學(xué)出版社 一、C 語言基本知識1. C 語言的特點(diǎn)以及 C 語言程序的組成；2 數(shù)據(jù)類型，包括整型、實(shí)型、字符型等常量與變量和變量的賦值；用 typedef 定義類型；3各種類型數(shù)據(jù)之間的混合運(yùn)算；4 各類運(yùn)算符（包括自增、自減運(yùn)算符的運(yùn)算規(guī)則與優(yōu)先級，條件運(yùn)算符；5 算術(shù)表達(dá)式、關(guān)系表達(dá)式和邏輯表達(dá)式，逗號運(yùn)算符和逗號表達(dá)式，表達(dá)式sizeof 的含義。二、語句 1.賦值語句（含條件賦值語句、條件語句（含 if、if-else、switch、循環(huán)語 句（含 while、do-while、for 語句，包括循環(huán)嵌套和 break 語句與 continue 語句；2.輸入/輸

6、出語句，包括整型、實(shí)型、字符型（含字符串等類型數(shù)據(jù)的格式輸入函 數(shù) scanf 和格式輸出函數(shù)printf。三、數(shù)組 1.一維數(shù)組和二維數(shù)組的定義、引用 與初始化；2.字符數(shù)組的定義、引用與初始化，字符數(shù)組的輸入與輸出，字符串 和字符串處理函數(shù)。 四、函數(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ù)的宏定義；2.包含文件的處理。六、 指針 1.指針的基本概念，變量的指針與指向變量的指 針變量，包括定義、引用以及指針變量作為函數(shù)參數(shù)；2.數(shù)組與指針，包括指向

7、 數(shù)組的指針變量的定義與賦值、通過指針引用數(shù)組元素、數(shù)組名作為函數(shù)參數(shù)；3.字符串與指針，指向字符串的指針變量。 七、結(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 函數(shù)和 fwrite 函數(shù)、fputc 函數(shù)和 fgetc