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 版) 严蔚敏 李冬梅 吴伟民编 人民邮电出版社

　　感谢您阅读2022年成都信息工程大学专升本数据结构考试大纲，本文出自：诚为径统招专升本网，转载需带上本文链接地址：https://tzzsb.cwjedu.com/ksjc/33290