《数据结构与数据库/操作系统》实验课作业和要求
数据结构与数据库课程组实验课教学研讨会讨论稿
2012年7月第1次研讨 2013年3月第2次研讨
实验一、线性表的应用：稀疏一元多项式运算器
实验目的:
熟练掌握指针和链表操作的基本功 熟练掌握数组操作的基本功
模块化程序设计（程序的分层结构、函数的功能和接口） 人机交互界面设计（界面美观，使用方便、操作的弹性好） 源程序的书写风格（缩进式，加注释，可读性要好） 对程序健壮性的处理
程序的调试技术训练(debug方法和测试数据的选择) 时空效率
实验学时：
12学时（第1,2,3次实验）
实验内容：
基本功能（必做）：
1. 创建 2. 显示 3. 复制 4. 求和 5. 求差 6. 求值 7. 销毁 8. 清空
9. 修改（①插入新的结点、②删除已有结点、③修改已有结点的系数和指数）
拓展功能（选做）：
10. 微分（N阶导数）
11. 不定积分 12. 定积分 13. 乘法和乘方 14. 除法
15. 最大公约式和最小公倍式
16. 多项式的四则运算（如 “(1+2*3)/4”）
数据组织：
多项式用带头结点的单链表表示
用指针数组存放N个多项式的头指针
存储结构示意图:
用户操作界面：
推荐用菜单驱动
实验报告：
实验检查和评分标准：
实验二、栈的应用
实验目的：
掌握栈的后进先出特点 掌握栈的表示和实现技术
掌握如何运用栈的特点来构建算法
实验内容
（在题目1~6中任选1题）：
题目1. 简单的行编辑器（提高难度：实现对文本文件的编辑） 题目2. 括号配对检验（提高难度：实现对括号优先级的检测） 题目3. 波兰式计算（提高难度：操作数为浮点数）
题目4. 逆波兰式计算（提高难度：操作数为浮点数） 题目5. 中缀式计算（提高难度：操作数为浮点数）
题目6. 迷宫求解（提高难度: 随机迷宫、最短路径的提取） 附加题：
一般表达式的计算，即在表达式中包含其他函数的运算，如: 2.5^3*tan(sin(1.2)+cos(3.5))
实验学时：4学时（第4次实验课当堂完成）
实验报告：
实验检查和评分标准：
实验三、二叉树的运算
实验目的：
掌握二叉树的递归特性
掌握二叉树的常用存储结构----二叉链表 掌握二叉树的创建、遍历等基本运算
了解递归函数的执行过程，学会编写递归程序
实验内容：
（在题目1、2中任选1题） 题目1. 二叉树运算 1. 创建二叉树
2. 遍历二叉树（先序、中序、后序、层序遍历）
3. 二叉树的计算（二叉树的结点数、叶子数、高度、宽度等） 4. 二叉树的处理（复制、销毁）
题目2.哈夫曼编码和解码 1. 输入电文串
2. 统计电文字符集和每种字符在电文中出现的次数 3. 构建huffman树
4. 产生每种字符的huffman编码 5. 将电文串翻译成比特流 6. 对电文比特流进行解码
附加题：用huffman压缩技术实现对文件的压缩和解压缩处理
实验学时：4学时（第5次实验课当堂完成）
实验报告：
实验检查和评分标准：
实验四、图
实验目的：
掌握图的两种存储结构: 邻接矩阵表示法和邻接表表示法 掌握图的DFS遍历和BFS遍历的算法
学会利用图的模型来编程解决实际应用问题
实验内容：
（在题目1、2、3中任选1题） 题目1. 图的遍历
1. 创建图G（任选邻接矩阵或邻接表） 2. 显示图
3. 深度优先搜索遍历图 4. 广度优先搜索遍历图 5. 在图中插入顶点 6. 在图中插入边
题目2: 求通讯网的最小代价生成树 1. 输入通讯网G
2. 用Prim算法构建G的最小生成树并输出 3. 用Kruskal算法构建G的最小生成树并输出
题目3. 铁路交通网的最短路径 1. 输入铁路交通网G
2. 用Dijkstra算法计算从始发站到终点站的最短路径
实验学时：4学时（第6次实验课当堂完成）
实验报告：
实验检查和评分标准：
实验五、哈希表
实验目的：
掌握哈希表的定义和特点
掌握哈希函数的构造方法和解决冲突的技术，实现哈希造表 掌握哈希表的查找、插入和删除技术 掌握哈希表平均查找长度ASL的计算方法
实验内容：
（1-5必做，其他选做） 1. 输入关键字序列；
2. 用除留余数法构建哈希函数，用线性探测法解决冲突，构建哈希表HT1； 3. 用除留余数法构建哈希函数，用拉链法解决冲突，构建哈希表HT2； 4. 分别对HT1和HT2计算在等概率情况下查找成功和查找失败的ASL； 5. 分别在HT1和HT2中查找给定的关键字（注意对墓碑的处理），给出比较次数 6. 在HT1中删除指定的关键字（注意对墓碑的处理） 7. 在HT1中插入新的关键字（注意对墓碑的处理）
实验学时：
4学时（第7次实验课当堂完成）
实验报告：
实验检查和评分标准：
实验六 数据库SQL语言
实验目的：
1.熟悉本实验所使用的DBMS环境：SQL SERVER 2005, 学会使用SQL SERVER 客户端工具查询分析器。
2.完成SQL语言的基本操作： 1）创建表
2）插入、删除 、修改、查询。 3）创建视图
实验内容：
1.下载SQL Server 客户端工具：,解压后执行isqlw.exe，【SQL SERVER(s)】输入192.168.50.211，【连接使用】选择“SQL server身份验证”，登录名和密码都是student。 此外，也可以使用实验室机器桌面上的SQL Server Management Studio Express 登录。
登录后显示如下界面，则可以执行sql语句了。
要注意，pubs数据库是系统样例数据库，里面提供了titles等实验中用到的示例表，student用户对其只有查询权，不可以修改。学生可以在student数据库中创建自己的表，创建表时请按照题目中要求的命名规则来命名。
在操作数据库是要注意当前数据库是pubs还是student，可以在界面面的combox选择窗口中
选择，也可以使用命令use pubs更改当前数据库。
2．熟悉pubs数据库中各个table的定义和关系。