B212CC: 数据结构与算法 课程描述 0 课程基本信息 课程编号 : B212CC 课程名称 : 数据结构与算法英文名称 : Data Structures and Algorithms 英文简称 : DSA 预备课程 : 计算系统基础 离散数学授课时间 : 二年级第一学期时间分配 : 课堂教学 (48 课时 )+ 实验安排 (48 课时 )+ 课后作业与阅读 (48 课时 ) 学分数 : 3 1 课程简介 本课程是软件工程专业的专业基础课程 主要内容包括常用的抽象数据类型 ( 表 串 栈 队列 树 图 ) 及其相关操作, 常用的基本算法 ( 查找和排序 ) 算法策略 ( 穷举 贪婪 分治和回溯 ) 和算法分析 ( 包括时间和空间复杂性分析 ), 以及递归和常用的递归算法 通过本课程的学习, 学生能够较为全面地掌握各种常用的数据结构及其算法, 能够为实际问题选择合适的数据结构及其算法 2 教材与参考资料 2.1 教材与指定阅读材料 1) Mark Allen Weiss, Data Structures and Algorithm Analysis in Java (Second Edition), Pearson Education, 2007 2.2 参考资料 1) 殷人昆等, 数据结构 ( 用面向对象方法与 C++ 描述 ), 清华大学出版社,1999 2) Sartaj Sahni, Data Structures, Algorithms, and Applications in C++, McGraw-Hill, 1998 3 教学目标 通过本课程的学习, 学生应该能够 : 1) 掌握表 串 栈 队列等数据结构的抽象数据类型描述及其相关操作 ; 2) 掌握树 图等数据结构抽象数据类型描述, 以及二叉树的遍历 线索二叉树, 图的遍历 生成树 最短路径 拓扑排序 关键路径等算法 ; 3) 掌握常用的查找和排序算法 ; 4) 掌握递归知识和常用的递归算法 ; 5) 初步掌握算法的时间复杂性与空间复杂性的分析 ; 6) 初步掌握基本的算法策略, 如穷举 贪婪 分治和回溯等 ; 7) 学会分析问题, 组织数据结构, 设计良好算法, 解决实际应用问题 附录 B 第 35 页
4 相关知识体系 编号 描述 k, c, a E, D, O 学时 CSE-PF.fds.0 基本数据结构 26 CSE-PF.fds.1 基本类型 c E * CSE-PF.fds.2 记录 c E * CSE-PF.fds.3 数组 c E * CSE-PF.fds.4 字符串和字符串处理 c E * CSE-PF.fds.5 数据在存储器中的表示 c E * CSE-PF.fds.6 静态分配 栈式分配和堆式分配 c E * CSE-PF.fds.7 运行时的存储器管理 c E * CSE-PF.fds.8 指针和引用 c E * CSE-PF.fds.9 链式结构 c E 2 CSE-PF.fds.10 栈和队列的基本概念 c E 1 CSE-PF.fds.11 栈和队列的顺序存储结构 c E 1 CSE-PF.fds.12 栈和队列的链式存储结构 c E 1 CSE-PF.fds.13 栈和队列的应用 c E 1 CSE-PF.fds.14 特殊矩阵的压缩存储 c E 1 CSE-PF.fds.15 散列的概念, 散列函数, 散列表 c E 1 CSE-PF.fds.16 树的概念 c E 1 CSE-PF.fds.17 二叉树 ( 二叉树的定义及其主要特征 二叉树的顺序存储结构和链式存储结构 二叉树的遍历 线索二叉树的基本概念和构造 二叉排序 树 平衡二叉树 ) CSE-PF.fds.18 树 森林 ( 树的存储结构 森林与二叉树的转换 树和森林的遍历 ) CSE-PF.fds.19 树的应用 ( 等价类问题 哈夫曼树和哈夫曼编码 ) CSE-PF.fds.20 图的概念 c E 1 CSE-PF.fds.21 图的存储及其基本操作 ( 邻接矩阵法 邻接表法 ) c E 2 CSE-PF.fds.22 图的遍历 ( 深度优先搜索 广度优先搜索 ) c E 2 CSE-PF.fds.23 图的基本应用及其复杂度分析 ( 最小 ( 代价 ) 生成树 最短路径 拓扑排序 关键路径 ) c E 2 CSE-PF.rec.0 递归 3 CSE-PF.rec.1 递归的概念 c E * CSE-PF.rec.2 递归数学函数 c E * CSE-PF.rec.3 递归过程 c E 1 CSE-PF.rec.4 递归的实现 c E 1 CSE-PF.alg.0 算法和问题求解 3 CSE-PF.alg.1 问题求解策略 a O * CSE-PF.alg.2 问题求解算法 a O 1 CSE-PF.alg.3 算法实现策略 a O 1 CSE-PF.alg.4 测试策略 a O * CSE-PF.alg.5 算法的概念和特性 a O * CSE-AL.fal.0 基本算法 10 附录 B 第 36 页
CSE-AL.fal.1 查找的基本概念 c E * CSE-AL.fal.2 顺序查找算法和折半查找算法 c E * CSE-AL.fal.3 B- 树 c E 1 CSE-AL.fal.4 二叉查找树 c E 1 CSE-AL.fal.5 散列表及其查找 c E 2 CSE-AL.fal.6 查找算法的分析及应用 c E * CSE-AL.fal.7 排序的基本概念 c E * CSE-AL.fal.8 插入排序 ( 直接插入排序 折半插入排序 ) c E 1 CSE-AL.fal.9 冒泡排序 (bubble sort) c E * CSE-AL.fal.10 简单选择排序 c E 1 CSE-AL.fal.11 希尔排序 (shell sort) c E 1 CSE-AL.fal.12 复杂度为 O(N*LogN) 排序算法 ( 快速排序 堆排序 归并排序 ) c E 1 CSE-AL.fal.13 基数排序 c E 1 CSE-AL.fal.14 各种内部排序算法的比较 c E * CSE-AL.fal.15 内部排序算法的应用 c E * CSE-AL.ala.0 算法分析基础 4 CSE-AL.ala.1 复杂性上界和平均复杂度的渐近分析 c E 1 CSE-AL.ala.2 最佳 最差和平均情况下的复杂度差异 c E * CSE-AL.ala.3 大 O 小 O Ω 和 θ 符号 c E * CSE-AL.ala.4 标准复杂度类 c E * CSE-AL.ala.5 性能的经验度量 c E * CSE-AL.ala.6 算法时间 空间复杂度的权衡 c E 1 CSE-AL.ala.7 用递归关系分析递归算法 c E 1 CSE-AL.als 算法策略 4 CSE-AL.als.1 穷举 a O 1 CSE-AL.als.2 贪婪 a O 1 CSE-AL.als.3 分治 a O 1 CSE-AL.als.4 回溯 a O 1 5 教学补充事项 5.1 对前驱课程的教学需求通过 计算与软件工程 I 课程的学习, 学生能够掌握程序设计的基本方法与技巧 通过 离散数学 课程的学习, 学生能够掌握图论的有关基础知识 5.2 本课程的教学考虑课程内容的教学既要强调数据结构和算法的实现, 提高学生的程序设计能力, 又要联系相关实例, 培养学生对知识的实际运用能力 5.3 对后续课程的教学建议 数据库系统 操作系统 等后继课程结合各自的需要, 进行各种数据结构和算法的实现, 通过实际应用加深学生对所相关数据结构和算法的理解 附录 B 第 37 页
6 教学计划 序号 主题 内容 课时 相关知识体 基本类型, 记录, 数组, 字符串和字符串处理, 1 概述 数据在存储器中的表示, 静态分配 栈式分配 CSE-PF.fds.1~8 3 和堆式分配, 运行时的存储器管理, 指针和引 CSE-PF.rec.1~3 用, 递归的概念, 递归数学函数, 递归过程 2 算法与问问题求解策略, 问题求解算法, 算法实现策略, 题求解测试策略, 算法的概念和特性 3 CSE-PF.alg.1~5 复杂性上界和平均复杂度的渐近分析, 最佳 最差和平均情况下的复杂度差异, 大 O 小 o 3 算法分析 Ω 和 θ 符号, 标准复杂度类, 性能的经验度量, 算法时间 空间复杂度的权衡, 用递归关系分析递归算法 4 CSE-AL.ala.1~7 4 5 6 7 散列 8 图 线性表 栈 队列 树与二叉树 查找与排序 线性表 栈和队列的 ( 基本概念, 顺序存储结构, 链式存储结构, 应用 ), 特殊矩阵的压缩存储, 递归的实现树的概念, 二叉树 ( 二叉树的定义及其主要特征 二叉树的顺序存储结构和链式存储结构 二叉树的遍历 线索二叉树的基本概念和构造 二叉排序树 平衡二叉树 ), 树 森林 ( 树的存储结构 森林与二叉树的转换 树和森林的遍历 ), 树的应用 ( 等价类问题 哈夫曼树和哈夫曼编码 ) 查找的基本概念, 顺序查找算法和折半查找算法,B- 树, 二叉查找树, 查找算法的分析及应用 ; 排序的基本概念, 插入排序 ( 直接插入排序 折半插入排序 ), 气泡排序 (bubble sort), 简单选择排序, 希尔排序 (shell sort), 快速排序, 堆排序, 二路归并排序 (merge sort), 基数排序, 各种内部排序算法的比较散列的概念, 散列函数, 散列表, 散列表及其查找, 解决冲突的方法 图的概念, 图的存储及其基本操作 ( 邻接矩阵法 邻接表法 ), 图的遍历 ( 深度优先搜索 广度优先搜索 ), 图的基本应用及其复杂度分析 ( 最小 ( 代价 ) 生成树 最短路径 拓扑排序 关键路径 ) 8 CSE-PF.fds.9~14 CSE-PF.rec.4 10 CSE-PF.fds.16~19 9 3 CSE-AL.fal.1~4 CSE-AL.fal.6~15 CSE-PF.fds.15 CSE-AL.fal.5 7 CSE-PF.fds.20~23 9 算法策略算法策略 ( 穷举, 贪婪, 分治, 回溯 ) 4 CSE-PF.als.1~4 7 实验 7.1 实验目标通过实验使学生掌握 分析问题 构筑解题框架 具体编程 上机调试 的解题过程 7.2 实验内容实验一 : 递归实现从 n 个自然数中取 r 个数的所有组合 ; 实验二 : 用递归或非递归实现 hanoi 塔 ; 附录 B 第 38 页
实验三 : 用链表实现多项式相加 ; 实验四 : 用数组或链表实现 Josephus(n, m) 问题 ; 实验五 : 用一趟扫描实现由中缀表达式到后缀表达式的转换, 再对后缀表达式求值 ; 实验六 : 建立一棵二叉树, 并输出先序 中序 后序遍历结果 ; 实验七 : 判别一个有向图中是否有环路, 并把所有环路打印出来 7.3 指导方式首先在课堂上讲清问题的要求 与同学一起分析解题的思路 ; 1) 课后由同学独立思考, 也可以小组讨论 接着编程 上机调试 ; 2) 助教最后一对一的检查每个同学的每个实验结果, 最后进行总结 8 课后作业 课后作业应该包含 : 1) 线性表的定义与基本操作 ; 2) 栈和队列的基本概念 栈和队列的顺序存储结构 栈和队列的链式存储结构 栈和队列 的应用 ; 3) 二叉树的顺序存储结构和链式存储结构 二叉树的遍历 线索二叉树的基本概念和构造 二叉排序树 平衡二叉树 ; 4) 树的存储结构 森林与二叉树的转换 树和森林的遍历 ; 5) 哈夫曼 (Huffman) 树和哈夫曼编码 ; 6) 图的存储及基本操作 ( 邻接矩阵法 邻接表法 ), 图的遍历 ( 深度优先搜索 广度优先搜 索 ), 图的基本应用及其复杂度分析 ( 最小生成树 最短路径 拓扑排序 关键路径 ); 7) 顺序查找法, 折半查找法,B- 树, 散列 (Hash) 表及其查找, 查找算法的分析及应用 ; 8) 插入排序, 直接插入排序, 折半插入排序, 气泡排序 (bubble sort), 简单选择排序, 希 尔排序 (shell sort), 快速排序, 堆排序, 二路归并排序 (merge sort), 基数排序 9 评分体系 笔试 60%+ 实验 30%+ 课后作业 10% 附录 B 第 39 页