《数据结构与数据库操作系统》实验课作业和要求

1、数据结构与数据库/操作系统实验课作业和要求实验一、线性表的应用：稀疏一元多项式运算器实验目的：熟练掌握指针和链表操作的基本功熟练掌握数组操作的基本功模块化程序设计（程序的分层结构、函数的功能和接口）人机交互界面设计（界面美观，使用方便、操作的弹性好）源程序的书写风格（缩进式，加注释，可读性要好）对程序健壮性的处理程序的调试技术训练（debug 方法和测试数据的选择）时空效率实验学时：12 学时（第 1,2,3 次实验）实验内容：基本功能（必做）：1.创建2.显示3.复制4.求和5.求差6.求值7.销毁8.淸空9. 修改（插入新的结点、删除已有结点、修改已有结点的系数和指数） 拓展功能（选做）：

2、10. 微分（N 阶导数）11. 不定积分12. 定积分13. 乘法和乘方14. 除法15. 最大公约式和最小公倍式16. 多项式的四则运算（如“（l+2*3）/4”）数据组织：多项式用带头结点的单链表表示用指针数组存放 N 个多项式的头指针 存储结构示意图:用户操作界面：推荐用菜单驱动实验二、栈的应用实验目的：掌握栈的后进先岀特点掌握栈的表示和实现技术掌握如何运用栈的特点来构建算法实验内容（在题目 L6 中任选1 题）:目 1目 2目 3目 5.目 6.附加题：一般表达式的计算，即在表达式中包含其他函数的运算，如:25A3*tan（sin（1.2）+cos（3.5）实验学时：4 学时（第 4

3、 次实验课当堂完成）简单的行编借器（提髙难度：实现对文本文件的编辑）括号配对检验（提髙难度：实现对括号优先级的检测） 波兰式计算（提高难度：操作数为浮点数） 逆波兰式计算（提髙难度：操作数为浮点数） 中缀式计算（提髙难度：操作数为浮点数） 迷宫求解（提高难度：随机迷宫.最短路径的提取）题题题题题题实验学时：4 学时（第5次实验课当堂完成）实验三、二叉树的运算实验目的：掌握二叉树的递归特性掌握二叉树的常用存储结构二叉链表掌握二叉树的创建、遍历等基本运算了解递归函数的执行过程，学会编写递归程序实验内容：（在题目 1、2 中任选 1 题）题目 1.二叉树运算1.创建二叉树2.遍历二叉树（先序、中序、

4、后序、层序遍历）3.二叉树的计算（二叉树的结点数、叶子数、髙度、宽度等）4.二叉树的处理（复制、销毁）题目 2哈夫曼编码和解码1.输入电文串2.统讣电文字符集和每种字符在电文中岀现的次数3.构建 huffman 树4.产生每种字符的 huffman 编码5.将电文串翻译成比特流6.对电文比特流进行解码附加题：用 huffman 压缩技术实现对文件的压缩和解压缩处理实验学时：4 学时（第6次实验课当堂完成）实验四、图 实验目的：掌握图的两种存储结构：邻接矩阵表示法和邻接表表示法掌握图的 DFS 遍历和 BFS 遍历的算法学会利用图的模型来编程解决实际应用问题实验内容：（在题目 1、2、3 中任选

5、题）题目 1.图的遍历1. 创建图 G （任选邻接矩阵或邻接表）2. 显示图3. 深度优先搜索迪历图4. 广度优先搜索遍历图5. 在图中插入顶点&在图中插入边题目 2:求通讯网的最小代价生成树1. 输入通讯网 G2. 用 Prim 算法构建 G 的最小生成树并输出3. 用 Kruskal 算法构建 G 的最小生成树并输出题目 3.铁路交通网的最短路径1. 输入铁路交通网 G2. 用 Dijkstra 算法 il算从始发站到终点站的最短路径实验五、哈希表实验目的：掌握哈希表的定义和特点掌握哈希函数的构造方法和解决冲突的技术，实现哈希造表掌握哈希表的查找、插入和删除技术掌握哈希表平均查找长

6、度 ASL 的计算方法 实验内容：（1-5 必做，其他选做）1. 输入关键字序列：2. 用除留余数法构建哈希函数，用线性探测法解决冲突，构建哈希表 HT1：3. 用除留余数法构建哈希函数，用拉链法解决冲突，构建哈希表 HT2：4. 分别对 HT1 和 HT2 计算在等概率情况下査找成功和查找失败的 ASL：5. 分别在 HT1 和 HT2 中查找给楚的关键字，给出比较次数&在 HT1 中删除指定的关键字7.在 HT1 中插入新的关键字实验学时：4 学时（第 7 次实验课当堂完成）实验六数据库SQL语言实验目的：1. 熟悉本实验所使用的 DBMS 环境：SQL SERVER 2005,学

7、会使用 SQL SERVER 客户端工 具査询分析器。2. 完成 SQL 语言的基本操作：1）创建表2）插入、删除、修改、査询。3）创建视图实验内容：1. T 载 SQL Server 客户端工具：03/querytool.rar,解压后执行 isqlw.exe,SQLSERVER（s）输入 11,【连接使用】选择aSQLserver 身份验证”, 登录剑和密码都是 student.,此外， 也可以使用实验室机器桌面上的 SQL Server Management Studio Express 登录。登录后显示如下界面，则可以执行 s

8、ql 语句了。要注意，pubs 数据库是系统样例数据库，里面提供了 titles 等实验中用到的示例表，student用户对其只有查询权，不可以修改。学生可以在 student 数据库中创建自己的表，创 建表时请按照题目中要求的命名规则来命名。在操作数据库是要注意当前数据库是 pubs 还是 student,可以在界面面的 combox 选择 窗口中M3选择，也可以使用命令 use pubs 更改当前数据库。2.熟悉 pubs 数据库中并个 table 的定义和关系。03/pubs.pdf3.查询操作（在 pubs 数据库中执行）：1）无条件査询查找 pub

9、 库中 authors 表的全部信息。2） 简单条件査询查找 titles 表中全部书号及书名。查找 titles 表中价格在$1518 元之间的书的书紅。查找 titles 表中书名以 T 开头的书号，书冬。对英他样例表构造务种简单查询条件，进行查询。3）多条件查询查找书名起始字符为 T.价格小于$16 元的书名及价格。查找书名起始字符不为 T 的，价格大于$16 元的书号，书名及价格。4）用连接操作（或嵌套査询）进行査询对表 titles, publishers 进行查询：査找出版社的名称以及所岀的书名。对表 authors, titleauthor, titles 进行査询：查找作者的姓

10、、剑和所写的书名。5）对查询结果排序查找作者的姓、名、电话号码，并按作者姓、统排列。查找书名和书的价格，按书价由大到小的次序排列。6）使用函数进行査找列出有多少类书。列岀书的定价有多少种。列岀书价最低的书劣和书价。查出书价最髙的书名及书价。列出当年销量的总和。4.表和视图创建及插入1）建表：创建两个表 S*和 T,并插入下面内容，其中和是本人的学号（下同）。Titleauthort_nopriceQTY计算机原理张一平S309220.80200C 语言程序设计李华H129815.30300数据库原理王家树D100722.70150计算机网络髙明S569018.90230软件工程鲁廷璋S200535.00200t_noPagepub-dateS30923041986D10072801993S50063151987S56903001993H129821019892） 用子查询方式建新表 SS* （包含 title 和 price 两个属性）。3） 用子查询方式建视图 VS