2023年数据结构大作业题目.pdf

《2023年数据结构大作业题目.pdf》由会员分享，可在线阅读，更多相关《2023年数据结构大作业题目.pdf（12页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构大作业专 业：_班 级：_题 目：_学生姓名：（课程设计报告撰写的基本规定）题 目 （三号，黑体，居中）（空一行）一、任务与目的（标题均为小一号，宋体）（正文均为小四号，宋体，行 距 1.5倍）（这部分需简朴介绍题目内容，即该题目到底要做什么。假如涉及明确的算法，最佳再简朴介绍一下算法产生的背景，还要列出各项本设计要达成的具体的目的。）二、方案设计与论证（对目的进行总体分析，说明要采用的基本思绪，说明碰到的问题和解决方法。说明完毕本次课程设计的完整过程。要描述程序的设计思想，重点描述你自己提出的与己有工作不同的程序设计思想。）三、算法说明（这一部分需具体描述解决问题所需要用到的算法和重

2、要的数据结构，即该课程设计到底应当怎么做。基本规定：解决问题中所用到的关键算法都要描述清楚，而不是仅描述主函数。算法和数据结构可用伪码和图示描述，不要只写源代码和注释。这一部分的目的是让读者在短时间内清楚地理解作者解决问题的整体思绪，表达方式必须比源代码更通俗易懂。假如读者感觉还不如直接读源代码来得明白，这一部分内容就失去了意义。）四、所有源程序清单（给出本次大作业所编写所有源程序已经调试好的可运营代码清单，字体可以用宋体五号，页数可增长，每个程序开头用注释文字说明此程序的用途和大体工作过程，程序中必要部分也要加入足够多的注释行。）五、程序运营的测试与分析（这一部分内容需要紧扣课程设计的题目类

3、型和规定，设计提供相应的测试方法和结果。这部分涉及运营图。对于需要比较不同算法性能优劣的题目，应设计并填写一张性能比较表格，列出不同算法在同一指标下的性能表现。仅仅罗列出一堆数据是不够的，还应将数字转化为图形、曲线等方式，帮助读者更直观地理解测试结果。对于需要运用某算法解决某问题的题目，应设计并填写一张测试用例表。每个测试用例一般应涉及下列内容：测试输入：设计一组输入数据：测试目的：设计该输入的目的在于测试程序在哪方面也许存在漏洞；对的输出：相应当输入，若程序对的，应当输出的内容；实际输出：该数据输入后，实际测试得到的输出内容；错误因素：假如实际输出与对的输出不符，需分析产生错误的也许因素；当

4、前状态：分 为“通过”（实际输出与对的输出相符）、已改正 （实际输出与对的输出不符，但现在已修改对的）、“待修改”（实际输出与对的输出不符，且尚未改正）三种状态。需要注意的是，测试员的态度，不是提供几组简朴的数据让程序员容易通过，从而宣称该程序是对的的；而应当是千方百计设计“刁难”的数据，想办法让所测试的程序暴露出问题，这样才干真正帮助程序员完毕对的的程序，最后通过严格的裁判数据测试。）六、结论与心得（重要说明程序调试中发现的问题和解决办法，涉及你学到了什么，哪里碰到困难，解决的办法，也许但因时间关系没有来得及完毕的想法，此后的目的等。）七、参考资料（用五号，宋体，按照规范格式列出。）（要列出

5、在完毕设计中查看过并有所运用的所有参考资料，涉及各类技术书籍、期刊论文和相关网页的网址。注意你看过但没有运用的资料不要列入，要可以回答你列出资料中的相关问题。）附录：供选择的数据结构大作业题目可选题目:1.航空客运订票系统.错误!未定义书签。2.散列法的实验研究.错误!未定义书签。3.学生搭配问题.错误!未定义书签。4.二叉排序树的实现.错误!未定义书签。5.运用栈求表达式的值.错误!未定义书签。6.走迷宫游戏.错误!未定义书签。7.顺序结构、动态链表结构下的一元多项式的加法、减法、乘法的实现。错误!未定义书签。8.线索二叉树的应用.错误!未定义书签。9.稀疏矩阵实现与应用.错误!未定义书签。

6、10.树的应用.错误!未定义书签。11.图的遍历和生成树求解实现.错误!未定义书签。12.排序综合.错误!未定义书签。13.纸牌游戏.错误!未定义书签。14.运用栈求表达式的值，可供小学生作业，并能给出分数。错误!未定义书签。15.数制转换问题.错误!未定义书签。16.停车场问题.错误!未定义书签。17.哈夫曼编码/译码器.错误!未定义书签。18.约瑟夫环.错误!未定义书签。19.任意长的整数加法.错误!未定义书签。20.关键途径问题.错误!未定义书签。1.航空客运订票系统通过此系统可以实现如下功能：录入：可以录入航班情况（数据可以存储在一个数据文献中，数据结构、具体数据自定）；查询：可以查询

