• 2025考研復(fù)試伴學(xué)班
• 2025考研復(fù)試標(biāo)準(zhǔn)班
• 2026考研英語全程班
• 26考研全科上岸規(guī)劃營「擇校▪規(guī)劃▪備考」
• 中國傳媒大學(xué)2025考研專業(yè)課復(fù)習(xí)資料「真題▪筆記▪講義▪題庫」

中國傳媒大學(xué)專業(yè)學(xué)位研究生入學(xué)考試《程序設(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è)計的基本方法，并具有綜合運用所學(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)用，共同體變量的定義和使用方法。

5、地址和指針的基本概念，如何使用指針來處理數(shù)組、字符串以及結(jié)構(gòu)體，函數(shù)指針的基本概念以及使用。

6、FILE的定義以及對文件進行的各種操作的庫函數(shù)。

(二) 線性表

1、 線性表的定義和基本操作

2、 線性表的實現(xiàn)

(1)順序存儲結(jié)構(gòu)：實現(xiàn)順序表的查找、插入、刪除、合并、分解等操作的程序設(shè)計。

(2)鏈?zhǔn)酱鎯�結(jié)構(gòu)：實現(xiàn)單鏈表、循環(huán)鏈表、雙向鏈表、雙向循環(huán)鏈表的生成、查找、插入、刪除、遍歷以及鏈表的分解和歸并等操作的程序設(shè)計。

3、線性表的應(yīng)用：從時間復(fù)雜度和空間復(fù)雜度的角度綜合比較線性表在順序和鏈?zhǔn)絻煞N存儲結(jié)構(gòu)下的特點，即其各自適用的場合。運用順序表和鏈表的特點解決復(fù)雜的應(yīng)用問題。

(三)棧、隊列和數(shù)組

1、棧和隊列的基本概念

2、棧和隊列的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯�結(jié)構(gòu)及應(yīng)用

(1)棧與遞歸的關(guān)系。

用遞歸解決的幾類問題：問題的定義是遞歸的;數(shù)據(jù)結(jié)構(gòu)是遞歸的;以及問題的解法是遞歸的。

典型遞歸問題的算法以及如何將遞歸算法轉(zhuǎn)換為非遞歸算法。

(2)在程序設(shè)計中，常需要棧這樣的數(shù)據(jù)結(jié)構(gòu)，使得與保存數(shù)據(jù)時相反順序來使用這些數(shù)據(jù)。在后續(xù)章節(jié)中多處有棧和隊列的應(yīng)用，如二叉樹遍歷的遞歸和非遞歸算法、圖的深度優(yōu)先遍歷等都用到棧，而樹的層次遍歷、圖的廣度優(yōu)先遍歷等則用到隊列。

3、特殊矩陣的壓縮存儲：對稱矩陣、對角矩陣、三角矩陣在壓縮存儲時的下標(biāo)變換公式。

(四)樹與二叉樹

1、二叉樹

(1)二叉樹的定義及其主要特征：二叉樹的五個性質(zhì)及證明方法，并把這種方法推廣到K叉樹。

(2)二叉樹的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯�結(jié)構(gòu)：二叉樹的順序存儲結(jié)構(gòu)和二叉鏈表、三叉鏈表存儲結(jié)構(gòu)的各自優(yōu)缺點及適用場合。

(3)二叉樹的遍歷

二叉樹的先序，中序和后序遍歷算法以及按層次遍歷。遍歷是基礎(chǔ)，在基本遍歷算法的基礎(chǔ)上實現(xiàn)二叉樹的其它算法。

(4)線索二叉樹的基本概念和構(gòu)造

線索化算法，線索化后二叉樹的遍歷算法，基本線索二叉樹的其它算法問題(如：查找某一類線索二叉樹中指定結(jié)點的前驅(qū)或后繼結(jié)點)。

(5)二叉排序樹

二叉排序樹的建立、查找、插入和刪除算法，以及判斷某棵二叉樹是否二叉排序樹的算法。

2、樹、森林

(1)樹的概念和存儲結(jié)構(gòu)

(2)森林與二叉樹的轉(zhuǎn)換

(3)樹和森林的遍歷

樹與森林的遍歷，有兩種遍歷算法：先根與后根(對于森林而言稱作：先序與中序遍歷)。二者的先根與后根遍歷與二叉樹中的遍歷算法是有對應(yīng)關(guān)系的：先根遍歷對應(yīng)二叉樹的先序遍歷，而后根遍歷對應(yīng)二叉樹的中序遍歷。

(五)圖

1、圖的概念、存儲及基本操作

(1)鄰接矩陣法

(2)鄰接表法

2、圖的遍歷

深度優(yōu)先搜索和廣度優(yōu)先搜索是圖的兩種基本的遍歷算法以及基于這兩種基本的遍歷算法的程序設(shè)計。

3、圖的基本應(yīng)用及其復(fù)雜度分析

(1)最小(代價)生成樹

(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è)計、手工模擬排序過程、性能分析(包括時間復(fù)雜度、空間復(fù)雜度、穩(wěn)定性)。

10、內(nèi)部排序算法的應(yīng)用

(八)進程管理

1、進程概念、進程的狀態(tài)與轉(zhuǎn)換

2、進程同步

(1)進程同步的基本概念

(2)實現(xiàn)臨界區(qū)互斥的基本方法

(3)信號量：PV原語的含義

(4)經(jīng)典同步問題：生產(chǎn)者-消費者問題;讀者-寫者問題;哲學(xué)家進餐問題。

重點掌握 PV 操作的概念、流程，以及 PV 操作在同步與互斥問題中的應(yīng)用。

3、死鎖的概念及處理策略

三、考試的基本題型

本試卷滿分為150分。

主要題型有：選擇題、綜合應(yīng)用題、程序設(shè)計題等。

四、考試的形式及時間

筆試，不需要任何輔助工具�？荚嚂r間為三小時。