为了帮助广大考生复习备考，也应广大考生的要求，现提供我校自命题专业课的考试大纲供考生下载。考生在复习备考时，应全面复习，我校自命题专业课的考试大纲仅供参考。

    上海电力大学2021年硕士研究生入学复试《算法与程序设计基础》课程考试大纲

    课程名称算法与程序设计基础

    参考书目[1]严蔚敏.《数据结构》(C语言版)，清华大学出版社，2009

    [2]数据结构与算法(C语言版第2版高等院校计算机教育系列教材)作者：郭龙源//胡虚怀//何光明出版社：清华大学

    出版时间：2010-03-01

    复习的总体要求

    掌握算法与程序设计的基本方法，理解算法、程序设计与数据结构的关系。理解数据结构的基本概念，掌握数据的逻辑结构、存储结构及其差异，以及各种基本操作的实现；在掌握基本的数据处理原理和方法的基础上，能够对算法进行基本的时间复杂度和空间复杂度的分析；能够选择合适的数据结构和方法进行问题求解，具备采用高级程序语言设计程序与实现算法的能力。

    复习内容

    1.数据结构及算法的相关概念和术语

    考核要求：理解算法、程序设计与数据结构的关系，掌握数据结构的概念以及分类、抽象数据类型的表示与实现、算法的概念、算法的特性、算法的目标、算法效率的度量、算法的存储空间需求。

    考核知识点：数据结构及算法的概念；数据的逻辑结构和存储结构；算法的定义及特性；算法时间复杂度和空间复杂度的分析方法。

    2.线性表、栈、队列的存储结构、基本运算及应用

    考核要求：了解线性表的结构特点；掌握顺序的和链式的存储结构各自特点；熟练掌握线性表的操作，以及链表的指针运算和各种链表的操作；理解循环链表以及双向链表。掌握栈和队列的表示和实现；理解栈和队列的操作特点；理解循环队列以及其相关操作。

    考核知识点：线性表、栈和队列的存储结构及其存储特点；线性表的基本操作在顺序存储及链式存储上的实现；各种变形链表(循环链表、双向链表、带头结点的链表等)的表示和基本操作的实现；递归过程的特点及实现方法；循环队列的判满、判空方法。

    3.串和数组、广义表的存储结构、基本运算及应用

    考核要求：理解串的存储结构；理解串的相关操作；掌握数组的存储结构；掌握矩阵的压缩存储；理解特殊矩阵以及稀疏矩阵；理解广义表的有关概念及其与线性表的关系。

    考核知识点：串的两种存储表示，串上实现的模式匹配算法及其时间性能分析；稀疏矩阵的存储方法和基本运算的实现(转置、矩阵加法等)；广义表的定义及其求表头和表尾的运算。

    4.树和二叉树的存储结构、遍历算法及应用

    考核要求：掌握树和二叉树的基本定义；熟练掌握二叉树的性质；掌握二叉树的存储结构；掌握遍历二叉树和线索二叉树；理解树和森林的概念以及存储结构；掌握森林与二叉树的转换；理解树和森林的遍历；掌握赫夫曼树及其应用；理解赫夫曼编码。

    考核知识点：二叉树和树的递归定义、基本术语、基本性质、满二叉树和完全二叉树的概念及特征；二叉树、树及森林的顺序存储及链式存储，以及相互转换算法；线索二叉树、二叉排序树的构建；各种遍历算法；哈夫曼树和哈夫曼编码的构建和应用。

    5.图的存储结构、遍历算法及应用

    考核要求：理解图的定义和术语；熟练掌握图的存储结构；熟练掌握图的遍历方法：深度优先搜索和广度优先搜索；理解图的连通性问题；理解无向图的连通分量和生成树；掌握最小生成树；了解有向无环图及其应用；掌握最短路径。

    考核知识点：图的基本概念和术语；图的基本存储方法：邻接矩阵、关联矩阵、邻接表、逆邻接表、十字链表；图的遍历算法：深度优先搜索算法和广度优先搜索算法；图的基本应用：最小生成树、最短路径。

    6.静态查找表、动态查找表和哈希表(包括二叉排序树、AVL树)

    考核要求：熟练掌握静态查找表的顺序表的查找、折半查找、分块查找；掌握动态查找表；掌握二叉排序树；理解平衡二叉树；掌握哈希表；掌握哈希函数的构造方法和处理冲突的方法；了解哈希表的查找及其分析。

    考核知识点：静态查找表、动态查找表和哈希表上的查找方法；哈希函数的基本构造方法，解决地址冲突的基本策略；各类查找算法的时间复杂度和空间复杂度。

    7.五类内部排序算法的算法思想、时间特性及稳定性

    考核要求：五类内部排序方法的基本思想、排序过程、算法实现、时间和空间性能的分析以及各种排序方法的比较和选择。在熟悉这些内容的基础上，掌握五类排序的基本思想及排序过程以及排序算法的实现。

    考核知识点：插入排序、交换排序、选择排序、归并排序和基数排序等五类排序算法的算法思想和时间复杂度；五类排序算法的特性、稳定性及适用情形。

添加上海电力大学学姐微信，或微信搜索公众号“考研派小站”，关注[考研派小站]微信公众号，在考研派小站微信号输入[上海电力大学考研分数线、上海电力大学报录比、上海电力大学考研群、上海电力大学学姐微信、上海电力大学考研真题、上海电力大学专业目录、上海电力大学排名、上海电力大学保研、上海电力大学公众号、上海电力大学研究生招生）]即可在手机上查看相对应上海电力大学考研信息或资源。