2020年成都信息工程大学专升本计算机类（数据结构）考试大纲

考试说明：计算机类综合考试总分 100 分，包括《 C 语言程序设计》和《 数据结构 》，每门课程各占 50 分。考试时间总计 120 分钟。

考试内容：

(一）绪论

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

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

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

(二）线性表

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

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 、选择( 1 0 分)

2 、判断( 1 0 分)

3、应用题 （20 分)

4、 算法设计( 10 分)

参考书目：

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

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

想要获得更多资讯，点击”专升本社区“你就知道！