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

1、-. z.目 录 TOC o 1-3 h z u HYPERLINK l _Toc297558192题目1：设计一元多项式简单计算 PAGEREF _Toc297558192 h 1HYPERLINK l _Toc297558193题目2：链表应用1 PAGEREF _Toc297558193 h 1HYPERLINK l _Toc297558194题目3：链表应用2 PAGEREF _Toc297558194 h 1HYPERLINK l _Toc297558195题目4：通讯录 PAGEREF _Toc297558195 h 2HYPERLINK l _Toc297558196题目5：停车

2、场管理系统 PAGEREF _Toc297558196 h 3HYPERLINK l _Toc297558197题目6：约瑟夫环 PAGEREF _Toc297558197 h 3HYPERLINK l _Toc297558198题目7：运动会分数统计 PAGEREF _Toc297558198 h 3HYPERLINK l _Toc297558199题目8：文学研究助手问题 PAGEREF _Toc297558199 h 4HYPERLINK l _Toc297558200题目9：银行业务模拟与离散事件模拟 PAGEREF _Toc297558200 h 4HYPERLINK l _Toc2

3、97558201题目10：学生信息管理系统任务用顺序表/链表 PAGEREF _Toc297558201 h 5HYPERLINK l _Toc297558202题目11：文章编辑功能 PAGEREF _Toc297558202 h 6HYPERLINK l _Toc297558203题目12：实验室管理 PAGEREF _Toc297558203 h 6HYPERLINK l _Toc297558204题目13：二叉树的根本操作建立、求二叉树树深度、遍历 PAGEREF _Toc297558204 h 6HYPERLINK l _Toc297558205题目14：纸牌游戏任务 PAGEREF

4、 _Toc297558205 h 7HYPERLINK l _Toc297558206题目15：算术表达式求值 PAGEREF _Toc297558206 h 7HYPERLINK l _Toc297558207题目16：内部排序算法比拟 PAGEREF _Toc297558207 h 7HYPERLINK l _Toc297558208题目17：哈夫曼树的构造和哈夫曼编码/译码 PAGEREF _Toc297558208 h 8HYPERLINK l _Toc297558209题目18：构造可以使n个城市连接的最小生成树 PAGEREF _Toc297558209 h 9HYPERLINK

5、l _Toc297558210题目19：交通咨询系统中的最短路径 PAGEREF _Toc297558210 h 9HYPERLINK l _Toc297558211题目20：集合的交、并、差运算 PAGEREF _Toc297558211 h 9HYPERLINK l _Toc297558212题目21：长整数四则运算 PAGEREF _Toc297558212 h 9HYPERLINK l _Toc297558213题目22：机订票系统 PAGEREF _Toc297558213 h 10HYPERLINK l _Toc297558214题目23：图书管理系统 PAGEREF _Toc29

6、7558214 h 10HYPERLINK l _Toc297558215题目24：哈希表应用 PAGEREF _Toc297558215 h 11HYPERLINK l _Toc297558216题目25：模拟旅馆管理系统的一个功能床位的分配与回收 PAGEREF _Toc297558216 h 12HYPERLINK l _Toc297558217题目26：地图着色问题 PAGEREF _Toc297558217 h 12HYPERLINK l _Toc297558218题目27：俄罗斯套娃问题 PAGEREF _Toc297558218 h 12HYPERLINK l _Toc29755

7、8219题目28：扫雷 PAGEREF _Toc297558219 h 13HYPERLINK l _Toc297558220题目29：用C语言设计一个日历系统 PAGEREF _Toc297558220 h 14-. z.题目1：设计一元多项式计算【任务要求】1能够按照指数降序排列建立并输出多项式；2能够完成两个多项式的相加、相减，并将结果输入；实现提示：可选择带头结点的单向循环链表或单链表存储多项式，头结点可存放多项式的参数，如项数等。要求：在上交资料中请写明：存储构造、多项式相加的根本过程的算法可以使用程序流程图 、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改良方法；【

8、测试数据】 自行选择题目2：链表应用1【任务要求】实现两个链表的合并根本功能要求：1建立两个链表A和B，链表元素个数分别为m和n个。2假设元素分别为(*1,*2,*m)，和(y1,y2, yn)。把它们合并成一个线形表C，使得：当m=n时，C=*1,y1,*2,y2,*n,yn,*m当nm时，C=y1,*1,y2,*2,ym,*m,yn输出线性表C3 用直接插入排序法对C进展升序排序，生成链表D，并输出链表D。【测试数据】1 A表30，41，15，12，56，80B表23，56，78，23，12，33，79，90，552 A表30，41，15，12，56，80，23，12，34B表23，56，

