2024年新葡萄8883官网AMG硕士研究生入学考试大纲

2024年新葡萄8883官网AMG硕士研究生入学考试大纲

考试科目名称：数据结构         考试科目代码：[924]

一、 考试要求

数据结构是讲授数据逻辑结构、存储结构以及操作算法等基本知识的课程。要求学生理解数据结构、算法的基本概念，掌握三大数据结构（线性表、树和图）的逻辑结构、存储结构以及基本运算算法；掌握常用的查找和排序算法及其性能分析；学会分析数据对象的特征，能够针对具体应用问题选择适当的数据结构及相应算法，初步掌握算法时间空间分析的技巧和复杂程序设计基本技能。

二、 考试内容

1. 绪论

² 数据、数据元素、数据对象、数据结构、数据类型、抽象数据类型

² 数据结构的研究内容：逻辑结构、存储结构、运算集合

² 算法、算法的性能评价、语句频度、时间复杂度、空间复杂度

2. 线性表

² 线性表的概念及其抽象数据类型定义

² 线性表的顺序存储结构及顺序表的基本运算

² 线性表的链式存储

1) 单链表及单链表的基本运算

2) 循环链表

3) 双向链表

² 顺序表与链表的综合比较

3. 栈、队列和数组

² 栈的定义

² 栈的表示及实现：顺序栈、双向栈、链式栈

² 栈与递归的实现：递归、递归算法设计

² 队列的定义

² 队列的表示及实现：顺序队列、循环队列、链式队列

² 二维数组的顺序存储结构：行优先存储、列优先存储

² 特殊矩阵的压缩存储：三角矩阵、带状矩阵、稀疏矩阵

4. 树和二叉树

² 树的定义及基本术语

² 二叉树的定义与基本操作

² 二叉树的性质

² 二叉树的存储结构：二叉链表

² 二叉树的遍历及线索化

1) 二叉树的先序、中序和后序遍历

2) 线索二叉树及其操作

3) 由遍历序列确定二叉树

² 树的存储结构

² 树、森林与二叉树的相互转换

² 哈夫曼树及其应用

1) 哈夫曼树概念和建立算法

2) 哈夫曼编码、前缀编码

3) 带权路径长度WPL

5. 图

² 图的定义与基本术语

² 图存储结构：邻接矩阵、邻接表

² 图的遍历

1) 深度优先搜索

2) 广度优先搜索

² 图的应用

1) 图的连通性问题：最小生成树、普里姆算法、克鲁斯卡尔算法

2) 有向无环图的应用：拓扑排序、关键路径

3) 最短路径：迪杰斯特拉算法

6. 查找

² 查找的基本概念

² 基于线性表的查找方法

1) 顺序查找法

2) 折半查找法

3) 分块查找法

² 基于树的查找方法：二叉排序树

² 计算式查找法——哈希法

1) 哈希函数的构造方法

2) 处理冲突的方法

3) 哈希表的查找

4) 哈希法性能分析

7. 内部排序

² 排序的基本概念

² 插入类排序

1) 直接插入排序

2) 折半插入排序

3) 希尔排序

² 交换类排序

1) 冒泡排序

2) 快速排序

² 选择类排序

1) 简单选择排序

2) 树形选择排序

3) 堆排序

² 归并排序

² 各种排序方法综合比较

三、 参考书目

[1]《数据结构－C语言描述》，耿国华，高等教育出版社，2015年，第二版。

[2]《数据结构与算法》，赵仲孟，高等教育出版社，2016年。