数据结构课程设计学生21个题目

1/1数据结构课程设计-学生-21个题目选题一：迷宫与栈问题

【问题描述】

以一个mXn的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。

【任务要求】

1)首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。

求得的通路以三元组（i，j，d）的形式输出。其中：（i，j）指示迷宫中的一个坐标，

d表示走到下一坐标的方向。如，对于下列数据的迷宫，输出一条通路为：（1，1，

1），（1，2，2），（2，2，2），（3，2，3），（3，1，2），…。

2)编写递归形式的算法，求得迷宫中全部可能的通路。

3)以方阵形式输出迷宫及其通路。

【测试数据】

迷宫的测试数据如下：左上角（0，1）为入口，右下角（8，9）为出口。

出口

出口

选题二：算术表达式与二叉树

【问题描述】

一个表达式和一棵二叉树之间，存在着自然的对应关系。写一个程序，实现基于二叉树表示的算术表达式的操作。

【任务要求】

假设算术表达式Expression内可以含有变量（a～z）、常量（0～9）和二元运算符（+，-，*，/，^(乘幂)）。实现以下操作：

1)ReadExpre(E)—以字符序列的形式输入语法正确的前缀表达式并构造表达式E。

2)WriteExpre(E)—用带括弧的中缀表达式输出表达式E。

3)Assign(V,c)—实现对变量V的赋值（V=c），变量的初值为0。

4)Value(E)—对算术表达式E求值。

5)CompoundExpr（P，E1，E2）--构造一个新的复合表达式（E1）P（E2）

【测试数据】

1)分别输入0；a；-91；+a*bc；+*5^x2*8x；+++*3^x3*2^x2x6并输出。

2)每当输入一个表达式后，对其中的变量赋值，然后对表达式求值。

选题三：银行业务模拟与离散大事模拟

【问题描述】

假设某银行有4个窗口对外接待客户，从早晨银行开门（开门9：00am，关门5：00pm）起不断有客户进入银行。由于每个窗口在某个时刻只能接待一个客户，因此在客户人数众多时需要在每个窗口前顺次排队，对于刚进入银行的客户（建议：客户进入时间使用随机函数产生），假如某个窗口的业务员正空闲，则可上前办理业务；反之，若4个窗口均有窗户所占，他便会排在人数最少的队伍后面。

【任务要求】

1)编制一个程序以模拟银行的这种业务活动并计算一天中客户在银行逗留的平均时

间。

2)建议有如下设置：

a)客户到达时间随机产生，一天客户的人数设定为100人。

b)银行业务员处理时间随机产生，平均处理时间10分钟。

3)将一天的数据（包括业务员和客户）以文件方式输出。

【测试数据】

由随机数产生器生成

选题四：文学讨论助手与模式匹配算法KMP

【问题描述】

文学讨论人员需要统计某篇英文小说中某些形容词的消失次数和位置。试写一个实现这一目标的文字统计系统

【任务要求】

1)英文小说存于一个文本文件中。待统计的词汇合合要一次输入完毕，即统计工作必

须在程序的一次运行之后就全部完成。程序的输出结果是每个词的消失次数和消失

位置所在的行的行号，格式自行设计。待统计的“单词”在文本串中不跨行消失，它或者从行首开头，或者前置以一个空格符。

2)模式匹配要基于KMP算法。

3)推广到更一般的模式集匹配问题，并设待查模式串可以跨行（提示：定义操作

GetAChar）。

【测试数据】

1)文本文件为testword.c

2)待统计的词集：if、else、for、while、return、void、int、char、typedef、struct

选题五：北理珠校内导游询问与最短路径

【问题描述】

1)从北京理工高校珠海学院的平面图中选取有代表性景点（10-15个），抽象成一个

无向带权图。以图中顶点表示景点，边上的权值表示两地之间距离。

2)本程序的目的是为用户供应路径询问。依据用户指定的始点和终点输出相应路径，

或者依据用户指定的景点输出景点的信息。

【任务要求】

1)从北京理工高校珠海学院的平面图中选取有代表性景点（10-15个），抽象成一个

无向带权图。以图中顶点表示校内各景点，存放景点名称、、简介等信息；以

边表示路径，存放路径长度等信息。

2)为来访客人供应图中任意景点相关信息的查询。

3)为来访客人供应图中任意景点的问路查询，即查询任意两个景点之间的一条最短的

简洁路径。

4)区分汽车线路与步行线路。

【测试数据】

北理珠校内导游图（距离可估量）。

