2019年硕士研究生入学考试自命题考试大纲
考试科目代码：[ ] 考试科目名称：计算机程序设计能力测试一、试卷结构
1、试卷成绩及考试时间
本试卷满分为150分，考试时间为120分钟。
2、答题方式：闭卷、笔试
3、题型结构
单选题：15小题，每小题2分，共30分
填空题：10小题，每小题2分，共20分
判断题：10小题，每小题 2分，共20分
程序阅读题：6小题，每小题 8分，共48分
程序设计题：2小题，每小题 16分，共32分
二、考试内容与考试要求
●考试目标：
1.系统全面理解、掌握程序设计的思想和常用个算法，能编程求解一般问题
2.要求学生熟练掌握C语言中的数据类型、运算符、表达式等基本语法；掌握函数的定义和调用，熟悉数组、指针及结构的用法，能熟练运用相关知识进行结构化程序设计解决实际问题。
3.要求学生掌握常用的算法，如分治算法、动态规划算法和贪心算法，回溯法和分支限界法等算法思想，并应用这些算法来解决实际问题，掌握常用算法的效率分析。
●考试内容
（一） 引言
1. 程序和指令
2. C语言程序的结构
3. C语言的语法，标识符与关键字
4. 程序设计的开发步骤及要素
（二） 用C语言编写程序
1. 变量和数据类型（整型和实型）
2. 算术运算符和表达式
3. 赋值运算符与表达式
4. 输入、输出数据
5. 常用数学函数
（三） 分支结构
1. 二分支结构和多分支结构
2. 字符型数据
3. 关系运算符和逻辑运算符
4. switch语句和break;
（四） 循环结构
1. 三种循环语句（while, for, do-while）
2. break语句和continue语句
3. 循环嵌套
（五） 函数
1. 函数的定义和调用
2. 函数的返回值
3. 局部变量与全局变量
4. 变量生存期与静态局部变量
5.函数的递归调用
（六） 数组
1. 一维数组的定义和使用
2. 二维数组的定义和使用
3. 字符数组与字符串
(七） 指针
1. 地址与指针的概念
2. 指针变量的定义和使用
3. 指针作为函数参数
4. 指针、数组和地址间的关系
5. 数组名作为函数参数
6. 字符串与字符指针
7. 常用的字符串处理函数
（八） 结构体
1. 结构体的概念与定义
2. 结构体变量的使用
3. 结构体数组
4. 结构体指针
（九）算法效率分析基础
1.算法效率分析框架，算法的最优、最差和平均效率
2.三种不同的渐进符号及其特性，基本的效率类型。
3.非递归算法的效率分析
4.递归算法的原理及效率分析框架
（十）分治法
1.分治算法的基本思想及算法效率分析
2.归并排序
3.快速排序
4.折半查找
（十一）动态规划方法
1.0-1背包问题
2. Warshall算法和Floyd算法
3. 最优二叉查找树问题
（十二）贪心方法
1.Prim算法求解最小生成树
2.Kruskal求解最小生成树
3.Dijkstra算法求解单源点最短路径
4.哈夫曼树
（十三）回溯法与分支定界法
1.回溯法，n皇后问题和哈密顿回路求解
2.分支-限界法，旅行商问题和背包问题的求解
