编辑: xwl西瓜xym | 2015-05-14 |
数组,单链表,双链表,循环链表;
基本运算;
查找,插入,删除 熟练掌握 8+6 栈LIFO,栈顶,栈底;
顺序栈,表达式求值 熟练掌握 4+2 链式栈 掌握 嵌套调用,递归程序转换为非递归程序 了解 队列 FIFO,队头,队尾;
顺序队,循环队;
熟练掌握 4+2 链式队,队的应用 掌握 字符串 存储,运算;
简单模式匹配算法 掌握 4+2 KMP算法 了解 广义表 原子结构,结点,表头,表尾,深度,长度,存储方式 了解
2 矩阵 数组的表示和实现 特殊矩阵和稀疏矩阵的压缩存储,稀疏矩阵的转置运算 掌握 4+4 树型结构 二叉树概念 定义和术语,满二叉树和完全二叉树,五条性质 熟练掌握 14+6 二叉树遍历 先序遍历,中序遍历,后序遍历 熟练掌握 按层次遍历 了解 二叉树存储 顺序存储,二叉链表存储 熟练掌握 二叉树应用 哈夫曼树及哈夫曼编码 熟练掌握 判定树 了解 树和森林 树和森林的定义;
树、森林与二叉树的转换 熟练掌握 树的存储 双亲表示法,孩子表示法,孩子兄弟表示法 了解 图型结构 图的概念 定义,术语,种类,生成树 掌握 10+4 图的存储方法 邻接矩阵,邻接表 熟练掌握 图的遍历 广度优先遍历,深度优先遍历 熟练掌握 DAG 拓扑排序,关键路径 了解 最小生成树 Prim算法,Kruskal算法 掌握 最短路径 Dijkstra算法,Floyd算法 了解 查找与索引 基本概念 查找长度,平均查找长度 掌握 8+4 表结构的查找 顺序查找,二分查找 熟练掌握 分块查找,索引查找 了解 哈希表 基本概念,哈希函数,冲突处理,哈希表的构造,查找算法 熟练掌握 二叉排序树 插入,删除 掌握 平衡树 AVL树 理解 B/B+树 基本概念,插入/删除操作,读盘和写盘次数分析,索引效率分析 了解 内部排序 基本概念 正序,逆序,稳定性,排序方法种类,衡量排序算法的指标 掌握 8+4 插入排序 直接插入排序, 熟练掌握 Shell排序 掌握 交换排序 冒泡排序 熟练掌握 快速排序 掌握 选择排序 直接选择排序 熟练掌握 堆排序 掌握 归并排序 二路归并 掌握 基数排序 顺序基数排序,链式基数排序 理解 排序算法分析 查找和移动次数,时间复杂度和空间复杂度,排序问题的下界 理解 说明:依据当今计算机科学与技术的前沿技术,结合现代数据结构的观点,在教学内容的组织上,应注意以下几点: (1)抽象数据类型ADT适合用C++等面向对象的语言来表达.不用 C 等过程式的语言来描述,以免导致师生们的困惑. (2)线索化二叉树已被摒弃.该部分内容可以作为例题讲解. (3)三元组主要用于有权图输入输出,不宜于矩阵运算. (4)索引技术中,散列和倒排,是非常主流和实用的技术;
B+树是比B树更实用的外存索引,应该重点强调. (5)平衡二叉树的主流为红黑树、伸展树;
AVL树删除操作难于实现和维护,不常用.
2、各章节讲授要求 概述(4+2学时) [教学内容] (1)什么是数据结构:主要讲授数据结构的含义,数据的分类、数据结构的存储方法、数据结构的基本运算 (2)基本概念和术语:主要讲授数据、数据元素、数据对象、数据结构、逻辑结构与存储结构、数据类型和抽象数据类型、算法、语句频度,算法的时间复杂度 (3)抽象数据类型的表示与实现:用一........