《数据结构与算法应用-实验题目.docx》由会员分享，可在线阅读，更多相关《数据结构与算法应用-实验题目.docx（12页珍藏版）》请在金锄头文库上搜索。
1、数据结构与算法应用上机实验题目题目1（线性表）问题描述利用带头结点的单链表实现两个集合的并、交、差运算。（难易程度：低）实验目的1、掌握线性表的链表存储结构。2、掌握在单链表上基本操作的实现。3、在掌握单链表的基本操作上进行综合题的实现。实验内容及要求1、要求用带头结点的单链表存储两个集合中的元素和最终的结果。2、集合的元素限定为十进制数，程序应对出现重复的数据进行过滤，即使得链表中没有重复数据。3、显示两个集合的内容及其并集、交集和差集的内容。4、要求不改变原来的集合，并集、交集和差集分别另外存放。测试数据1、set1=3, 8, 5, 8,11，set2=22, 6, 8, 3, 15,1
2、1,20 set1set2set1set2set1-set22、其中一个集合为空集3、两个集合都是空集4、创建集合时有重复数据的情况题目2（栈、串）问题描述利用栈实现算术表达式的求值。可以简单一些，假设表达式中含有一位整数，以及+、-、*、/、（、）。但不受此限制。（难易程度：中）实验目的1、掌握栈的应用。2、掌握算符优先表达式求值的算法。3、掌握字符串处理和数值的转换。实验内容及要求1、表达式以字符串形式输入，并以#开始和结束（#也作为算法来处理）。如输入：#63*(9-7)-8/2#2、能够有效判别表达式的输入格式是否有误（如缺失操作数、非法算符、括号不匹配等错误），若输入格式错误，输出错
3、误提示。测试数据1、#63*(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、掌握二叉排序树的插入和删除操作。实验内容及要求1、构造二叉查找树（1）从文本文件中读入文本内容，能够分离出单词，过滤掉阿拉伯数字和标点符号，并将英文字母的大写形式全部转换成小写形式。（2）按照英文字母表的顺序构造英文单词的二叉查找树。当两个英
4、文单词的首字母相同时，按第二个字母进行排序，依次类推。（3）当待插入的单词已在二叉查找树中，则将该单词的出现次数增1。2、遍历二叉查找树（1）搜索：输入一个待检索单词，在二叉查找树中进行查找，如果能找到该单词，则输出该单词及其出现次数；（2）实现二叉查找树的中序遍历，并将遍历结果输出到屏幕上，包括单词和单词出现的位置。3、删除结点：给定一个停用词列表（停用词是指对搜索没有作用的词，如：of, and, a, an, the等等），将二叉查找树中的属于停用词表中的单词依次删除。4、可以显示菜单，在菜单中可以进行如下四项操作（但并不局限这些操作）：（1）读入文本内容，包含若干英文单词、标点符号以及
5、阿拉伯数字，用于构建二叉查找树。（2）输入停用词，每个停用词占一行。对于每个停用词，都需要删除二叉查找树中的相应结点，即：每输入一个停用词，执行一次删除结点的操作。（3）中序遍历二叉查找树，遍历结果中的每个单词占一行，先输出该单词，然后输出一个空格，再输出该单词出现的次数。（4）输入查询词。对每个查询词，都需要在二叉查找树中的搜索相应结点，如果找到，则输出该单词及其出现次数；如果未找到，则输出相应的信息。每个查询词的查询结果占一行，先输出该单词，然后输出一个空格，再输出该单词出现的次数。测试数据1、输入的文本含有大小写字母、阿拉伯数字、标点符号及其它字符。2、单词的数量应当足够多，并有一定量的
6、相同单词。、题目4（队列）问题描述实现一个简单银行叫号模拟系统。银行有三个窗口可以同时办理业务，当有用户到达银行时，首先选择自己要办理的业务，可以选择一种或多种。系统计算办理此业务所需的时间并显示给用户，然后系统查看有无空闲的窗口，如果有，通知用户到一个空闲窗口办理，如果没有空闲窗口，则需安排用户到某个窗口等候，系统先计算每个队列中用户办理业务的总时间，将用户安排到时间最短的队列等候。模拟输出多个用户办理业务的过程。（难易程度：高）实验目的1、深入理解队列的特性。2、掌握使用队列实现某些问题。实验内容及要求1、建立3个队列存放在三个窗口等待的用户。2、建立业务表，描述银行能够办理的各项业务，以
7、及办理业务所需时间。3、建立用户表，描述用户办理的业务，用户的状态等4、可以随机产生用户进入银行的时间，让用户输入所需办理的业务。5、由于输入的数据量较大，可以采用文本文件存放需要输入的数据。测试数据以下数据供参考：用户1在时间1到达银行，在1号窗口办理业务，需要1分钟用户1在时间2结束，离开用户2在时间3达到。在1号窗口开始办理，办理业务需要4分钟用户3在时间3到达，在2号窗口开始办理，办理业务需要5分钟用户4在时间5到达，在3号窗口开始办理，办理需要8分钟用户5在时间6到达，在1号窗口等待，办理业务需要4分钟用户2在时间8办理完业务，离开用户5在时间8在1号窗口，办理业务需要4分钟用户6在
8、时间8到达，在1号窗口等待，办理业务需要6分钟用户7在时间8到达，在2号窗口等待，办理业务需要10分钟题目5（二叉树）问题描述树和二叉树是最常用的非线性结构(树型结构)，其中以二叉树最为常见。遍历二叉树是二叉树各种操作的基础，它分为先序、中序和后序。（难易程度：中）实验目的1、熟练掌握二叉树的结构特性。2、掌握二叉树的各种存储结构的特点及使用范围。3、通过二叉树的基本操作的实现，从而思考一般树的基本操作的实现。4、熟练掌握各种遍历二叉树的递归和非递归算法。实验内容及要求1、创建二叉树时可以根据前序遍历序列进行创建，或者以其他方式创建二叉树。创建好之后将结点的值写入文本文件。2、创建好二叉链表之
9、后实现以下功能：（1）结点的值从文本文件读出，在屏幕上以树的形式或层次的形式显示。（2）输入一个结点值，输出其双亲及其所有子女，以及兄弟结点值。3、对二叉树进行递归和非递归遍历（先序、中序、后序），。测试数据1、用二叉链表表示一个大家族的家谱，即采用孩子兄弟表示法存储数。根为祖先结点，每个结点的左子树是其第一个孩子，右子树是其下一个兄弟。2、输入的结点值最好能够体现结点之间的双亲、孩子、兄弟之间的关系，以便于测试。题目6（哈夫曼树的编/译码器）问题描述利用哈夫曼编码进行通讯可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统将待传数据进行预先编码；在接受
10、端将传来的数据进行解码（复原）。对于可以双向传输的信道，每端都要有一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼的编译码系统。（难易程度：高）实验目的1、通过哈夫曼树的定义，掌握构造哈夫曼树的意义。2、掌握构造哈夫曼树的算法思想。3、通过具体构造哈夫曼树，进一步理解构造哈夫曼树编码的意义。实验内容及要求1、从终端读入字符集大小为n（即字符的个数），逐一输入n个字符和相应的n个权值（即字符出现的频度），建立哈夫曼树，将它存于文件 hfmtree 中。并将建立好的哈夫曼树以树或凹入法形式输出;对每个字符进行编码并且输出。2、利用已建好的哈夫曼编码文件 hfmtree ，对已编码的正文进行
11、译码，输出译码后的正文。3、采用文本文件存放文本，先统计文本中的每个字符出现的频率，然后再建立哈夫曼树，并进行编码和译码。测试数据1、用下表给出的字符集和频度的实际统计数据建立哈夫曼树。字符ABCDEFGHIJKLMN频度641322321032115475715322057字符OPQRSTUVWXYZ空格频度63151485180238181161168并实现以下报文的译码和输出：THIS PROGRAM IS MY FAVORITE2、采用文本文件存放文本，测试实验内容及要求的第3项。题目7（图）问题描述给定一个无向图或有向图，利用深度优先遍历和广度优先遍历对给定图进行遍历。（难易程度：低
12、）实验目的1、熟悉图的两种常用的存储结构。2、掌握对图的两种遍历方法，即深度优先遍历和广度优先遍历。3、进一步掌握利用递归或队列结构进行算法设计方法。实验内容及要求1、构造一个具有n个顶点的无向图或有向图。2、输出以深度优先遍历和广度优先遍历图的顶点序列。3、考虑如何把递归实现的深度优先遍历算法改为非递归算法。测试数据以下图作为测试数据：题目8（利用Prim算法求无向网的最小生成树）问题描述如果要在n个城市之间建设通信网络，只需架设n-1条线路即可。如何以最低的经济代价建设这个通信网，是求一个无向网的最小生成树问题。（难易程度：低）实验目的1、掌握图的各种存储结构和基本操作。2、对于实际问题的
13、求解能够选用合适的存储结构。3、通过Prim算法理解如何求无向网的最小生成树。实验内容及要求1、构造具有n个顶点的无向网，并利用Prim算法求网的最小生成树。2、以文本形式输出所求得的最小生成树中各条边以及它们的权值。测试数据以下图作为测试数据：题目9（图，最短路径）问题描述某旅行团要从南宁坐飞机周游东南亚7国，如果八地之间都有直飞航班，已知南宁坐标（378,78），河内（327,119），曼谷（232,266），金边（314,311），吉隆坡（255,477），新加坡（296,513），文莱（510,438），马尼拉（628,246），编程寻找最短周游路径，并显示出来。（例如：南宁-河内-曼
14、谷.）（难易程度：高）实验目的1、掌握图的各种存储结构和基本操作。2、对于实际问题的求解会选用合适的存储结构。3、通过Dijkstra算法求有向网的最短路径。实验内容及要求1、构造具有8个顶点的有向网，并利用Dijkstra或Floyd算法求最短路径。2、以文本形式输出所求得的最短路径中各条边以及它们的权值。测试数据按照题目的问题描述给出完全有向网，并作为测试数据。题目10（串、模式匹配）问题描述统计英文文章中单词个数、空格个数和标点符号的个数，同时还能够查找指定的单词，并替换为新的单词。（难易程度：中）实验目的1、掌握串的各种存储结构。2、根据实际问题选用合适的存储结构。3、掌握串的运算和模式匹配算法。实验内容及要求1、通过模式匹配算法及串的运算完成单词的查找和替换。2、以文本文件的形式存放英文文章，现将文章读入到串中，读入时需使用EOF函数判断文件结束标记。测试数据 英文文章的长度不能过短，必须能够说明问题。题目11（散列表）问题描述实现Hash表的建立、删除、插入以及查找操作，对学生信息（如学号、姓名、性别）进行管理。（难易程度：高）实验目的 1、掌握散列函数及解决冲突的方法。2、对于实际问题能够选用合适的散列
