数据结构与算法应用-实验题目

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

1、《数据结构与算法应用》上机实验题目题目1（线性表）[问题描述]利用带头结点的单链表实现两个集合的并、交、差运算。（难易程度：低）[实验目的]1、掌握线性表的链表存储结构。2、掌握在单链表上基本操作的实现。3、在掌握单链表的基本操作上进行综合题的实现。[实验内容及要求]1、要求用带头结点的单链表存储两个集合中的元素和最终的结果。2、集合的元素限定为十进制数，程序应对出现重复的数据进行过滤，即使得链表中没有重复数据。3、显示两个集合的内容及其并集、交集和差集的内容。4、要求不改变原来的集合，并集、交集和差集分别另外存放。[测试数据]1、set

2、1={3,8,5,8,11}，set2={22,6,8,3,15,11,20}set1∪set2＝set1∩set2＝set1-set2＝2、其中一个集合为空集3、两个集合都是空集4、创建集合时有重复数据的情况题目2（栈、串）[问题描述]利用栈实现算术表达式的求值。可以简单一些，假设表达式中含有一位整数，以及+、-、*、/、（、）。但不受此限制。（难易程度：中）[实验目的]1、掌握栈的应用。12/122、掌握算符优先表达式求值的算法。3、掌握字符串处理和数值的转换。[实验内容及要求]1、表达式以字符串形式输入，并以‘#’开始和结束（‘#’

3、也作为算法来处理）。如输入：#6＋3*(9-7)-8/2#2、能够有效判别表达式的输入格式是否有误（如缺失操作数、非法算符、括号不匹配等错误），若输入格式错误，输出错误提示。[测试数据]1、#6＋3*(9-7)-8/2#2、#(8-2)/(3-1)*(9-6)#3、#5+a*(8-4)/2#4、#5+(7-3)*6#题目3（二叉排序树）[问题描述]利用二叉查找树（又称为二叉排序树、二叉搜索树）实现对输入的英文单词进行搜索，同时可给出单词出现的次数。（难易程度：高）[实验目的]1、掌握二叉链表的存储结构。2、掌握搜索和过滤的方法。3、掌握二

4、叉排序树的插入和删除操作。[实验内容及要求]1、构造二叉查找树（1）从文本文件中读入文本内容，能够分离出单词，过滤掉阿拉伯数字和标点符号，并将英文字母的大写形式全部转换成小写形式。（2）按照英文字母表的顺序构造英文单词的二叉查找树。当两个英文单词的首字母相同时，按第二个字母进行排序，依次类推。（3）当待插入的单词已在二叉查找树中，则将该单词的出现次数增1。2、遍历二叉查找树（1）搜索：输入一个待检索单词，在二叉查找树中进行查找，如果能找到该单词，则输出该单词及其出现次数；（2）实现二叉查找树的中序遍历，并将遍历结果输出到屏幕上，包括单词和

5、单词出现的位置。12/123、删除结点：给定一个停用词列表（停用词是指对搜索没有作用的词，如：of,and,a,an,the等等），将二叉查找树中的属于停用词表中的单词依次删除。4、可以显示菜单，在菜单中可以进行如下四项操作（但并不局限这些操作）：（1）读入文本内容，包含若干英文单词、标点符号以及阿拉伯数字，用于构建二叉查找树。（2）输入停用词，每个停用词占一行。对于每个停用词，都需要删除二叉查找树中的相应结点，即：每输入一个停用词，执行一次删除结点的操作。（3）中序遍历二叉查找树，遍历结果中的每个单词占一行，先输出该单词，然后输出一个空

6、格，再输出该单词出现的次数。（4）输入查询词。对每个查询词，都需要在二叉查找树中的搜索相应结点，如果找到，则输出该单词及其出现次数；如果未找到，则输出相应的信息。每个查询词的查询结果占一行，先输出该单词，然后输出一个空格，再输出该单词出现的次数。[测试数据]1、输入的文本含有大小写字母、阿拉伯数字、标点符号及其它字符。2、单词的数量应当足够多，并有一定量的相同单词。、题目4（队列）[问题描述]实现一个简单银行叫号模拟系统。银行有三个窗口可以同时办理业务，当有用户到达银行时，首先选择自己要办理的业务，可以选择一种或多种。系统计算办理此业务所

7、需的时间并显示给用户，然后系统查看有无空闲的窗口，如果有，通知用户到一个空闲窗口办理，如果没有空闲窗口，则需安排用户到某个窗口等候，系统先计算每个队列中用户办理业务的总时间，将用户安排到时间最短的队列等候。模拟输出多个用户办理业务的过程。（难易程度：高）[实验目的]1、深入理解队列的特性。2、掌握使用队列实现某些问题。[实验内容及要求]1、建立3个队列存放在三个窗口等待的用户。12/122、建立业务表，描述银行能够办理的各项业务，以及办理业务所需时间。3、建立用户表，描述用户办理的业务，用户的状态等4、可以随机产生用户进入银行的时间，让用

8、户输入所需办理的业务。5、由于输入的数据量较大，可以采用文本文件存放需要输入的数据。[测试数据]以下数据供参考：用户1在时间1到达银行，在1号窗口办理业务，需要1分钟用户1在时间2结束，离开用