2019年中國傳媒大學827程序設計考研大綱

• 2025考研復試標準班
• 26考研全科上岸規劃營「擇校▪規劃▪備考」
• 中國傳媒大學2026考研專業課復習資料「真題▪筆記▪講義▪題庫」

中國傳媒大學專業學位研究生入學考試《程序設計》考試大綱

一、考試的總體要求

《程序設計》是計算機科學與技術及相關學科的重要基礎，主要考核內容包括基于數據結構的程序設計和基于操作系統的程序設計兩大部分。要求考生對計算機科學與技術學科的基本知識、基本理論、基本方法有較深入、系統的理解，掌握各種數據結構的定義和實現算法，掌握操作系統所涉及的關鍵內容，對C語言的基本知識有較深入的了解，掌握程序設計的基本方法，并具有綜合運用所學知識分析問題和解決問題的能力。

二、考試的內容

(一) 程序設計基礎

1、C語言的基本數據類型、各種運算符和表達式、基本控制結構。

2、數組的定義、數組元素的引用、數組的初始化，掌握與字符串相關的庫函數。

3、函數的定義語法，函數調用中參數的傳遞機制;局部變量和全局變量的有效范圍。

4、結構體類型變量的定義、結構體變量的引用、結構體變量的初始化方法，結構體數組的定義、初始化和結構體數組的應用，共同體變量的定義和使用方法。

5、地址和指針的基本概念，如何使用指針來處理數組、字符串以及結構體，函數指針的基本概念以及使用。

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

(二) 線性表

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

2、 線性表的實現

(1)順序存儲結構：實現順序表的查找、插入、刪除、合并、分解等操作的程序設計。

(2)鏈式存儲結構：實現單鏈表、循環鏈表、雙向鏈表、雙向循環鏈表的生成、查找、插入、刪除、遍歷以及鏈表的分解和歸并等操作的程序設計。

3、線性表的應用：從時間復雜度和空間復雜度的角度綜合比較線性表在順序和鏈式兩種存儲結構下的特點，即其各自適用的場合。運用順序表和鏈表的特點解決復雜的應用問題。

(三)棧、隊列和數組

1、棧和隊列的基本概念

2、棧和隊列的順序存儲結構和鏈式存儲結構及應用

(1)棧與遞歸的關系。

用遞歸解決的幾類問題：問題的定義是遞歸的;數據結構是遞歸的;以及問題的解法是遞歸的。

典型遞歸問題的算法以及如何將遞歸算法轉換為非遞歸算法。

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

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

(四)樹與二叉樹

1、二叉樹

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

(2)二叉樹的順序存儲結構和鏈式存儲結構：二叉樹的順序存儲結構和二叉鏈表、三叉鏈表存儲結構的各自優缺點及適用場合。

(3)二叉樹的遍歷

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

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

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

(5)二叉排序樹

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

2、樹、森林

(1)樹的概念和存儲結構

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

(3)樹和森林的遍歷

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

(五)圖

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

(1)鄰接矩陣法

(2)鄰接表法

2、圖的遍歷

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

3、圖的基本應用及其復雜度分析

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

(2)最短路徑

(3)拓撲排序

(4)關鍵路徑

(六)查找

1、查找的基本概念

2、順序查找法、折半查找法

3、散列(Hash)表及其查找

4、查找算法的分析及應用

(七)內部排序

1、 排序的基本概念

2、插入排序

3、冒泡排序

4、簡單選擇排序

5、希爾排序

6、快速排序

7、堆排序

8、二路歸并排序

9、各種內部排序算法的比較

各種排序方法的算法思想及程序設計、手工模擬排序過程、性能分析(包括時間復雜度、空間復雜度、穩定性)。

10、內部排序算法的應用

(八)進程管理

1、進程概念、進程的狀態與轉換

2、進程同步

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

(2)實現臨界區互斥的基本方法

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

(4)經典同步問題：生產者-消費者問題;讀者-寫者問題;哲學家進餐問題。

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

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

三、考試的基本題型

本試卷滿分為150分。

主要題型有：選擇題、綜合應用題、程序設計題等。

四、考試的形式及時間

筆試，不需要任何輔助工具。考試時間為三小時。