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

計算機考研專業(yè)課大綱——專業(yè)學位
第一部分  概述
一、考查目標
計算機學科專業(yè)綜合考試包括《數(shù)據(jù)結(jié)構(gòu)》和《高級語言程序設計》學科專業(yè)基礎課程。要求考生比較系統(tǒng)地掌握上述專業(yè)基礎課程的概念，理論、技能和方法，能夠運用所學的知識判斷和解決相關的理論問題和實際問題。

二、考試形式和試卷結(jié)構(gòu)
試卷滿分及考試時間
本試卷滿分為150分，考試時間為180分鐘
答題方式：閉卷、筆試

三、試卷內(nèi)容結(jié)構(gòu)
數(shù)據(jù)結(jié)構(gòu) 75分
高級語言程序設計75分

四、試卷題型結(jié)構(gòu)
第二部分 《數(shù)據(jù)結(jié)構(gòu)》
第三部分 《高級語言程序設計》

第二部分 《數(shù)據(jù)結(jié)構(gòu)》
考查目標
1. 熟悉數(shù)據(jù)結(jié)構(gòu)的相關概念及其分類，數(shù)據(jù)結(jié)構(gòu)與算法的關系。掌握線性表、堆棧和隊列，數(shù)組和字符串等數(shù)據(jù)結(jié)構(gòu)的存儲、操作和應用，樹與二叉樹的性質(zhì)與應用算法，圖的存儲結(jié)構(gòu)和相關算法，排序與查找的典型算法。
2. 掌握算法時空復雜性分析和正確性驗證的基本方法。
3．能夠綜合運用數(shù)據(jù)結(jié)構(gòu)、算法、數(shù)學等多種知識，對問題進行分析、建模，選擇或構(gòu)建合適的數(shù)據(jù)結(jié)構(gòu)，設計較優(yōu)算法。
題型結(jié)構(gòu)：包括問答題與算法設計題
具體內(nèi)容：
一、緒論
（1）數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)的定義及其關系；
（2）數(shù)據(jù)邏輯結(jié)構(gòu)及其分類；
（3）算法的定義和特征；
（4）算法的正確性證明方法；
（5）算法的時間和空間復雜性分析方法及復雜性函數(shù)的漸進表示。
二、 線性表、堆棧和隊列
（1）線性結(jié)構(gòu)的概念和特點；
（2）順序存儲和鏈式存儲線性表的基本操作；
（3）堆棧的定義和兩種存儲結(jié)構(gòu)下堆棧的基本操作；
（4）堆棧在括號匹配和遞歸中的應用；
（5）隊列的定義和兩種存儲結(jié)構(gòu)下隊列的基本操作；
（6）隊列的應用。
三、數(shù)組和字符串
（1）二維及多維數(shù)組的存儲原理及尋址方式；
（2）矩陣的存儲及基本操作；
（3）三元組表和十字鏈表存儲的稀疏矩陣的基本操作；
（4）字符串的存儲及基本操作；
（5）模式匹配算法。
四、 樹與二叉樹
（1）樹的概念、相關術(shù)語和表示方法；
（2）二叉樹的定義和性質(zhì)；
（3）二叉樹的順序存儲結(jié)構(gòu)和鏈接存儲結(jié)構(gòu)；
（4）二叉樹遍歷的遞歸與非遞歸算法；
（5）線索二叉樹的定義和操作；
（6）樹與二叉樹的轉(zhuǎn)換；
（7）樹的鏈接存儲結(jié)構(gòu)，樹和森林的遍歷算法；
（8）樹的順序存儲結(jié)構(gòu)；
（9）樹在并查集實現(xiàn)中的應用。
五、圖 
（1）圖的基本概念；
（2）圖的鄰接矩陣和鄰接表存儲結(jié)構(gòu)；
（3）圖的遍歷算法；
（4）拓撲排序和關鍵路徑算法；
（5）無權(quán)最短路徑算法、正權(quán)最短路徑算法、每對頂點之間的最短路徑算法，滿足約束的最短路徑問題；
（6）最小支撐樹算法；
（7）圖的可及性及傳遞閉包算法、連通分量算法。
六、排序 
（1）直接插入排序和Shell排序；
（2）冒泡排序和快速排序；
（3）直接選擇排序；
（4）堆的概念與性質(zhì)，堆排序算法；
（5）合并排序算法；
（6）分治排序的一般方法，基于關鍵詞比較的排序算法下界分析。
七、查找 
（1）順序查找算法；
（2）對半查找、一致對半查找、斐波那契查找和插值查找算法；
（3）對半查找算法的二叉判定樹；
（4）二叉查找樹的概念和性質(zhì)，二叉查找樹的查找、插入和刪除算法；
（5）高度平衡樹的概念和性質(zhì)，高度平衡樹的查找和插入過程；
（6）B樹及B+樹的概念和基本操作；
（7）散列的基本概念，散列函數(shù)的構(gòu)造方法；
（8）散列函數(shù)的沖突調(diào)節(jié)方法，拉鏈法和線性探查法。
第三部分 《高級語言程序設計》
考查目標
1. 了解程序設計語言主要成分，掌握表達式，輸入輸出語句，順序、分支、循環(huán)邏輯結(jié)構(gòu)的使用方法；可以熟練使用函數(shù)、數(shù)組和指針；能夠使用文件進行外存操作；理解結(jié)構(gòu)化程序設計原則，掌握模塊化和遞歸程序設計；理解動態(tài)變量概念，掌握鏈表、樹和圖的基本概念和操作。
2. 可以運用復雜數(shù)據(jù)類型和程序結(jié)構(gòu)設計程序解決實際問題，并對程序進行分析調(diào)試和測試。
題型結(jié)構(gòu)：包括綜合應用題
具體內(nèi)容：
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.4  C 語言
1.5  Code::Blocks集成開發(fā)環(huán)境
1.6  Visual C++集成開發(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  復合語句——順序控制結(jié)構(gòu)
2.6  輸入輸出
2.6.1　字符輸入
2.6.2　字符輸出
2.6.3　格式輸出
2.6.4　格式輸入
3.分支程序設計
3.1 雙分支程序設計
3.2單分支程序設計
3.3 if語句相關問題
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.3 for 語句
4.2 多重循環(huán)程序設計
5.模塊化程序設計——函數(shù)
5.1  模塊化程序設計思想
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  下標表達式
6.1.3  數(shù)組操作
6.2  多維數(shù)組
6.3  線性表——分類與檢索
6.4  數(shù)組初值
6.5  字符串
6.5.1  結(jié)束標志
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.結(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  對結(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. 遞歸程序設計
10.1  直接遞歸程序設計
10.2  遞歸程序執(zhí)行過程
10.3  間接遞歸
11.文件
11.1  文件概述
11.2  打開關閉文件
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ù)
11.4.3  VC6.0設定程序參數(shù)
11.4.4  Code::Blocks設定程序參數(shù)
11.4.5  程序健壯性
12. 程序開發(fā)
12.1  結(jié)構(gòu)化程序設計原則
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ù)結(jié)構(gòu)
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.1  break
14.3.2  continue
14.3.3  for的延伸
14.3.4  goto和標號
14.4  數(shù)據(jù)組織
14.4.1  行指針
14.4.2  枚舉類型
14.4.3  共用體
14.4.4  位段
14.5  存儲類別
14.5.1  數(shù)據(jù)在內(nèi)存中的存儲
14.5.2  生存期
14.5.3  局部變量的存儲類別
14.5.4  全局變量的存儲類別
14.5.5  函數(shù)的存儲類別
14.6  編譯預處理
14.6.1  宏
14.6.2  條件編譯

吉林大學

本文來源：http://www.qiang-kai.com/jilindaxue/cankaoshu_461160.html