貴州師范大學(xué)2013年碩士研究生入學(xué)考試大綱 （復(fù) 試）

(科目：050程序設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu))

程序設(shè)計(jì)

【考查目標(biāo)】

1、掌握結(jié)構(gòu)化程序設(shè)計(jì)的基本方法，了解面向?qū)ο蟪绦蛟O(shè)計(jì)的基本思路，對兩種方法編寫的程序有讀、改、寫的能力，能實(shí)現(xiàn)計(jì)算機(jī)常用算法的編制。

2、對計(jì)算機(jī)語言有較好的了解，能識別程序語言中的語法錯(cuò)誤，能用像C++等語言編程。

一、語言基本知識

1、像程序設(shè)計(jì)語言C/C++的發(fā)展，程序設(shè)計(jì)語言詞、句子的組成，數(shù)據(jù)類型與表達(dá)式等概念

2、程序設(shè)計(jì)的上機(jī)過程，運(yùn)行調(diào)試中常見錯(cuò)誤的鑒別

3、了解常用的程序風(fēng)格和規(guī)范

二、面向過程程序設(shè)計(jì)方法

1、程序的基本組成，算法的概念和表示

2、順序結(jié)構(gòu)、選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)語句的語法規(guī)定，及運(yùn)用三種結(jié)構(gòu)編寫程序

3、掌握函數(shù)組裝程序的意義，對庫函數(shù)、自定義函數(shù)、局部變量和全程變量有正確的知識，并能用函數(shù)進(jìn)行程序設(shè)計(jì)，了解遞歸函數(shù)

4、對批量數(shù)據(jù)的處理，能正確運(yùn)用數(shù)組或結(jié)構(gòu)體進(jìn)行程序設(shè)計(jì)，能熟練處理字符數(shù)據(jù)

5、了解指針、文件和異常處理

三、面向?qū)ο蟪绦蛟O(shè)計(jì)方法

1、面向?qū)ο蟪绦蛟O(shè)計(jì)的基本思想，能看懂面向過程程序設(shè)計(jì)和面向?qū)ο蟪绦蛟O(shè)計(jì)方法的程序，面向?qū)ο蟪绦蛟O(shè)計(jì)方法的特點(diǎn)

2、了解類與對象、封裝、重載、繼承的概念

數(shù)據(jù)結(jié)構(gòu)

一、考試科目：

數(shù)據(jù)結(jié)構(gòu)

二、適用專業(yè)：

計(jì)算機(jī)應(yīng)用技術(shù)

三、考試性質(zhì)：

《數(shù)據(jù)結(jié)構(gòu)》是計(jì)算機(jī)各專業(yè)的核心基礎(chǔ)課程。在研究生復(fù)試時(shí)通過對該課程的考核，以檢驗(yàn)考生在本科階段對該課程的掌握情況，確保被錄取者具有基本的專業(yè)理論基礎(chǔ)及程序設(shè)計(jì)能力，能順利完成研究生階段的學(xué)業(yè)。

四、考試的基本要求：

系統(tǒng)地理解數(shù)據(jù)結(jié)構(gòu)的基本概念和基本理論，具備綜合應(yīng)用相關(guān)知識分析問題和解決問題的能力。具體要求如下：

1．各種基本類型的數(shù)據(jù)結(jié)構(gòu)的概念、特征、操作、存儲表示和基本應(yīng)用；

2．各種基本查找表的概念、特征及其查找方法

3．基本的排序方法；

4．基本算法性能的分析與評價(jià)；

5．使用C（或C++）語言的風(fēng)格描述算法和進(jìn)行程序設(shè)計(jì)。

五、考試內(nèi)容與具體要求：

1．算法與數(shù)據(jù)結(jié)構(gòu)

了解數(shù)據(jù)結(jié)構(gòu)、抽象數(shù)據(jù)類型的基本概念，熟悉掌握數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)，掌握算法定義、算法的基本特性、算法分析的基本概念和方法。

2．線性表

線性表的定義、邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、基本操作、基本算法性能的分析。

3．棧

棧的定義、特性、存儲結(jié)構(gòu)、基本操作、基本算法性能的分析，棧與遞歸算法及其基本應(yīng)用。

4．隊(duì)列

隊(duì)列的定義、特性、存儲結(jié)構(gòu)、基本操作、基本算法性能的分析以及基本應(yīng)用。

5．串

串的定義、基本概念、存儲結(jié)構(gòu)與基本操作；串的模式匹配算法；

6．?dāng)?shù)組與廣義表

(1)數(shù)組的定義、存儲結(jié)構(gòu)與基本操作；特殊矩陣和稀疏矩陣的壓縮存儲；

(2)廣義表的基本性質(zhì)，求廣義表的長度、表頭與表尾。

7．樹和二叉樹

(1)樹的基本概念和基本操作；

(2)二叉樹的基本概念、性質(zhì)及存儲結(jié)構(gòu)；二叉樹的先序、中序及后序遍歷的算法；

(3)樹與二叉樹之間的轉(zhuǎn)換、森林與二叉樹之間的轉(zhuǎn)換；

(4) 哈夫曼樹(Huffman)的概念，哈夫曼編碼的構(gòu)造及帶權(quán)路徑長度的計(jì)算。

8．圖

(1)圖的基本概念和基本操作；

(2)圖的存儲結(jié)構(gòu)：鄰接矩陣、鄰接表與逆鄰接表表示法；

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

(4)生成樹、最小生成樹的概念；克魯斯卡爾(Kruskal)算法,普里姆(Prim)算法。

9．查找

(1)查找的概念，關(guān)鍵字比較次數(shù)與平均查找長度；

(2)順序查找、折半查找、分塊查找、索引順序表的查找算法；

(3)二叉排序樹與平衡二叉樹，B-樹與B+樹；

(4)哈希(Hash)表的概念，哈希函數(shù)的基本構(gòu)造方法與解決沖突的基本方法，哈希表的建立和查找。

(5)各種查找算法的性能分析及其應(yīng)用。

10．內(nèi)部排序

(1)排序的概念及其排序的穩(wěn)定性；關(guān)鍵字比較次數(shù)與記錄移動次數(shù)；

(2)交換類排序：冒泡排序與快速排序；

(3)插入類排序：直接插入排序、折半插入排序、2-路插入排序、希爾排序。

(4)選擇類排序:直接選擇排序、錦標(biāo)賽排序、堆排序。

(5歸并排序。

(6)基數(shù)排序。

(7)種排序算法的評價(jià)（穩(wěn)定性、時(shí)間復(fù)雜度、空間復(fù)雜性度）及其應(yīng)用。

六、考試形式與試卷結(jié)構(gòu)：

1．考試方式：閉卷，筆試。

2．考試時(shí)間：60分鐘；

3．考查內(nèi)容及分值比例：

(1) 基本概念、基本知識、基本方法約占50%；

(2) 綜合應(yīng)用、算法和程序設(shè)計(jì)與算法分析約占50%。

4．試卷題型結(jié)構(gòu)：

試卷共計(jì)50分，基本題型如下：

(1)單項(xiàng)選擇題：10分，占20%；

(2)填空題（含程序填空題）：10分，占20%

(3)綜合應(yīng)用題（包括簡答題、解答題、分析算法與程序的功能）：20分，占40%；

(4)算法與程序設(shè)計(jì)：10分，占20%

七、參考書：

嚴(yán)蔚敏，吳偉民．《數(shù)據(jù)結(jié)構(gòu)》(C語言版) ．清華大學(xué)出版社．1997年版

更多學(xué)歷考試信息請查看學(xué)歷考試網(wǎng)