北京师范大学《数据结构》课程教学大纲 一、课程基本信息 中文名称： 数据结构 英文名称：Data Structure 课程类别（公共任选课、学科基础课、专业方向课）：学科基础课 学分： 4 学时： 48+32 建议开设学期：2 开课单位建议：信息科学与技术学院 主讲教师： （姓名） 沈复兴 （性别） 男 （职称） （学科方向） 教授 计算机软件 郑新 女 副教授 计算机应用 肖永康 男 讲师 计算机应用 二、课程目标： 本课程的主要目标是使学生深入了解数据结构的思想和数据结构的实现方法，特别是数据结构在实际工作中的应用和技术。本课程追求理论联系实际，实践教学与相应的教学内容相呼应。在形式上，灵活多样地采取了实践、拓展性学习、报告会等多种形式，目的在于加深学生对所学内容的理解，发展学生从事发展算法与程序设计研究和实践的能力，努力做到学以致用，同时激发学生的学习兴趣和主动参与精神，更好地掌握和运用所学习的知识。 三、课程内容与主要学习材料（含教材及参考书目） 课程内容： 第一章 绪论 1. 教学内容: ♦ 数据结构的一些基本概念：数据、数据元素、数据的逻辑结构、物 理结构、算法等。 ♦ 抽 象 数据类 型 。 ♦ 描 述 算法的程序语 言 （C++）。 ♦ 算法时间 复杂 度 和空 间 复杂 度 的分 析 。 2. 教学目的及 要求 ♦ 掌握数据、数据对象、数据元素、数据结构、数据的逻辑结构与物理结构、逻辑结构与物理结构间的关系等数据结构的基本概念； ♦ 了解数据类型、抽象数据类型、数据抽象和信息隐蔽原则以及面向对象这种数据抽象实现方法 ♦ 了解算法的定义、算法的特性、算法的时间代价、算法的空间代价 ♦ 掌握用 C++语言描述算法的方法，能够使用 C++语言编写程序 3. 教学重点 数据结构的概念；算法分析；C ++语言。 4. 学时分配 本章共教授 4 学时. 第二章 数组 1 . 教学内容 ♦ 线性表的基本概念 ♦ 顺序表：顺序表的定义和特点；顺序表的类定义；顺序表的查找、插入和删除；使用顺序表的事例；顺序表复杂度分析 ♦ 特殊矩阵的压缩存储：特殊矩阵定义、稀疏矩阵类定义、矩阵转置与快速转置、矩阵乘法与输出 ♦ 字符串：字符串类型定义；字符串操作的实现；字符串的模式匹配 2 . 教学目的及要求 ♦ 了解线性表的逻辑结构特性，以及线性表的两种存储实现方式 ♦ 熟练掌握顺序表的定义与实现，包括搜索、插入、删除算法...
