数据课程复习考试内容总结.ppt

题 型 填空 选择 问答 算法分析/应用/填空 算法设计 要求内容 数据结构的概念 逻辑结构 物理结构 算法 每一种数据结构的 基本概念和性质 存储结构及定义 典型算法及应用 重要的数据结构 线性结构 顺序表 链表 单链表、双链表、循环单链表 线性结构的应用 栈、队列、字符串 非线性结构 树 树、二叉树 图 有向图、无向图 线性结构(一) 顺序表 逻辑结构 存储结构及数据引用 顺序表的查找、插入、删除算法 线性结构(二) 链表 单链表、双链表的存储结构及数据引用 循环链表 单链表、双链表的查找、插入、删除算法 线性结构(三) 栈 性质和典型操作 栈的顺序表实现 栈的链表实现 栈的应用(算法设计) 队列 性质和典型操作 队列的顺序表实现 队列的链表实现 队列应用(算法设计) 线性结构(四) 串 字符串的定义 字符串的存储结构（参考C语言） 字符串的典型操作 数组 多维数组的存储(一维和二维) 数组的应用(算法设计) 树 树的基本术语 二叉树 定义和性质 存储结构(顺序存储法和二叉链表法) 二叉树的前序、中序和后序遍历(算法及应用) 树 存储结构(双亲法和孩子兄弟法) 树(林)和二叉树的相互转换 树(林)的先序和中序遍历 二叉查找树(查找、插入、删除算法和应用) Huffman树/Huffman编码 AVL树的定义 图 图的术语 图的存储结构(邻接矩阵法和邻接表法) 图的深度优先和广度优先遍历(算法及应用) 图的连通分量和生成树(应用) 图的最小生成树(应用) 拓扑排序(应用) 单源最短路径(原理、应用、计算） 查找 顺序表的查找(顺序查找算法) 有序表的查找(二分/折半查找算法) Hash表的原理 以上各种查找方法的性能分析 排序 掌握以下排序算法的基本思想和性能分析，熟练掌握至少两种排序算法 直接插入排序 希尔排序 起泡排序 快速排序 简单选择排序 堆排序 / 归并排序 * *