总复习(最新)

数据结构 2012年秋季 课程总复习 各部分比重分布各章重要知识点题型考试安排 课程各部分内容比重分布 Chapter1程序性能 重要知识点 本章重要知识点 算法的性能分析与度量程序 算法 的时间复杂性操作计数 Chapter1程序性能 重要复习题 本章重要复习题P381 10P391 12 1 13 Chapter2线性表 重要知识点 本章重要知识点什么是线性结构公式化描述与链表描述的含义线性表的公式化描述 顺序表特性 操作 插入 删除 搜索线性表的链表描述 链表 重点 单链表双向链表 循环链表操作 插入 删除 搜索 合并 拆分 逆置等 Chapter2线性表 本章重要算法 程序 顺序表类顺序表的基本操作单链表类单链表的基本操作循环链表 查找 双向链表 定义 Chapter2线性表 1 顺序存储与链式存储的比较与区别2 区别带表头节点和不带表头节点的链表结构 为了避免把空链表作为特殊情况处理使用头节点后 每个链表至少包含一个节点 头节点 3 各种链表结构的区别4 链表合并 拆分 逆置等算法 Chapter2线性表 重要复习题 本章重要复习题P832 2P842 4P862 15 2 22 Chapter3栈和队列 重要知识点 栈重要知识点栈结构的特性 LIFO栈的公式化描述 顺序栈 重点 栈的链式描述 链栈描述操作 入栈 出栈 取栈顶元素 栈空 栈满等栈的应用括号匹配表达式求值 Chapter3栈和队列 重要算法 栈重要算法顺序栈及操作链栈及操作括号匹配算法 Chapter3栈和队列 重要知识点 队列重要知识点队列结构的特性 FIFO队列的公式化描述 循环队列 重点 队列的链式描述 链队列描述操作 入队列 出队列 取队头元素 队空 队满等 Chapter3栈和队列 重要算法 队列重要算法循环队列及操作链队列及操作 Chapter3栈和队列 重要复习题 本章重要复习题P1323 7 3 16P1333 22 Chapter4数组和矩阵 串不考 本章重要知识点二维数组的一维存储 行优先 列优先 计算元素位置特殊矩阵的压缩存储对角 三对角 带状 上 下 三角 对阵矩阵注意下标的起止值行 列 对角线优先映射公式稀疏矩阵的压缩存储三元组顺序表转置操作 Chapter4数组和矩阵 重要复习题 本章重要复习题P1834 1 4 2 Chapter5二叉树和树 Huffman 堆 重要知识点 本章重要知识点非线性结构树结构的特性二叉树 满二叉树 完全二叉树的定义二叉树的特性及证明方法 注意特性 二叉树的顺序存储二叉树的链式存储 二叉链表二叉树的遍历及遍历的应用树的二叉链表表示形式 Chapter5二叉树和树 Huffman 堆 重要知识点 堆堆的定义 判断堆的 初始化及插入 删除算法堆排序Huffman树及Huffman算法Huffman树的定义及性质带权路径长度 WPL Huffman算法Huffman编码 Chapter5二叉树和树 Huffman 堆 重要程序 本章重要程序二叉链表类二叉树的操作二叉树遍历的应用 高度 交换 前序和中序或中序和后序唯一确定一棵二叉树表达式二叉树 前缀 中缀 后缀树的二叉树描述左孩子 右兄弟表示法转换方法 Chapter5二叉树和树 Huffman 堆 重要程序 最小 大 堆类最小 大 堆的插入 删除及复杂度分析初始化非空最大堆堆排序及性能分析Huffman树的建立 Chapter5二叉树和树 Huffman 堆 重要复习题 本章重要复习题P2465 6 5 7P2475 9 5 16P2485 17 5 18 5 19 5 20 Chapter6集合 字典散列 重要知识点 本章重要知识点字典结构的特点散列 重点 散列函数什么是冲突 冲突解决方案 开散列散列表搜索 Chapter6集合 字典散列 重要复习题 本章重要复习题P2956 9 Chapter7搜索结构 本章重要知识点二叉搜索树 BST树 二叉搜索树定义 特点在二叉搜索树中搜索元素的算法平均搜索长度的计算 ASL二叉搜索树的插入 删除AVL树定义 特点平衡化旋转的方法 Chapter7搜索结构 本章重要程序二叉搜索树类二叉搜索树树的搜索 插入二叉搜索树的删除AVL树的构造及四种平衡化旋转的方法 Chapter7搜索结构 重要复习题 本章重要复习题P3427 2 7 3 对画判定树不做要求 P3427 8P3437 14 7 15 Chapter8图 本章重要知识点图的基本概念路径 连通分量 生成树图的类型无向图 有向图 加权图 网 每种图的基本特性图的表示方法及特点邻接矩阵 邻接链表图的遍历及应用DFSBFS Chapter8图 本章重要算法 遍历 搜索邻接矩阵的GetFirstNeighbor GetNextNeighbor函数邻接链表的GetFirstNeighbor GetNextNeighbor函数BFS实现DFS实现最小生成树Kruskal算法Prim算法最短路径拓扑排序 AOV网络 Chapter8图 重要复习题 本章重要复习题P3928 1 8 2 8 3 8 4 8 6 8 7 8 10 8 10P3958 24 Chapter9排序