数据结构课程设计-学生-个题目———————————————————————————————— 作者：———————————————————————————————— 日期：选题一：迷宫与栈问题【问题描述】以一个mXn的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。【任务要求】首先实现一个以链表作存储构造的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组〔i，j，d〕的形式输出。其中：〔i，j〕指示迷宫中的一个坐标，d表示走到下一坐标的方向。如，对于以下数据的迷宫，输出一条通路为：〔1，1，1〕，〔1，2，2〕，〔2，2数据结构课程设计题目，2〕，〔3，2，3〕，〔3，1，2〕，…。编写递归形式的算法，求得迷宫中所有可能的通路。以方阵形式输出迷宫及其通路。【测试数据】迷宫的测试数据如下：左上角〔0，1〕为入口，右下角〔8，9〕为出口。选题二：算术表达式与二叉树【问题描述】一个表达式和一棵二叉树之间，存在着自然的对应关系。写一个程序，实现基于二叉树表示的算术表达式的操作。【任务要求】假设算术表达式内可以含有变量〔a～z〕、常量〔0～9〕和二元运算符〔+，-，*，/，^(乘幂)〕。
实现以下操作：(E)—以字符序列的形式输入语法正确的前缀表达式并构造表达式E。(E)—用带括弧的中缀表达式输出表达式E。(V,c)—实现对变量V的赋值〔V=c〕，变量的初值为0。Value(E)—对算术表达式E求值。〔P，E1，E2〕--构造一个新的复合表达式〔E1〕P〔E2〕【测试数据】分别输入0；a；-91；+abc；+5^x28x；+++3^x3*2^x2x6并输出。每当输入一个表达式后，对其中的变量赋值，然后对表达式求值。选题三：银行业务模拟与离散事件模拟【问题描述】假设某银行有4个窗口对外接待客户，从早晨银行开门〔开门9：00am，关门5：00pm〕起不断有客户进入银行。由于每个窗口在某个时刻只能接待一个客户，因此在客户人数众多时需要在每个窗口前顺次排队，对于刚进入银行的客户〔建议：客户进入时间使用随机函数产生〕，如果某个窗口的业务员正空闲，那么可上前办理业务；反之，假设4个窗口均有窗户所占，他便会排在人数最少的队伍后面。【任务要求】编制一个程序以模拟银行的这种业务活动并计算一天中客户在银行逗留的平均时间。
建议有如下设置：客户到达时间随机产生，一天客户的人数设定为100人。银行业务员处理时间随机产生，平均处理时间10分钟。将一天的数据〔包括业务员和客户〕以文件方式输出。【测试数据】由随机数产生器生成选题四：文学研究助手与模式匹配算法KMP【问题描述】文学研究人员需要统计某篇英文小说中某些形容词的出现次数和位置。试写一个实现这一目标的文字统计系统【任务要求】英文小说存于一个文本文件中。待统计的词聚集合要一次输入完毕，即统计工作必须在程序的一次运行之后就全部完成。程序的输出结果是每个词的出现次数和出现位置所在的行的行号，格式自行设计。待统计的“单词〞在文本串中不跨行出现，它或者从行首开场，或者前置以一个空格符。模式匹配要基于KMP算法。推广到更一般的模式集匹配问题，并设待查模式串可以跨行〔提示：定义操作〕。【测试数据】待统计的词集：if、else、for、while、、void、int、char、、选题五：北理珠校园导游咨询与最短路径【问题描述】从北京理工大学珠海学院的平面图中选取有代表性景点〔10-15个〕，抽象成一个无向带权图。以图中顶点表示景点，边上的权值表示两地之间距离。
本程序的目的是为用户提供路径咨询。根据用户指定的始点和终点输出相应路径，或者根据用户指定的景点输出景点的信息。【任务要求】从北京理工大学珠海学院的平面图中选取有代表性景点〔10-15个〕，抽象成一个无向带权图。以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等信息。为来访客人提供图中任意景点相关信息的查询。为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。区分汽车线路与步行线路。【测试数据】北理珠校园导游图〔距离可估计〕。选题六：B-树与B+树及其操作【问题描述】学习并研究B-树与B+树，并编写演示它们操作的程序。【任务要求】B-树构建、查找、插入和删除操作程序。B+树构建、查找、插入和删除操作程序。【测试数据】选题七：哈夫曼()编/译码器【问题描述】利用哈夫曼编码进展通信可以大大提高信道利用率，缩短信息传输时间，降低传输本钱。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进展译码〔复原〕。对于双工信道〔即可以双向传输信息的信道〕，每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。
【任务要求】一个完整的系统应具有以下功能：I：初始化〔〕。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件中。E：编码〔〕。利用以建好的哈夫曼树〔如不在内存，那么从文件中读入〕，对文件中的正文进展编码，然后将结果存入文件中。D：译码〔〕。利用已建好的哈夫曼树将文件中的代码进展译码，结果存入文件中。P：印代码文件〔Print〕。将文件以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件中。T：印哈夫曼树〔Tree 〕。将已在内存中的哈夫曼树以直观的方式〔树或凹入表形式〕显示在终端上，同时将此字符形式的哈夫曼树写入文件中。【测试数据】利用教科书例6-2〔严蔚敏?数据构造?P148〕中的数据调试程序。用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“THIS IS MY 〞。
字符空格频度字符频度选题八：比拟【问题描述】在教科书中，各种的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机数据比拟各种算法的关键字比拟次数和关键字移动次数，以取得直观感受。【任务要求】对以下7种常用的进展比拟：冒泡排序、直接插入排序、简单项选择择排序、希尔排序、堆排序、归并排序、快速排序。待排序表的表长不小于100；其中的数据要用伪随机数程序产生；至少要用5组不同的输入数据作比拟；比拟的指标为有关键字参加的比拟次数和关键字的移动次数〔关键字交换计为3次移动〕。最后要对结果作出简单分析，包括对各组数据得出结果波动大小的解释。【测试数据】由随机数产生器生成选题九：简单行编辑程序【问题描述】文本编辑器程序是利用计算机进展文字加工的根本软件工具数据结构课程设计题目 数据结构课程设计学生个题目.doc 23页，实现对文本文件的插入、删除等修改操作。限制这些操作以行为单位进展的编辑程序称为行编辑程序。被编辑的文本文件可能很大，全部读入编辑程序的数据空间〔内存〕的作法既不经济，也不总能实现。
一种解决方法是逐段地编辑。任何时刻只把待编辑文件的一段放在内存，利为活区。试按照这种方法实现一个简单的行编辑程序。设文件每行不超过320个字符，很少超过80个字符。【任务要求】实现以下4条根本编辑命令：行插入：格式：i将插入活区中第行之后。行删除。格式：d[]删除活区中第(到第行)。例如“d10〞和“d10 14活区切换。格式：n将活区写入输出文件，并从输入文件中读入下一段，作为新的活区。活区显示。模式：p逐页地〔每页20行〕显示活区内容，每显示一页之后请用户决定是继续显示以后各页〔如果存在〕。印出的每一行要前置行号和一个空格符，行号固定占4位，增量为1。各条命令中的行号均须在活区中各行行号范围之内，只有插入命令的行号可以等于活区第一行行号减1，表示插入当前屏幕中第一行之前，否那么命令参数非法。【测试数据】自行设定，注意测试将活区删空等特殊情况。选题十：一元多项式计算【问题描述】1.能够按照指数降序排列建立并输出多项式；2.能够完成两个多项式的相加、相减，并将结果输入；【任务要求】1.存储构造;2.多项式相加的根本过程的算法〔可以使用程序流程图〕3.可以提出算法的改良方法；【测试数据】自行设定，注意边界等特殊情况。
选题十一：集合的交、并、差运算【问题描述】编制一个能演示执行集合的交、并和差运算的程序。【任务要求】集合元素用小写英文字母，执行各种操作应以对话方式执行。算法要点：利用单链表表示集合；理解好三种运算的含【测试数据】自行设定，注意边界等特殊情况。选题十二：动态查找表【问题描述】利用二叉排序树完成动态查找表的建立、指定关键字的查找、插入与删除指定关键字结点。【任务要求】算法输入：指定一组数据。算法输出：显示二叉排序树的中序遍历结果、查找成功与否的信息、插入和删除后的中序遍历结果(排序结果)。算法要点：二叉排序树建立方法、动态查找方法,对树进展中序遍历。【测试数据】自行设定，注意边界等特殊情况。选题十三：学生成绩管理【问题描述】本例对学生的成绩管理做一个简单的模拟，用菜单项选择择方式完成以下功能： 登记学生成绩；查询学生成绩；插入学生成绩；删除学生成绩。【任务要求】算法输入：操作要求，学生信息算法输出：操作结果算法要点：把问题看成是对线性表的操作。将学生成绩组织成顺序表，那么登记学生成绩即是建立顺序表操作；查询学生成绩、插入学生成绩、删除学生成绩即是在顺序表中进展查找、插入和删除操作。
【测试数据】自行设定，注意边界等特殊情况。选题十四：马踏棋盘【问题描述】将马随机放在国际象棋的8 8棋盘Bord[8Ⅱ8]的某个方格中，马按走棋规那么进展移动。要求每个方格上只进入一次，走遍棋盘上全部64个方格。【任务要求】编制非递归程序，求出马的行走路线 ，并按求出的行走路线，将数字1，2，…，64依次填入一个8 8的方阵数据结构课程设计题目，输出之。测试数据：由读者指定,可自行指定一个马的初始位置。实现提示：每次在多个可走位置中选择一个进展试探，其余未曾试探过的可走位置必须用适当构造妥善管理，以备试探失败时的“回溯〞(悔棋)使用。【测试数据】自行设定，注意边界等特殊情况。选题十五： 环【问题描述】编号是1，2，……,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码〔正整数〕。一开场任选一个正整数作为报数上限值m,从第一个仍开场顺时针方向自1开场顺序报数，报到m时停顿报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开场重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。【任务要求】利用单向循环链表存储构造模拟此过程，按照出列的顺序输出各个人的编号。
测试数据：m的初值为20，n=7 ,7个人的密码依次为3，1，7，2，4，7，4，首先m=6,那么正确的输出是什么？ 要求：输入数据：建立输入处理输入数据，输入m的初值，n ，输入每个人的密码，建立单循环链表。 输出形式：建立一个输出函数，将正确的输出序列【测试数据】自行设定，注意边界等特殊情况。选题十六： 最小生成树【问题描述】在n个城市之间建立网络，只需保证连通即可，求最经济的架设方法。对于图，其生成树中的边也带权，将生成树各边的权值总和称为生成树的权，并将权值最小的生成树称为最小生成树〔 Tree〕，简称为MST。有两种非常典型的算法：Prim算法和算法。【任务要求】设计程序完成如下功能：对给定的网和起点，用PRIM算法和算法的根本思想求解出所有的最小生成树。存储构造可自行选择。【测试数据】自行设定，注意边界等特殊情况。选题十七：通讯录管理【问题描述】该设计采用菜单作为应用程序的主要界面，用控制语句来改变程序执行的顺序，控制语句是实现构造化程序设计的根底。该设计的任务是利用一个简单实用的菜单，通过菜单单项进展选择，实现和完成通讯录管理中常用的几个不同的功能。
【任务要求】菜单内容通讯录链表的建立通讯者结点的插入通讯者结点的查询通讯者结点的删除通讯录链表的输出退出管理系统请选择0~5：设计要求使用0~5来选择菜单项，其他输入那么不起作用。功能函数设计5个不同功能的算法实现编程题，目的是练习利用链表构造来解决实际应用问题的能力，进一步理解和熟悉线形表的链式存储构造。【测试数据】自行设定，注意边界等特殊情况。选题十八：运动会分数统计【问题描述】参加运动会有n个学校，学校编号为1……n。比赛分成m个男子工程，和w个女子工程。工程编号为男子1……m，女子m+1……m+w。不同的工程取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。〔m
文章来源:https://max.book118.com/html/2021/1030/5341223022004043.shtm