《数据结构与数据库系统》理论教学大纲

1、数据结构与数据库系统理论教学大纲 (2006年制订)课程编号：210181英 文 名：Data Structures and Database System课程类别：文化技能前 置 课：计算机实用技术、C语言程序设计后 置 课：学 分：6学分课 时：108课时（其中理论教学72课时，实验教学36课时）主讲教师：李亚志等选定教材：严蔚敏,陈文博.数据结构及应用算法教程.北京：清华大学出版社,2001年. 陈联诚.SQL Server 2000实用教程.北京：电子工业出版社，2006年课程概述： 本课程共分为数据结构与数据库系统两部分。数据结构内容的选取，定位于以数据结构知识为主，同时加强了算法设

2、计和分析方法的内容，本课程讨论的知识内容和提倡的技术方法，无论对进一步学习计算机领域的其他课程，还是从事软件工程的开发，都有着不可替代的作用。该部分主要内容包括：线性表、栈和队列、串、数组和广义表、树和二叉树、图、查找、排序。数据库系统侧重于实际应用，因此该部分较详细地介绍Microsoft SQL Server 2000数据库应用系统的开发技术。主要内容包括：SQL Server 2000的安装和配置，SQL Server 2000数据类型，数据库和数据表，数据库的查询，索引与数据完整性，视图，Transact-SQL程序设计，存储过程，触发器，用户自定义函数与事务，SQL Server 2

3、000管理数据库综合开发应用。教学目的： 数据结构既是计算机专业的重要专业基础课程，又是非计算机相关专业的重要学科基础课程，其目的是培养学生在问题的分析中抽象出数据、数据集合和数据关系，并以此为基础设计算法，把算法分解成为对数据集上的数据结构和各种运算。因此要求学生学会从问题入手，分析研究计算机加工的数据结构的特性，以便为应用所涉及的数据选择适当的逻辑结构，存储结构及其相应的操作算法，并初步掌握时间和空间分析技术。数据库系统可以作为非计算机专业学生的数据库知识的文化技能课，从实用角度来讲，其目的是使学生具备数据库系统的基础知识和培养学生数据库编程与设计能力，为学生将来从事计算机信息系统软件的开

4、发打下坚实的基础。教学方法： 本课程采用立体化教学模式。课堂教学以讲授教材内容为主线，同时讲授实验方法和内容，适时安排作业分析和习题课。实验环节进行实验课训练。以强化学生的动手能力，培养和提高实践创新能力，加强学生对本课程理性认识与感性认识的有机结合，为后续课程的学习奠定基础。各章教学要求及教学要点数据结构部分第一章 绪论课时分配： 2课时教学要求：掌握数据结构及其相关概念。熟悉数据的四种基本结构类型。熟悉四种不同存储结构。熟悉算法的五个重要特征。掌握算法的设计要求。了解算法的两种效率量度。教学内容：第一节数据结构讨论的范畴一、数据结构讨论的范畴。第二节 与数据结构相关的概念一、基本概念和术语

5、。二、数据结构。三、数据类型和抽象数据类型。第三节 算法及其描述和分析一、算法。二、算法的描述。三、算法效率的衡量方法和准则。四、算法的存储空间要求。思考题： 1.数据结构由哪几部分组成？2.数据的物理结构和逻辑结构分别包括哪几种类型？3.算法的五个重要特性是什么？第二章 线性表课时分配：4课时教学要求： 掌握线性表的逻辑结构特性。理解在计算机中，表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构，掌握这两类存储结构的描述方法，以及线性表的各种基本操作的实现。了解从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。教学内容： 第一节 线性表的类型定义一、线性表的

6、定义。二、线性表的基本操作。第二节 线性表的顺序表示和实现一、顺序表线性表的顺序存储表示。二、顺序表中基本操作的实现。三、顺序表其他算法举例。第三节 线性表的链式表示和实现一、单链表和指针。二、单链表的基本操作。三、单链表的其他操作举例。四、循环链表。五、双向链表。第四节 有序表一、有序表。思考题： 1.线性表的逻辑结构特征是什么？当顺序表和链表作为其存储结构时，线性表中结点之间的关系分别用什么来表示？2.顺序表中插入和删除一个结点平均需要移动多少个结点？具体移动的结点个数取决于哪两个参数？3.编写一个在带头结点的单链表中删除一个最小节点的算法。第三章 排序课时分配：6课时教学要求：了解排序的