选题六：B-树与B+树及其操作

【问题描述】

学习并讨论B-树与B+树，并编写演示它们操作的程序。

【任务要求】

1)B-树构建、查找、插入和删除操作程序。

2)B+树构建、查找、插入和删除操作程序。

【测试数据】

选题七：哈夫曼(Huffman)编/译码器

【问题描述】

利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。

【任务要求】

一个完整的系统应具有以下功能：

1)I：初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，

建立哈夫曼树，并将它存于文件hfmTree中。

2)E：编码（Encoding）。利用以建好的哈夫曼树（如不在内存，则从文件hfmTree中

读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。

3)D：译码（Decoding）。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，

结果存入文件TextFile中。

4)P：印代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，每行50个代

码。同时将此字符形式的编码文件写入文件CodePrin中。

5)T：印哈夫曼树（TreePrinting）。将已在内存中的哈夫曼树以直观的方式（树或凹

入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。【测试数据】

1)利用教科书例6-2（严蔚敏《数据结构》P148）中的数据调试程序。

2)用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码

选题八：内部排序算法比较

【问题描述】

在教科书中，各种内部排序算法的时间简单度分析结果只给出了算法执行时间的阶，或也许执行时间。试通过随机数据比较各种算法的关键字比较次数和关键字移动次数，以取得直观感受。

【任务要求】

1)对以下7种常用的内部排序算法进行比较：冒泡排序、直接插入排序、简洁选择排

序、希尔排序、堆排序、归并排序、快速排序。

2)待排序表的表长不小于100；其中的数据要用伪随机数程序产生；至少要用5组不

同的输入数据作比较；比较的指标为有关键字参与的比较次数和关键字的移动次数

（关键字交换计为3次移动）。

3)最终要对结果作出简洁分析，包括对各组数据得出结果波动大小的解释。

【测试数据】

由随机数产生器生成

选题九：简洁行编辑程序

【问题描述】

文本编辑器程序是利用计算机进行文字加工的基本软件工具，实现对文本文件的插入、删除等修改操作。限制这些操作以行为单位进行的编辑程序称为行编辑程序。

被编辑的文本文件可能很大，全部读入编辑程序的数据空间（内存）的作法既不经济，也不总能实现。一种解决方法是逐段地编辑。任何时刻只把待编辑文件的一段放在内存，利为活区。试根据这种方法实现一个简洁的行编辑程序。设文件每行不超过320个字符，很少超过80个字符。

【任务要求】

实现以下4条基本编辑命令：

1)行插入：格式：i

●将插入活区中第行之后。

2)行删除。格式：d

●删除活区中第(到第行)。例如“d10”和“d1014”

3)活区切换。格式：n

●将活区写入输出文件，并从输入文件中读入下一段，作为新的活区。

4)活区显示。模式：p

●逐页地（每页20行）显示活区内容，每显示一页之后请用户打算是连续显示

以后各页（假如存在）。印出的每一行要前置行号和一个空格符，行号固定占

4位，增量为1。

各条命令中的行号均须在活区中各行行号范围之内，只有插入命令的行号可以等于活区第一行行号减1，表示插入当前屏幕中第一行之前，否则命令参数非法。

【测试数据】

自行设定，留意测试将活区删空等特别状况。

选题十：一元多项式计算

【问题描述】

1.能够根据指数降序排列建立并输出多项式；

2.能够完成两个多项式的相加、相减，并将结果输入；

【任务要求】

1.存储结构;

2.多项式相加的基本过程的算法（可以使用程序流程图）

3.可以提出算法的改进方法；

【测试数据】

自行设定，留意边界等特别状况。

选题十一：集合的交、并、差运算

【问题描述】

编制一个能演示执行集合的交、并和差运算的程序。

【任务要求】

1)集合元素用小写英文字母，执行各种操作应以对话方式执行。

2)算法要点：利用单链表表示集合；理解好三种运算的含

【测试数据】

自行设定，留意边界等特别状况。

选题十二：动态查找表

【问题描述】

利用二叉排序树完成动态查找表的建立、指定关键字的查找、插入与删除指定关键字结点。

【任务要求】

算法输入：指定一组数据。

算法输出：显示二叉排序树的中序遍历结果、查找胜利与否的信息、插入和删除后的中序遍历结果(排序结果)。

算法要点：二叉排序树建立方法、动态查找方法,对树进行中序遍历。

【测试数据】

自行设定，留意边界等特别状况。

选题十三：同学成果管理

