2022年成都信息工程大学专升本数据结构考试大纲

2022年成都信息工程大学专升本数据结构考试大纲

考试内容：

(一) 绪论

1. 数据结构的基本概念和术语;

2. 抽象数据类型(ADT)的概念;

3. 算法的时间复杂性和空间复杂性分析方法。

(二) 线性表

1. 线性表的逻辑结构特性和线性表的抽象数据类型(ADT)的设 计;

2. 线性表的顺序存储结构和链式存储结构实现方法;

(1) 顺序表的创建、查找、插入和删除等基本操作及相关算法;

(2) 单链表的创建、查找、插入和删除等基本操作及相关算法;

(3) 双向链表的插入和删除等基本操作及相关算法;

(4) 循环链表的特点及创建、查找、插入和删除等基本操作及相关算法

3. 一元多项式的表示方法及相加算法。

(三) 栈与队列

1. 栈与队列的定义、 操作特点;

2. 栈、队列(包括循环队列) 的表示和基本操作的实现。

3.栈和队列在表达式求值、括号匹配、数制转换、 舞伴问题中的应用。

(四) 树和二叉树

1.二叉树的定义、结构特点和性质;

2. 二叉树的设计和实现： 二叉树存储结构的特点， 三种遍历方式 的递归算法，二叉树的线索化过程和算法;

3. 树的设计和实现、树的各种表示方法及基本术语， 树和森林与 二叉树的转换方法; 4. 哈夫曼树的构造算法、哈夫曼编码。

(五) 图

1. 图的定义、术语和性质;

2.图的设计和实现：

(1) 图的邻接矩阵、邻接表的存储结构及其构造方法;

(2) 图的两种遍历方法：深度优先遍历和广度优先遍历;

3.图的应用：

(1) 最小生成树的算法;

(2) 构造最短路径的 Dijkstra 算法和 Floyd 算法。

(六) 查找

1.查找的基本概念

2. 线性表的查找

(1) 顺序查找算法

(2) 折半查找算法

(3) 分块查找算法

3.树表的查找

(1) 二叉排序树的定义和基本操作(创建、插入、删除、查找);

(2) 平衡二叉树的定义、平衡调整方法

4.Hash 表的查找

(1) Hash 查找的基本概念;

(2) Hash 函数的构造方法、处理冲突的方法;

(3) Hash 表的查找算法

(七) 排序

1.排序的基本概念

2. 插入排序

(1) 直接插入排序算法

(2) 折半插入排序算法

(3) 希尔排序算法

3.交换排序

(1) 冒泡排序

(2) 快速排序

4.选择排序

(1) 简单选择排序

(2) 堆排序

考试题型：

1.选择 ( 10 分)

2.判断 ( 10 分)

3.应用题

4.算法设计

(20 分)

(10 分)

参考书目：

1.《数据结构》(C 语言版) 严蔚敏 吴伟民编 清华大学出版社

2.《数据结构》(C 语言版|第 2 版) 严蔚敏 李冬梅 吴伟民编 人民邮电出版社