数据结构与数据库试验课作业和要求

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

2、拓展功能（选做） ：10. 微分（N阶导数）11. 不定积分12. 定积分13. 乘法和乘方14. 除法15. 最大公约式和最小公倍式16. 多项式的四则运算（如“ （1 +2*3）/ 4”）数据组织：多项式用带头结点的单链表表示 用指针数组存放 N 个多项式的头指针存储结构示意图I-头抬针数织pji L十J-H318A1o -*A34 A*用户操作界面：推荐用菜单驱动实验目的：实验二、栈的应用掌握栈的后进先出特点 掌握栈的表示和实现技术 掌握如何运用栈的特点来构建算法实验内容（在题目 16 中任选 1 题）：题目 1. 简单的行编辑器（提高难度：实现对文本文件的编辑）题目 2. 括号配对检验

3、（提高难度：实现对括号优先级的检测）题目 3. 波兰式计算（提高难度：操作数为浮点数）题目 4. 逆波兰式计算（提高难度：操作数为浮点数）题目 5. 中缀式计算（提高难度：操作数为浮点数）题目 6. 迷宫求解（提高难度 : 随机迷宫、最短路径的提取） 附加题：一般表达式的计算，即在表达式中包含其他函数的运算，如2.5A3*ta n（si n（1.2）+cos（3.5）实验学时： 第 5 次实验课当堂完成实验目的：实验三、二叉树的运算掌握二叉树的递归特性掌握二叉树的常用存储结构 二叉链表掌握二叉树的创建、遍历等基本运算 了解递归函数的执行过程，学会编写递归程序实验内容：（在题目 1、2 中任选

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

5、法 学会利用图的模型来编程解决实际应用问题实验内容：（在 题目 1、 2、 3 中任选 1 题）题目 1. 图的遍历1. 创建图G （任选邻接矩阵或邻接表）2. 显示图3. 深度优先搜索遍历图4. 广度优先搜索遍历图5. 在图中插入顶点6. 在图中插入边题目 2: 求通讯网的最小代价生成树1. 输入通讯网 G2. 用Prim算法构建G的最小生成树并输出3. 用Kruskal算法构建G的最小生成树并输出题目 3. 铁路交通网的最短路径1. 输入铁路交通网 G2. 用 Dijkstra 算法计算从始发站到终点站的最短路径实验目的：实验五、哈希表掌握哈希表的定义和特点 掌握哈希函数的构造方法和解决冲

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

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

8、界面，则可以执行sql语句了。要注意，pubs数据库是系统样例数据库，里面提供了titles等实验中用到的示例表，student用户对其只有查询权，不可以修改。学生可以在student数据库中创建自己的表，创建表时请按照题目中要求的命名规则来命名。在操作数据库是要注意当前数据库是pubs还是student，可以在界面面的 combox选择韦50L *向甘析莊1 “ 闵DBSiEETEA. ft udent 口 st ndrnt左杯=3* 1-0®理Iff (t:l晦査谭卸 TA H）E!口对曲如Jiff Xft 2? H7 * |QT| 卅智区 CFselect « fio

9、oi pubarrjtJuirl2. 熟悉pubs数据库中各个 table的定义和关系。03 /pubs.pdf3查询操作（在pubs数据库中执行）：1）无条件查询查找pub库中authors表的全部信息。2）简单条件查询查找titles表中全部书号及书名。查找titles表中价格在 $1518元之间的书的书名。 查找titles表中书名以T开头的书号，书名。对其他样例表构造各种简单查询条件，进行查询。3）多条件查询查找书名起始字符为T,价格小于$16元的书名及价格。查找书名起始字符不为T的，价格大于$16元的书号，书名及价格。4）用连接操作（或嵌套查询）进

10、行查询对表titles, publishers进行查询：查找出版社的名称以及所出的书名。 对表authors, titleauthor, titles进行查询：查找作者的姓、名和所写的书名。5）对查询结果排序IDEEKrKXbtUihnUJ DESDATSxdh用户畫* _| -Iba+ m dbl J.bi+ 匚)4bi. » | + 二J -Iba + 二1 4J>b* 二4ba.+ 匚)dbi.* 二1 Jbi + _l朋，i用口宦您的親哥轴 ct-wlwt 丄用口羸+ _|耒贬& JWE+ _|科曲过H&-丄函冲片_1用.口定.立関貌JS疲 *: lj

11、5<n* LJ9 tJm U.VXtlrf'Xl.disecviti . M|J.4r|n» 卜.涸« FjjMj iktrs .TQyEgd .i.klax k 1(.44T41 h E i-|l«MlllttT K UXL"|-au idau lnaie3U.fDaaepbonvaddie-rscityst at a ziprant i *7*AJna-K-nwJehnin4GSJ396-T2231 叩卫 Bin Rd,KtttU FtttE94.D26B2213-481 C；eb«i很sae-mo3阳5t. I<1Oa

12、klandS946 J 01323H-95*?7C CaiCheiyl41155-J8-TY235B9 Damn LiuBeikelerCA94TD5l!I2fi?-4-2394 O' LeaeyMichael血朗 S-M2S22 Cl&wlarid Av. ELIjii'i JoseClL96328ii5対9处肋扪r曲曲4L&P34也 Lfli沛汕亡011«(A Av.Oak liuid亡A.94咖13M 1-2173? SHth911UBrPIS6KK40T4D0-56-TQ(B B?nrwtAbiahaK取65S-P932622-3 Batsna

13、a 5t.SeikplqyCA9470BBE42?-LT-23 LSIhillAnn4IISB36-TI2®3L0 Blonde St-Pal* AltCA94301b94T2-2T-2M9 GriEnlesbyEiut70rT938-m&R) &dx ?92CaveloCA.9E428L104618-59-1LocksltivQLB6-4132012 BlTMjlvny gjAFi S'tfAnCllCG3LI4130L11527-732-15 Wttl*isrnsyicrttr2S7-Z733Z2 C£t.ybtG Houtt Rd.Wuttui

14、HtTIT315013640-9?-1ER2 Blotshflt-HallsEvfinald.50375-MO?SE OillaiialR BlCnialli-ranmaoII13fiT2-7!-3249 YokcuirtciAkikodiis035-422S3 SilvBi CtTai nut CrppkCAMJHBl!J-4112-45-lflT del CastilloIlUWJSLS9982?&2286 Ce» Pl.氐跖Anri AEborJill曲】05L15122-61-E4&4血直転們回JlichelEa?-S9323 Bildiiu PL'J

15、utIff4叙031!V rw PHhJTJUS谒花臥GEEDATB 19. DJ xiulu-iiD DO:DDS3打乃刿湘哇按3查找作者的姓、名、电话号码，并按作者姓、名排列。 查找书名和书的价格，按书价由大到小的次序排列。6）使用函数进行查找列出有多少类书。 列出书的定价有多少种。列出书价最低的书名和书价。 查出书价最高的书名及书价。 列出当年销量的总和。4表和视图创建及插入1）建表：创建两个表S*和T*，并插入下面内容，其中*是本人的学号（下同）。*Titleauthort nopriceQTY计算机原理张一平S309220.80200C语言程序设计李华H129815.30300数据库原理王家树D100722.70150计算机网络高明S569018.90230软件工程鲁廷璋S200535.00200T*t noPagepub-dateS30923041986D10072