貴州師范大學(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ì)兩種方法編寫的程序有讀、改、寫的能力，能實(shí)現(xiàn)計(jì)算機(jī)常用算法的編制。
2、對(duì)計(jì)算機(jī)語言有較好的了解，能識(shí)別程序語言中的語法錯(cuò)誤，能用像C++等語言編程。
一、語言基本知識(shí)
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ù)組裝程序的意義，對(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ì)的基本思想，能看懂面向過程程序設(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í)通過對(duì)該課程的考核，以檢驗(yàn)考生在本科階段對(duì)該課程的掌握情況，確保被錄取者具有基本的專業(yè)理論基礎(chǔ)及程序設(shè)計(jì)能力，能順利完成研究生階段的學(xué)業(yè)。
四、考試的基本要求：
系統(tǒng)地理解數(shù)據(jù)結(jié)構(gòu)的基本概念和基本理論，具備綜合應(yīng)用相關(guān)知識(shí)分析問題和解決問題的能力。具體要求如下：
1．各種基本類型的數(shù)據(jù)結(jié)構(gòu)的概念、特征、操作、存儲(chǔ)表示和基本應(yīng)用；
2．各種基本查找表的概念、特征及其查找方法
3．基本的排序方法；
4．基本算法性能的分析與評(píng)價(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)與存儲(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．樹和二叉樹
(1)樹的基本概念和基本操作；
(2)二叉樹的基本概念、性質(zhì)及存儲(chǔ)結(jié)構(gòu)；二叉樹的先序、中序及后序遍歷的算法；
(3)樹與二叉樹之間的轉(zhuǎn)換、森林與二叉樹之間的轉(zhuǎn)換；
(4) 哈夫曼樹(Huffman)的概念，哈夫曼編碼的構(gòu)造及帶權(quán)路徑長(zhǎng)度的計(jì)算。
8．圖
(1)圖的基本概念和基本操作；
(2)圖的存儲(chǔ)結(jié)構(gòu)：鄰接矩陣、鄰接表與逆鄰接表表示法；
(3)圖深度優(yōu)先搜索遍歷與廣度優(yōu)先搜索遍歷；
(4)生成樹、最小生成樹的概念；克魯斯卡爾(Kruskal)算法,普里姆(Prim)算法。
9．查找
(1)查找的概念，關(guān)鍵字比較次數(shù)與平均查找長(zhǎng)度；
(2)順序查找、折半查找、分塊查找、索引順序表的查找算法；
(3)二叉排序樹與平衡二叉樹，B-樹與B+樹；
(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%
七、參考書：
嚴(yán)蔚敏，吳偉民．《數(shù)據(jù)結(jié)構(gòu)》(C語言版) ．清華大學(xué)出版社．1997年版
更多學(xué)歷考試信息請(qǐng)查看學(xué)歷考試網(wǎng)