貴州師范大學(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ì)的基本思路，對(duì)兩種方法編寫(xiě)的程序有讀、改、寫(xiě)的能力，能實(shí)現(xiàn)計(jì)算機(jī)常用算法的編制。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

數(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í)通過(guò)對(duì)該課程的考核，以檢驗(yàn)考生在本科階段對(duì)該課程的掌握情況，確保被錄取者具有基本的專業(yè)理論基礎(chǔ)及程序設(shè)計(jì)能力，能順利完成研究生階段的學(xué)業(yè)。

四、考試的基本要求：

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

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

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

3．基本的排序方法；

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

5．使用C（或C++）語(yǔ)言的風(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)與存儲(chǔ)結(jié)構(gòu)，掌握算法定義、算法的基本特性、算法分析的基本概念和方法。

2．線性表

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

3．棧

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

4．隊(duì)列

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

5．串

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

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

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

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

7．樹(shù)和二叉樹(shù)

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

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

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

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

8．圖

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

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

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

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

9．查找

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

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

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

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

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

10．內(nèi)部排序

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

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

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

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

(5歸并排序。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

七、參考書(shū)：

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

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