《数据结构与数据库》教学大纲-

1、所有欺骗中，自欺是最为严重的。 数据结构与数据库教学大纲 课程编码：11272007 课程名称：数据结构与数据库 英文名称：Data Structure and Database 开课学期：7 学时/学分：90/5（其中实验学时：20 ） 课程类型：专业必修课 开课专业：信息管理与信息系统 选用教材： 1、 严蔚敏编著：数据结构（C语言版） 清华大学出版社 2、 王珊编著：数据库系统原理教程 清华大学出版社 1998年7月版 主要参考书： 1、 陈志泊主编：数据库原理及应用教程 人民邮电出版社 2002年3月 2、 刘瑞新主编：Visual Foxpro程序设计教程 机械工业出版社 2001年

2、9月 3、 教育部考试中心：全国计算机等级考试三级教程-数据库技术 高等教育出版社 4、 刘大有主编：数据结构 吉林大学出版社 1994年版 执笔人：牟冬梅 一、 课程性质、目的与任务 数据结构与数据库是信息管理与信息系统专业的骨干课程之一 其中数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科 数据库系统、完整地讲述了当前数据库技术从基本原理到应用实践的主要内容 数据库是数据管理的最新技术 是计算机科学的重要分支 数据库是在学生学习了数据结构、离散数学等技术基础课后的一门专业必修课 通过对本课程的讲授 一方面将进一步加深学生对各种计算机程序设计算法

3、的理解 熟练运用所学算法及程序设计语言编写满足不同要求的应用程序 启发并诱导学生独立思考及发现新算法的能力 另一方面使学生掌握数据库基础、数据库开发、数据库设计以及数据库管理与维护等方面的理论知识 二、 教学基本要求 1、 了解数据的逻辑结构和物理结构之间的关系 数据结构和数据类型的关系 数据结构和算法的关系 2、 熟悉和掌握各种基本数据结构的概念、特点和存储结构 各种基本数据结构的运算及算法设计：根据实际问题提出的要求 选择和设计合理的数据结构 3、 熟悉和掌握排序和查找算法的分析方法 根据实际问题提出的要求学会如何选择合理的排序和查找算法 4、 注重算法的应用 提高学生学以致用的能力 5、

4、 熟悉和掌握关系代数和数据库基础理论 6、 掌握数据库开发、数据库设计及数据库管理与维护等方面的理论与实践知识 7、 加强学生算法与程序实现结合和数据库理论与数据库实践结合的能力 要求学生编写程序 完成数据库设计 提高学生分析问题、解决问题的能力 三、 各章节内容及学时分配 第一篇 数据结构（40学时） 教学目的与 要求 了解数据的逻辑结构和物理结构之间的关系 数据结构和数据类型的关系 数据结构和算法的关系 熟悉和掌握各种基本数据结构的概念、特点和存储结构 各种基本数据结构的运算及算法设计：根据实际问题提出的要求 选择和设计合理的数据结构 熟悉和掌握排序和查找算法的分析方法 根据实际问题提出的

5、要求学会如何选择合理的排序和查找算法 第一章 绪论（2学时） 教学目的与要求 通过本部分的学习 要求学生重点掌握数据、类型、数据结构 理解算法的定义、描述、算法设计的要求及初步分析方法 数据结构的主要运算 教学内容 第一节 什么是数据结构 第二节 基本概念和术语 第三节 抽象数据类型的表示与实现 第四节算法和算法分析 一、算法 二、算法设计的要求 三、算法效率的度量 四、算法的存储空间需求 考核要求 了解：数据结构的主要运算 理解：算法（定义、描述、算法设计的要求及分析初步） 掌握：数据 类型 数据结构（逻辑结构和存储结构） 第二章 线性表（4学时） 教学目的与要求 通过本部分的学习 学生应重

6、点掌握顺序表、链表的插入和删除 链表的遍历、合并、查找等算法；数组的存储（例如数组元素在内存位置的计算方法） 广义表等 理解1、线性表定义和基础运算、线性表的存储结构、链式表的应用:多项式的表示与相加 教学内容 第一节 线性表的类型定义 第二节 线性表的顺序表示和实现 第三节 线性表的链式表示和实现 一、线性链表 二、循环链表 三、双向链表 考核要求 理解：线性表定义和基础运算 线性表的存储结构 链式表的应用:多项式的表示与相加 掌握：顺序表、链表的插入和删除 链表的遍历、合并、查找等算法； 数组的存储（例如数组元素在内存位置的计算方法） 广义表 第三章 栈和队列（4学时） 教学目的与要求 通

