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年。