2021通化师范学院专升本数据结构课程考试大纲(试行)

　　2021年通化师范学院专升本招生

　　数据结构课程考试大纲(试行)

　　一、考试内容

　　数据结构知识点难易程度及所占比例

　　1.数据结构基本概念及简单的算法分析

　　(1)数据结构部分：

　　a.掌握数据结构基本概念;

　　b.了解抽象数据类型;

　　c.理解逻辑结构与存储结构。

　　(2)算法部分：

　　a.了解算法的定义及算法的特性;

　　b.掌握算法的性能分析与度量方法。

　　2.线性表

　　(1)掌握线性表的定义及实现。

　　(2)掌握单链表和循环链表的定义及实现。

　　(3)理解双向链表的定义。

　　(4)掌握顺序表的定义。

　　(5)掌握顺序表的查找、插入和删除算法的实现。

　　3.栈和队列

　　(1)理解栈的逻辑结构与应用。

　　(2)掌握顺序栈的表示和操作的实现。

　　(3)理解队列的逻辑结构与应用。

　　(4)掌握链队列的表示和操作的实现。

　　4.串和数组

　　(1)理解串的应用。

　　(2)掌握串的表示和实现。

　　(3)掌握数组的定义。

　　(4)掌握数组的顺序表示和实现。

　　5.树和二叉树

　　(1)树部分：

　　a.掌握树的定义和基本概念;

　　b.掌握树的遍历;

　　c.理解树的存储结构。

　　(2)二叉树部分：

　　a.掌握二叉树的定义和基本形态;

　　b.掌握斜树、满二叉树、完全二叉树的特征;

　　c.掌握二叉树的基本性质;

　　d.掌握二叉树的遍历及构造;

　　e.了解二叉树的存储结构及实现。

　　(3)了解树、森林和二叉树的转换。

　　(4)掌握哈夫曼树及哈夫曼编码的构造。

　　6.图

　　(1)掌握图的定义、基本术语。

　　(2)掌握图的深度优先遍历和广度优先遍历。

　　(3)图的应用：

　　a.了解最小生成树;

　　b.了解拓扑排序;

　　c.理解单源点最短路径;

　　d.理解关键路径。

　　7.查找

　　(1)掌握查找的基本概念。

　　(2)掌握线性表的顺序查找、折半查找的实现。

　　(3)理解二叉排序树的基本概念及其查找算法。

　　(4)了解哈希查找的基本概念及哈希函数的构造方法，了解哈希查找算法。

　　8.排序

　　(1)理解排序的基本概念。

　　(2)掌握基本排序方法：冒泡排序、直接插入排序。

　　(3)了解快速排序、归并排序、堆排序。

　　二、试卷结构

　　考试题型为单项选择题、判断题、填空题，基础应用题、算法实现题，满分100分。