7、定义和各种排序方法的特点。熟悉各种方法的排序过程及其依据的原则。了解各种排序方法的时间复杂度的分析方法。理解排序方法“稳定”或“不稳定”的含义，弄清楚在什么情况下要求应用的排序方法必须是稳定的。教学内容： 第一节 排序的基本概念一、排序的基本概念第二节 简单排序方法一、插入排序。二、起泡排序。第三节 先进排序方法一、快速排序。二、归并排序。三、堆排序。第四节 基数排序一、基数排序。思考题：1.已知序列503，47，512，612，908，270，897，275，653，462，请给出采用快速排序法对该序列作升序时的每一趟结果。2.已知序列47，18，60，40，7，35，73，65，85，请给

8、出采用堆排序法对该序列作升序排序时的每一趟结果。3.已知序列503，87，512，61，908，170，897，275，653，462，请给出采用归并排序法对该序列作升序时的每一趟结果。第四章 栈和队列课时分配：4课时教学要求：掌握栈和队列类型的特点，了解在相应的应用问题中如何正确选用它们。掌握顺序栈类型的实现方法和熟悉顺序栈类型基本操作。了解链栈的实现方法。掌握循环队列和链队列的基本操作实现算法。教学内容：第一节 栈一、栈的结构特点和操作。二、栈的表示和操作的实现。第二节 栈的应用举例一、数制转换。二、括号匹配的检验。第三节 队列一、队列的结构特点和操作。二、队列的表示和操作的实现。第四节

9、队列应用举例一、杨辉三角二、运动会日程安排思考题：1.编写一个算法，利用栈的基本运算，将指定栈中的内容进行逆转。2.向循环队列中插入一个元素时，通常的操作是什么？3.编写一个算法，利用队列和栈的基本算法，将指定队列中的内容进行逆转。第五章 串和数组课时分配： 4课时教学要求： 掌握串的七种基本操作的定义。了解利用这些基本操作来实现串的其它各种操作的方法。掌握在串的定长顺序存储结构上实现串的各种操作的方法。了解串的堆存储结构以及在其上实现串操作的基本方法。了解串的匹配操作。掌握数组的两种存储表示方法。熟悉数组在以行为主的存储结构中的地址计算方法。教学内容： 第一节 串的定义和操作一、串的定义和操

10、作。第二节 串的表示和实现一、定长顺序存储表示。二、堆分配存储表示。三、块链存储表示。第三节 正文模式匹配一、正文模式匹配。第四节 串操作应用举例一、正文编辑。第五节 数组一、数组的定义和操作。二、数组的顺序表示和实现。三、数组的应用。第六节 矩阵的压缩存储一、特殊形状矩阵的存储表示。二、随机稀疏矩阵的存储压缩。思考题：1.链串的优点、缺点各是什么？2.已知字符串A、B、C、D，确定对它们的复制操作、替换操作、找子串操作、插入删除操作等操作结果。3. 设二维数组A58的每个元素占8个字节，存储器按字节编址，已知A的基地址为100，则A的终端节点A47的存储地址是多少？若按行存储时A25的地址是

11、多少？按列存储时A25的存储地址是多少？第六章 二叉树和树课时分配：6课时教学要求：熟练掌握二叉树的结构特性。熟悉二叉树的各种存储结构的特点及适用范围。掌握各种遍历策略的递归算法，运用遍历算法，实现二叉树的其它操作。了解二叉树线索化的实质。了解二叉树的线索化过程。掌握树的各种存储结构及其特点。掌握树和森林与二叉树的转换方法。掌握建立二叉树的顺序表和二叉链表结构。掌握建立树的双亲表示法，孩子表示法及二叉链表结构的存储结构方法。理解编写实现树的各种操作的算法。掌握建立最优树和哈夫曼编码的方法。教学内容：第一节 二叉树一、二叉树的定义和基本术语。二、二叉树的几个基本性质。三、二叉树的存储结构。第二节

