数据结构与算法“概论”教学设计 北京大学信息科学技术学院赵海燕 1.概论在课程中的定位和前测知识点 “数据结构与算法”是计算机专业的核心课程之一,上承“计算引论”与“程序设计实习”, 下启“算法分析与设计”和“计算复杂性理论”,为后续的操作系统、软件工程、数据库概论 编译技术、人工智能、计算机图形学等多门专业课程,提供了必要的知识和技能准备。诸如, 程序设计语言及其编译技术要使用的栈、散列表及语法树,操作系统会用到的队列、存储管 理表及目录树,数据库系统将用到的线性表、多链表以及索引书等基本数据结构及其相关算 概论一章主要介绍在后续各章都要用到的一些预备知识和相应的设计原则,包括数据结 构的概念与分类、抽象数据类型、算法及其特性,并重点介绍算法复杂性的分析技术。 前测知识点要求如下,可以根据需要给学生补充 1)熟练掌握一门编程语言 2)设计简单的算法 3)掌握常用的数学术语、集合和关系、对数、级数求和、递归和递推等概念,熟练应 用反证法和数学归纳法等数学证明方 前测习题 1)设计一个算法,自大到小依次输出顺序读入的三个整数X,Y和Z的值。 2)在一个具有n个元素的集合上可以定义多少个全序?并加以解释。 3)用归纳法证明:T(n)=T(n-1)+n,T(1)=1有闭合形式解Tn)=n(n+12 2.学习目标 (1)了解数据结构与算法课程在计算机学科中的定位、以及本课程所包含的基本内 (2)了解数据结构与算法在求解实际问题中的核心地位和基本步骤 (3)对数据结构和算法的基本概念有初步的认识,对抽象数据类型的意义和作用有 基本的认识; (4)了解如何评价一个算法的优劣,并掌握基本的算法复杂性分析方法 3.知识点和学时分配 理论授课2学时,建议安排实验1-2学时 以下内容是本课程要求的基本教学内容,在授课中必须完全涵盖,主讲教师可以根据学 生的状况、教师的科研背景等在某些方面进行扩展和对学生进行引导,以适当扩大学生的涉 猎面 各知识点建议授课时间如下 利用计算机求解问题的基本方法 0.5小时 数据结构的基本概念 0.5小时 算法概念及设计方法 0.5小时
数据结构与算法“概论”教学设计 北京大学信息科学技术学院 赵海燕 1. 概论在课程中的定位和前测知识点 “数据结构与算法”是计算机专业的核心课程之一，上承“计算引论”与“程序设计实习”， 下启“算法分析与设计”和“计算复杂性理论”，为后续的操作系统、软件工程、数据库概论、 编译技术、人工智能、计算机图形学等多门专业课程，提供了必要的知识和技能准备。诸如， 程序设计语言及其编译技术要使用的栈、散列表及语法树，操作系统会用到的队列、存储管 理表及目录树，数据库系统将用到的线性表、多链表以及索引书等基本数据结构及其相关算 法。 概论一章主要介绍在后续各章都要用到的一些预备知识和相应的设计原则，包括数据结 构的概念与分类、抽象数据类型、算法及其特性，并重点介绍算法复杂性的分析技术。 前测知识点要求如下，可以根据需要给学生补充： 1) 熟练掌握一门编程语言； 2) 设计简单的算法； 3) 掌握常用的数学术语、集合和关系、对数、级数求和、递归和递推等概念，熟练应 用反证法和数学归纳法等数学证明方法。 前测习题 1) 设计一个算法，自大到小依次输出顺序读入的三个整数 X, Y 和 Z 的值。 2) 在一个具有 n 个元素的集合上可以定义多少个全序？并加以解释。 3) 用归纳法证明：T(n) = T(n-1) + n, T(1) = 1 有闭合形式解 T(n) = n(n+1)/2. 2．学习目标 （1） 了解数据结构与算法课程在计算机学科中的定位、以及本课程所包含的基本内 容； （2） 了解数据结构与算法在求解实际问题中的核心地位和基本步骤； （3） 对数据结构和算法的基本概念有初步的认识，对抽象数据类型的意义和作用有 基本的认识； （4） 了解如何评价一个算法的优劣，并掌握基本的算法复杂性分析方法。 3. 知识点和学时分配 理论授课 2 学时，建议安排实验 1-2 学时。 以下内容是本课程要求的基本教学内容，在授课中必须完全涵盖，主讲教师可以根据学 生的状况、教师的科研背景等在某些方面进行扩展和对学生进行引导，以适当扩大学生的涉 猎面。 各知识点建议授课时间如下： 利用计算机求解问题的基本方法 0.5 小时 数据结构的基本概念 0.5 小时 算法概念及设计方法 0.5 小时
算法评价标准及分析方法 0.5小时 4.重点和难点 概论一章的重点如下 (1)利用计算机求解问题的基本方法和步骤 (2)数据结构的基本概念 (3)算法概念及设计方法; (4)算法评价标准及分析方 其中,难点在于 (1)如何从问题求解出发,在基础理论、抽象和设计的三个层次组织课程的知识体 (2)如何从抽象数据类型的角度刻画数据结构的三个方面 (3)如何运用已有数学知识来分析和评价一个算法的好坏 5.授课提示 结合计算机科学技术的现代前沿研究课题,设计研究启发式教学案例,扩展学生知识体 系,培养主动学习、研究和创新意识 下面是概论一章的重点和难点内容的讲授注意事项。 (1)利用计算机求解问题的基本方法和步骤 利用计算机求解实际问题,首先需要明确问题的需求,然后对问题进行分析和抽象,建 立问题的抽象模型;在此基础上,确定该模型所采用的数据结构,设计相应的法来求解该问 题;最后选定某种程序设计语言来编码实现。 整个问题的求解过程即是一个所谓的问题抽象、数据抽象和算法抽象的过程,这也是学 生不易理解的地方。要在基础理论、抽象和设计的三个层次组织和建立课程的知识体系,授 课时需要在此点上下功夫,通过实例来说明这三方面的抽象为好 (2)数据结构的基本概念 数据结构描述的是按照一定逻辑关系组织起来的待处理数据元素的表示及相关操作,涉 及三个方面:数据的逻辑结构、数据的存储结构和数据的运算。其中,逻辑结构是从具体问 题抽象出来的数学模型,反映了事物的组成结构及其事物之间的逻辑关系;存储结构则解决 各种逻辑结构在计算机中的物理存储表示;运算则是建立在数据的逻辑结构之上的,其实现 与数据的存储结构紧密相关。 需要注意的是,数据结构重点研究的是数据间的结构关系,因而把组成结构的那些元素 都一同视为结点。结点是数据结构中数据的基本单位。根据数据间的逻辑关系可将数据结构 分为线性结构、树结构和图结构。此处,以一个二元组B=(K,R)来表示数据的逻辑结构」 易于讲解。其中,K是数据结点组成的有穷集合,每一个结点代表一个数据或一组有明确结 构的数据;关系集R是定义在集合K上的一组二元关系,其中每个关系r(r∈R)都是KxK 上的二元关系,用来描述结点数据之间的逻辑关系 (3)抽象数据类型 抽象数据类型(简称ADT)是定义了一组运算的数学模型,这种抽象的数据类型可以 在较高级别的算法中直接引用,而不用考虑它的实现细节,很好地支持了逻辑设计和物理实 现的分离。ADT有力地支持了封装和信息隐蔽,使得学生可以在不同的设计阶段采用不同 的抽象数据类型作为设计的基础,在适当的抽象层次上考虑程序的结构和算法 个三元组(D,S,P)可用来刻画一个抽象数据类型,其中D表示数据对象,S表示
算法评价标准及分析方法 0.5 小时 4．重点和难点 概论一章的重点如下： （1） 利用计算机求解问题的基本方法和步骤； （2） 数据结构的基本概念； （3） 算法概念及设计方法； （4） 算法评价标准及分析方法。 其中，难点在于 （1） 如何从问题求解出发，在基础理论、抽象和设计的三个层次组织课程的知识体 系； （2） 如何从抽象数据类型的角度刻画数据结构的三个方面； （3） 如何运用已有数学知识来分析和评价一个算法的好坏； 5．授课提示 结合计算机科学技术的现代前沿研究课题，设计研究启发式教学案例，扩展学生知识体 系，培养主动学习、研究和创新意识。 下面是概论一章的重点和难点内容的讲授注意事项。 （1）利用计算机求解问题的基本方法和步骤 利用计算机求解实际问题，首先需要明确问题的需求，然后对问题进行分析和抽象，建 立问题的抽象模型；在此基础上，确定该模型所采用的数据结构，设计相应的法来求解该问 题；最后选定某种程序设计语言来编码实现。 整个问题的求解过程即是一个所谓的问题抽象、数据抽象和算法抽象的过程，这也是学 生不易理解的地方。要在基础理论、抽象和设计的三个层次组织和建立课程的知识体系，授 课时需要在此点上下功夫，通过实例来说明这三方面的抽象为好。 （2）数据结构的基本概念 数据结构描述的是按照一定逻辑关系组织起来的待处理数据元素的表示及相关操作，涉 及三个方面：数据的逻辑结构、数据的存储结构和数据的运算。其中，逻辑结构是从具体问 题抽象出来的数学模型，反映了事物的组成结构及其事物之间的逻辑关系；存储结构则解决 各种逻辑结构在计算机中的物理存储表示；运算则是建立在数据的逻辑结构之上的，其实现 与数据的存储结构紧密相关。 需要注意的是，数据结构重点研究的是数据间的结构关系，因而把组成结构的那些元素 都一同视为结点。结点是数据结构中数据的基本单位。根据数据间的逻辑关系可将数据结构 分为线性结构、树结构和图结构。此处，以一个二元组 B = ( K，R )来表示数据的逻辑结构 易于讲解。其中，K 是数据结点组成的有穷集合，每一个结点代表一个数据或一组有明确结 构的数据；关系集 R 是定义在集合 K 上的一组二元关系，其中每个关系 （r r ∈ R）都是 K×K 上的二元关系，用来描述结点数据之间的逻辑关系。 （3）抽象数据类型 抽象数据类型（简称 ADT）是定义了一组运算的数学模型，这种抽象的数据类型可以 在较高级别的算法中直接引用，而不用考虑它的实现细节，很好地支持了逻辑设计和物理实 现的分离。ADT 有力地支持了封装和信息隐蔽，使得学生可以在不同的设计阶段采用不同 的抽象数据类型作为设计的基础，在适当的抽象层次上考虑程序的结构和算法。 一个三元组（D，S，P）可用来刻画一个抽象数据类型，其中 D 表示数据对象，S 表示
D上的关系集,D和S二者定义了数据的模型,是对数据的抽象;P是表示D上的基本操作 集,定义了该数据模型的功用,是对数据操作的抽象 学生不易理解的是抽象数据类型和数据运算的具体实现之间的关系,需通过实例多加说 明 (4)算法及其复杂性的分析与评价 算法设计与算法分析是计算机科学的核心问题 算法设计是求解问题时必须要考虑的问题,其任务是对各类具体问题设计良好的算法及 研究设计算法的规律和方法。需要在此简单介绍包括穷举法、回溯法、分治法、递归法和贪 心法等在内的常用的算法设计方法的基本思想,并在后续章节使用到时详加阐述 算法的复杂性是度量算其效率、评价其优劣的重要依据。算法分析技术即是利用数学工 具,对每一个具体算法讨论其各种复杂度,以探讨某种具体算法适用于哪类问题,或某类问 题宜采用哪种算法;并从解决同一问题的不同算法中选择出较为合适的一种,或者是对原有 的算法进行改造、加工,使其更优、更好 算法复杂性体现在运行该算法所需要的计算机资源的多少上面,所需的资源越多表明该 算法的复杂性越高:反之,该算法的复杂性越低。计算机资源中最重要的是时间资源和空间 资源。所以,算法的复杂性通常由时间复杂性和空间复杂性两个指标来表示。 讲授算法分析方法时需要强调的是,算法复杂性并非采用诸如微秒、纳秒这样的真实的 时间单位来表示,也即,算法分析感兴趣的并非具体的时间、空间单位,而是算法与输入规 模之间的关系,即用一定“规模”的数据作为输入时程序运行所需的“基本操作”或“基本 空间”数来描述时间或空间效率。另外,由于用来表示数据规模和时间、空间开销关系的函 数都相当复杂,通常采用渐进分析方法,即在分析时忽略那些不能显著改变函数量级的部分, 而把注意力集中在相对重要的部分 6.课后练习和实习 作为教学的重要一环,课后练习和实习帮助学生巩固课堂所学理论知识,训练学生创新 思维能力训练、工程实践能力。 概论部分可以安排2-3道书面作业,也可酌情采用 ACM/ICPC程序竞赛题库POJ系统 安排1道相对简单的实习题来训练学生熟悉POJ环境和使用方法。例如,下面的ACM题目 http://acm.pku.edu.cn/judgeonline/problem?id=1000 http://acm.pku.edu.cn/judgeonline/problem?id=1045 7.教学案例 以算法时间复杂性分析作为讲解渐进分析方法的实例 大多数情况下,算法的时间复杂度是根据算法执行过程中需要实施的赋值、比较等运算 数目的多寡来衡量的。 可以先从简单的例子开始分析。例如, for( 0,i<n;,i++) sum +=all 是一段对数组中的各个元素求和的代码。其中主要的操作为赋值运算,故其时间代价主要体 现在赋值操作的数目上。在循环开始之前有两次赋值,分别对ⅰ和对sum进行;循环进行 了n次,每次循环中执行两次赋值,分别对sum和对i进行更新操作。总共有2+2n次赋
D 上的关系集，D 和 S 二者定义了数据的模型，是对数据的抽象；P 是表示 D 上的基本操作 集，定义了该数据模型的功用，是对数据操作的抽象。 学生不易理解的是抽象数据类型和数据运算的具体实现之间的关系，需通过实例多加说 明。 （4）算法及其复杂性的分析与评价 算法设计与算法分析是计算机科学的核心问题。 算法设计是求解问题时必须要考虑的问题，其任务是对各类具体问题设计良好的算法及 研究设计算法的规律和方法。需要在此简单介绍包括穷举法、回溯法、分治法、递归法和贪 心法等在内的常用的算法设计方法的基本思想，并在后续章节使用到时详加阐述。 算法的复杂性是度量算其效率、评价其优劣的重要依据。算法分析技术即是利用数学工 具，对每一个具体算法讨论其各种复杂度，以探讨某种具体算法适用于哪类问题，或某类问 题宜采用哪种算法；并从解决同一问题的不同算法中选择出较为合适的一种，或者是对原有 的算法进行改造、加工，使其更优、更好。 算法复杂性体现在运行该算法所需要的计算机资源的多少上面，所需的资源越多表明该 算法的复杂性越高；反之，该算法的复杂性越低。计算机资源中最重要的是时间资源和空间 资源。所以，算法的复杂性通常由时间复杂性和空间复杂性两个指标来表示。 讲授算法分析方法时需要强调的是，算法复杂性并非采用诸如微秒、纳秒这样的真实的 时间单位来表示，也即，算法分析感兴趣的并非具体的时间、空间单位，而是算法与输入规 模之间的关系，即用一定“规模”的数据作为输入时程序运行所需的“基本操作”或“基本 空间”数来描述时间或空间效率。另外，由于用来表示数据规模和时间、空间开销关系的函 数都相当复杂，通常采用渐进分析方法，即在分析时忽略那些不能显著改变函数量级的部分， 而把注意力集中在相对重要的部分。 6．课后练习和实习 作为教学的重要一环，课后练习和实习帮助学生巩固课堂所学理论知识，训练学生创新 思维能力训练、工程实践能力。 概论部分可以安排 2-3 道书面作业，也可酌情采用 ACM/ICPC 程序竞赛题库 POJ 系统 安排 1 道相对简单的实习题来训练学生熟悉 POJ 环境和使用方法。例如，下面的 ACM 题目： http://acm.pku.edu.cn/JudgeOnline/problem?id=1000 http://acm.pku.edu.cn/JudgeOnline/problem?id=1045 7．教学案例 以算法时间复杂性分析作为讲解渐进分析方法的实例。 大多数情况下，算法的时间复杂度是根据算法执行过程中需要实施的赋值、比较等运算 数目的多寡来衡量的。 可以先从简单的例子开始分析。例如， for (i = sum = 0; i<n; i++） sum += a[i]; 是一段对数组中的各个元素求和的代码。其中主要的操作为赋值运算，故其时间代价主要体 现在赋值操作的数目上。在循环开始之前有两次赋值，分别对 i 和对 sum 进行；循环进行 了 n 次，每次循环中执行两次赋值，分别对 sum 和对 i 进行更新操作。总共有 2 + 2n 次赋
值操作,其渐进复杂度为O(n) 随着循环中嵌套循环,其时间复杂度会相应增大。例如,下面这段代码依次求出给定数 组的所有子数组中各元素之和 for(i=0; i<n; i++) for(=1,sum=a[0;j<=;j++) sum +=all 循环开始前,有一次对i的赋值操作。之后,外层循环共进行n次,每个循环中包含 个内层循环,以及对i,j,sum分别进行赋值的操作;每个内层循环执行2个赋值操作,分 别更新sum和j;共执行i次(i=1,2,…,n-1)。所以,整个程序总共执行的赋值操作为 +3n+∑2=1+3n+2(1+2+…+n-1)=1+3n+n(n-1)=O)+On2)=O(n2)° 一般情况下,循环中嵌套循环会增加算法的时间复杂度,但也并非总是如此。例如,在 上面的实例中,如果只对每个子数组的前5个元素求和,则相应的代码可采用下面的方式 for(F4; K<n; 1++) for(=|-3,sum=a[i-4;j<=i,j++) sum +=all: 此时,外层循环进行n-4次。对每个i而言,内层循环只执行4次,每次的操作次数与 的大小无关:8次赋值操作。外加对i的初始化,整个代码总共进行O(1)+8(n-4)=O(n)次 赋值操作。尽管存在嵌套循环,但算法的整体时间复杂度依然呈线性增长 关键是通过这些案例让学生领会和掌握基本的算法分析方法。 8.总结 概论是《数据结构与算法》课程提纲挈领的一章,是帮助学生了解课程目标、把握课程 基本内容和方法的重要环节 除了上述教学注意事项之外。还需要提醒学生注意实际应用,针对同一个问题一般会存 在多种算法,这些算法在时间和空间开销上的优劣往往表现出“时空折衷”的性质。需要根 据应用的具体情况,在设计或选择数据结构时进行适当的权衡。 参考文献: 1.张铭,王腾蛟,赵海燕,《数据结构与算法》,高等教育出版社,2008年6月。—普 通高等教育“十一五”国家级规划教材 2.张铭、赵海燕、王腾蛟、宋国杰、高军,北京大学“数据结构与算法”教学设计,《计 算机教育》2008第20期。获得“英特尔杯2008年全国计算机教育优秀论文评比”一等 奖 3.北京大学《数据结构与算法》精品课程网站(2008年北京市“精品课程”暨国家“精品 课程),http://www.jpk.pkueducn/pkujpk/course/sjjg/ 4.蒋宗礼,“编译原理教学设计”。《计算机教育》,2008.3。 5.张铭、许卓群、杨冬青、唐世渭,“数据结构知识系统及教学实践”。《计算机教育》。《计 算机教育》,2004年2、3月合刊,PP89-91
值操作，其渐进复杂度为 O(n) 。 随着循环中嵌套循环，其时间复杂度会相应增大。例如，下面这段代码依次求出给定数 组的所有子数组中各元素之和： for (i = 0; i < n; i++) for (j = 1, sum = a[0]; j <= i; j++) sum += a[j]; 循环开始前，有一次对 i 的赋值操作。之后，外层循环共进行 n 次，每个循环中包含一 个内层循环，以及对 i，j，sum 分别进行赋值的操作；每个内层循环执行 2 个赋值操作，分 别更新 sum 和 j；共执行 i 次（i=1,2, …,n-1）。所以，整个程序总共执行的赋值操作为： n 1 2 2 i 1 1 3n 2i 1 3n 2(1 2 .... n 1) 1 3n n(n 1) O(n) O(n ) O(n ) 。 一般情况下，循环中嵌套循环会增加算法的时间复杂度，但也并非总是如此。例如，在 上面的实例中，如果只对每个子数组的前 5 个元素求和，则相应的代码可采用下面的方式： for ( i=4; i<n; i++) for (j = i-3, sum = a[i-4]; j <= i; j++) sum += a[j]; 此时，外层循环进行 n-4 次。对每个 i 而言，内层循环只执行 4 次，每次的操作次数与 i 的大小无关：8 次赋值操作。外加对 i 的初始化，整个代码总共进行 O(1) + 8(n-4) = O(n)次 赋值操作。尽管存在嵌套循环，但算法的整体时间复杂度依然呈线性增长。 关键是通过这些案例让学生领会和掌握基本的算法分析方法。 8．总结 概论是《数据结构与算法》课程提纲挈领的一章，是帮助学生了解课程目标、把握课程 基本内容和方法的重要环节。 除了上述教学注意事项之外。还需要提醒学生注意实际应用，针对同一个问题一般会存 在多种算法，这些算法在时间和空间开销上的优劣往往表现出“时空折衷”的性质。需要根 据应用的具体情况，在设计或选择数据结构时进行适当的权衡。 参考文献： 1. 张铭，王腾蛟，赵海燕，《数据结构与算法》，高等教育出版社，2008 年 6 月。——普 通高等教育“十一五”国家级规划教材。 2. 张铭、赵海燕、王腾蛟、宋国杰 、高军，北京大学“数据结构与算法”教学设计，《计 算机教育》2008 第 20 期。获得“英特尔杯 2008 年全国计算机教育优秀论文评比”一等 奖。 3. 北京大学《数据结构与算法》精品课程网站（2008 年北京市“精品课程”暨国家“精品 课程”）， http://www.jpk.pku.edu.cn/pkujpk/course/sjjg/ 4. 蒋宗礼，“编译原理教学设计”。《计算机教育》, 2008.3。 5. 张铭、许卓群、杨冬青、唐世渭，“数据结构知识系统及教学实践”。《计算机教育》。《计 算机教育》，2004 年 2、3 月合刊，PP89-91