9、78，23，12题目3：链表应用2【问题描述】非空线性链表第一个链结点的指针为list，写出以下各项操作的算法程序。1逆转该线性链表；2删除线性链表中从左往右第一个数据为data的链结点；3删除从第I个链结点开场的连续k个结点。【任务要求】设计一组输入数据并编写完整的程序。调试程序并对相应的输出作出分析；修改输入数据，预期输出并验证输出的结果。【提示】1逆转一个链表是指在不增加新结点的前提下，依次改变链表中结点的连接方向。2)删除数据结点时，首先判断链表是否为空，假设非空，先判断第一个结点是否满足条件，假设是则删除；否则从第二个结点开场顺序查找，直到找到为止，然后删除；对任何不满足条件的情况都

10、报告相应提示信息。3从第I个结点开场连续删除k个结点时，考虑以下两种情况：当I=1时，从第一个开场删除即可；当I1时，先找到前一个结点然后再连续删除K个结点。最后释放各个结点空间。【测试数据】 自行设定题目4：通讯录【问题描述】 该设计采用菜单作为应用程序的主要界面，用控制语句来改变程序执行的顺序，控制语句是实现构造化程序设计的根底。该设计的任务是利用一个简单实用的菜单，通过菜单单项进展选择，实现和完成通讯录管理中常用的几个不同的功能。通讯者所包含信息请自行设定【任务要求】 菜单内容：0通讯录链表的建立1通讯者结点的插入2通讯者结点的查询3通讯者结点的删除4通讯录链表的输出5退出管理系统设计要

11、求：使用05来选择菜单项，其他输入则不起作用。功能函数设计5个不同功能的算法实现编程题，目的是练习利用链表构造来解决实际应用问题的能力，进一步理解和熟悉线形表的链式存储构造。【测试数据】自行设定，注意边界等特殊情况。题目6：约瑟夫环【问题描述】编号是1，2，,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码正整数。一开场任选一个正整数作为报数上限值m,从第一个仍开场顺时针方向自1开场顺序报数，报到m时停顿报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开场重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。【任务要求】利用单向循环链表存储构造模

12、拟此过程，按照出列的顺序输出各个人的编号。输入数据：输入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).可以输入各个工程的前三名或前五

13、名的成绩；2)能统计各学校总分，3)可以按学校编号、学校总分、男女团体总分排序输出；4).可以按学校编号查询学校*个工程的情况；可以按工程编号查询取得前三或前五名的学校。 规定：输入数据形式和*围：20以内的整数如果做得更好可以输入学校的名称，运动工程的名称输出形式：有中文提示，各学校分数为整型界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。存储构造：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。数据文件的数据读写方法等相关内容在c语言程序设计的书上，请自学解决请在最后的上交资料中指明你用到的存储构造；【测试数据】1、全部合法数据

14、；2、整体非法数据；3、局部非法数据。进展程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明；题目9：银行业务模拟与离散事件模拟【问题描述】假设*银行有4个窗口对外接待客户，从早晨银行开门开门9：00am，关门5：00pm起不断有客户进入银行。由于每个窗口在*个时刻只能接待一个客户，因此在客户人数众多时需要在每个窗口前顺次排队，对于刚进入银行的客户建议：客户进入时间使用随机函数产生，如果*个窗口的业务员正空闲，则可上前办理业务；反之，假设4个窗口均有窗户所占，他便会排在人数最少的队伍后面。【任务要求】编制一个程序以模拟银行的这种业务活动并计算一天中客户在银行逗留的平均时间。建议

15、有如下设置：客户到达时间随机产生，一天客户的人数设定为100人。银行业务员处理时间随机产生，平均处理时间10分钟。将一天的数据包括业务员和客户以文件方式输出。【测试数据】由随机数产生器生成题目13：二叉树的根本操作建立、求二叉树树深度、遍历【任务要求】要求输入二树的各个结点，求二叉树的树深度，并能够输出指定遍历方式层序、先序、中序、后序的遍历序列；分别建立；建立二叉树存储构造的的输入函数、求二叉树的树深度的函数、遍历序列的函数层序遍历用队列的方法实现中序遍历 用递归和非递归的方法一起都实现先序遍历 用递归和非递归的方法一起都实现后序遍历 用递归和非递归的方法一起都实现题目14：纸牌游戏任务【问

