文华学院普通专升本考试
《数据结构》考试大纲
第一部分 考试说明
一、 考试方法与考试时间
（1）答卷方式：闭卷，笔试
（2）答题时间：120分钟
（3）题型：基本概念：约30%；求解题：约60%；算法设计：约10%
二、主要参考书目
严蔚敏.数据结构（C语言版）.清华大学出版社.
第二部分 考试范围、考试内容及试卷结构
第一章 绪论
一、学习目的与要求
通过本章学习，理解数据结构的基本概念和基本术语，掌握算法的分析方法
二、考核知识点与考核目标
（一）基本概念（次重点）
理解：数据结构研究的内容
识记：数据结构的逻辑结构和物理结构
（二）算法分析（重点）
理解：算法的基本特征
识记：算法分析的方法
第二三四五章 线性表，栈和队列，串，数组
一、 学习目的与要求
通过本章学习，熟悉并掌握线性表、栈、队列、串、数组的逻辑结构、存储结构和对数据的基本运算；
二、考核知识点与考核目标
（一）线性表、栈、队列、串、数组的特征（一般）
识记：理解并掌握线性表、栈、队列、串、数组的基本特点
（二）线性表的存储方法和基本操作（重点）
识记：顺序存储和链式存储，插入和删除一些操作的实现
（三）栈，队列（重点）
识记：栈的实现，循环队列的实现，递归的应用，懂得利用栈和队列的思想实现算法
（四）串和数组（次重点）
理解：串和数组的特征
识记：串的简单模式匹配算法，数组存储地址的运算，稀疏矩阵的三元组表示法
第六章 树和二叉树
一、学习目的与要求
通过本章学习，了解树和二叉树的概念，理解二叉树的表示方法，掌握二叉树的存储方法和遍历算法的实现，掌握树与二叉树的相互转换及哈夫曼树的构造。
二、考核知识点与考核目标
（一）树和二叉树的概念（次重点）
理解：树的概念及特征
识记：二叉树的定、义术语和基本逻辑结构特性；
识记：树与二叉树的相互转换
（二）二叉树的存储和遍历算法（重点）
识记：理解二叉树的遍历算法思想，掌握递归和非递归遍历算法实现
（三）哈夫曼树（重点）
理解：哈夫曼树的特性
识记：哈夫曼树的构造
第七章 图
一、学习目的与要求
通过本章学习，掌握图的基本概念，掌握图的存储结构，掌握图的遍历算法，了解并掌握图的典型应用，如最小生成树、拓扑排序、关键路径、最短路径等。
二、考核知识点与考核目标
（一）图的概念（次重点）
理解：图的逻辑结构
识记：图的一些基本术语，基本特征
（二）图的存储结构，图的遍历算法（重点）
识记：理解并掌握图的存储结构；
识记：掌握图的深度优先和广度优先遍历算法；
（三）图的典型应用（重点）
识记：最小生成树，拓扑排序，最短路径
第八章 查找
一、 学习目的与要求
通过本章学习，理解静态查找表和动态查找表的特征，掌握常见几种查找算法。
二、考核知识点与考核目标
（一）静态查找（重点）
识记：顺序查找、折半查找、分块查找；
（二）动态查找表（重点）
识记：二叉排序树
（三）哈希查找表（重点）
识记：掌握哈希表的概念和查找方法和哈希函数的构造方法，解决冲突的基本方法
第九章 排序
一、 学习目的与要求
通过本章学习，掌握几种常见的排序算法
二、考核知识点与考核目标
（一）插入排序（重点）
识记：直接插入排序，希尔排序
（二）交换思想的排序（重点）
识记：冒泡排序，快速排序
（三）选择排序（重点）
识记：简单选择排序、堆排序；
（三）其他排序（重点）
识记：掌握其它排序算法如：归并排序、基数排序；
识记：能够对各种排序算法进行分析比较
二、试卷结构
（一）、单项选择题
1．数据的最小单位是（ ）。
(A) 数据项 (B) 数据类型 (C) 数据元素 (D) 数据变量
（二）、分析题
设某棵二叉树的中序遍历序列为ABCDEFGHIJK，前序遍历序列为EBADCFHGIKJ，要求画出该二叉树。
（三）、求解题
1．设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为7、19、2、6、32、3、21、10，根据这些频率作为权值构造哈夫曼树，并求其哈夫曼编码。
（四）、补充程序题
1. 下面程序段的功能是利用从尾部插入的方法建立单链表的算法，请在下划线处填上正确的内容。
typedef struct node
{ int data;
struct node *next;
} lklist;
void lklistcreate(_____________ *&head )
{
for (i=1;i<=n;i++)
{
