资源简介：2017年湖南师范大学计算机算法设计与分析考研大纲    

        下载流程： 考研真题 点击“考研试卷””下载; 考博真题 点击“考博试卷库” 下载

 

1
湖南师范大学硕士研究生入学考试自命题考试大纲
考试科目代码：[ ] 考试科目名称：计算机算法设计与分析
一、试卷结构
1) 试卷成绩及考试时间
本试卷满分为 100 分，考试时间为 180 分钟。
2)答题方式：闭卷、笔试
3)试卷内容结构
计算机算法设计与分析部分 100%
4)题型结构
a: 填空题，10 小题，共 20 分
b: 简答题，4 小题，共 20 分
c: 解答题(包括证明题)，4 小题，共 60 分
二、考试内容与考试要求
1、 算法概述
考试内容
算法的概念和性质 算法的复杂性概念和分析角度 计算时间的渐近表示及其相关性质
NP 完全性理论中的基本概念
考试要求
（1）理解算法的概念和性质。
（2）理解程序与算法的区别和内在联系。
（3）理解算法的复杂性概念和时间复杂度分析角度（最佳、最差和平均情况）。
（4）掌握计算时间的渐近表示及其相关性质。
（5）掌握算法复杂度分析的基本技术和方法。
（6）理解 P 和 NP 类问题的概念，了解 Cook 定理和几个 NP 完全问题。
2、 递归算法设计与分析
考试内容
递归的概念 递归算法的实现机制 设计和分析递归算法的一般方法 消去递归
考试要求
（1）理解递归的概念。
（2）掌握递归算法的实现机制。
2
（3）掌握设计和分析递归算法的一般方法。
（4）了解如何消去递归。
3、 分治策略
考试内容
分治法的基本思想和适用条件 分治法的效率分析 分治法应用的经典实例
考试要求
（1）掌握分治法的基本思想和适用条件。
（2）掌握分治法的效率分析的一般性技巧。
（3）掌握分治法应用的经典实例，如二分搜索法，快速排序，归并排序，大整数乘法，Strassen
矩阵乘法，循环赛安排，线性选择问题等。掌握这些算法的基本思路、实现技术以及复杂度
分析过程。
（4）通过学习分治法，会用某高级语言对算法进行描述。
4、动态规划
考试内容
动态规划的基本原理和应用条件 动态规划的效率分析 动态规划应用的经典实例
考试要求
（1）掌握动态规划的基本思想。
（2）掌握动态规划的两个基本要素：最优子结构性质和重叠子问题性质。
（3）了解动态规划的一般性求解步骤，会将问题化为多阶段图，并能对具体问题写出正确
的递推公式。
（4）掌握动态规划应用的经典实例：多段图、矩阵连乘、0/1 背包、每对节点之间的最短路
径、最优二分检索树、最长公共子序列以及最大子段和问题。针对这些实例，会用某高级语
言对算法进行描述，掌握分析动态规划算法效率分析的一般性方法。
（5）理解动态规划与分治法的区别。
5、贪心法
考试内容
贪心法的基本原理和基本要素 贪心算法的效率分析和可靠性（正确性）分析 贪 心 法
应用的经典实例
考试要求
（1）掌握贪心法的基本原理。
（2）掌握动态规划的两个基本要素：最优子结构性质和贪心选择性质。针对一些简单的问
题，会证明算法的正确性。
（3）掌握典型问题如背包问题、最优装载问题、带有限期的作业排序问题、活动安排问题、
最小生成树、单源点最短路径等的算法设计原理、实现技术以及算法效率的分析。
（4）掌握贪心法与动态规划算法的区别。
6、回溯法
考试内容
回溯法的基本思想 剪枝函数的设计 回溯法的效率分析 回溯法应用的经典实例
考试要求
（1）掌握利用回溯法解决问题的基本思想和算法的基本框架。
（2）理解活结点、死结点和扩展结点的概念。
（3）掌握回溯法在下述问题上的应用：n 皇后问题、最优装载问题、0/1 背包、图的 m 着

 

说明：本站提供的《2017年湖南师范大学计算机算法设计与分析考研大纲 》源自权威渠道，为历年考过（被使用过）的真题试卷，除标注有“回忆版”字样的试题外，其余均为原版扫描，权威可靠；回忆版试题由当年参加全国硕士、博士研究生入学考试考生回忆，内容完整。