7、过本部分的学习 学生应重点掌握栈的存储结构与实现、递归的实现、队列的基本运算 理解栈的定义、队列的定义 教学内容 第一节 栈 一、抽象数据类型栈的定义 二、栈的表示和实现 第二节 栈的应用举例 一、数制转换 二、括号匹配的检验 三、行编辑程序 四、迷宫求解 五、表达式求值 第三节 栈与递归的实现 第四节 队列 一、抽象数据类 型队列的定义 二、链队列队列的链式表示和实现 三、循环队列队列的顺序表示和实现 第五节离散事件模拟 考核要求 理解：栈的定义、队列的定义 掌握：栈存储结构与实现、递归的实现、队列的基本运算 第四章 串（4学时） 教学目的与要求 通过本部分的学习 学生应重点掌握串的运算和存

8、储结构 理解串的定义 概括了解串的模式匹配算法 掌握： 教学内容 第一节 串类型的定义 第二节 串的表示和实现 一、定长顺序存储表示 二、堆分配存储表示 三、串的块链存储表示 第三节串的模式匹配算法 一、求子串位置的定位函数Index(S T pos 二、模式匹配的一种改进算法 第四节串操作应用举例 一、文本编辑 二、建立词索引表 考核要求 了解：串的模式匹配算法 理解：串的定义 掌握：串的运算和存储结构 第五章 数组和广义表（3学时） 教学目的与要求 通过本部分的学习 学生应重点掌握数组的顺序存储结构及存储地址 理解数组的运算 广义表的基本运算 矩阵的压缩存储 了解数组的定义 广义表的定义

9、教学内容 第一节 数组的定义 第二节 数组的顺序表示和实现 第三节矩阵的压缩存储 一、特殊矩阵 二、稀疏矩阵 第四节广义表的定义 第五节广义表的存储结构 第六节m元多项式的表示 第七节广义表的递归算法 一、求广义表的深度 二、复制广义表 三、建立广义表的存储结构 考核要求 了解：数组的定义 广义表的定义 理解：数组的运算 广义表的基本运算 矩阵的压缩存储 掌握：数组的顺序存储结构及存储地址 第六章 树和二叉树（8学时） 教学目的与要求 通过本部分的学习 要求学生重点掌握树、森林和二叉树的概念 如何把树或森林转化为二叉树、二叉树的基本性质、存储结构、遍历、查找和穿线；了解满二叉树、完全二叉树、平

10、衡二叉树的区别 教学内容 第一节 树的定义和基本术语 第二节 二叉树 一、二叉树的定义 二、二叉树的性质 三、二叉树的存储结构 第三节 遍历二叉树和线索二叉树 一、遍历二叉树 二、线索二叉树 第四节树和森林 一、树的存储结构 二、森林与二叉树的转换 三、树和森林的遍历 第五节树与等价问题 第六节赫夫曼树及其应用 一、最优二叉树（赫夫曼树） 二、赫夫曼编码 第七节回溯法与树的遍历 第八节树的计数 考核要求 了解：树的定义二叉树的定义 性质 理解：树的基本运算和存储结构二叉树基本运算和存储结构 掌握：二叉树的遍历和线索二叉树 第七章 图（5学时） 教学目的与要求 通过本部分的学习 学生应重点掌握图

11、的遍历 理解图的定义、图的存储结构、连通性问题、有向无环图及其应用、最短路径问题 教学内容 第一节 图的定义和术语 第二节 图的存储结构 一、数组的表示法 二、邻接表 三、十字链表 四、邻接多重表 第三节 图的遍历 一、深度优先搜索 二、广度优先搜索 第四节 图的连通性问题 一、无向图的连通分量和生成树 二、有向图的强连通分量 三、最小生成树 第五节 有向无环图及其应用 一、拓扑排序 二、关键路径 三、阶段评审 第六节 最短路径 一、从某个源点到其余顶点的最短路径 二、每一对顶点之间的最短路径 考核要求 理解：1、图的定义 2、图的存储结构 3、连通性问题 4、有向无环图及其应用 5、最短路径

12、 掌握：图的遍历 第八章 查找（4学时） 教学目的与要求 通过本部分的学习 学生应重点掌握哈希表 理解静态查找表和动态查找表中的二叉排序树和平衡二叉树 了解B树和B树 教学内容 第一节 静态查找表 一、顺序表的查找 二、有序表的查找 三、静态树表的查找 四、索引顺序表的查找 第二节 动态查找表 一、二叉排序树和平衡二叉树 二、B-树和B树 三、键树 第三节哈希表 一、什么是哈希表 二、哈希函数的构造方法 三、处理冲突的方法 四、哈希表的查找及其分析 考核要求 了解：树和树 理解：静态查找表和动态查找表中的二叉排序树和平衡二叉树 掌握：哈希表 第九章 内部排序（4学时） 教学目的与要求 通过本部

13、分的学习 学生应重点掌握插入排序、快速排序、选择排序的方法 理解：归并排序和基数排序的思想 了解各种内部排序方法的不同 教学内容 第一节 概述 第二节 插入排序 一、直接插入排序 二、其他插入排序 三、希尔排序 第三节快速排序 第四节选择排序 一、简单选择排序 二、树形选择排序 三、堆排序 第五节归并排序 第六节基数排序 一、多关键字的排序 二、链式基数排序 第七节各种内部排序方法的比较讨论 考核要求 了解：各种内部排序方法的不同 理解：归并排序和基数排序 掌握：插入排序、快速排序、选择排序 第十章 外部排序（1学时） 教学目的与要求 通过本部分的学习 学生应理解外部排序的方法 了解外部存储器

14、 外部排序的特点和最佳归并树 教学内容 第一节 外存信息的存取 第二节 外部排序的方法 第三节 多路平衡归并的实现 第四节 置换选择排序 第五节 最佳归并树 考核要求 了解：外部存储器 外部排序的特点 最佳归并树 理解：外部排序的方法 第十一章 文件（1学时） 教学目的与要求 通过本部分的实践教学 学生应理解基本概念 了解顺序文件、索引文件、ISAM文件和VSAM文件、直接存储文件等 教学内容 第一节文件 第二节顺序文件 第三节索引文件 第四节ISAM文件和VSAM文件 第五节直接存取文件（散列文件） 第六七多关键字文件 考核要求 了解：文件组织 理解：基本概念 第二篇 数据库系统原理（30学

15、时） 教学目的与要求 通过本部分的讲授 使学生掌握关系代数、关系数据库原理、关系数据库基础理论、数据库开发、数据库设计以及数据库管理与维护等方面的理论知识；通过数据库分析 掌握数据库设计方法、步骤和技巧 提高分析问题、解决问题的能力 第一章 绪论（4学时） 教学目的与要求 通过本部分的学习 学生应重点掌握数据模型 数据库系统三级模式和两层映象 理解数据库、数据库系统及数据库管理系统等基本概念算法 理解三种主要的数据库模型 理解数据系统的组成 了解数据库技术的产生和发展 教学内容 第一节 引言 一、数据、数据库、数据库系统、数据库管理系统 二、数据库技术的产生与发展 三、数据库技术的研究领域 第

16、二节数据模型 一、数据模型的要素 二、概念模型 三、数据模型 第三节数据库系统的结构 一、数据库系统的模式结构 二、数据库系统的体系结构 第四节数据库管理系统 一、数据库管理系统的功能与组成 二、数据库管理系统的工作过程 三、数据库管理系统的实现方法 第五节数据库工程与应 用 一、数据库设计的目标与特点 二、数据库设计方法 三、数据库设计步骤 四、数据库应用 考核要求 了解：数据库技术的产生和发展 理解： （1） 数据库、数据库系统及数据库管理系统等基本概念算法（定义、描述、算法设计的要求及分析初步） （2） 三种主要的数据库模型 （3） 数据库系统的组成 掌握： （1）数据库系统的核心和基础

17、-数据模型 包括数据模型的三要素、概念模型 （2）数据库系统三级模式和两层映象 第二章 关系数据库（6学时） 教学目的与要求 通过本部分的学习 学生应重点掌握关系数据库的重要概念和关系代数 理解关系数据库模式和关系数据库 了解关系演算 教学内容 第一节关系模型 第二节关系的形式化定义 第三节关系的性质 第四节关系的键 第五节关系数据库模式与关系数据库 第六节关系代数 一、传统的集合运算 二、专门的关系运算 第七节关系演算 考核要求 了解：关系演算 理解：关系数据库模式与关系数据库 掌握： （1） 关系数据库的重要概念 包括关系模型的数据结构、关系的完整性以及关系操作 （2） 用关系代数表达查询

18、 第三章 关系数据库标准语言SQL（8学时） 教学目的与要求 通过本部分的学习 学生应重点掌握SQL语言在数据定义、数据查询、数据更新、数据控制方面的功能 学会使用嵌入式SQL 理解SQL和视图的基本概念 教学内容 第一节SQL语言的基本概念与特点 第二节SQL数据定义 一、定义、删除与修改基本表 二、建立与删除索引 第三节SQL数据查询 一、单表查询 二、连接查询 三、嵌套查询 四、集合查询 第四节SQL数据更新 一、插入数据 二、修改数据 三、删除数据 第五节视图 一、定义视图 二、查询视图 三、更新视图 四、视图的用途 第六节SQL数据控制 第七节嵌入式SQL 一、 嵌入式SQL的一般形

19、式 二、 嵌入式SQL语句与主语言之间的通信 三、 不用游标的SQL语句 四、 使用游标的SQL语句 考核要求 理解：SQL的基本概念 视图的概念 掌握：SQL语言在数据定义、数据查询、数据更新、数据控制方面的功能 学会使用嵌入式SQL 第四章 关系数据库理论（4学时） 教学目的与要求 通过本部分 的学习 使学生重点掌握关系规范化理论 理解函数依赖的有关概念 第一范式、第二范式和第三范式的定义 了解规范化理论的研究背景及其数据依赖的公理系统及模式分解 教学内容 第一节数据依赖 一、 关系模式中的数据依赖 二、 数据依赖对关系模型的影响 三、 有关概念 第二节范式 一、 第一范式 二、 第二范式

20、 三、 第三范式 四、 BC范式 五、 多值依赖与第四范式 第四节关系模式的规范化 一、 关系模式规范化的步骤 二、 关系模式的分解 考核要求 了解：数据依赖的公理系统及模式分解 了解关系规范理论研究的背景 理解：函数依赖的基本概念、一范式、二范式、三范式的定义 掌握：关系规范化理论 第五章数据库保护（4学时） 教学目的与要求 通过本部分的学习 使学生重点掌握DBMS完整性实现的机制 包括完整性约束定义机制、完整性检查机制和违背完整性约束条件时DBMS应采取的动作 重点掌握事务的概念和特点及并发控制的三级封锁协议 理解数据库系统安全性技术和方法 了解数据库故障的种类和恢复技术 教学内容 第一节

21、数据库的安全性 一、 安全性控制的一般方法 二、 ORACLE数据库的安全性措施 第二节完整性控制 一、 完整性约束条件 二、 完整性控制 三、 ORACLE的完整性 第三节并发控制与封锁 一、 并发控制概述 二、 并发控制的调度 三、 封锁 四、 死锁和活锁 五、 ORACLE的并发控制 第四节数据库的恢复 一、 恢复的原理 二、 恢复的实现技术 三、 ORACLE的恢复技术 考核要求 了解：故障的种类和恢复技术 理解：数据库系统安全性技术和方法 掌握：完整性实现机制 事务的概念和特点 并发控制 三级封锁协议 第六章数据库设计（4学时） 教学目的与要求 通过本部分的学习 使学生重点掌握概念结

22、构的设计和逻辑结构的设计 理解数据库设计和步骤 了解数据库设计的任务、内容 教学内容 第一节数据库设计概述（任务、内容、特点、方法、步骤） 第二节系统需求分析 一、 需求分析的任务 二、 需求分析的方法 三、 数据字典 第三节概念结构设计 一、 概念结构设计的方法与步骤 二、 数据抽象与局部视图设计 三、 视图的集成 第四节逻辑结构设计 一、 ER图向数据模型的转换 二、 数据模型的优化 三 、 设计用户子模式 第五节数据库物理设计 第六节数据库实施 第七节数据库运行和维护 考核要求 了解：数据库设计的任务和特点 理解：数据库设计的方法和步骤 掌握：概念结构的设计和逻辑结构的设计 四、 实验： 1. 实验目的与任务 数据库结构与数据库课程是高等院校信息管理与信息系统专业（医药信息专业方