| 上海电力学院2014年硕士研究生入学考试《算法与程序设计基础》课程考试大纲 | |
| 课程名称 | 算法与程序设计基础 |
| 参考书目 | [1] 严蔚敏. 《数据结构》(C语言版)，清华大学出版社，2009 |
| 复习的总体要求 掌握算法与程序设计的基本方法，理解算法、程序设计与数据结构的关系。理解数据结构的基本概念，掌握数据的逻辑结构、存储结构及其差异，以及各种基本操作的实现；在掌握基本的数据处理原理和方法的基础上，能够对算法进行基本的时间复杂度和空间复杂度的分析；能够选择合适的数据结构和方法进行问题求解，具备采用高级程序语言设计程序与实现算法的能力。 复习内容 1. 数据结构及算法的相关概念和术语考核要求：理解算法、程序设计与数据结构的关系，掌握数据结构的概念以及分类、抽象数据类型的表示与实现、算法的概念、算法的特性、算法的目标、算法效率的度量、算法的存储空间需求。考核知识点：数据结构及算法的概念；数据的逻辑结构和存储结构；算法的定义及特性；算法时间复杂度和空间复杂度的分析方法。 2. 线性表、栈、队列的存储结构、基本运算及应用考核要求：了解线性表的结构特点；掌握顺序的和链式的存储结构各自特点；熟练掌握线性表的操作，以及链表的指针运算和各种链表的操作；理解循环链表以及双向链表。掌握栈和队列的表示和实现；理解栈和队列的操作特点；理解循环队列以及其相关操作。考核知识点：线性表、栈和队列的存储结构及其存储特点；线性表的基本操作在顺序存储及链式存储上的实现；各种变形链表(循环链表、双向链表、带头结点的链表等)的表示和基本操作的实现；递归过程的特点及实现方法；循环队列的判满、判空方法。 3. 串和数组、广义表的存储结构、基本运算及应用考核要求：理解串的存储结构；理解串的相关操作；掌握数组的存储结构；掌握矩阵的压缩存储；理解特殊矩阵以及稀疏矩阵；理解广义表的有关概念及其与线性表的关系。考核知识点：串的两种存储表示，串上实现的模式匹配算法及其时间性能分析；稀疏矩阵的存储方法和基本运算的实现(转置、矩阵加法等)；广义表的定义及其求表头和表尾的运算。 4. 树和二叉树的存储结构、遍历算法及应用考核要求：掌握树和二叉树的基本定义；熟练掌握二叉树的性质；掌握二叉树的存储结构；掌握遍历二叉树和线索二叉树；理解树和森林的概念以及存储结构；掌握森林与二叉树的转换；理解树和森林的遍历；掌握赫夫曼树及其应用；理解赫夫曼编码。考核知识点：二叉树和树的递归定义、基本术语、基本性质、满二叉树和完全二叉树的概念及特征；二叉树、树及森林的顺序存储及链式存储，以及相互转换算法；线索二叉树、二叉排序树的构建；各种遍历算法；哈夫曼树和哈夫曼编码的构建和应用。 5. 图的存储结构、遍历算法及应用考核要求：理解图的定义和术语；熟练掌握图的存储结构；熟练掌握图的遍历方法：深度优先搜索和广度优先搜索；理解图的连通性问题；理解无向图的连通分量和生成树；掌握最小生成树；了解有向无环图及其应用；掌握最短路径。考核知识点：图的基本概念和术语；图的基本存储方法：邻接矩阵、关联矩阵、邻接表、逆邻接表、十字链表；图的遍历算法：深度优先搜索算法和广度优先搜索算法；图的基本应用：最小生成树、最短路径。 6. 静态查找表、动态查找表和哈希表(包括二叉排序树、AVL树) 考核要求：熟练掌握静态查找表的顺序表的查找、折半查找、分块查找；掌握动态查找表；掌握二叉排序树；理解平衡二叉树；掌握哈希表；掌握哈希函数的构造方法和处理冲突的方法；了解哈希表的查找及其分析。考核知识点：静态查找表、动态查找表和哈希表上的查找方法；哈希函数的基本构造方法，解决地址冲突的基本策略；各类查找算法的时间复杂度和空间复杂度。 7. 五类内部排序算法的算法思想、时间特性及稳定性考核要求：五类内部排序方法的基本思想、排序过程、算法实现、时间和空间性能的分析以及各种排序方法的比较和选择。在熟悉这些内容的基础上，掌握五类排序的基本思想及排序过程以及排序算法的实现。考核知识点：插入排序、交换排序、选择排序、归并排序和基数排序等五类排序算法的算法思想和时间复杂度；五类排序算法的特性、稳定性及适用情形。 | |
更多信息请查看学历考试网