2025年西安工程大学硕士研究生入学考试大纲
考试科目名称：数据结构 考试科目代码：[843]
一、考试要求
数据结构讲授数据逻辑结构、存储结构以及操作算法等基本知识的专业核心课程。要求学生理解数据结构、算法的基本概念，掌握三大数据结构（线性表、树和图）的逻辑结构、存储结构以及基本运算算法；掌握常用的查找和排序算法及其性能分析；学会分析数据对象的特征，能够针对具体应用问题选择适当的数据结构及相应算法，并掌握算法时间空间分析的技巧和复杂程序设计基本技能。
二、考试内容
1.绪论
² 数据结构的基础概念（数据、数据元素、数据对象、数据结构、数据类型、抽象数据类型）
² 数据结构的内容（逻辑结构、存储结构、运算集合）
² 算法及算法的性能评价（语句频度、时间复杂度、空间复杂度）
² 数据结构与C语言表示
2.线性表
² 线性表的概念及其抽象数据类型定义
² 线性表的顺序存储结构及顺序表的基本运算
² 线性表的链式存储
1) 单链表及单链表的基本运算
2) 循环链表
3) 双向链表
4) 静态链表
² 线性表的应用——一元多项式的表示及相加
² 顺序表与链表的综合比较
3.限定性线性表——栈和队列
² 栈的定义
² 栈的表示及实现（顺序栈、双向栈、链式栈）
² 栈的应用
² 栈与递归的实现
² 队列的定义
² 队列的表示及实现（顺序队列、循环队列、链式队列）
² 队列的应用
4.串
² 串的基本概念
² 串的存储实现（定长顺序串、堆串、块链串）
² 串的简单模式匹配算法Brute-Force(布鲁特-福斯)算法
² 串的应用
5.数组与广义表
² 数组的定义
² 数组的顺序存储与实现
² 特殊矩阵的压缩存储（三角矩阵、带状矩阵、稀疏矩阵）
² 广义表的概念
² 广义表的存储结构
² 广义表的操作实现
6.树与二叉树
² 树的定义及基本术语
² 二叉树的定义与基本操作
² 二叉树的性质
² 二叉树的存储结构（二叉链表）
² 二叉树的遍历及线索化
1) 二叉树的遍历
2) 遍历算法的应用
3) 基于栈的递归消除
4) 线索二叉树
5) 由遍历序列确定二叉树
² 树的存储结构
² 树、森林与二叉树的相互转换
² 树和森林的遍历
² 哈夫曼树及其应用
1) 哈夫曼的概念和建立算法
2) 哈夫曼编码的算法
7.图
² 图的定义与基本术语
² 图存储结构
1) 邻接矩阵
2) 邻接表
3) 十字链表
4) 邻接多重表
² 图的遍历
1) 深度优先搜索
2) 广度优先搜索
² 图的应用
1) 图的连通性问题（无向图的连通分量、图中两个顶点之间的简单路径、图的生成树与最小生成树、普里姆算法、克鲁斯卡尔算法）
2) 有向无环图的应用（拓扑排序、关键路径）
3) 最短路径（迪杰斯特拉算法、佛罗伊德算法）
8.查找
² 查找的基本概念
² 基于线性表的查找方法
1) 顺序查找法
2) 折半查找法
3) 分块查找法
² 基于树的查找方法
1) 二叉排序树
2) 平衡二叉排序树
3) B树
² 计算式查找法——哈希法
1) 哈希函数的构造方法
2) 处理冲突的方法
3) 哈希表的查找
4) 哈希法性能分析
9.内部排序
² 排序的基本概念
² 插入类排序
1) 直接插入排序
2) 折半插入排序
3) 希尔排序
² 交换类排序
1) 冒泡排序
2) 快速排序
² 选择类排序
1) 简单选择排序
2) 树形选择排序
3) 堆排序
² 归并排序
² 分配类排序
1) 多关键字排序
2) 链式基数排序
3) 基数排序的顺序表实现
² 各种排序方法综合比较
10.算法设计与分析
² 递归与分治（递归方法设计、分治法）
² 回溯法
² 分支限界法
² 贪心算法
² 动态规划法
参考书目：
《数据结构－C语言描述》，耿国华，高等教育出版社，2015年。
《数据结构与算法》，赵仲孟，高等教育出版社，2016年。
