山东大学数据结构《数据结构》实验大纲 ver1.docx
- 文档编号:12786060
- 上传时间:2023-06-08
- 格式:DOCX
- 页数:19
- 大小:168.70KB
山东大学数据结构《数据结构》实验大纲 ver1.docx
《山东大学数据结构《数据结构》实验大纲 ver1.docx》由会员分享,可在线阅读,更多相关《山东大学数据结构《数据结构》实验大纲 ver1.docx(19页珍藏版)》请在冰点文库上搜索。
山东大学数据结构《数据结构》实验大纲ver1
《数据结构》实验指导书
(本实验指导书尚未定稿,因此会经常改进,建议大家每次上机前重新下载,由于尚未定稿,可能存在错误,发现后请标注颜色发给lbd@,非常感谢。
如果有其他问题可以通过qq:
723812464联系我。
)
一、实验要求
1、独立完成实验,不可抄袭其他同学程序,包括往届同学的程序,实验平台具有查重功能,如果涉嫌抄袭,将被要求完成对应的补充实验才能够得到全部得分。
2、因采用程序进行测试,因此对输出格式要求严格,格式不对也会被判结果错误。
输出数据时,每个数之间用“,”隔开,特别注意,任何地方不要有多余的空格、冒号等,参考样例在需要的地方换行。
3、输入数据前,要显示“input”字样,输出前要有“Output”字样,输出结束有“End”字样。
详细格式要求参考每个实验的格式样例。
4、程序输入输出数据采用标准输入输出方式“cin>>、cout<<”,程序中不要使用getch()、getchar()、cin.get()、putchar()函数,否则会造成运行错误或者结果错误。
5、特别注意:
getch()、getchar()、cin.get()也不要出现在注释中,否则造成“输入错误”
二、开发工具
MicrosoftVisualC++6.0
三、实验周数
8周*2小时
四、评分标准
在要求完成时间(实验内容中有准确的要求完成时间)之前完成并提交到实验平台,测试通过,该实验计10分或者15分,在规定时间之后完成,计应得分数的80%。
如果查重涉嫌作弊,在上面得分基础上仅仅得60%的得分,可以通过完成补充实验提高实验得分。
五、指导书下载地址
Ftp服务器地址:
211.87.224.23,用户/密码:
db/dbsystem
六、作业提交步骤及办法
1、每次上机,登入系统提交试验作业。
登入网址:
http:
//211.87.224.23:
8080/testplat/
账号密码:
学号/123
登入成功后如果不能够看到实验平台画面,可以输入下面网址:
http:
//211.87.224.23:
8080/testplat/index.jsp,就可以进入实验平台了。
2、源程序(即源代码)文件名采用test01_ID.cpp(如果是多个cpp文件,合并到一个cpp文件后上传),test01代表实验一(下面相同),ID代表本人学号(下面相同),例如学号为201000300001的学生的第一个实验源程序文件名为test01_201000300001.cpp。
程序编译后会在源程序所在文件夹下的debug文件夹下创建一个可执行程序(即目标代码)test01_ID.exe文件。
3、无论采用哪一种开发工具,编译后产生的目标代码必须确保能够不依赖系统环境能够独立运行,既不能依赖其他任何DLL程序。
目前实验室的VC环境能够正确编译成可执行程序。
4、作业自测通过后,在实验平台上,将test01_ID.cpp文件上传到相应实验源代码,将test01_ID.exe文件上传到相应实验的目标代码,然后提交实验,等待10秒后,执行【刷新】,查看实验状态:
1)上传源代码:
已经正确上传完源代码。
2)上传目标代码:
已经正确上传目标代码。
3)提交试验:
已经提交实验,等待后台测试目标代码。
如果保持该状态超过1分钟,说明后台出现错误,请通知实验指导教师。
4)按时完成:
程序在要求时间内完成实验。
如果错误描述显示“涉嫌作弊,请完成对应的补充实验”,则得分为总分值的10%。
可以通过完成对应的补充实验,获得剩余的90%分值。
5)超时完成:
程序在要求时间后完成实验。
如果错误描述显示“涉嫌作弊,请完成对应的补充实验”,则得分为总分值的6%。
可以通过完成对应的补充实验,获得剩余的54%分值。
6)运行错误:
上传的目标代码可能不能正确运行,再一次提交实验进行尝试,如果仍然没有解决问题,进一步测试你的程序能够正确运行,是否按要求的格式输入数据。
7)结果错误:
程序运行后输出的结果和答案不一致,也就是你的程序存在逻辑错误,需要你进一步修改调试。
8)正在查重:
后台已经开始查重。
如果保持该状态超过1分钟,说明后台出现错误,请通知实验指导教师。
9)正在测试:
后台已经开始测试目标代码。
如果保持该状态超过1分钟,说明后台出现错误,请通知实验指导教师。
11)文件名错误:
源程序文件名采用test01_ID.cpp,目标文件名称采用test01_ID.exe。
12)文件太小:
源程序有效代码太少,低于20行。
如果你的程序确实低于20行代码,请联系指导教师。
特别注意:
错误描述是系统自动给出的错误判断,因此不一定准确指明错误的原因,可以通过多次刷新,查看是否有更加准确的错误描述。
5、如果没有通过,根据提示继续调试你的程序直到通过。
实验一递归练习
一、要求完成时间
实验开始后的第二周之前完成
二、实验目的
1、熟悉开发工具的使用。
2、掌握递归的实现思想。
三、实验内容
1、输入2-10个大于0的正整数,如果输入0作为结束。
2、输出这几个整数的全排列,每个数之间用半角“,”隔开,中间不要有空格,每个排列单独一行。
3、程序一定要有Input、Output、End提示信息,但是不要有格式没有出现的其他提示,以下各实验相同。
4、程序最后增加system(pause),显示Pressanykeytocontinue并暂停。
四、输入输出请严格按下面要求的格式实现
实验二排序算法
一、要求完成时间
实验开始后的第三周之前完成
二、实验目的
掌握各种排序方法的实现思想。
三、实验内容
1、输入2-10个不为零的正整数,遇到0代表输入结束,0不参与排序。
2、数字选择排序方法,1-冒泡排序、2-插入排序、3-基数排序
3、基数排序能够实现小于10的正整数的排序。
4、使用所选排序方法的排序,结果输出所用方法以及结果,每个数之间用“,”隔开,中间不要有空格。
5、输入输出请严格按下面要求的格式实现
实验三线性表操作
一、要求完成时间
实验开始后的第四周之前完成
二、实验目的
1、掌握线性表的基本操作:
插入、删除、查找。
2、掌握链表遍历器的使用方法。
三、实验内容
1、创建线性表类。
线性表的存储结构使用链表。
2、完成表首插入元素、删除指定元素、搜索表中是否有指定元素、输出链表。
3、输入n个不为零的整数作为节点元素值,遇到0代表输入结束(不创建元素值为0的节点),创建链表。
输出整个链表。
4、输入一个整数,将该数作为一个元素值插入表首位置。
输出整个链表。
5、输入一个整数,在链表中进行搜索,输出其在链表中的位置。
如果不存在输出0。
6、再一次输入一个整数,在链表中进行搜索,输出其在链表中的位置。
如果不存在输出0。
7、再一次输入n个不为零的整数作为节点元素值,遇到0代表输入结束(不创建元素值为0的节点),创建并输出整个链表。
8、实现上面两个链表的合并,第一个链表在前第二个在后,输出合并后的链表。
9、使用链表遍历器输出合并后的链表的反序输出。
四、输入输出请严格按下面要求的格式实现
实验四堆栈的应用
一、要求完成时间
实验开始后的第五周之前完成
二、实验目的
掌握堆栈的使用。
三、实验内容
1、输入一个数学表达式(假定表达式输入格式合法),计算表达式结果并输出。
2、数学表达式由单个数字和运算符“+”、“-”、“*”、“/”、“(、)”构成,例如2+3*(4+5)-6/4。
3、变量、输出采用整数,只舍不入。
四、输入输出请严格按下面要求的格式实现(结果可能不对)
实验五二叉树操作
一、要求完成时间
实验开始后的第六周之前完成
二、实验目的
掌握二叉树的基本概念,二叉树的存储结构使用链表。
三、实验内容
1、输入一个完全二叉树的层次遍历字符串,创建这个二叉树,输出这个二叉树的前序遍历字符串、中序遍历字符串、后序遍历字符串、结点数目、二叉树高度(上述每一个结果独立一行显示)。
2、输入二叉树前序序列和中序序列(各元素各不相同),创建这个二叉树,输出该二叉树的后序序列、层次遍历。
四、输入输出请严格按下面要求的格式实现
实验六堆和搜索树
一、要求完成时间
实验开始后的第七周之前完成
二、实验目的
掌握堆和搜索树的基本概念,插入、删除方法。
三、实验内容
1、输入一系列不为零的正整数(最多不超过20个),遇到0代表输入结束(不包含0)。
2、根据上面输入的数据序列,用初始化方法创建最大堆(不要用节点依次插入的办法创建最大堆),然后输出最大堆的层次序列。
3、输出用堆排序后的排序结果。
4、根据上面输入的数据,创建二叉搜索树,输出二叉搜索树的前序序列、中序序列(分行输出)。
5、根据上面输入的数据作为字母出现的频率(第1个数代表A频率,第2个数代表B频率,……),创建Huffman树,输出Huffman编码,要求左子树权值小于右子树权值,左边为0,右边为1。
按字母由A到Z的顺序输出,格式采用“大写字母:
编码”,例如A:
0,B:
10……Z:
1100
四、输入输出请严格按下面要求的格式实现(结果可能不对)
实验七图的操作
一、要求完成时间
实验开始后的第八周之前完成
二、实验目的
掌握图的基本概念,描述方法;遍历方法。
三、实验内容
1、创建图类,存储结构使用邻接矩阵。
2、输入图的节点数n(不超过10个)、边数m,节点分别用1-n代表。
3、采用“起始节点,终止节点,权值”输入图的m条边,创建图。
4、输出从节点1开始的BFS遍历,要求小的节点在前大的在后。
5、输出从节点1开始的DFS遍历,要求小的节点在前大的在后。
6、输出从第1节点到第n节点最短路径的长度,如果没有路经,输出0。
7、输出最小生成树的所有边。
输出格式采用“起始节点-终止节点:
权值”,小的节点在前,大的节点在后,每个边独立一行输出,例如1-2:
12是正确的,2-1:
12是错误的。
如果没有最小生成树,输出0-0:
0
四、输入输出请严格按下面要求的格式实现(结果可能不对)
查重涉嫌作弊,要求完成如下对应的实验
补充实验一递归练习
一、要求完成时间
实验开始后的第二周之前完成
二、实验目的
1、熟悉开发工具的使用。
2、掌握递归的实现思想。
三、实验内容
1、输入2-10个大于0的正整数,如果输入0作为结束。
2、输出这几个整数的形成集合的所有子集,每个子集用{}括起来,每个数之间用半角“,”隔开,中间不要有空格,每个子集单独一行。
四、输入输出请参考下面要求的格式实现
补充实验二排序算法
一、要求完成时间
实验开始后的第三周之前完成
二、实验目的
掌握基数排序方法的实现思想。
三、实验内容
1、输入2-10个不为零的正数(非正整数),遇到0代表输入结束,0不参与排序。
2、数字选择排序方法,1-冒泡排序、2-插入排序、3-归并排序
3、使用所选排序方法的排序,结果输出所用方法以及结果,每个数之间用“,”隔开,中间不要有空格,如果输出是整数,则小数点后面不要输出0。
4、输入输出请参考下面要求的格式实现
补充实验三线性表操作
一、要求完成时间
实验开始后的第四周之前完成
二、实验目的
3、掌握线性表的基本操作:
插入、删除、查找。
4、掌握链表遍历器的使用方法。
三、实验内容
1、创建线性表类。
线性表的存储结构使用链表。
2、完成表首插入元素、删除指定元素、搜索表中是否有指定元素、输出链表。
3、再一次输入n个不为零的整数作为节点元素值,遇到0代表输入结束(不创建元素值为0的节点),创建另外一个链表,输出整个链表。
4、使用链表遍历器实现上面两个链表的合并,第二个链表在前第一个在后,输出合并后的链表。
5、输出合并后的链表的反序输出。
6、输入一个整数,在合并后的链表中找到这个数并删除这个节点,然后输出整个链表。
如果找不到这个数,不做任何删除,输出整个链表。
四、输入输出请参考下面要求的格式实现
补充实验四堆栈的应用
一、要求完成时间
实验开始后的第五周之前完成
二、实验目的
掌握堆栈的使用。
三、实验内容
4、输入一个数学表达式(假定表达式输入格式合法),计算表达式结果并输出。
5、数学表达式由单个数字和运算符“+”、“-”、“*”、“/”、“(、)”构成,例如2+3*(4+5)–6/4。
6、变量、输出全部采用实数,例如上式输出结果27.5。
四、输入输出请参考下面要求的格式实现(结果可能不对)
补充实验五二叉树操作
一、要求完成时间
实验开始后的第六周之前完成
二、实验目的
掌握二叉树的基本概念,二叉树的存储结构使用链表。
三、实验内容
1、输入一个完全二叉树的层次遍历字符串,创建这个二叉树,输出这个二叉树的前序遍历字符串、中序遍历字符串、后序遍历字符串、结点数目、二叉树高度。
2、输入二叉树前序序列和中序序列(各元素各不相同),创建这个二叉树,输出该二叉树的后序序列、层次序列。
四、输入输出请参考下面要求的格式实现
补充实验六堆和搜索树
一、要求完成时间
实验开始后的第七周之前完成
二、实验目的
掌握堆和搜索树的基本概念,插入、删除方法。
三、实验内容
1、输入一系列不为零的正整数(最多不超过20个),遇到0代表输入结束(不包含0)。
2、根据输入的数据,创建最大堆,输出最大堆的层次序列。
3、输出用堆排序后的排序结果。
4、根据输入的数据,创建二叉搜索树,输出二叉搜索树的前序序列。
5、输出二叉搜索树的中序序列。
6、根据输入的数据作为字母出现的频率(第1个数代表A频率,第2个数代表B频率,……),创建Huffman树,输出Huffman编码,要求左子树权值小于右子树权值,左边为0,右边为1。
输出按字数顺序由小到大输出,格式采用“字母:
编码”,例如A:
0,B:
10……
四、输入输出请参考下面要求的格式实现(结果可能不对)
补充实验七图的操作
一、要求完成时间
实验开始后的第八周之前完成
二、实验目的
掌握图的基本概念,描述方法;遍历方法。
三、实验内容
1、创建图类,存储结构使用邻接矩阵。
2、输入图的节点数n(不超过10个)、边数m,节点分别用1-n代表。
3、采用“起始节点,终止节点,权值”输入图的m条边,创建图。
4、输出从节点1开始的BFS遍历。
5、输出从节点1开始的DFS遍历。
6、输出从第1节点到第n节点最短路径的长度,如果没有路经,输出0。
7、输出最小生成树的所有边。
输出格式采用“起始节点-终止节点:
权值”,小的节点在前,大的节点在后,每个边独立一行输出,例如1-2:
12是正确的,2-1:
12是错误的。
如果没有最小生成树,输出0-0:
0
四、输入输出请参考下面要求的格式实现(结果可能不对)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 山东大学数据结构数据结构实验大纲 ver1 山东大学 实验 大纲
![提示](https://static.bingdoc.com/images/bang_tan.gif)