2021武汉轻工大学计算机专业基础综合（数据结构、算法基础）专业研究生考试大纲 正文

考试目标：
考察学生对数据结构和算法基础知识和基本技术的理解、掌握情况及运用相关知识和技
术解决实际问题的能力。
考试内容
1. 数据结构基础知识
理解数据、数据元素、数据对象、数据结构和数据类型的定义。掌握数据的逻辑结构和
存储结构及其种类以及算法的重要特征。掌握算法的时间复杂度和空间复杂度的计算方法。
2. 线性表
了解线性表的定义和线性结构的特点。理解线性表的顺序存储和链式存储，理解数组与
单链表表示表的优缺点。掌握顺序表中数据元素的存储位置的计算。掌握顺序表、单链表、
循环链表和双向链表的插入、删除等有关操作。
3. 栈和队列
了解栈和队列的定义和特点。理解线性表、栈和队列特点及区别，栈对实现递归过程的
作用。掌握顺序栈、链栈的入栈和出栈操作，顺序队列、链队列的入队和出队操作，循环队
列的队空和队满的判断。
4. 串
了解串的有关定义。理解串的逻辑结构和存储结构。
5. 数组和广义表
了解数组、特殊矩阵和稀疏矩阵的定义。理解矩阵的压缩存储的概念。掌握矩阵的压缩
存储的有关计算方法。了解广义表的概念和存储结构，掌握广义表表头和表尾操作。 6. 树和二叉树
了解树的定义和二叉树的定义。理解二叉树的性质、二叉树的存储结构。掌握遍历二叉
树的方法、线索二叉树的构造，森林与二叉树的转换，最优二叉树和哈夫曼编码。
7. 图
了解图的定义和术语，以及生成树和最小生成树的概念。理解并掌握图的邻接矩阵和邻
接表表示。掌握深度优先搜索和广度优先搜索算法。会用 Prim 算法和 Kruskal 算法构造最小
生成树，会求拓扑序列、关键路径和最短路径。
8. 查找
了解查找及相关概念。掌握顺序查找、二分查找，了解分块查找。了解二叉排序树和平
衡二叉树、哈希查找相关概念。理解二叉排序树的性质，掌握二叉排序树的查找、插入和删
除操作算法。掌握维护平衡二叉树平衡的方法。掌握相关查找方法的平均查找长度。掌握哈
希函数的构造方法和处理冲突的方法，会用哈希函数、开放地址法或链地址法建立哈希表。 9. 排序
了解排序及相关概念。理解直接插入排序、希尔排序、起泡排序、快速排序、简单选择
排序、堆排序、归并排序和基数排序的基本思想。掌握直接插入排序、希尔排序、起泡排序、
快速排序、简单选择排序、堆排序、归并排序的算法实现和时间复杂度分析。
10. 算法基础知识
理解算法的概念和性质、算法的复杂性概念和分析方法、计算时间的渐近表示及其相关
性质。
11. 递归和分治
理解递归的概念和递归算法的实现机制，掌握设计和分析递归算法的一般方法。理解分
治法的基本思想和适用条件，掌握分治法的效率分析。理解并掌握分治法应用的经典实例。
12. 动态规划
理解动态规划的基本原理和应用条件，理解动态规划的效率分析，理解并掌握动态规划
应用的经典实例。
13. 贪心算法
理解贪心法的基本原理和基本要素，理解贪心算法的效率分析和正确性分析，理解并掌
握贪心法应用的经典实例。
14. 回溯法
理解回溯法的基本思想和剪枝函数的设计，理解回溯法的效率分析，理解并掌握回溯法
应用的经典实例。
15. 分支限界法
理解分支限界法的基本思想，理解队列式分支限界法和优先队列式分支限界法，理解并
掌握分支限界法应用的经典实例。
总分值：150 分
试题形式与结构：1. 名词解释；2. 填空题；3. 选择题；4. 判断题；5. 问答题；6. 应
用题；7. 算法设计题
参考教材： 1、 严蔚敏，吴伟民编著. 数据结构（C 语言版）. 北京: 清华大学出版社，1997.4
2、 严蔚敏等编著. 数据结构题集（C 语言版）. 北京: 清华大学出版社，1999.2 3、 王晓东编著. 计算机算法设计与分析（第 5 版）. 北京：电子工业出版社，2018.8
4、 王晓东编著. 计算机算法设计与分析习题解答（第 5 版）. 北京：电子工业出版社，
2018.10

武汉轻工大学

本文来源：http://www.okaoyan.com/wuhanqinggongdaxue/cankaoshumu_384715.html