計(jì)算機(jī)考研專業(yè)課大綱-專業(yè)學(xué)位

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