福州理工学院教 案课程名称 系〔部〕 教研室 授课教师 职 称数据结构与算法设计信息工程系计算机黄取治讲师课程名称数据结构与算法设计学分总计：学时讲授：学时上机：学时实验/训：学时其它：学时类另 IJ 〔请打 J〕口公共课口公共选修课口专业根底课口专业必修课口专业方向选修 课口实验实训课〔仅限本科〕□公共课口公共选修课口专业根底课口专业必修课口专业选修课口 实验实训课〔仅限高职〕授课对象 〔请打 J〕□本科 □高职 □其他使 用 教 材 参考资料〔注明书名、主编、出版社、出版时间〕教 学 方 法 教学手段考核方式学生创新 精神与实 践水平的 培养方法附件 2：案〔数据结构与算法设计 课程教案(续页)授课时间第 1 周授课方式 (请打 J)□讲授 口上机 口实验/训 口其它课时 安排授课题目(章节或单位课时)： 第一章绪论教学目的与要求(分了解、熟悉、掌握三个层次)：1.了解数据结构课程的重要性和课程的根本要求,以及本课程涵盖的内容；2.掌握数据结构的根本概念；3.理解算法描述和简单的算法分析.教学重点与难点：1.重点是数据结构的根本概念2.难点是时间复杂度分析教学内 容备注1.从后序课(数据库、操作系统、编译原理、人工智能)的需要和考研两方面 介绍数据结构课程的重要性.2.通过三个例子讲解数据结构研究的内容.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) *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)常量阶：时间复杂度为 0(1)++x;s=0;语句频度为 1,时间复杂度为 O(1).fora=ly<=10000;++j){++X； s+=x;}语句频度为 10000,时间复杂度为 O(l)o(2)对数阶：时间复杂度为 O(logn)s=0;for(j=l; j<=n; j*...
