数据结构程序设计题目共29题

-目 录题目1：设计一元多项式简单计算1题目2：链表应用11题目3：链表应用21题目4：通讯录2题目5：停车场管理系统3题目6：约瑟夫环3题目7：运动会分数统计3题目8：文学研究助手问题4题目9：银行业务模拟与离散事件模拟4题目10：学生信息管理系统任务（用顺序表/链表）5题目11：文章编辑功能6题目12：实验室管理6题目13：二叉树的基本操作（建立、求二叉树树深度、遍历）6题目14：纸牌游戏任务7题目15：算术表达式求值7题目16：内部排序算法比较7题目17：哈夫曼树的构造和哈夫曼编码/译码8题目18：构造可以使n个城市连接的最小生成树9题目19：交通咨询系统中的最短路径9题目20：集合的交、并、差运算9题目21：长整数四则运算9题目22：机订票系统10题目23：图书管理系统10题目24：哈希表应用11题目25：模拟旅馆管理系统的一个功能床位的分配与回收12题目26：地图着色问题12题目27：俄罗斯套娃问题12题目28：扫雷13题目29：用C语言设计一个日历系统14欢迎下载题目1：设计一元多项式计算【任务要求】（1）能够按照指数降序排列建立并输出多项式；（2）能够完成两个多项式的相加、相减，并将结果输入；实现提示：可选择带头结点的单向循环链表或单链表存储多项式，头结点可存放多项式的参数，如项数等。要求：在上交资料中请写明：存储结构、多项式相加的基本过程的算法（可以使用程序流程图） 、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；【测试数据】 自行选择题目2：链表应用1【任务要求】实现两个链表的合并基本功能要求：（1）建立两个链表A和B，链表元素个数分别为m和n个。（2）假设元素分别为(x1,x2,xm)，和(y1,y2, yn)。把它们合并成一个线形表C，使得：当m=n时，C=x1,y1,x2,y2,xn,yn,xm当nm时，C=y1,x1,y2,x2,ym,xm,yn输出线性表C（3） 用直接插入排序法对C进行升序排序，生成链表D，并输出链表D。【测试数据】1） A表（30，41，15，12，56，80）B表（23，56，78，23，12，33，79，90，55）2） A表（30，41，15，12，56，80，23，12，34）B表（23，56，78，23，12）题目3：链表应用2【问题描述】已知非空线性链表第一个链结点的指针为list，写出下列各项操作的算法程序。（1）逆转该线性链表；（2）删除线性链表中从左往右第一个数据为data的链结点；（3）删除从第I个链结点开始的连续k个结点。【任务要求】设计一组输入数据并编写完整的程序。调试程序并对相应的输出作出分析；修改输入数据，预期输出并验证输出的结果。【提示】1）逆转一个链表是指在不增加新结点的前提下，依次改变链表中结点的连接方向。2)删除数据结点时，首先判断链表是否为空，若非空，先判断第一个结点是否满足条件，若是则删除；否则从第二个结点开始顺序查找，直到找到为止，然后删除；对任何不满足条件的情况都报告相应提示信息。3）从第I个结点开始连续删除k个结点时，考虑以下两种情况：当I=1时，从第一个开始删除即可；当I1时，先找到前一个结点然后再连续删除K个结点。最后释放各个结点空间。【测试数据】 自行设定题目4：通讯录【问题描述】 该设计采用菜单作为应用程序的主要界面，用控制语句来改变程序执行的顺序，控制语句是实现结构化程序设计的基础。该设计的任务是利用一个简单实用的菜单，通过菜单单项进行选择，实现和完成通讯录管理中常用的几个不同的功能。通讯者所包含信息请自行设定【任务要求】 菜单内容：（0）通讯录链表的建立（1）通讯者结点的插入（2）通讯者结点的查询（3）通讯者结点的删除（4）通讯录链表的输出（5）退出管理系统设计要求：使用05来选择菜单项，其他输入则不起作用。功能函数设计5个不同功能的算法实现编程题，目的是练习利用链表结构来解决实际应用问题的能力，进一步理解和熟悉线形表的链式存储结构。【测试数据】自行设定，注意边界等特殊情况。 题目6：约瑟夫环 【问题描述】编号是1，2，,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。【任务要求】利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。输入数据：输入m的初值，n ，输入每个人的密码，建立单循环链表。输出形式：建立一个输出函数，将正确的输出序列【测试数据】m的初值为20，n=7 ,7个人的密码依次为3，1，7，2，4，7，4。题目7：运动会分数统计【问题描述】 参加运动会有n个学校，学校编号为1n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1m，女子m+1m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。（m=20,n=20）【任务要求】 功能要求：1).可以输入各个项目的前三名或前五名的成绩；2)能统计各学校总分，3)可以按学校编号、学校总分、男女团体总分排序输出；4).可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。 规定：输入数据形式和范围：20以内的整数（如果做得更好可以输入学校的名称，运动项目的名称）输出形式：有中文提示，各学校分数为整型界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。（数据文件的数据读写方法等相关内容在c语言程序设计的书上，请自学解决）请在最后的上交资料中指明你用到的存储结构；【测试数据】1、全部合法数据；2、整体非法数据；3、局部非法数据。进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明；题目9：银行业务模拟与离散事件模拟【问题描述】假设某银行有4个窗口对外接待客户，从早晨银行开门（开门9：00am，关门5：00pm）起不断有客户进入银行。由于每个窗口在某个时刻只能接待一个客户，因此在客户人数众多时需要在每个窗口前顺次排队，对于刚进入银行的客户（建议：客户进入时间使用随机函数产生），如果某个窗口的业务员正空闲，则可上前办理业务；反之，若4个窗口均有窗户所占，他便会排在人数最少的队伍后面。【任务要求】编制一个程序以模拟银行的这种业务活动并计算一天中客户在银行逗留的平均时间。建议有如下设置：客户到达时间随机产生，一天客户的人数设定为100人。银行业务员处理时间随机产生，平均处理时间10分钟。将一天的数据（包括业务员和客户）以文件方式输出。【测试数据】由随机数产生器生成题目13：二叉树的基本操作（建立、求二叉树树深度、遍历）【任务要求】要求输入二树的各个结点，求二叉树的树深度，并能够输出指定遍历方式（层序、先序、中序、后序）的遍历序列；分别建立；建立二叉树存储结构的的输入函数、求二叉树的树深度的函数、遍历序列的函数层序遍历（用队列的方法实现）中序遍历（ 用递归和非递归的方法一起都实现）先序遍历（ 用递归和非递归的方法一起都实现）后序遍历（ 用递归和非递归的方法一起都实现）题目14：纸牌游戏任务【问题描述】编号为1-52张牌，正面向上，从第2张开始，以2为基数，是2的倍数的牌翻一次，直到最后一张牌；然后，从第3张开始，以3为基数，是3的倍数的牌翻一次，直到最后一张牌；然后从第4张开始，以4为基数，是4的倍数的牌翻一次， 直到最后一张牌；.再依次5的倍数的牌翻一次，6的，7的 直到 以52为基数的 翻过，输出：这时正面向上的牌有哪些？【任务要求】采用合适的数据结构输出最后正面向上的牌，并将以252奇数翻牌的过程显示出来题目15：算术表达式求值【问题描述】在计算机中，算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同的优先级，又要考虑括号，因此，算术表达式的求值不可能严格地从左到右进行。因而在程序设计时，借助栈实现。【任务要求】算法输入：一个算术表达式，由常量、变量、运算符和括号组成（以字符串形式输入）。为简化，规定操作数只能为正整数，操作符为+、-*、/，用#表示结束。算法输出：表达式运算结果。算法要点：设置运算符栈和运算数栈辅助分析算符优先关系。在读入表达式的字符序列的同时，完成运算符和运算数的识别处理，以及相应运算。题目16：内部排序算法比较【问题描述】编制一个演示内部排序算法比较的程序。利用随机函数产生30000个随机整数，利用冒泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、归并排序和堆排序等排序方法进行排序，并统计每一种排序上机所花费的时间。【任务要求】算法输入：以菜单的形式选择排序方法算法输出：不同情况下关键字参加的比较次数和关键字的移动次数，每一种排序上机所花费的时间。算法要点：（1）利用随机函数产生30000个随机整数。（2）利用不同排序方法排序并统计两类次数，列表显示（3）程序以对话方式执行。题目17：哈夫曼树的构造和哈夫曼编码/译码【问题描述】利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。【任务要求】一个完整的系统应具有以下功能：I：初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。E：编码（Encoding）。利用以建好的哈夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。D：译码（Decoding）。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。P：打印代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrin中。T：打印哈夫曼树（Tree Printing）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。【测试数据】利用教科书P169第15题中的数据调试程序。用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“THIS PROGRAM IS MY FAVORITE”。字符空格ABCDEFGHIJKLM频度1866413223210321154757153220字符NOPQRSTUVWXYZ频度5763151485180238181161题目18：构造可以使n个城市连接的最小生成树 【问题描述】给定一个地区的n个城市间的距离网，用Prim算法和Kruskal算法建立最小生成树，并计算得到的最小生成树的代价。【任务要求】输入：表示城市间距离网的邻接矩阵（要求至少6个城市，10条边）城市间的距离网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树的代价。输出：最小生成树中包括的边及其权值，并显示得到的最小生成树的代价。 题目19：交通咨询系统中的最短路径【问题描述】建立交通图的存储结构、解决单源最短路径问题、再实现两个地点最短路径问题，也就是实现迪杰斯特拉和弗洛伊德方法【测试数据】 自行设定交通图，交通站点不少于6个题目21：长整数四则运算【问题描述】设计一个实现任意长的整数进行加法运算的演示程序。【任务要求】利用双向循环链表实现长整数的存储，每个结点含一个整形变量。任何整形变量的范围是 -(215 - 1) (215 - 1)。输入和输出形式：按中国对于长整数的表示习惯，每四位一组，组间用逗号隔开。 【测试数据】（1）0；0；应输出“0”。（2）-2345,6789；-7654,3211；应输出“-1,0000,0000”。（3）-9999,9999；1,0000,0000,0000；应输出“9999,0000,0001”。（4）1,0001,0001；-1,0001,0001；应输出“0”。（5）1,0001,0001；-1,0001,0000；应输出“1”。（6）-9999,9999,9999；-9999,9999,9999；应输出“1,9999,9999,9998”。（7）1,0000,9999,9999；1；应输出“1,0001,0000,0000”。实现提示：（1）每个结点中可以存放的最大整数为32767，才能保证两数相加不会溢出，但若这样存放，即相当于按32768进制存放，在十进制与32768进制数之间的转换十分不方便，故可以在每个结点中仅存十进制的4位，即不超过9999的非负整数，整个链表表示为万进制。（2）可以利用头结点数据域的符号代表长整数的符号。用其绝对值表示元素结点数目。相加过程中不要破坏两个操作数链表。两操作数的头指针存于指针数组中是简化程序结构的一种方法。不能给长整数位数规定上限。题目23：图书管理系统【问题描述】设计一个计算机管理系统完成图书管理基本业务。【任务要求】1)每种书的登记内容包括书号、书名、著作者、现存量和库存量；2)对书号建立索引表（线性表）以提高查找效率；3)系统主要功能如下：*采编入库：新购一种书，确定书号后，登记到图书帐目表中，如果表中已有，则只将库存量增加；*借阅：如果一种书的现存量大于0，则借出一本，登记借阅者的书证号和归还期限，改变现存量；*归还：注销对借阅者的登记，改变该书的现存量。【进一步完成内容】1)系统功能的进一步完善；2)索引表采用树表。3)设计内容4)程序流程图5)源程序6)软件测试报告（包括所用到的数据及结果）题目24：哈希表应用【问题描述】 利用哈希表进行存储。【任务要求】 任务要求：针对一组数据进行初始化哈希表，可以进行显示哈希表，查找元素，插入元素，删除元素，退出程序操作。设计思想：哈希函数用除留余数法构造，用线性探测再散列处理冲突。设计目的：实现哈希表的综合操作简体中文控制台界面：用户可以进行创建哈希表，显示哈希表，查找元素，插入元素，删除元素。显示元素：显示已经创建的哈希表。查找元素：查找哈希表中的元素，分为查找成功和查找不成功。插入元素：在哈希表中，插入一个元素，分为插入成功和失败。删除元素：在已有的数据中，删除一个元素。退出系统：退出程序。【测试数据】自行设定，注意边界等特殊情况。题目25：模拟旅馆管理系统的一个功能床位的分配与回收【问题描述】某旅馆有n个等级的房间，第I等级有ai个房间，每个等级有bi个床位（1in）。试模拟旅馆管理系统中床位分配和回收的功能，设计能为单个旅客分配床位，在其离店便回收床位（供下次分配）的算法。【任务要求】（1）输入数据分配时，输入旅客姓名、年龄、性别、到达日期和所需房间等级。回收时，输入房间等级、房间号和床位号。（2）输出数据分配成功时打印旅客姓名、年龄、到达日期、房间等级、房间号码和床位号码。分配不成功时，如所有等级均无床位，则打印“客满”信息；如旅客需要的等级均无空床位，则打印“是否愿意更换等级？”的询问信息。若旅客愿意更换，则重新输入有关信息，再进行分配，否则分配工作结束。题目26：地图着色问题【问题描述】已知中国地图,对各省进行着色,要求相邻省所使用的颜色不同,并保证使用的颜色总数最少提示【任务要求】（1） 数据结构的设计：地图可以采用图的数据结构，每个省为一个节点，边表示对应的两个省相邻。（2） 算法设计：设计着色算法，保证邻接点不是同一种颜色。（3） 地图数据的输入采取从文件中读取。（4） 结果输出方式可以采用图形方式或文本方式。题目27：俄罗斯套娃问题【问题描述】伊万洛夫在比武大会上力克群雄，成为新一届“草原雄鹰”，为部落赢得了莫大荣誉。首领决定要重重奖赏，他对伊万洛夫说：“孩子，你是知道的，面前的这片草原，南北向和东西向的道路纵横交错。现在，路口放着纯金打造的俄罗斯娃娃，重量大小不等，重的都能装下轻的。你可以沿着道路飞奔，拾取路口的娃娃，要求是任何时刻必须是一个套娃，装好后就不能再拆开了。注意不要走重复路。”请你为伊万洛夫规划路线，使得他能够有最大的收获。【任务要求】Input: cross.txt 输入包括多组测试用例； 每个测试用例开始是一对整数，R表示东西向道路数，C表示南北向道路总数；接下来R行，每行包括C个正整数（或0）Wr,c，分别表示第r条东西向道路与第c条南北向道路交叉处路口放置的俄罗斯娃娃的重量（或表示没有放置娃娃）。Output: 输出能有最大收获的路径规划。假设1： cross.txt 2 7 1 2 13 6 7 12 11 14 3 4 5 8 9 10输出：1 2 3 4 5 6 7 8 9 10 11 12假设2： cross.txt 5 5 1 16 15 14 13 2 17 24 23 12 3 18 25 22 11 4 19 20 21 10 5 6 7 8 9输出：1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25注释:1)从出发;2)路线不能重复;3)不要求最后回到出发点。题目28：扫雷【问题描述】做一个N x M的扫雷游戏，每个方格包 含两种状态：关闭（closed）和打开（opened），初始化时每个方格都是关闭的，一个打开的方格也会 包含两种状态：一个数字（clue）和一个雷（bomb）。你可以打开（open）一个方格，如果你打开的是 一个bomb，那么就失败；否则就会打开一个数字，该数字是位于0，8的一个整数，该数字表示其所有 邻居方格（neighboring squares）所包含的雷数。【任务要求】1.能 够打开一个方格，一个已打开的方格不能再关闭。2.能够标记一个方格，标记方格的含义是 对该方格有雷的预测