2022年吉林大学计算机科学与技术学院专业学位硕士研究生专业课考试大纲 正文

计算机考研专业课大纲——专业学位
第一部分  概述
一、考查目标
计算机学科专业综合考试包括《数据结构》和《高级语言程序设计》学科专业基础课程。要求考生比较系统地掌握上述专业基础课程的概念，理论、技能和方法，能够运用所学的知识判断和解决相关的理论问题和实际问题。

二、考试形式和试卷结构
试卷满分及考试时间
本试卷满分为150分，考试时间为180分钟
答题方式：闭卷、笔试

三、试卷内容结构
数据结构 75分
高级语言程序设计75分

四、试卷题型结构
第二部分 《数据结构》
第三部分 《高级语言程序设计》

第二部分 《数据结构》
考查目标
1. 熟悉数据结构的相关概念及其分类，数据结构与算法的关系。掌握线性表、堆栈和队列，数组和字符串等数据结构的存储、操作和应用，树与二叉树的性质与应用算法，图的存储结构和相关算法，排序与查找的典型算法。
2. 掌握算法时空复杂性分析和正确性验证的基本方法。
3．能够综合运用数据结构、算法、数学等多种知识，对问题进行分析、建模，选择或构建合适的数据结构，设计较优算法。
题型结构：包括问答题与算法设计题
具体内容：
一、绪论
（1）数据、数据元素、数据逻辑结构和存储结构的定义及其关系；
（2）数据逻辑结构及其分类；
（3）算法的定义和特征；
（4）算法的正确性证明方法；
（5）算法的时间和空间复杂性分析方法及复杂性函数的渐进表示。
二、 线性表、堆栈和队列
（1）线性结构的概念和特点；
（2）顺序存储和链式存储线性表的基本操作；
（3）堆栈的定义和两种存储结构下堆栈的基本操作；
（4）堆栈在括号匹配和递归中的应用；
（5）队列的定义和两种存储结构下队列的基本操作；
（6）队列的应用。
三、数组和字符串
（1）二维及多维数组的存储原理及寻址方式；
（2）矩阵的存储及基本操作；
（3）三元组表和十字链表存储的稀疏矩阵的基本操作；
（4）字符串的存储及基本操作；
（5）模式匹配算法。
四、 树与二叉树
（1）树的概念、相关术语和表示方法；
（2）二叉树的定义和性质；
（3）二叉树的顺序存储结构和链接存储结构；
（4）二叉树遍历的递归与非递归算法；
（5）线索二叉树的定义和操作；
（6）树与二叉树的转换；
（7）树的链接存储结构，树和森林的遍历算法；
（8）树的顺序存储结构；
（9）树在并查集实现中的应用。
五、图 
（1）图的基本概念；
（2）图的邻接矩阵和邻接表存储结构；
（3）图的遍历算法；
（4）拓扑排序和关键路径算法；
（5）无权最短路径算法、正权最短路径算法、每对顶点之间的最短路径算法，满足约束的最短路径问题；
（6）最小支撑树算法；
（7）图的可及性及传递闭包算法、连通分量算法。
六、排序 
（1）直接插入排序和Shell排序；
（2）冒泡排序和快速排序；
（3）直接选择排序；
（4）堆的概念与性质，堆排序算法；
（5）合并排序算法；
（6）分治排序的一般方法，基于关键词比较的排序算法下界分析。
七、查找 
（1）顺序查找算法；
（2）对半查找、一致对半查找、斐波那契查找和插值查找算法；
（3）对半查找算法的二叉判定树；
（4）二叉查找树的概念和性质，二叉查找树的查找、插入和删除算法；
（5）高度平衡树的概念和性质，高度平衡树的查找和插入过程；
（6）B树及B+树的概念和基本操作；
（7）散列的基本概念，散列函数的构造方法；
（8）散列函数的冲突调节方法，拉链法和线性探查法。
第三部分 《高级语言程序设计》
考查目标
1. 了解程序设计语言主要成分，掌握表达式，输入输出语句，顺序、分支、循环逻辑结构的使用方法；可以熟练使用函数、数组和指针；能够使用文件进行外存操作；理解结构化程序设计原则，掌握模块化和递归程序设计；理解动态变量概念，掌握链表、树和图的基本概念和操作。
2. 可以运用复杂数据类型和程序结构设计程序解决实际问题，并对程序进行分析调试和测试。
题型结构：包括综合应用题
具体内容：
1. 绪论
1.1  “鸡兔同笼”——计算
1.2  算法——程序设计精髓
1.2.1  算法概念
1.2.2  表示算法——PAD
1.3  程序设计
1.3.1  程序设计语言
1.3.2  程序
1.3.3  程序执行
1.4  C 语言
1.5  Code::Blocks集成开发环境
1.6  Visual C++集成开发环境
2. 顺序程序设计
2.1  计算平均成绩——顺序程序设计
2.2  基本符号
2.2.1  字符集
2.2.2  特定符
2.2.3  标识符
2.2.4  间隔符
2.2.5  注释
2.3  数据
2.3.1  数据类型
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.3 if语句相关问题
3.4逻辑判断——布尔类型
3.4.1关系运算
3.4.2布尔运算
3.5 多分支程序设计 
4. 循环程序设计
4.1 单层循环程序设计
4.1.1 后判断条件循环
4.1.2 先判断条件循环
4.1.3 for 语句
4.2 多重循环程序设计
5.模块化程序设计——函数
5.1  模块化程序设计思想
5.2  函数
5.2.1 函数定义
5.2.2 函数调用
5.2.3 函数原型 105
5.3  程序调试 109
5.3.1 Code::Blocks环境下调试
5.3.2 VC环境下调试
6. 批量数据组织——数组
6.1  数组类型
6.1.1  数组声明
6.1.2  下标表达式
6.1.3  数组操作
6.2  多维数组
6.3  线性表——分类与检索
6.4  数组初值
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  指针与数组
7.4.1  指针标识数组
7.4.2  指针运算
7.4.3  应注意的问题
7.4.4  多维数组与指针
7.4.5  指针数组
7.5  指针与字符串
8.结构体
8.1  结构体类型
8.2  结构体类型名
8.3  结构体变量
8.4  指向结构体变量的指针
8.5  访问结构体变量的成分
8.6  对结构体变量的操作
9. 再论函数
9.1  参数
9.1.1  参数传递规则
9.1.2  指针作参数
9.1.3  数组作参数
9.1.4  结构体作参数
9.2  函数值
9.2.1  返回指针值的函数
9.2.2  返回结构体值的函数
9.3  作用域
9.3.1  作用域
9.3.2  局部量和全局量 
10. 递归程序设计
10.1  直接递归程序设计
10.2  递归程序执行过程
10.3  间接递归
11.文件
11.1  文件概述
11.2  打开关闭文件
11.3  I/O操作
11.3.1  字符读写
11.3.2  字符串读写
11.3.3  格式化读写
11.3.4  数据块读写
11.3.5  文件定位
11.4  程序参数
11.4.1  基本概念
11.4.2  命令行设定程序参数
11.4.3  VC6.0设定程序参数
11.4.4  Code::Blocks设定程序参数
11.4.5  程序健壮性
12. 程序开发
12.1  结构化程序设计原则
12.2  程序风格
12.2.1  行文格式
12.2.2  标识符
12.2.3  注释
12.2.4  关于程序的“说明和定义”
12.3  八皇后——穷举与试探
12.3.1  数据表示
12.3.2  穷举法迭代实现
12.3.3  试探法迭代实现
12.3.4  穷举法递归实现
12.3.5  试探法递归实现
12.3.6  检验函数
13. 动态数据组织
13.1 动态数据结构
13.2  动态变量
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  函数
14.1.1  函数指针
14.1.2  函数作参数
14.1.3  指针形参作指针参数的实参
14.1.4  实参计算顺序
14.1.5  函数副作用
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  数据组织
14.4.1  行指针
14.4.2  枚举类型
14.4.3  共用体
14.4.4  位段
14.5  存储类别
14.5.1  数据在内存中的存储
14.5.2  生存期
14.5.3  局部变量的存储类别
14.5.4  全局变量的存储类别
14.5.5  函数的存储类别
14.6  编译预处理
14.6.1  宏
14.6.2  条件编译

吉林大学

本文来源：http://www.okaoyan.com/jilindaxue/cankaoshu_461160.html