数据结构期末考点

一、题型

1. 选择题 20分
2. 综合应用题
   • 平衡二叉树
   • Prim算法
   • 关键路径的选择，最晚发生时间
   • 散列表
3. 编程题 子程序算法

二、章节重点

1. 绪论
   • 算法定义，特征
   • 时间/空间复杂度计算
   • 常用算法的时间复杂度
2. 线性表
   • 概念清晰 头节点 头指针 带尾指针
   • 课后选择 链表编程题 奇偶数
3. 栈/队列
   • 结构：注意入栈/出栈顺序
   • 不出编程
   • 括号匹配 回文
   • 循环队列 rear front
4. 字符串/***数组
   • 模式匹配 KMP匹配 next数组
   • 特殊矩阵的压缩存储 地址变换
   • 三元组不考
   • 选择（算符优先）
5. 树/二叉树
   • 选择
     • 二叉树结点个数 完全/满二叉树结点 求结点数
     • 遍历
   • 编程
     • 前/中/后/层序遍历
     • 结点 树深
     • 非递归不考
     • 哈夫曼树构造
     • 线索二叉树
     • 程序不考
     • 前/中/后画线索二叉树
6. 图
   • 存储结构
   • 图的遍历 深度/广度
   • 判断非连通图有几个连通分量
   • 连通图有无回路
   • 图的四个应用
     • 最小生成树
     • 最短路径
     • 拓扑排序
     • 关键路径 综合题
     • 不考程序
7. 查找
   • 顺序 折半
   • 折半查找判定树
   • 二叉排序树的构造
   • 平衡二叉树的构造
   • 散列
   • 查找：散列表中怎么查找下一个元素 告诉冲突方法 查找方法
8. 排序
   • 初始序列 排序 趟
   • 程序 课后题 6/7