貴州師范大學2013年碩士研究生入學考試大綱 （復 試）

(科目：050程序設計與數(shù)據(jù)結構)

程序設計

【考查目標】

1、掌握結構化程序設計的基本方法，了解面向對象程序設計的基本思路，對兩種方法編寫的程序有讀、改、寫的能力，能實現(xiàn)計算機常用算法的編制。

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

一、語言基本知識

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

2、程序設計的上機過程，運行調(diào)試中常見錯誤的鑒別

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

二、面向過程程序設計方法

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

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

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

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

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

三、面向對象程序設計方法

1、面向對象程序設計的基本思想，能看懂面向過程程序設計和面向對象程序設計方法的程序，面向對象程序設計方法的特點

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

數(shù)據(jù)結構

一、考試科目：

數(shù)據(jù)結構

二、適用專業(yè)：

計算機應用技術

三、考試性質：

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

四、考試的基本要求：

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

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

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

3．基本的排序方法；

4．基本算法性能的分析與評價；

5．使用C（或C++）語言的風格描述算法和進行程序設計。

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

1．算法與數(shù)據(jù)結構

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

2．線性表

線性表的定義、邏輯結構、存儲結構、基本操作、基本算法性能的分析。

3．棧

棧的定義、特性、存儲結構、基本操作、基本算法性能的分析，棧與遞歸算法及其基本應用。

4．隊列

隊列的定義、特性、存儲結構、基本操作、基本算法性能的分析以及基本應用。

5．串

串的定義、基本概念、存儲結構與基本操作；串的模式匹配算法；

6．數(shù)組與廣義表

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

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

7．樹和二叉樹

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

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

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

(4) 哈夫曼樹(Huffman)的概念，哈夫曼編碼的構造及帶權路徑長度的計算。

8．圖

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

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

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

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

9．查找

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

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

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

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

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

10．內(nèi)部排序

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

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

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

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

(5歸并排序。

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

(7)種排序算法的評價（穩(wěn)定性、時間復雜度、空間復雜性度）及其應用。

六、考試形式與試卷結構：

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

2．考試時間：60分鐘；

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

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

(2) 綜合應用、算法和程序設計與算法分析約占50%。

4．試卷題型結構：

試卷共計50分，基本題型如下：

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

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

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

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

七、參考書：

嚴蔚敏，吳偉民．《數(shù)據(jù)結構》(C語言版) ．清華大學出版社．1997年版

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