貴州大學(xué)碩士研究生入學(xué)考試大綱考試科目代碼及名稱：831程序設(shè)計與數(shù)據(jù)結(jié)構(gòu)一、考試基本要求本科目考試著重考核考生掌握程序設(shè)計與數(shù)據(jù)結(jié)構(gòu)基本概念、基本思想、基本分析方法和基本理論的程度，要求考生對程序設(shè)計與數(shù)據(jù)結(jié)構(gòu)理論體系的基本框架有一個比較全面的了解，并能綜合運(yùn)用所學(xué)的程序設(shè)計和數(shù)據(jù)結(jié)構(gòu)的基本知識分析現(xiàn)實問題，并進(jìn)行問題抽象、算法提煉和編程實現(xiàn)。二、適用范圍適用于計算機(jī)科學(xué)與技術(shù)專業(yè)(學(xué)術(shù)型研究生)適用于計算機(jī)技術(shù)、軟件工程專業(yè)(專業(yè)型研究生)三、考試形式閉卷，180分鐘四、考試內(nèi)容和考試要求(一)程序設(shè)計部分程序設(shè)計基本知識考試內(nèi)容：c語言的基本知識、c語言的符號體系、簡單程序的設(shè)計；考試要求：理解C語言程序的基本構(gòu)成，變量的定義與變量名的基本規(guī)則；領(lǐng)會類型修飾的使用和功能，整型與字符型數(shù)據(jù)的混合運(yùn)算；掌握算術(shù)表達(dá)式、賦值表達(dá)式與逗號表達(dá)式；數(shù)據(jù)的輸入與輸出、以及輸入與輸出的基本要求。選擇結(jié)構(gòu)程序設(shè)計考試內(nèi)容：條件選擇語句if和switch的語法及其應(yīng)用；考試要求：領(lǐng)會if語句與條件表達(dá)式的區(qū)別、switch語句的執(zhí)行流程。掌握if語句與switch語句在程序中的使用。循環(huán)結(jié)構(gòu)程序設(shè)計考試內(nèi)容：for、while、do-while三種循環(huán)控制語句的語法特點(diǎn)和應(yīng)用；考試要求：理解for、while、do-while語句的執(zhí)行流程及其循環(huán)條件表達(dá)式的作用和以及區(qū)別；掌握break與continue語句的區(qū)別與應(yīng)用；能熟練地用三種循環(huán)語句進(jìn)行循環(huán)程序設(shè)計。函數(shù)考試內(nèi)容：C或C++中函數(shù)的定義和使用；考試要求：理解全局變量與局部變量、變量的生存期與作用域、變量的動態(tài)與靜態(tài)存儲方式等的區(qū)別；了解在多個程序文件中函數(shù)與函數(shù)的關(guān)系；熟練掌握在程序設(shè)計中正確使用函數(shù)；對于已知的遞歸算法，能寫出相應(yīng)的遞歸程序。數(shù)組考試內(nèi)容：—維和二維數(shù)組的定義及其應(yīng)用；考試要求：理解一維數(shù)組與二維數(shù)組的地址結(jié)構(gòu)、字符串的結(jié)束標(biāo)志；掌握常用的幾個字符串函數(shù)；掌握在程序設(shè)計中應(yīng)用一維數(shù)組、二維數(shù)組、字符串；掌握對數(shù)組進(jìn)行簡單排序和查找的方法；掌握數(shù)組做函數(shù)參數(shù)的程序設(shè)計。指針考試內(nèi)容：C或C++中指針的概念、定義、運(yùn)算和應(yīng)用；考試要求：理解一維數(shù)組與二維數(shù)組的地址結(jié)構(gòu)；理解返回指針的函數(shù)與函數(shù)指針的區(qū)別；理解指針數(shù)組、數(shù)組指針、指向指針的指針之間的關(guān)系與區(qū)別；理解指針運(yùn)算的用途和意義；掌握在程序中利用指針操作數(shù)組元素、字符串，以及用指針作函數(shù)參數(shù)；掌握在程序中應(yīng)用指針數(shù)組。7?結(jié)構(gòu)體、共用體和枚舉類型考試內(nèi)容：結(jié)構(gòu)體、共用體、枚舉等自定義數(shù)據(jù)類型的定義和運(yùn)用；考試要求：理解結(jié)構(gòu)體與共用體的區(qū)別；掌握結(jié)構(gòu)體、共用體、枚舉類型數(shù)據(jù)的應(yīng)用，會用typedef定義結(jié)構(gòu)體、共用體等數(shù)據(jù)類型別名。8?文件考試內(nèi)容：文件的打開和讀取；考試要求：理解文件指針的概念和定義；掌握文件的打開方法、文件打開函數(shù)返回值的處理；掌握在程序中讀寫外部的文本文件或者二進(jìn)制文件的方法。(二)數(shù)據(jù)結(jié)構(gòu)部分基本概念考試內(nèi)容：數(shù)據(jù)結(jié)構(gòu)的基本概念；漸進(jìn)算法分析方法。考試要求：（1）掌握數(shù)據(jù)結(jié)構(gòu)的概念，包括數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、算法的概念,以及它們之間的關(guān)系。（2）掌握漸進(jìn)算法分析方法，能夠估算算法的時空復(fù)雜度線性表和字符串考試內(nèi)容：線性表的特點(diǎn)，線性表的順序?qū)崿F(xiàn)和鏈?zhǔn)綄崿F(xiàn)，線性表的應(yīng)用；字符串的基本運(yùn)算，字符串匹配算法?？荚囈螅海?）理解線性表的結(jié)構(gòu)和特點(diǎn)，掌握線性表上基本操作的實現(xiàn)算法。（2）掌握順序存儲線性表的方法以及基本操作的實現(xiàn)算法。（3）掌握鏈接存儲線性表的方法，并掌握單鏈表和循環(huán)鏈表的結(jié)構(gòu)，以及基本操作的實現(xiàn)算法。（4）理解字符串的存儲結(jié)構(gòu)，字符串的基本運(yùn)算。（5）掌握字符串簡單的匹配算法。棧和隊列考試內(nèi)容：棧和隊列的基本運(yùn)算及其應(yīng)用?？荚囈螅海?）理解棧的定義和結(jié)構(gòu)特點(diǎn)，掌握其存儲方式（順序存儲和鏈接存儲）和基本操作的實現(xiàn)算法。（2）理解隊列的結(jié)構(gòu)和特點(diǎn)，掌握其存儲方式（順序存儲和鏈接存儲）和基本操作的實現(xiàn)算法。遞歸考試內(nèi)容：遞歸的基本概念，遞歸的簡單應(yīng)用。考試要求：（1）理解遞歸的基本概念和實現(xiàn)原理，掌握用遞歸思想描述問題和構(gòu)造算法的方法。（2）掌握求階乘、漢諾塔等問題的遞歸解法。（3）了解用棧將遞歸改為非遞歸的方法。樹和二叉樹考試內(nèi)容：樹和二叉樹考試要求：（1）理解樹的結(jié)構(gòu)和定義，掌握樹的主要概念。（2）理解各種二叉樹的結(jié)構(gòu)，掌握其特點(diǎn)。（3）掌握二叉樹的三種遍歷方法的實現(xiàn)原理和性質(zhì)，能將二叉樹的遍歷方法應(yīng)用于求解二叉樹的葉子結(jié)點(diǎn)個數(shù)。二叉樹計數(shù)等問題，掌握遍歷的非遞歸實現(xiàn)方法。（4）理解樹的存儲結(jié)構(gòu)，掌握樹的遍歷等方法的實現(xiàn)。（5）理解霍夫曼編碼的基本原理和使用。集合和搜索考試內(nèi)容：集合、二叉搜索樹和AVL樹考試要求：（1）理解集合的基本概念，掌握常用實現(xiàn)集合的各種存儲方法。（2）掌握無序線性表的順序搜索、有序線性表的二分搜索。（3）理解二叉搜索樹的定義和特點(diǎn)，掌握二叉搜索樹插入和刪除的算法。（4）理解AVL樹的定義和特點(diǎn)，掌握AVL樹上插入新結(jié)點(diǎn)的方法。圖考試內(nèi)容：圖的存儲，圖的遍歷，最小生成樹，最短路徑和活動網(wǎng)絡(luò)。考試要求：（1）掌握圖的基本概念、圖的鄰接矩陣存儲方式和鄰接表存儲方式。（2）掌握圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷方法。（3）掌握Kluskal和Prim生成最小生成樹的方法。（4）掌握Dijkstra求單源最短路徑的方法。（5）掌握AOV活動網(wǎng)絡(luò)的拓?fù)渑判蚍椒?，AOE活動網(wǎng)絡(luò)的關(guān)鍵路徑的方法。排序考試內(nèi)容：插入排序、交換排序、選擇排序、歸并排序和基數(shù)排序。考試要求：理解各種排序方法的實現(xiàn)，掌握各種排序算法的特點(diǎn)和時間復(fù)雜度，能按指定的排序方法實現(xiàn)對數(shù)表做排序。索