中國傳媒大學(xué)專業(yè)學(xué)位研究生入學(xué)考試

1、1中國傳媒大學(xué)專業(yè)學(xué)位研究生入學(xué)考試中國傳媒大學(xué)專業(yè)學(xué)位研究生入學(xué)考試《程序設(shè)計程序設(shè)計》考試大綱考試大綱一、考試的總體要求《程序設(shè)計》是計算機科學(xué)與技術(shù)及相關(guān)學(xué)科的重要基礎(chǔ)，主要考核內(nèi)容包括基于數(shù)據(jù)結(jié)構(gòu)的程序設(shè)計和基于操作系統(tǒng)的程序設(shè)計兩大部分。要求考生對計算機科學(xué)與技術(shù)學(xué)科的基本知識、基本理論、基本方法有較深入、系統(tǒng)的理解，掌握各種數(shù)據(jù)結(jié)構(gòu)的定義和實現(xiàn)算法，掌握操作系統(tǒng)所涉及的關(guān)鍵內(nèi)容，對C語言的基本知識有較深入的了解，掌握程序設(shè)計

2、的基本方法，并具有綜合運用所學(xué)知識分析問題和解決問題的能力。二、考試的內(nèi)容（一）程序設(shè)計基礎(chǔ)1、C語言的基本數(shù)據(jù)類型、各種運算符和表達式、基本控制結(jié)構(gòu)。2、數(shù)組的定義、數(shù)組元素的引用、數(shù)組的初始化，掌握與字符串相關(guān)的庫函數(shù)。3、函數(shù)的定義語法，函數(shù)調(diào)用中參數(shù)的傳遞機制；局部變量和全局變量的有效范圍。4、結(jié)構(gòu)體類型變量的定義、結(jié)構(gòu)體變量的引用、結(jié)構(gòu)體變量的初始化方法，結(jié)構(gòu)體數(shù)組的定義、初始化和結(jié)構(gòu)體數(shù)組的應(yīng)用，共同體變量的定義和使用方法。

3、5、地址和指針的基本概念，如何使用指針來處理數(shù)組、字符串以及結(jié)構(gòu)體，函數(shù)指針的基本概念以及使用。6、FILE的定義以及對文件進行的各種操作的庫函數(shù)。（二）線性表1、線性表的定義和基本操作2、線性表的實現(xiàn)（1）順序存儲結(jié)構(gòu)：實現(xiàn)順序表的查找、插入、刪除、合并、分解等操作的程序設(shè)計。（2）鏈?zhǔn)酱鎯Y(jié)構(gòu)：實現(xiàn)單鏈表、循環(huán)鏈表、雙向鏈表、雙向循環(huán)鏈表的生成、查找、插入、刪除、遍歷以及鏈表的分解和歸并等操作的程序設(shè)計。3、線性表的應(yīng)用：從時間復(fù)雜

4、度和空間復(fù)雜度的角度綜合比較線性表在順序和鏈?zhǔn)絻煞N存儲結(jié)構(gòu)下的特點，即其各自適用的場合。運用順序表和鏈表的特點解決復(fù)雜的3樹與森林的遍歷，有兩種遍歷算法：先根與后根（對于森林而言稱作：先序與中序遍歷）。二者的先根與后根遍歷與二叉樹中的遍歷算法是有對應(yīng)關(guān)系的：先根遍歷對應(yīng)二叉樹的先序遍歷，而后根遍歷對應(yīng)二叉樹的中序遍歷。（五）圖1、圖的概念、存儲及基本操作（1）鄰接矩陣法（2）鄰接表法2、圖的遍歷深度優(yōu)先搜索和廣度優(yōu)先搜索是圖的兩種基本的

5、遍歷算法以及基于這兩種基本的遍歷算法的程序設(shè)計。3、圖的基本應(yīng)用及其復(fù)雜度分析（1）最?。ù鷥r）生成樹（2）最短路徑（3）拓撲排序（4）關(guān)鍵路徑（六）查找1、查找的基本概念2、順序查找法、折半查找法3、散列（Hash）表及其查找4、查找算法的分析及應(yīng)用（七）內(nèi)部排序1、排序的基本概念2、插入排序3、冒泡排序4、簡單選擇排序5、希爾排序6、快速排序7、堆排序8、二路歸并排序9、各種內(nèi)部排序算法的比較各種排序方法的算法思想及程序設(shè)計、手工模