7、某个航线的情况（如，输入航班号，查询起降时间，起飞到达城市，航班票价，票价折扣，拟定航班是否满仓）；可以输入起飞到达城市，查询飞机航班情况；订票：（订票情况可以存在一个数据文献中，结构自己设定）可以订票，假如该航班己经无票，可以提供相关可选择航班；退票：可退票，退票后修改相关数据文献；客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。修改航班信息：当航班信息改变可以修改航班数据文献规定：根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完毕功能;2.散列法的实验研究基本规定：1、设每个记录有下列数据项：电话号码、用户名、地址；2、从键盘输入各记录，分别以电话号码和用户名为关键

8、字建立散列表；3、采用一定的方法解决冲突；4、查找并显示给定电话号码的记录；5、查找并显示给定用户名的记录。进一步完毕内容：1、设计不同的散列函数，比较冲突率；2、在散列函数拟定的前提下，尝试各种不同类型解决冲突的方法，考察平均查找长度的变化。3.学生搭配问题一班有m 个女生，有 n 个男生（m 不等于n）,现要开一个舞会.男女生分别编号坐在舞池的两边的椅子上.每曲开始时，依次从男生和女生中各出一人配对跳舞，本曲没成功配对者坐着等待下一曲找舞伴.请设计一系统模拟动态地显示出上述过程，规定如下：1、输出每曲配对情况2、计算出任何一个男生（编号为X）和任意女生（编号为Y）,在 第 K 曲配对跳舞的

9、情况.至少求出K 的两个值.3、尽量设计出多种算法及程序4、提醒:用队列来解决比较方便.4.二叉排序树的实现用顺序和二叉链表作存储结构1）以回车（）为输入结束标志，输入数列L,生成一棵二叉排序树T；2）对二叉排序树T 作中序遍历，输出结果；3）输入元素x,查找二叉排序树T,若存在含x 的结点，则删除该结点,并作中序遍历（执行操作2）；否则输出信息“无 x”；5.运用栈求表达式的值编写程序实现表达式求值，即验证某算术表达式的对的性，若对的，则计算该算术表达式的值。重要功能描述如下：1、从键盘上输入表达式。2、分析该表达式是否合法：（1）是数字，则判断该数字的合法性。若合法，则压入数据到堆栈中。(

10、2)是规定的运算符，则根据规则进行解决。在解决过程中，将计算该表达式的值。(3)若是其它字符，则返回错误信息。3、若上述解决过程中没有发现错误，则认为该表达式合法，并打印解决结果。程序中应重要包含下面几个功能函数：void initstack()：初始化堆栈int Make_str()：语法检查并计算int push_operate(int operate)：将操作码压入堆栈int push_num(double num)：将操作数压入堆栈int procede(int operate)：解决操作码int change_opnd(int operate)：将字符型操作码转换成优先级int pu

11、sh_opnd(int operate)：将操作码压入堆栈int pop_opnd()：将操作码弹出堆栈int caculate(int cur_opnd)：简朴计算+,*,/double pop_num()：弹出操作数6.走迷宫游戏程序开始运营时显示一个迷宫地图，迷宫中央有一只老鼠，迷宫的右下方有一个粮仓。游戏的任务是使用键盘上的方向键操纵老鼠在规定的时间内走到粮仓处。规定：老鼠形象可辨认，可用键盘操纵老鼠上下左右移动；迷宫的墙足够结实，老鼠不能穿墙而过；对的检测结果，若老鼠在规定期间内走到粮仓处，提醒成功，否则提醒失败；添加编辑迷宫功能，可修改当前迷宫，修改内容：墙变路、路变墙；找出走出迷

12、宫的所有途径，以及最短途径。运用序列化功能实现迷宫地图文献的存盘和读出等功能7 .顺序结构、动态链表结构下的一元多项式的加法、减法、乘法的实现。设 有 一 元 多 项 式Am(X)和Bn(X).Am(X)=A o+A 1X1+A2X2+A3X3+.+AmXmBn(X)=B o+B lX1+B2X2+B3X3+.+BnXn请实现求 M(x)=A m(x)+Bn(x)、M(x)=A m(x)-Bn(x)和 M(x)=Am(x)xBn(x).8 .线索二叉树的应用规定：实现线索树建立、插入、删除、恢复线索的实现。9 .稀疏矩阵实现与应用规定：实现三元组，十字链表下的稀疏矩阵的下列应用0(1)稀疏矩阵