16、题描述】编号为1-52*牌，正面向上，从第2*开场，以2为基数，是2的倍数的牌翻一次，直到最后一*牌；然后，从第3*开场，以3为基数，是3的倍数的牌翻一次，直到最后一*牌；然后从第4*开场，以4为基数，是4的倍数的牌翻一次， 直到最后一*牌；.再依次5的倍数的牌翻一次，6的，7的 直到 以52为基数的 翻过，输出：这时正面向上的牌有哪些？【任务要求】采用适宜的数据构造输出最后正面向上的牌，并将以252奇数翻牌的过程显示出来题目15：算术表达式求值【问题描述】在计算机中，算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同的优先级，又要考虑括号，因此，算术表达式的求值不可能严格地从

17、左到右进展。因而在程序设计时，借助栈实现。【任务要求】算法输入：一个算术表达式，由常量、变量、运算符和括号组成以字符串形式输入。为简化，规定操作数只能为正整数，操作符为+、-*、/，用#表示完毕。算法输出：表达式运算结果。算法要点：设置运算符栈和运算数栈辅助分析算符优先关系。在读入表达式的字符序列的同时，完成运算符和运算数的识别处理，以及相应运算。题目16：内部排序算法比拟【问题描述】编制一个演示内部排序算法比拟的程序。利用随机函数产生30000个随机整数，利用冒泡排序、直接插入排序、简单项选择择排序、快速排序、希尔排序、归并排序和堆排序等排序方法进展排序，并统计每一种排序上机所花费的时间。【

18、任务要求】算法输入：以菜单的形式选择排序方法算法输出：不同情况下关键字参加的比拟次数和关键字的移动次数，每一种排序上机所花费的时间。算法要点：1利用随机函数产生30000个随机整数。2利用不同排序方法排序并统计两类次数，列表显示3程序以对话方式执行。题目17：哈夫曼树的构造和哈夫曼编码/译码【问题描述】利用哈夫曼编码进展通信可以大大提高信道利用率，缩短信息传输时间，降低传输本钱。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进展译码复原。对于双工信道即可以双向传输信息的信道，每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。【任务

19、要求】一个完整的系统应具有以下功能：I：初始化Initialization。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。E：编码Encoding。利用以建好的哈夫曼树如不在内存，则从文件hfmTree中读入，对文件ToBeTran中的正文进展编码，然后将结果存入文件CodeFile中。D：译码Decoding。利用已建好的哈夫曼树将文件CodeFile中的代码进展译码，结果存入文件Te*tFile中。P：打印代码文件Print。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrin中。T

20、：打印哈夫曼树Tree Printing。将已在内存中的哈夫曼树以直观的方式树或凹入表形式显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。【测试数据】利用教科书P169第15题中的数据调试程序。用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：THIS PROGRAM IS MY FAVORITE。字符空格ABCDEFGHIJKLM频度1866413223210321154757153220字符NOPQRSTUVW*YZ频度5763151485180238181161题目18：构造可以使n个城市连接的最小生成树【问题描述】给定一个地区的n个城

21、市间的距离网，用Prim算法和Kruskal算法建立最小生成树，并计算得到的最小生成树的代价。【任务要求】输入：表示城市间距离网的邻接矩阵要求至少6个城市，10条边城市间的距离网采用邻接矩阵表示，邻接矩阵的存储构造定义采用课本中给出的定义，假设两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树的代价。输出：最小生成树中包括的边及其权值，并显示得到的最小生成树的代价。 题目19：交通咨询系统中的最短路径【问题描述】建立交通图的存储构造、解决单源最短路径问题、再实现两个地点最短路径问题，也就是实现迪杰斯特

22、拉和弗洛伊德方法【测试数据】 自行设定交通图，交通站点不少于6个题目21：长整数四则运算【问题描述】设计一个实现任意长的整数进展加法运算的演示程序。【任务要求】利用双向循环链表实现长整数的存储，每个结点含一个整形变量。任何整形变量的*围是 -(215 - 1) (215 - 1)。输入和输出形式：按中国对于长整数的表示习惯，每四位一组，组间用逗号隔开。 【测试数据】10；0；应输出0。2-2345,6789；-7654,3211；应输出-1,0000,0000”。3-9999,9999；1,0000,0000,0000；应输出9999,0000,0001”。41,0001,0001；-1,00

23、01,0001；应输出0。51,0001,0001；-1,0001,0000；应输出1。6-9999,9999,9999；-9999,9999,9999；应输出1,9999,9999,9998”。71,0000,9999,9999；1；应输出1,0001,0000,0000”。实现提示：1每个结点中可以存放的最大整数为32767，才能保证两数相加不会溢出，但假设这样存放，即相当于按32768进制存放，在十进制与32768进制数之间的转换十分不方便，故可以在每个结点中仅存十进制的4位，即不超过9999的非负整数，整个链表表示为万进制。2可以利用头结点数据域的符号代表长整数的符号。用其绝对值表示元

