1、福 州 理 工 学 院教 案 课 程 名 称数据结构与算法设计 系 （部）信息工程系教 研 室计算机授 课 教 师黄取治职 称讲师附件2： 教 案（首页）课程名称数据结构与算法设计学 分总计 ： 学时讲授： 学时上机： 学时实验/训： 学时其它： 学时类 别（请打）公共课公共选修课专业基础课专业必修课专业方向选修课实验实训课（仅限本科）公共课公共选修课专业基础课专业必修课专业选修课实验实训课（仅限高职）授课对象（请打）本科 高职 其他使用教材参考资料（注明书名、主编、出版社、出版时间）教学方法教学手段考核方式学生创新精神与实践能力的培养方法 数据结构与算法设计 课程教案（续页）授课时间第 1
2、周 授课方式（请打）讲授 上机 实验/训 其它课时安排授课题目（章节或单位课时）：第一章 绪论教学目的与要求（分了解、熟悉、掌握三个层次）：1.了解数据结构课程的重要性和课程的基本要求，以及本课程涵盖的内容；2. 掌握数据结构的基本概念；3. 理解算法描述和简单的算法分析。教学重点与难点：1. 重点是数据结构的基本概念2. 难点是时间复杂度分析教 学 内 容备 注1. 从后序课（数据库、操作系统、编译原理、人工智能）的需要和考研两方面介绍数据结构课程的重要性。2. 通过三个例子讲解数据结构研究的内容。3. 介绍基本概念：数据的三个层次，数据结构的三个要素，数据结构的分类，四种存储结构，抽象数据
3、类型，算法，算法的五个特性，对算法设计的要求，算法描述和算法分析，时间复杂度和空间复杂度。4. 从“百钱买百鸡”(“一百元钱买一百支笔”)的算法例子说明选择算法的重要性：方案1： for( i = 0; i =100; i+) for( j = 0; j =100; j+) for( k= 0; k =100; k+) if(i+j+k=100 &3*i+2*j+0.5*k=100) printf(“i=%d，j=%d，k=%d”,i,j,k) 方案2： for( i = 0; i =20; i+) for( j = 0; j =34-i; j+) if(3*i+2*j+(100-i-j) *
4、0.5=100) printf(“i=%d,j=%d,k=%d”,i,j, 100-i-j);方案1 内层循环超过100万次，在某机器上运行了50分钟；方案2 的if语句执行525次，运行了2秒钟，相差1500倍。5. 算法分析举例（1）常量阶：时间复杂度为O(1)+x; s=0;语句频度为1，时间复杂度为O(1)。for(j=1;j=10000;+j)+x; s+=x;语句频度为10000，时间复杂度为O(1)。（2）对数阶：时间复杂度为O(logn)s=0;for(j=1; j=n; j*=2)s+;语句频度为logn，所以时间复杂度为O(logn)。（3）线性阶：时间复杂度为O(logn
5、)S=0;for(j=1;j=n;+j)s+;语句频度为n，所以时间复杂度为O(n)。（4）时间复杂度为O(nlogn)s=0;for(j=1;j=n;j*=2)for(k=1;k=n;+k) s+;时间复杂度为O(nlogn) （5）平方阶：时间复杂度为O(logn)s=0;for(j=1;j=n;+j)for(k=1;k=n;+k)s+;语句频度为n2，所以时间复杂度为O(n2)。s=0;for(j=1; j=n; j+)for(k=1;k=j;+k)s+;语句频度为n(n+1)/2，所以时间复杂度仍为O(n2)。（6）立方阶：时间复杂度为O( n3)例：矩阵乘法：n x n for( i
6、 = 0; i n; i+) /(n+1) for( j = 0; j n; j+) /n(n+1) cij = 0； /n2 for( k= 0; k n; j+) / n2 (n+1) cij = cij+aik* bkj; / n3 说明：各语句行后的数字是该语句重复执行的次数; 本算法时间复杂度为O (n3)6. 空间复杂度算法原地（就地）工作： 若所用额外存储空间相对于输入数据量来说是常数，则称此算法为原地（就地）工作。教 案（末页）复习思考题：推荐阅读书目：数据结构与算法设计 课程教案（续页）授课时间第 周 授课方式（请打）讲授 上机 实验/训 其它课时安排授课题目（章节或单位课时
7、）：教学目的与要求（分了解、熟悉、掌握三个层次）：教学重点与难点：教 学 内 容备 注教 案（末页）复习思考题：推荐阅读书目：数据结构与算法设计 课程教案（续页）授课时间第 周 授课方式（请打）讲授 上机 实验/训 其它课时安排授课题目（章节或单位课时）：教学目的与要求（分了解、熟悉、掌握三个层次）：教学重点与难点：教 学 内 容备 注教 案（末页）复习思考题：推荐阅读书目：数据结构与算法设计 课程教案（续页）授课时间第 周 授课方式（请打）讲授 上机 实验/训 其它课时安排授课题目（章节或单位课时）：教学目的与要求（分了解、熟悉、掌握三个层次）：教学重点与难点：教 学 内 容备 注教 案（末
8、页）复习思考题：推荐阅读书目：数据结构与算法设计 课程教案（续页）授课时间第 周 授课方式（请打）讲授 上机 实验/训 其它课时安排授课题目（章节或单位课时）：教学目的与要求（分了解、熟悉、掌握三个层次）：教学重点与难点：教 学 内 容备 注教 案（末页）复习思考题：推荐阅读书目：数据结构与算法设计 课程教案（续页）授课时间第 周 授课方式（请打）讲授 上机 实验/训 其它课时安排授课题目（章节或单位课时）：教学目的与要求（分了解、熟悉、掌握三个层次）：教学重点与难点：教 学 内 容备 注教 案（末页）复习思考题：推荐阅读书目：数据结构与算法设计 课程教案（续页）授课时间第 周 授课方式（请打
9、）讲授 上机 实验/训 其它课时安排授课题目（章节或单位课时）：教学目的与要求（分了解、熟悉、掌握三个层次）：教学重点与难点：教 学 内 容备 注教 案（末页）复习思考题：推荐阅读书目：数据结构与算法设计 课程教案（续页）授课时间第 周 授课方式（请打）讲授 上机 实验/训 其它课时安排授课题目（章节或单位课时）：教学目的与要求（分了解、熟悉、掌握三个层次）：教学重点与难点：教 学 内 容备 注教 案（末页）复习思考题：推荐阅读书目：数据结构与算法设计 课程教案（续页）授课时间第 周 授课方式（请打）讲授 上机 实验/训 其它课时安排授课题目（章节或单位课时）：教学目的与要求（分了解、熟悉、掌
10、握三个层次）：教学重点与难点：教 学 内 容备 注教 案（末页）复习思考题：推荐阅读书目：数据结构与算法设计 课程教案（续页）授课时间第 周 授课方式（请打）讲授 上机 实验/训 其它课时安排授课题目（章节或单位课时）：教学目的与要求（分了解、熟悉、掌握三个层次）：教学重点与难点：教 学 内 容备 注教 案（末页）复习思考题：推荐阅读书目：数据结构与算法设计 课程教案（续页）授课时间第 周 授课方式（请打）讲授 上机 实验/训 其它课时安排授课题目（章节或单位课时）：教学目的与要求（分了解、熟悉、掌握三个层次）：教学重点与难点：教 学 内 容备 注教 案（末页）复习思考题：推荐阅读书目：数据结构与算法设计 课程教案（续页）授课时间第 周 授课方式（请打）讲授 上机 实验/训 其它课时安排授课题目（章节或单位课时）：教学目的与要求（分了解、熟悉、掌握三个层次）：教学重点与难点：教 学 内 容备 注教 案（末页）复习思考题：推荐阅读书目：