13、的存储(2)稀疏矩阵加法(3)矩阵乘法(4)矩阵转置1 0 .树的应用规定：实现树与二叉树的转换的实现。以及树的前序、后序的递归、非递归算法，层顺序的非递归算法的实现，应包含建树的实现。1 1 .图的遍历和生成树求解实现规定：先任意创建一个图;图的DFS,BFS的递归和非递归算法的实现最小生成树（两个算法）的实现，求连通分量的实现规定用邻接矩阵、邻接表、十字链表多种结构存储实现1 2 .排序综合运用随机函数产生N 个随机整数（20230以上），对这些数进行多种方法进行排序。规定：至少采用三种方法实现上述问题求解（提醒，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并

14、排序）。并把排序后的结果保存在不同的文献中。记录每一种排序方法的性能（以上机运营程序所花费的时间为准进行对比），找出其中两种较快的方法。假如采用4 种或4 种以上的方法者，可适当加分。1 3 .纸牌游戏任务：编号为1-52张牌，正面向上，从第2 张开始，以2 为基数，是 2 的倍数的牌翻一次,直到最后一张牌；然后，从第3 张开始，以 3 为基数，是 3 的倍数的牌翻一次，直到最后一张牌；然后从第4 张开始，以 4 为基数，是 4 的倍数的牌翻一次，直到最后一张牌；再依次5 的倍数的牌翻一次，6 的，7 的 直 到 以 52为基数的翻过，输出：这时正面向上的牌有哪些？1 4 .运用栈求表达式的值

15、，可供小学生作业，并能给出分数。规定：建立试题库文献，随机产生n 个题目；题目涉及加减乘除，带括弧的混合运算；随时可以退出；保存历史分数，能回顾历史，给出与历史分数比较后的评价1 5 .数制转换问题任意给定一个M 进制的数x,请实现如下规定1）求出此数x 的 10进 制 值（用 MD表达）2）实现对x 向任意的一个非M 进制的数的转换。3）至少用两种或两种以上的方法实现上述规定（用栈解决，用数组解决，其它方法解决）。16.停车场问题停车场是一条可以停放n 辆车的狭窄通道，且只有一个大门汽车停放安到达时间的先后依次由北向南排列（大门在最南端，最先到达的第一辆车停在最北端）若停车场已经停满n 辆车

16、,后来的汽车在便道上等候，一旦有车开走，排在便道上的第一辆车可以开入；当停车场的某辆车要离开时，停在他后面的车要先后退为他让路，等它开出后其他车在按照原顺序开入车场，每两停在车场的车要安时间长短缴费。规定：以栈模拟停车场，以队列车场外的便道,按照从终端输入的数据序列进行模拟管理。每一组数据涉及三个数据项：汽车“到达”或“拜别”信息、汽车牌照号码、以及到达或拜别的时刻。对每一组数据进行操作后的信息为：若是车辆到达，则输出汽车在停车场的内或便道上的位置：若是车辆拜别则输出汽车在停车场内的停留时间和应缴纳的费用（在便道上的停留时间不收费）。栈以顺序结构实现，队列以链表结构实现。17.哈夫曼编码/译码

17、器【问题描述】设计一个运用哈夫曼算法的编码和译码系统，反复地显示并解决以下项目，直到选择退出为止。【基本规定】1）将权值数据存放在数据文献（文献名为data.txt,位于执行程序的当前目录中）2）分别采用动态和静态存储结构3）初始化：键盘输入字符集大小n、n 个字符和n 个权值，建立哈夫曼树；4）编码：运用建好的哈夫曼树生成哈夫曼编码；5）输出编码;6）设字符集及频度如下表：字符空格 A B C D E F G H IJK L M频度 186 64 13 22 32 103 21 15 47 57 1 5 32 20字符 N O P Q R S T U V W X Y Z频度 57 63 15

18、 1 48 51 80 23 8 18 1 16 1【进一步完毕内容】1）译码功能；2）显示哈夫曼树；3）界面设计的优化。1 8 .约瑟夫环问题描述：编号为1,2 n 的 n 个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数的上限值m,从第一个人开始按顺时针方向自1开始顺序报数，报到m 时停止报数，报 m 的人出列，将他的密码作为新的m 值，从他的顺时针方向上的下一个开始重新从1报数，如此下去，直至所有人所有出列为止，设计一个程序求出出列顺序。基本规定：1、运用单循环链表作为存储结构模拟此过程；2、键盘输入总人数、初始报数上限值m 及各人密码；3、按照出列顺序输出各人的编号。1 9 .任意长的整数加法问题描述：设计一个程序实现两个任意长的整数的求和运算。基本规定：运用双向循环链表，设计一个实现任意长的整数进行加法运算的演示程序。规定输入和输出每四位一组，组间用逗号隔开。如：1,0000,0000,0000,000020.关键途径问题问题描述：设计一个程序求出完毕整项工程至少需要多少时间以及整项工程中的关键活动。基本规定：（1）对一个描述工程的AOE网，应判断其是否可以顺利进行。（2）若该工程能顺利进行，输出完毕整项工程至少需要多少时间，以及每一个关键活动所依附的两个顶点、最早发生时间、最迟发生时间。