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