计算机考研专业课大纲-专业学位

计算机考研专业课大纲——专业学位第一部分概述一、考查目标计算机学科专业综合考试包括《数据结构》和《高级语言程序设计》学科专业基础课程。要求考生比较系统地掌握上述专业基础课程的概念，理论、技能和方法，能够运用所学的知识判断和解决相关的理论问题和实际问题。二、考试形式和试卷结构试卷满分及考试时间本试卷满分为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.4C语言 1.5Code::Blocks集成开发环境 1.6VisualC++集成开发环境 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.3if语句相关问题3.4逻辑判断——布尔类型3.4.1关系运算3.4.2布尔运算3.5多分支程序设计 4.循环程序设计4.1单层循环程序设计4.1.1后判断条件循环4.1.2先判断条件循环4.1.3for语句 4.2多重循环程序设计5.模块化程序设计——函数5.1模块化程序设计思想5.2函数5.2.1函数定义 5.2.2函数调用5.2.3函数原型 1055.3程序调试 1095.3.1Code::Blocks环境下调试5.3.2VC环境下调试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.3I/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.3VC6.0设定程序参数11.4.4Code::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.1break14.3.2continue14.3.3for的延