【问题描述】

本例对同学的成果管理做一个简洁的模拟，用菜单选择方式完成下列功能：登记

同学成果；查询同学成果；插入同学成果；删除同学成果。

【任务要求】

算法输入：操作要求，同学信息

算法输出：操作结果

算法要点：把问题看成是对线性表的操作。将同学成果组织成挨次表，则登记同学成果即是建立挨次表操作；查询同学成果、插入同学成果、删除同学成果即是在挨次表中进行查找、插入和删除操作。

【测试数据】

自行设定，留意边界等特别状况。

选题十四：马踏棋盘

【问题描述】

将马随机放在国际象棋的8*8棋盘Bord[8Ⅱ8]的某个方格中，马按走棋规章进行移动。要求每个方格上只进入一次，走遍棋盘上全部64个方格。

【任务要求】

编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1，2，…，64依次填入一个8*8的方阵，输出之。

测试数据：由读者指定,可自行指定一个马的初始位置。

实现提示：每次在多个可走位置中选择一个进行摸索，其余未曾摸索过的可走位置必需用适当结构妥当管理，以备摸索失败时的“回溯”(悔棋)使用。

【测试数据】

自行设定，留意边界等特别状况。

选题十五：joseph环

【问题描述】

编号是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个城市之间建设网络，只需保证连通即可，求最经济的架设方法。

对于图，其生成树中的边也带权，将生成树各边的权值总和称为生成树的权，并将权值最小的生成树称为最小生成树（MinimunSpanningTree），简称为MST。有两种特别典型的算法：Prim算法和kruskal算法。

【任务要求】

设计程序完成如下功能：对给定的网和起点，用PRIM算法和kruskal算法的基本思想求解出全部的最小生成树。存储结构可自行选择。

【测试数据】

自行设定，留意边界等特别状况。

选题十七：通讯录管理

【问题描述】

该设计采纳菜单作为应用程序的主要界面，用掌握语句来转变程序执行的挨次，掌握语句是实现结构化程序设计的基础。该设计的任务是利用一个简洁有用的菜单，通过菜单单项进行选择，实现和完成通讯录管理中常用的几个不同的功能。

【任务要求】

（1）菜单内容

1、通讯录链表的建立

2、通讯者结点的插入

3、通讯者结点的查询

4、通讯者结点的删除

5、通讯录链表的输出

0、退出管理系统

请选择0~5：

（2）设计要求

使用0~5来选择菜单项，其他输入则不起作用。

（3）功能函数设计

5个不同功能的算法实现编程题，目的是练习利用链表结构来解决实际应用问题的力量，进一步理解和熟识线形表的链式存储结构。

【测试数据】

自行设定，留意边界等特别状况。

选题十八：运动会分数统计

【问题描述】

参与运动会有n个学校，学校编号为1……n。竞赛分成m个男子项目，和w个女子项目。项目编号为男子1……m，女子m+1……m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由同学自己设定。（m<=20,n<=20）

【任务要求】

功能要求：1).可以输入各个项目的前三名或前五名的成果；

2)．能统计各学校总分，

3)．可以按学校编号、学校总分、男女团体总分排序输出；

4).可以按学校编号查询学校某个项目的状况；可以按项目编号查询取得前三或前五名的学校。

规定：输入数据形式和范围：20以内的整数（假如做得更好可以输入学校的名称，运动项目的名称）

输出形式：有中文提示，各学校分数为整形

界面要求：有合理的提示，每个功能可以设立菜单，依据提示，可以完成相关的功能要求。

存储结构：同学自己依据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。（数据文件的数据读写方法等相关内容在c语言程序设计的书上，请自学解决）请在最终的上交资料中指明你用到的存储结构；

测试数据：要求使用1、全部合法数据；2、整体非法数据；3、局部非法数据。进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明；

【测试数据】

自行设定，留意边界等特别状况。

选题十九：航班信息的查询与检索

【问题描述】

该设计要求对飞机航班信息进行排序和查找。可按航班的航班号、起点站、到达站、起飞时间以及到达时间等信息进行查询。

【任务要求】

对于本设计，可采纳基数排序法对一组具有结构特点的飞机航班号进行排序，利用二分查找法对排好序的航班记录按航班号实现快速查找，按其他次关键字的查找可采纳最简洁的挨次查找方法进行，因此他们用得较少。

每个航班记录包括八项，分别是：航班号、起点站、终点站、班期、起飞时间、到达时间、飞机型号以及票价等