数据结构实验题目与要求

《数据结构实验题目与要求》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构与算法实验计算机软件所2015.09数据结构与算法实验实验一背包问题的求解实验二农夫过河问题的求解实验三简易电子表格的设计实验四八皇后问题实验五约瑟夫环问题仿真实验六教学计划编制问题（*）实验七二叉排序树与平衡二叉树的实现（*）实验八停车场模拟管理程序的设计与实现实验九学生成绩分析实验十一元稀疏多项式计算器实验十一、哈夫曼压缩/解压缩算法（编译码器）（*）实验十二、全国交通咨询模拟系统（*）实验十三、迷宫问题（*）2西安交通大学计算机系数据结构与算法实验注：从上述题目中任选3题目，打星号至少选1

2、题，共3个实验！3西安交通大学计算机系成绩评定题目完成情况的验收基本题目验收时间：上机时间完成当场验收验收方式：本人简要介绍完成的情况，并检查程序运行结果成绩评定：按照预先给定的各题分值进行成绩评定选做题目验收时间：上机时间完成当场验收，并给所指定的分数验收方式：填写成绩评定考核表，本人简要介绍完成的情况，检查程序运行结果，提交专题实验报告成绩评定：实验题目完成情况和报告完成情况，最后核定成绩结果正确程序没有BUG并有独到之处成绩为所给题目分数的90－100％结果正确程序没有BUG成绩为所给题目分数的7

3、5-90％结果不完全正确成绩为所给题目分数的>60-75%结果不正确成绩为所给题目分数的<60%实验报告电子版发至：ymzhang@mail.xjtu.edu.cn文件名：数据结构与算法专题实验实验报告_计算机XX班_学号_姓名实验报告纸质版：专题实验课程结束时，各班收齐上交到刘向东老师或赵仲孟老师最终成绩总成绩=实验题目得分+实验报告得分4西安交通大学计算机系实验一背包问题的求解1.问题描述假设有一个能装入总体积为T的背包和n件体积分别为w1,w2,…wn的物品，能否从n件物品中挑选若干件恰好装满背包

4、，即使w1+w2+…+wm=T，要求找出所有满足上述条件的解。例如：当T=10，各件物品的体积{1,8,4,3,5,2}时，可找到下列4组解：(1,4,3,2)(1,4,5)(8,2)(3,5,2)。2.实现提示可利用回溯法的设计思想来解决背包问题。首先，将物品排成一列，然后，顺序选取物品装入背包，若已选取第i件物品后未满，则继续选取第i+1件，若该件物品“太大”不能装入，则弃之，继续选取下一件，直至背包装满为止。如果在剩余的物品中找不到合适的物品以填满背包，则说明“刚刚”装入的物品“不合适”，应将它取

5、出“弃之一边”，继续再从“它之后”的物品中选取，如此重复，直到求得满足条件的解，或者无解。由于回溯求解的规则是“后进先出”，自然要用到“栈”。进一步考虑：如果每件物品都有体积和价值，背包又有大小限制，求解背包中存放物品总价值最大的问题解---最优解或近似最优解。5西安交通大学计算机系实验二农夫过河问题的求解1.问题描述一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸。他要把这些东西全部运到北岸。他面前只有一条小船，船只能容下他和一件物品，另外只有农夫才能撑船。如果农夫在场，则狼不能吃羊，羊不能吃白菜，

6、否则狼会吃羊，羊会吃白菜，所以农夫不能留下羊和白菜自己离开，也不能留下狼和羊自己离开，而狼不吃白菜。请求出农夫将所有的东西运过河的方案。2.实现提示求解这个问题的简单方法是一步一步进行试探，每一步搜索所有可能的选择，对前一步合适的选择后再考虑下一步的各种方案。要模拟农夫过河问题，首先需要对问题中的每个角色的位置进行描述。可用4位二进制数顺序分别表示农夫、狼、白菜和羊的位置。用0表在南岸，1表示在北岸。例如，整数5(0101)表示农夫和白菜在南岸，而狼和羊在北岸。现在问题变成：从初始的状态二进制0000(

7、全部在河的南岸)出发，寻找一种全部由安全状态构成的状态序列，它以二进制1111(全部到达河的北岸)为最终目标。总状态共16种(0000到1111)，(或者看成16个顶点的有向图)可采用广度优先或深度优先的搜索策略---得到从0000到1111的安全路径。以广度优先为例：整数队列---逐层存放下一步可能的安全状态；Visited[16]数组标记该状态是否已访问过，若访问过，则记录前驱状态值---安全路径。最终的过河方案应用汉字显示出每一步的两岸状态。6西安交通大学计算机系实验三简易电子表格的设计1.问题描

8、述设计一个支持基本计算统计功能和其它一些表格管理/处理功能的软件，使用户可在该软件的支持下，用交互方式进行表格建立、数据输入、数据编辑及其它一些表格操作。即类似于简易Execel表格处理软件。2.基本要求(1)建立表格：建立空白表格，同时在屏幕上显示，使其处于可输入数据的状态。用户可指定新建表格的行列数。(2)输入数据与编辑数据：通过键盘将数据输入到显示在屏幕上的电子表格上。(3)基本统计计算：可选择按行或列合计、求平均、求最大最小。(4)