2022年吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院專業(yè)學(xué)位碩士研究生專業(yè)課考試大綱 正文

計(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)試和測(cè)試。
題型結(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.4  C 語言
1.5  Code::Blocks集成開發(fā)環(huán)境
1.6  Visual C++集成開發(fā)環(huán)境
2. 順序程序設(shè)計(jì)
2.1  計(jì)算平均成績(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.3 if語句相關(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.3 for 語句
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ù)原型 105
5.3  程序調(diào)試 109
5.3.1 Code::Blocks環(huán)境下調(diào)試
5.3.2 VC環(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)缸兞?br /> 7.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.3  I/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.3  VC6.0設(shè)定程序參數(shù)
11.4.4  Code::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.1  break
14.3.2  continue
14.3.3  for的延伸
14.3.4  goto和標(biāo)號(hào)
14.4  數(shù)據(jù)組織
14.4.1  行指針
14.4.2  枚舉類型
14.4.3  共用體
14.4.4  位段
14.5  存儲(chǔ)類別
14.5.1  數(shù)據(jù)在內(nèi)存中的存儲(chǔ)
14.5.2  生存期
14.5.3  局部變量的存儲(chǔ)類別
14.5.4  全局變量的存儲(chǔ)類別
14.5.5  函數(shù)的存儲(chǔ)類別
14.6  編譯預(yù)處理
14.6.1  宏
14.6.2  條件編譯

吉林大學(xué)

本文來源：http://m.lyhuahuisp.com/jilindaxue/cankaoshu_461160.html