数据结构与算法“概论”教学设计 北京大学信息科学技术学院赵海燕 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 小时