《数据结构》专升本考试大纲12年2月.docVIP

《数据结构》考试大纲 考核知识点 绪论 数据结构的定义 数据结构有关的概念和术语 数据、、、的 线性表的 线性链表 存储特点，结点结构，线性表的单链表存储结构描述 线性表的常用操作（构造空表、求表长、判表空、取指定位置的元素值、表元素插入、表元素删除、遍历表）在单链表上的实现 表元素插入、删除的算法分析 循环链表 存储特点 双向链表 存储特点，结点结构，线性表的双向链表存储结构描述 双向链表上的表元素插入、删除算法 第三章 栈和队列 栈的概念，特点，抽象数据类型栈的定义 栈的顺序表示和实现，栈的链接表示和实现 栈的典型应用 数制转换 括号匹配的检验 表达式求值 栈与递归 队列的概念，特点，抽象数据类型队列的定义 队列的顺序表示和实现，队列的链接表示和实现 第四章 串 串类型的定义 串的定义，特点，串的抽象数据类型定义 串的表示和实现 定长顺序存储表示 堆分配存储表示 块链存储表示 串的模式匹配定义 第五章 数组和广义表 数组 定义，特点 数组元素存储位置的计算 广义表的定义，特点 第六章 树和二叉树 树的定义及有关概念 树定义 结点，度，根结点，叶结点，分支结点，父结点，子女结点，结点层次，树的高度，森林等概念 抽象数据类型树的定义 二叉树 二叉树的定义 二叉树的性质 抽象数据类型二叉树的定义 二叉树的存储结构 二叉树的遍历 线索化二叉树 树和森林 树的存储结构 树和森林的遍历 树和森林与二叉树的转换 赫夫曼树及其应用 赫夫曼树的定义 赫夫曼树的构造 赫夫曼编码 第七章 图 图的定义及有关概念 图定义 顶点，弧，有向图，无向图，完全图，邻接点，关联，度，路经，回路，简单路径，连通，连通分量，强连通图，生成树等概念。 抽象数据类型图的定义 图的存储结构 邻接矩阵 邻接表 图的常用运算 图的遍历 无向图的连通分量和生成树，最小生成树（Prim算法和Kruskal算法） 有向无环图及其应用 最短路径（dijkstra 算法floyd 算法 动态查找表 二叉排序树 平衡二叉树 哈希表 哈希表定义 构造方法 冲突处理方法 哈希表的查找 第九章 排序 排序的概念 定义 稳定性 常用的排序算法 直接插入排序 二分法插入排序 简单选择排序 冒泡排序 希尔排序 快速排序 堆排序 归并排序 基数排序 各类内部排序方法的特点 时间复杂度 空间复杂度 稳定性 试卷题型及分值分布（满分150分） 单项选择题（30分）、填空题（30分）、判断题（20分）、应用题（40分）、综合算法题（30分） 参考教材 《数据结构（C语言））》，主编：严蔚敏，清华大学出版社 1 1