计算机算法设计与分析

1、中国科学院大学硕士研究生入学考试计算机算法设计与分析考试大纲一、考试科目基本要求及适用范围概述本计算机算法设计与分析考试大纲适用于中国科学院大学工业工程专业硕士研究生入 学考试。计算机算法设计与分析是工业工程专业方向，特别是信息技术相关领域的重要基础 课程，为使用计算机分析、解决工程实际问题提供基础数学理论和方法的支持。本科目的考 试内容主要包括基础数据结构、计算机算法分析的一般性理论和数学方法、算法设计的常用 方法及其分析方法等，要求考生对算法相关的基本概念有较深入、系统的理解，掌握算法设 计与分析所涉及的基本理论和方法，并具有综合运用所学知识分析问题和解决问题的能力。二、考试形式考试采用闭

2、卷笔试形式，考试时间为180分钟，试卷满分150分。试卷结构：计算分析题、算法设计题。三、考试内容：（一）基础数据结构（熟练掌握）数据结构的基本概念、逻辑结构和存储结构；线性表、栈与队列；数组与广义表；树、二叉树与图。（二）算法分析基础（灵活运用）函数的渐进阶，基于渐进阶的函数分类；递归和数学归纳法，递推方程求解，主定理；算法分析的目的和意义，算法的正确性概念，算法的时间复杂度和空间复杂度；最坏情况时间复杂度和平均时间复杂度的定义和基本计算方法。（三）分治法与排序算法（灵活运用）分治法的基本原理、设计方法和适用条件；排序算法的设计与分析：插入排序、快速排序、归并排序、堆排序；以比较为基本操作的

3、排序算法时间复杂度下界分析。（四）选择与检索（掌握）选择算法设计，对手论证法；动态集合（并查集），并查集上的合并查找程序；分摊时间分析方法。（五）高级算法设计与分析技术（熟练掌握）贪心算法设计及分析；动态规划算法设计及分析；字符串匹配算法（KMP算法、BM算法、近似匹配算法）。（六）图算法（熟练掌握）图的表示和数据结构；图的搜索与遍历（有向图的深度和广度优先搜索、有向无环图的拓扑排序、有向图 的强连通分量、无向图的深度优先搜索）；最小生成树（Prim算法、Kruskal算法）；单源最短路径（Dijkstra算法）。（七）计算复杂性理论概述（了解）问题分类及多项式复杂度；NP完全性及其证明；NP

4、完全问题。四、考试要求：（一）基础数据结构理解数据结构的基本概念、逻辑结构和存储结构；熟练掌握线性表、栈与队列的特点及实现方法；熟练掌握数组与广义表的概念和存储结构；熟练掌握树、二叉树与图的概念、相关数学性质和存储结构。（二）算法分析基础理解函数的渐进阶概念，熟练掌握基于渐进阶的函数分类方法；熟练掌握递归和数学归纳法、递推方程求解方法及主定理，并灵活应用于算法复杂 度的分析；理解算法分析的目的和意义、算法的正确性概念、算法的时间复杂度和空间复杂度 概念；熟练掌握最坏情况时间复杂度和平均时间复杂度的定义和基本计算方法。（三）分治法与排序算法理解分治法的基本原理、设计方法和适用条件，灵活应用分治法

5、的基本思想针对实 际问题设计有效算法；掌握排序算法的设计与分析方法，重点掌握插入排序、快速排序、归并排序、堆排 序的基本原理和复杂度；掌握以比较为基本操作的排序算法时间复杂度下界分析的方法和结果。（四）选择与检索掌握选择算法设计的基本方法，理解对手论证法的基本思想；理解动态集合（并查集）的基本概念和特点，掌握并查集上的合并查找程序设计和 分析方法；掌握分摊时间分析的基本原理和用法。（五）高级算法设计与分析技术：（熟练掌握）掌握贪心算法设计及分析的原理和方法，并熟练应用于具体的算法设计中；掌握动态规划算法设计及分析的原理和方法，并熟练应用于具体的算法设计中；了解字符串匹配算法（包括KMP算法、B

6、M算法、近似匹配算法）的原理和时间复杂 度。（六）图算法熟练掌握图的表示和数据结构；熟练掌握图的搜索与遍历算法框架，并能够灵活应用于实际图问题的算法设计；掌握最小生成树问题经典算法的设计和分析（包括Prim算法、Kruskal算法）；掌握单源最短路径问题经典算法的设计和分析（Dijkstra算法）。（七）计算复杂性理论概述理解问题分类及多项式复杂度的概念及内涵；了解NP完全性概念及其证明方法；理解NP完全问题的概念及意义。五、主要参考书目：Introduction to Algorithms（Second Edition）, Thomas H. Cormen, Charles E. Leiserson, et al.中译本：算法导论，潘金贵等译，机械工业出版社，2006年9月；计算机算法设计与分析导论（第3版 影印版），Sara Baase & Allen Van Gelder，高等教育出版社2001年7月出版。原版书名：“Computer Algorithms: Introduction to Design and Analysis （3rd Edition”，作者：（美）Sara Baase & Allen