計算機考研專業(yè)課大綱-專業(yè)學位

計算機考研專業(yè)課大綱——專業(yè)學位第一部分概述一、考查目標計算機學科專業(yè)綜合考試包括《數(shù)據(jù)結構》和《高級語言程序設計》學科專業(yè)基礎課程。要求考生比較系統(tǒng)地掌握上述專業(yè)基礎課程的概念，理論、技能和方法，能夠運用所學的知識判斷和解決相關的理論問題和實際問題。二、考試形式和試卷結構試卷滿分及考試時間本試卷滿分為150分，考試時間為180分鐘答題方式：閉卷、筆試三、試卷內容結構數(shù)據(jù)結構75分高級語言程序設計75分四、試卷題型結構第二部分《數(shù)據(jù)結構》第三部分《高級語言程序設計》第二部分《數(shù)據(jù)結構》考查目標1.熟悉數(shù)據(jù)結構的相關概念及其分類，數(shù)據(jù)結構與算法的關系。掌握線性表、堆棧和隊列，數(shù)組和字符串等數(shù)據(jù)結構的存儲、操作和應用，樹與二叉樹的性質與應用算法，圖的存儲結構和相關算法，排序與查找的典型算法。2.掌握算法時空復雜性分析和正確性驗證的基本方法。3．能夠綜合運用數(shù)據(jù)結構、算法、數(shù)學等多種知識，對問題進行分析、建模，選擇或構建合適的數(shù)據(jù)結構，設計較優(yōu)算法。題型結構：包括問答題與算法設計題具體內容：一、緒論 （1）數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)邏輯結構和存儲結構的定義及其關系；（2）數(shù)據(jù)邏輯結構及其分類；（3）算法的定義和特征；（4）算法的正確性證明方法；（5）算法的時間和空間復雜性分析方法及復雜性函數(shù)的漸進表示。二、線性表、堆棧和隊列（1）線性結構的概念和特點；（2）順序存儲和鏈式存儲線性表的基本操作；（3）堆棧的定義和兩種存儲結構下堆棧的基本操作；（4）堆棧在括號匹配和遞歸中的應用；（5）隊列的定義和兩種存儲結構下隊列的基本操作；（6）隊列的應用。三、數(shù)組和字符串（1）二維及多維數(shù)組的存儲原理及尋址方式；（2）矩陣的存儲及基本操作；（3）三元組表和十字鏈表存儲的稀疏矩陣的基本操作；（4）字符串的存儲及基本操作；（5）模式匹配算法。 四、樹與二叉樹 （1）樹的概念、相關術語和表示方法；（2）二叉樹的定義和性質；（3）二叉樹的順序存儲結構和鏈接存儲結構；（4）二叉樹遍歷的遞歸與非遞歸算法；（5）線索二叉樹的定義和操作；（6）樹與二叉樹的轉換；（7）樹的鏈接存儲結構，樹和森林的遍歷算法；（8）樹的順序存儲結構；（9）樹在并查集實現(xiàn)中的應用。五、圖 （1）圖的基本概念；（2）圖的鄰接矩陣和鄰接表存儲結構；（3）圖的遍歷算法；（4）拓撲排序和關鍵路徑算法；（5）無權最短路徑算法、正權最短路徑算法、每對頂點之間的最短路徑算法，滿足約束的最短路徑問題；（6）最小支撐樹算法；（7）圖的可及性及傳遞閉包算法、連通分量算法。六、排序 （1）直接插入排序和Shell排序；（2）冒泡排序和快速排序；（3）直接選擇排序；（4）堆的概念與性質，堆排序算法；（5）合并排序算法；（6）分治排序的一般方法，基于關鍵詞比較的排序算法下界分析。七、查找 （1）順序查找算法；（2）對半查找、一致對半查找、斐波那契查找和插值查找算法；（3）對半查找算法的二叉判定樹；（4）二叉查找樹的概念和性質，二叉查找樹的查找、插入和刪除算法；（5）高度平衡樹的概念和性質，高度平衡樹的查找和插入過程；（6）B樹及B+樹的概念和基本操作；（7）散列的基本概念，散列函數(shù)的構造方法；（8）散列函數(shù)的沖突調節(jié)方法，拉鏈法和線性探查法。第三部分《高級語言程序設計》考查目標1.了解程序設計語言主要成分，掌握表達式，輸入輸出語句，順序、分支、循環(huán)邏輯結構的使用方法；可以熟練使用函數(shù)、數(shù)組和指針；能夠使用文件進行外存操作；理解結構化程序設計原則，掌握模塊化和遞歸程序設計；理解動態(tài)變量概念，掌握鏈表、樹和圖的基本概念和操作。2.可以運用復雜數(shù)據(jù)類型和程序結構設計程序解決實際問題，并對程序進行分析調試和測試。題型結構：包括綜合應用題具體內容：1.緒論1.1“雞兔同籠”——計算 1.2算法——程序設計精髓 1.2.1算法概念 1.2.2表示算法——PAD 1.3程序設計 1.3.1程序設計語言 1.3.2程序 1.3.3程序執(zhí)行 1.4C語言 1.5Code::Blocks集成開發(fā)環(huán)境 1.6VisualC++集成開發(fā)環(huán)境 2.順序程序設計2.1計算平均成績——順序程序設計2.2基本符號2.2.1字符集2.2.2特定符2.2.3標識符2.2.4間隔符2.2.5注釋2.3數(shù)據(jù)2.3.1數(shù)據(jù)類型2.3.2常量2.3.3變量2.4表達式2.4.1組成2.4.2計算2.5語句2.5.1表達式語句2.5.2賦值語句 2.5.3復合語句——順序控制結構 2.6輸入輸出 2.6.1字符輸入 2.6.2字符輸出 2.6.3格式輸出 2.6.4格式輸入 3.分支程序設計3.1雙分支程序設計3.2單分支程序設計3.3if語句相關問題3.4邏輯判斷——布爾類型3.4.1關系運算3.4.2布爾運算3.5多分支程序設計?4.循環(huán)程序設計4.1單層循環(huán)程序設計4.1.1后判斷條件循環(huán)4.1.2先判斷條件循環(huán)4.1.3for語句 4.2多重循環(huán)程序設計5.模塊化程序設計——函數(shù)5.1模塊化程序設計思想5.2函數(shù)5.2.1函數(shù)定義 5.2.2函數(shù)調用5.2.3函數(shù)原型 1055.3程序調試 1095.3.1Code::Blocks環(huán)境下調試5.3.2VC環(huán)境下調試6.批量數(shù)據(jù)組織——數(shù)組6.1數(shù)組類型 6.1.1數(shù)組聲明 6.1.2下標表達式 6.1.3數(shù)組操作 6.2多維數(shù)組 6.3線性表——分類與檢索6.4數(shù)組初值 6.5字符串 6.5.1結束標志 6.5.2初始化6.5.3輸入輸出6.5.4運算 6.6類型定義6.7線性表——棧和隊列 ?7.指針7.1指針與變量7.1.1指針類型和指針變量7.1.2指針所指變量7.1.3空指針與無效指針7.2指針操作 7.3指向指針的指針 7.4指針與數(shù)組7.4.1指針標識數(shù)組7.4.2指針運算7.4.3應注意的問題7.4.4多維數(shù)組與指針7.4.5指針數(shù)組7.5指針與字符串 8.結構體 8.1結構體類型 8.2結構體類型名8.3結構體變量8.4指向結構體變量的指針8.5訪問結構體變量的成分8.6對結構體變量的操作9.再論函數(shù)9.1參數(shù)9.1.1參數(shù)傳遞規(guī)則9.1.2指針作參數(shù) 9.1.3數(shù)組作參數(shù) 9.1.4結構體作參數(shù)9.2函數(shù)值9.2.1返回指針值的函數(shù)9.2.2返回結構體值的函數(shù)9.3作用域 9.3.1作用域9.3.2局部量和全局量?10.遞歸程序設計10.1直接遞歸程序設計10.2遞歸程序執(zhí)行過程10.3間接遞歸11.文件 11.1文件概述11.2打開關閉文件11.3I/O操作11.3.1字符讀寫11.3.2字符串讀寫11.3.3格式化讀寫11.3.4數(shù)據(jù)塊讀寫11.3.5文件定位11.4程序參數(shù) 11.4.1基本概念11.4.2命令行設定程序參數(shù)11.4.3VC6.0設定程序參數(shù)11.4.4Code::Blocks設定程序參數(shù)11.4.5程序健壯性12.程序開發(fā)12.1結構化程序設計原則12.2程序風格12.2.1行文格式12.2.2標識符12.2.3注釋12.2.4關于程序的“說明和定義” 12.3八皇后——窮舉與試探 12.3.1數(shù)據(jù)表示12.3.2窮舉法迭代實現(xiàn)12.3.3試探法迭代實現(xiàn)12.3.4窮舉法遞歸實現(xiàn)12.3.5試探法遞歸實現(xiàn)12.3.6檢驗函數(shù)13.動態(tài)數(shù)據(jù)組織13.1動態(tài)數(shù)據(jù)結構13.2動態(tài)變量13.3鏈表13.3.1基本概念13.3.2基本操作13.3.3棧與隊列13.4樹13.4.1基本概念13.4.2基本操作13.5圖 13.5.1基本概念13.5.2存儲方式13.5.3基本操作14.若干深入問題14.1函數(shù)14.1.1函數(shù)指針14.1.2函數(shù)作參數(shù)14.1.3指針形參作指針參數(shù)的實參14.1.4實參計算順序14.1.5函數(shù)副作用14.2運算14.2.1復合賦值14.2.2順序表達式14.2.3條件表達式14.2.4位運算14.2.5左值14.3語句14.3.1break14.3.2continue14.3.3for的延