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

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

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

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

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

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