12、 二叉树的遍历一、问题的提出。二、遍历算法的描述。三、二叉树遍历应用举例。四、线索二叉树。第三节 树和森林一、树和森林的定义。二、树和森林的存储结构。三、树和森林的遍历第四节 树的应用一、堆排序的实现。二、二叉排序树。三、哈夫曼树及其应用思考题：1.假设二叉树采用链接存储方式存储，编写一个二叉树中序遍历的非递归算法。2.写一个算法判断二叉树是否为满二叉树。3.已知5个字符的哈夫曼编码中，3个字符编码分别为01、10、11，其余两个字符的编码长度为3，则这两个字符的编码分别是多少？第七章 图和广义表课时分配：6课时教学要求：熟练掌握图的各种存储结构。掌握图的两种搜索路径的遍历。遍历的逻辑定义、深

13、度优先搜索和广度优先搜索的算法。了解应用图的遍历算法求解各种简单路径问题。教学内容：第一节 图的定义和术语一、图的定义和术语。第二节 图的存储结构一、图的数组存储表示。二、图的邻接表存储表示。第三节 图的遍历一、深度优先搜索遍历图。二、广度优先搜索遍历图。第四节 连通图的最小生成树一、连通图的最小生成树。第五节 单源最短路径一、单源最短路径。第六节 拓扑排序一、拓扑排序。第七节 关键路径一、关键路径。第八节 广义表一、广义表的定义。二、广义表的存储结构。三、广义表的遍历。思考题：1.图有哪三种表示方法？2.使用普里姆算法构造出图的一棵最小生成树。3. 设广义表A=（z,x,c），B=(A,(s

14、,f)，C=(a,(B,A),(e,f) ，请运算写出head(A)的运算结果。第八章 查找表课时分配： 4课时教学要求：理解顺序表和有序表的查找方法及其平均查找长度的计算方法。掌握静态查找树的构造方法和查找算法。了解静态查找树和折半查找的关系。熟练掌握二叉排序树的构造和查找方法，以及插入删除操作。掌握哈希表的构造方法。了解按定义计算各种查找方法在等概率情况下查找成功时的平均查找长度。教学内容：第一节 静态查找表一、顺序查找。二、折半查找。三、分块查找。第二节 动态查找表一、二叉查找树。二、键树。第三节 哈希表及其查找一、什么是哈希表。二、构造哈希函数的几种方法。三、处理冲突的方法和建表示例。

15、四、哈希表的查找及其性能分析。五、哈希表的应用举例。思考题：1.在分块查找中，若用折半查找确定块，则查找成功时的平均查找长度约为多少？若用顺序查找确定块，则查找成功时的平均查找长度为多少？2.判定给定的二叉树是否是二叉排序树。3.给定一组关键字和装载因子，构建哈希表，并计算哈希表的平均查找长度。数据库系统部分第一章SQL Server 2000的安装和配置课时分配： 2课时教学要求：掌握SQL Server2000的安装和配置方法，学会使用常用的数据库管理工具，如企业管理器和查询分析器。教学内容：第一节SQL Server 2000简介一、SQL Server 2000简介。第二节SQL Se

16、rver 2000的安装一、软件需求。二、硬件需求。三、安装SQL Server 2000。第三节 SQL Server 2000的主要管理工具一、SQL Server 2000企业管理器。二、SQL Server 2000查询分析器。三、服务管理器。第四节 注册服务器 一、注册服务器。思考题：1简述SQL Server2000安装过程。2简述服务帐户的概念。3简述SQL Server 2000企业管理器的功能。第二章SQL Server 2000数据类型课时分配： 2课时教学要求：掌握SQL Server 2000系统的基本数据类型，学会用户自定义数据类型的方法。教学内容：第一节 系统数据类

17、型一、字符数据类型。二、数值型数据类型。三、货币型数据类型。四、时间/日期数据类型。五、二进制数据类型。六、其他数据类型。第二节用户自定义数据类型 一、用户自定义数据类型。思考题：1列举SQL Server 2000的系统数据类型。2通过企业管理器如何定义用户自定义数据类型？3通过对比SQL Server 2000数据类型与C语言数据类型，进一步掌握SQL Server 2000数据类型。第三章数据库和数据表课时分配： 4课时教学要求：掌握对数据库的创建和管理。、掌握数据表的各种基本操作。学会分离和附加数据库方法。教学内容：第一节创建和管理数据库一、数据库简介。二、创建数据库。三、管理数据库。

18、第二节创建和管理数据表一、数据表简介。二、创建数据表。三、设置约束。四、管理数据表。五、数据表操作。第三节 分离与附加数据库一、分离与附加数据库。思考题： 1在检查SQL Server的设置情况时，突然发现某一数据库的大小为250MB，但是却只使了20的空间。假定该数据库容量不会再增大，则应该采取什么操作？A. 为了节省空间，应该减少数据文件的大小。B. 为了节省空间，应该进行磁盘碎片处理。C. 为了节省空间，应该收缩数据库。D. 为了节省空间，应该使用NTFS分区，然后使用压缩功能进行压缩。2简单介绍删除与其他表存在关联的表的操作步骤。3如果在创建新的数据库时，发现可以设置的最小容量为5MB

19、，而不是通常情况下的1MB，最可能的原因是： Amaster数据库大小为5MB。 B缺省数据文件的大小为5MB。 C应该使用TransactSQL而不是企业管理器来创建数据库。 Dmodel数据库大小为5MB。第四章数据库的查询课时分配： 4课时教学要求：掌握基本的SQL查询语句，学会使用系统函数，掌握多表联接查询、联合查询、嵌套查询等。教学内容：第一节SELECT语句结构一、SELECT语句结构。第二节 基本子句查询一、SELECT子句。二、FROM子句。三、WHERE子句。四、ORDER BY子句。五、INTO子句。第三节 数据汇总一、使用聚合函数。二、使用GROUP BY子句。三、使用H

20、AVING子句。四、使用COMPUTE和COMPUTE BY子句。第四节 多表联接查询一、联接简介。二、联接的类型。第五节 联合查询 一、联合查询。第六节 嵌套查询 一、嵌套查询。思考题：1简述SELECT语句的结构。2请为三建工程项目建立一个供应情况的视图，包括供应商代码(SNO)、零件代码(PNO)、供应数量(QTY)。针对该视图完成下列查询：(1) 找出三建工程项目使用的各种零件代码及其数量。(2) 找出供应商S1的供应情况。3简述联接的类型第五章索引与数据完整性课时分配： 2课时教学要求：掌握索引的建立、删除，分析和维护，学会设置数据库数据的完整性。教学内容：第一节索引一、 索引的概念

21、。二、 索引的建立。三、 索引的删除。四、 索引的分析与维护。第二节 数据完整性一、域完整性。二、实体完整性。三、引用完整性。思考题：1什么是索引？如何创建和删除索引？2数据完整性包括哪些？3某公司有数据库，其中有一个表包含几十万个数据，但是用户抱怨说查询速度太慢，下面哪种方法能最好地提高查询速度： A收缩数据库。 B减少数据库占用的空间。 C建立聚集索引和非聚集索引。 D换个高档服务器。第六章视图课时分配： 4课时教学要求： 掌握视图的基本概念和定义方法，学会使用视图查询数据，管理数据表中的数据。教学内容：第一节视图的概念 一、视图的概念。第二节 创建视图一、使用企业管理器创建视图。二、使用

22、Transact-SQL语言创建视图。第三节 修改视图一、使用企业管理器修改视图。二、使用Transact-SQL语言修改视图。第四节 使用视图查询数据 一、使用视图查询数据。第五节 使用视图管理数据表中的数据一、使用视图管理数据表中的数据。思考题：1下面关于视图的说法，哪一个正确？ A视图是将基本表中的数据检索出来后重新组成的一个新表。 B视图是一种虚拟表，本身保存的只是视图的定义，查看视图数据时，SQL Server将其定义转换为相应的SELECT语句，然后进行检索并显示结果。 C通过视图可以修改多个基本表的数据。 D对任何视图，都可以通过该视图修改基本表的数据。2简述Create vie

23、w 语句中with check option选项的含义。3创建一个视图，名称为“订单”，并使用它来检索定购日期、客户名称、书名、单价、数量和总额。第七章Transact-SQL程序设计课时分配：4课时教学要求：掌握Transact-SQL语言的基本语法和基础编程。学会使用游标。教学内容：第一节Transact-SQL语言基础一、Transact-SQL语言基础。第二节 Transact-SQL语言要素一、批处理。二、注释语句。三、标识符。四、全局变量与局部变量。五、运算符和表达式。六、流程控制语句。第三节 使用游标一、游标的声明。二、打开和读取游标。三、关闭和释放游标。思考题：1使用bookd

24、b数据库，查询价格大于35的书籍的书名、作者、价格和出版社，在显示时用中文名字。2在test数据库中建立一个表，字段分别为col1和col2，均为整型，然后插入两笔记录（任意），计算每笔记录中两个字段的乘积。最后显示所有记录及其乘积，使用SQL语句完成上述功能。3编制一个函数，用于对给定的分数进行判断：大于60，返回“及格”；小于60，则返回“不及格”。第八章存储过程课时分配：4课时教学要求：掌握使用企业管理器做存储过程的创建、执行，修改和删除。教学内容：第一节存储过程简介一、存储过程的优点。二、存储过程的类别。第二节 创建存储过程一、使用企业管理器创建存储过程。二、使用Transact-SQ

25、L语言创建存储过程。第三节 执行存储过程一、执行存储过程。第四节 修改和删除存储过程一、使用企业管理器查看和修改存储过程。二、使用Transact-SQL语言查看和修改存储过程。思考题：1存储过程的优点是什么？2存储过程分为哪几类？3试举例说明如何创建、执行、修改和删除存储过程。第九章触发器课时分配： 2课时教学要求：掌握使用企业管理器进行触发器的创建、修改和删除。教学内容：第一节触发器简介一、触发器的概念。二、触发器的功能。三、触发器的类型和触发操作。第二节 创建触发器一、使用企业管理器创建触发器。二、使用Transact-SQL语言创建触发器。第三节 修改触发器一、使用企业管理器修改触发器

26、。二、使用Transact-SQL语言管理触发器。第四节 删除触发器一、在企业管理器中删除触发器。二、使用Transact-SQL语言删除触发器。思考题：1 什么是触发器？ 2触发器的功能有哪些？ 3举例说明如何创建、修改、删除触发器？第十章用户自定义函数与事务课时分配： 2课时教学要求：掌握用户自定义函数的创建、修改和删除。掌握事务处理和锁的基本概念。教学内容：第一节用户自定义函数简介 一、用户自定义函数。第二节 创建用户自定义函数一、使用企业管理器创建用户自定义函数。二、使用Transact-SQL语言创建用户自定义函数。第三节 修改、删除用户自定义函数一、修改用户自定义函数。二、删除用户

27、自定义函数。第四节 事务处理一、事务简介。二、事务处理。第五节 锁一、锁的概念。二、死锁及其排除。思考题： 1什么是用户自定义函数？有哪些方法可以创建用户自定义函数？2什么是事务？什么是事务处理？3什么是锁？死锁排除的方法有哪些？第十一章SQL Server 2000管理课时分配： 2课时教学要求：掌握SQL Server 2000的安全管理。学会数据的导入导出方法。掌握数据库的备份和恢复方法。教学内容：第一节安全管理一、SQL Server 2000的身份验证。二、账户管理。三、角色管理。四、权限管理。第二节 数据的导入导出(DTS)一、数据的导出。二、数据的导入。第三节 数据库备份一、备份

28、设备。二、备份策略。三、执行数据库备份。第四节 数据库恢复 一、数据库恢复。思考题： 1如何设置SQL Server2000的身份认证？2简述数据导入/导出的步骤。3简述执行数据备份的步骤。第十二章数据库综合开发应用课时分配： 4课时教学要求： 掌握数据库设计的基本方法，学会用ASP.NET和VB.NET操作数据库。教学内容：第一节ADO.NET简介一、ADO.NET介绍。第二节 数据库设计一、数据库设计。第三节 ASP.NET 操作数据库一、ASP.NET运行环境。二、ASP.NET开发工具。三、ASP.NET程序设计。第四节 VB.NET 操作数据库一、启动Visual Basic.NET 集成开发环境。二、VB.NET程序设计。思考题：1编