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