福州理工学院教案课程名称数据结构与算法设计系（部）信息工程系教研室计算机授 课教师黄取治职称讲师附件：D课程名称数据结构与算法设计学分总计:学时讲授：学时上机：学时实验训：学时其它：学时类另 U（请打丁）□公共课□公共选修课□专业基础课□专业必修课□专业方向选修课□实验实训课（仅限本科）□公共课口公共选修课口专业基础课口专业必修课口专业选修课口实验实训课（仅限高职）授课对象（请打丁）□本科□高职□其他使用教材参考资料（注明书名、主编、出版社、出版时间）教学方法教学手段考核方式学生创新精神与实践能力的培养方法数据结构与算法设计课程教案（续页）授课时间第周授课方式（请打 V）□讲授□上机□实验训□其它课时安排授课题目（章节或单位课时）：第一章绪论教学目的与要求（分了解、熟悉、掌握三个层次）：1•了解数据结构课程的重要性和课程的基本要求，以及本课程涵盖的内容；2. 掌握数据结构的基本概念；3. 理解算法描述和简单的算法分析。教学重点与难点：1. 重点是数据结构的基本概念2. 难点是时间复杂度分析教学内容备注1. 从后序课(数据库、操作系统、编译原理、人工智能)的需要和考研两方面介绍数据结构课程的重要性。2. 通过三个例子讲解数据结构研究的内容。3. 介绍基本概念：数据的三个层次，数据结构的三个要素，数据结构的分类，四种存储结构，抽象数据类型，算法，算法的五个特性，对算法设计的要求，算法描述和算法分析，时间复杂度和空间复杂度。4. 从“百钱买百鸡”C'一百元钱买一百支笔”)的算法例子说明选择算法的重要性：万案 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)。for(j=1；jv=10000；++j){++x;s+=x;}语句频度为 10000，时间复杂度为 0(1)。(2) 对数阶：时间复杂度为 O(logn)s=0;for(j=1;jv=n;j*=2)s++;语句频度为 logn，所以时间复杂度为 O(logn)。(3) 线性阶：时间复杂度为 O(logn)S=0;for(j=1;j<=n;++j)s...