24、素结点数目。相加过程中不要破坏两个操作数链表。两操作数的头指针存于指针数组中是简化程序构造的一种方法。不能给长整数位数规定上限。题目23：图书管理系统【问题描述】设计一个计算机管理系统完成图书管理根本业务。【任务要求】1)每种书的登记内容包括书号、书名、著作者、现存量和库存量；2)对书号建立索引表线性表以提高查找效率；3)系统主要功能如下：*采编入库：新购一种书，确定书号后，登记到图书帐目表中，如果表中已有，则只将库存量增加；*借阅：如果一种书的现存量大于0，则借出一本，登记借阅者的书证号和归还期限，改变现存量；*归还：注销对借阅者的登记，改变该书的现存量。【进一步完成内容】1)系统功能的进一

25、步完善；2)索引表采用树表。3)设计内容4)程序流程图5)源程序6)软件测试报告包括所用到的数据及结果题目24：哈希表应用【问题描述】利用哈希表进展存储。【任务要求】 任务要求：针对一组数据进展初始化哈希表，可以进展显示哈希表，查找元素，插入元素，删除元素，退出程序操作。设计思想：哈希函数用除留余数法构造，用线性探测再散列处理冲突。设计目的：实现哈希表的综合操作简体中文控制台界面：用户可以进展创立哈希表，显示哈希表，查找元素，插入元素，删除元素。显示元素：显示已经创立的哈希表。查找元素：查找哈希表中的元素，分为查找成功和查找不成功。插入元素：在哈希表中，插入一个元素，分为插入成功和失败。删除元

26、素：在已有的数据中，删除一个元素。退出系统：退出程序。【测试数据】自行设定，注意边界等特殊情况。题目25：模拟旅馆管理系统的一个功能床位的分配与回收【问题描述】*旅馆有n个等级的房间，第I等级有ai个房间，每个等级有bi个床位1in。试模拟旅馆管理系统中床位分配和回收的功能，设计能为单个旅客分配床位，在其离店便回收床位供下次分配的算法。【任务要求】1输入数据分配时，输入旅客*、年龄、性别、到达日期和所需房间等级。回收时，输入房间等级、房间号和床位号。2输出数据分配成功时打印旅客*、年龄、到达日期、房间等级、房间和床位。分配不成功时，如所有等级均无床位，则打印客满信息；如旅客需要的等级均无空床位

27、，则打印是否愿意更换等级？的询问信息。假设旅客愿意更换，则重新输入有关信息，再进展分配，否则分配工作完毕。题目26：地图着色问题【问题描述】中国地图,对各省进展着色,要求相邻省所使用的颜色不同,并保证使用的颜色总数最少提示【任务要求】1 数据构造的设计：地图可以采用图的数据构造，每个省为一个节点，边表示对应的两个省相邻。2 算法设计：设计着色算法，保证邻接点不是同一种颜色。3 地图数据的输入采取从文件中读取。4 结果输出方式可以采用图形方式或文本方式。题目27：俄罗斯套娃问题【问题描述】伊万洛夫在比武大会上力克群雄，成为新一届草原雄鹰，为部落赢得了莫大荣誉。首领决定要重重奖赏，他对伊万洛夫说：

28、孩子，你是知道的，面前的这片草原，南北向和东西向的道路纵横交织。现在，路口放着纯金打造的俄罗斯娃娃，重量大小不等，重的都能装下轻的。你可以沿着道路飞奔，拾取路口的娃娃，要求是任何时刻必须是一个套娃，装好后就不能再拆开了。注意不要走重复路。请你为伊万洛夫规划路线，使得他能够有最大的收获。【任务要求】Input: cross.t*t 输入包括多组测试用例； 每个测试用例开场是一对整数，R表示东西向道路数，C表示南北向道路总数；接下来R行，每行包括C个正整数或0Wr,c，分别表示第r条东西向道路与第c条南北向道路穿插处路口放置的俄罗斯娃娃的重量或表示没有放置娃娃。Output: 输出能有最大收获的路

29、径规划。假设1： cross.t*t 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.t*t 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 * M的扫雷游戏，每个方格包 含两种状态：关闭closed和翻开opened，初始化时每个方格都是关闭的，一个翻开的方格也会 包含两种状态：一个数字clue和一个雷bomb。你可以翻开open一个方格，如果你翻开的是 一