程序設(shè)計考試大綱(共4頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上中國傳媒大學專業(yè)學位研究生入學考試程序設(shè)計考試大綱一、考試的總體要求程序設(shè)計是計算機科學與技術(shù)及相關(guān)學科的重要基礎(chǔ)，主要考核內(nèi)容包括基于數(shù)據(jù)結(jié)構(gòu)的程序設(shè)計和基于操作系統(tǒng)的程序設(shè)計兩大部分。要求考生對計算機科學與技術(shù)學科的基本知識、基本理論、基本方法有較深入、系統(tǒng)的理解，掌握各種數(shù)據(jù)結(jié)構(gòu)的定義和實現(xiàn)算法，掌握操作系統(tǒng)所涉及的關(guān)鍵內(nèi)容，對C語言的基本知識有較深入的了解，掌握程序設(shè)計的基本方法，并具有綜合運用所學知識分析問題和解決問題的能力。 二、考試的內(nèi)容（一） 程序設(shè)計基礎(chǔ)1、C語言的基本數(shù)據(jù)類型、各種運算符和表達式、基本控制結(jié)構(gòu)。2、數(shù)組的定義、數(shù)組元素的引用、數(shù)組的

2、初始化，掌握與字符串相關(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ù)組的應用，共同體變量的定義和使用方法。5、地址和指針的基本概念，如何使用指針來處理數(shù)組、字符串以及結(jié)構(gòu)體，函數(shù)指針的基本概念以及使用。6、FILE的定義以及對文件進行的各種操作的庫函數(shù)。（二） 線性表 1、 線性表的定義和基本操作 2、 線性表的實現(xiàn) （1）順序存儲結(jié)構(gòu)：實現(xiàn)順序表的查找、插入、刪除、合并、分解等操作的程序設(shè)計。（2）鏈式存儲結(jié)構(gòu)：實現(xiàn)單鏈表、循環(huán)鏈表、雙向鏈表、雙向

3、循環(huán)鏈表的生成、查找、插入、刪除、遍歷以及鏈表的分解和歸并等操作的程序設(shè)計。3、線性表的應用：從時間復雜度和空間復雜度的角度綜合比較線性表在順序和鏈式兩種存儲結(jié)構(gòu)下的特點，即其各自適用的場合。運用順序表和鏈表的特點解決復雜的應用問題。（三）棧、隊列和數(shù)組 1、棧和隊列的基本概念 2、棧和隊列的順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)及應用（1）棧與遞歸的關(guān)系。用遞歸解決的幾類問題：問題的定義是遞歸的；數(shù)據(jù)結(jié)構(gòu)是遞歸的；以及問題的解法是遞歸的。典型遞歸問題的算法以及如何將遞歸算法轉(zhuǎn)換為非遞歸算法。（2）在程序設(shè)計中，常需要棧這樣的數(shù)據(jù)結(jié)構(gòu)，使得與保存數(shù)據(jù)時相反順序來使用這些數(shù)據(jù)。在后續(xù)章節(jié)中多處有棧和隊列的應

4、用，如二叉樹遍歷的遞歸和非遞歸算法、圖的深度優(yōu)先遍歷等都用到棧，而樹的層次遍歷、圖的廣度優(yōu)先遍歷等則用到隊列。3、特殊矩陣的壓縮存儲：對稱矩陣、對角矩陣、三角矩陣在壓縮存儲時的下標變換公式。（四）樹與二叉樹 1、二叉樹 （1）二叉樹的定義及其主要特征：二叉樹的五個性質(zhì)及證明方法，并把這種方法推廣到K叉樹。（2）二叉樹的順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)：二叉樹的順序存儲結(jié)構(gòu)和二叉鏈表、三叉鏈表存儲結(jié)構(gòu)的各自優(yōu)缺點及適用場合。（3）二叉樹的遍歷二叉樹的先序，中序和后序遍歷算法以及按層次遍歷。遍歷是基礎(chǔ)，在基本遍歷算法的基礎(chǔ)上實現(xiàn)二叉樹的其它算法。（4）線索二叉樹的基本概念和構(gòu)造線索化算法，線索化后二叉樹

5、的遍歷算法，基本線索二叉樹的其它算法問題（如：查找某一類線索二叉樹中指定結(jié)點的前驅(qū)或后繼結(jié)點）。（5）二叉排序樹 二叉排序樹的建立、查找、插入和刪除算法，以及判斷某棵二叉樹是否二叉排序樹的算法。2、樹、森林 （1）樹的概念和存儲結(jié)構(gòu) （2）森林與二叉樹的轉(zhuǎn)換 （3）樹和森林的遍歷 樹與森林的遍歷，有兩種遍歷算法：先根與后根（對于森林而言稱作：先序與中序遍歷）。二者的先根與后根遍歷與二叉樹中的遍歷算法是有對應關(guān)系的：先根遍歷對應二叉樹的先序遍歷，而后根遍歷對應二叉樹的中序遍歷。（五）圖 1、圖的概念、存儲及基本操作 （1）鄰接矩陣法 （2）鄰接表法 2、圖的遍歷 深度優(yōu)先搜索和廣度優(yōu)先搜索是圖的

6、兩種基本的遍歷算法以及基于這兩種基本的遍歷算法的程序設(shè)計。3、圖的基本應用及其復雜度分析 （1）最小（代價）生成樹 （2）最短路徑 （3）拓撲排序 （4）關(guān)鍵路徑 （六）查找 1、查找的基本概念 2、順序查找法、折半查找法 3、散列（Hash）表及其查找 4、查找算法的分析及應用（七）內(nèi)部排序 1、 排序的基本概念 2、插入排序 3、冒泡排序 4、簡單選擇排序 5、希爾排序 6、快速排序 7、堆排序 8、二路歸并排序 9、各種內(nèi)部排序算法的比較 各種排序方法的算法思想及程序設(shè)計、手工模擬排序過程、性能分析（包括時間復雜度、空間復雜度、穩(wěn)定性）。10、內(nèi)部排序算法的應用 （八）進程管理 1、進程概念、進程的狀態(tài)與轉(zhuǎn)換 2、進程同步（1）進程同步的基本概念 （2）實現(xiàn)臨界區(qū)互斥的基本方法 （3）信號量：PV原語的含義（4）經(jīng)典同步問題：生產(chǎn)者-消費者問題；讀者-寫者問題；哲學家進餐問題。重點掌握 PV 操作的概念、流程，以及 PV 操作在同步與互斥問題中的