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

1、题目 1：设计一元多项式简单计算 错误 !未定义书签。题目 2：链表应用 1 错. 误 !未定义书签。题目 3：链表应用 2 错误!未定义书签。题目 4：?通讯录 错误 ! 未定义书签。题目 5：停车场管理系统 . 错误!未定义书签。题目 6：约瑟夫环 . 错误!未定义书签。题目 7：运动会分数统计 . 错误!未定义书签。题目 8：文学研究助手问题 错误 !未定义书签。题目 9：银行业务模拟与离散事件模拟 错误 !未定义书签。题目 10：学生信息管理系统任务（用顺序表 / 链表） . 错误!未定义书签。 题目 11：文章编辑功能 错误 !未定义书签。题目 12：实验室管理 错误 !未定义书签。

2、题目 13：二叉树的基本操作（建立、求二叉树树深度、遍历）. 错误 !未定义书签。题目 14：纸牌游戏任务 错误 !未定义书签。题目 15：算术表达式求值 . 错误 !未定义书签。题目 16：内部排序算法比较 错误 !未定义书签。题目 17：哈夫曼树的构造和哈夫曼编码 / 译码 错误 !未定义书签。题目 18：构造可以使 n 个城市连接的最小生成树 错误!未定义书签。题目 19：交通咨询系统中的最短路径 错误 !未定义书签。题目 20：集合的交、并、差运算 . 错误!未定义书签。题目 21：长整数四则运算 . 错误 !未定义书签。题目 22：机订票系统 错误 !未定义书签。题目 23：图书管理

3、系统 错误 !未定义书签。题目 24：哈希表应用 错误 !未定义书签。题目 25：模拟旅馆管理系统的一个功能床位的分配与回收. 错误 !未定义书签。题目 26：地图着色问题 错误 !未定义书签。题目 27：俄罗斯套娃问题 . 错误 !未定义书签。题目 28：扫雷 错误 !未定义书签。题目29:用C语言设计一个日历系统 错误!未定义书签。题目 1：设计一元多项式计算【任务要求】(1) 能够按照指数降序排列建立并输出多项式；(2) 能够完成两个多项式的相加、相减，并将结果输入； 实现提示：可选择带头结点的单向循环链表?或单链表存储多项式，头结点可存放多项式的参数，如项数等。要求： 在上交资料中请写

4、明：存储结构、 多项式相加的基本过程的算法 (可以使用程序流程 图) 、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；【测试数据】自行选择?题目 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,并输出链表Do【测试数据】

5、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 个结点。 【任务要求】设计一组输入数据并编写完整的程序。 调试程序并对相应的输出作出分析； 修改输入数 据，预期输出并验证输出的结

6、果。【提示】1）逆转一个链表是指在不增加新结点的前提下，依次改变链表中结点的连接方向。2）删除数据结点时， 首先判断链表是否为空， 若非空，先判断第一个结点是否满足条件，若 是则删除； 否则从第二个结点开始顺序查找， 直到找到为止， 然后删除；对任何不满足条件 的情况都报告相应提示信息。3）从第 I 个结点开始连续删除 k 个结点时，考虑以下两种情况：当 I=1 时，从第一个开始 删除即可；当11时，先找到前一个结点然后再连续删除K个结点。最后释放各个结点空间。【测试数据】自行设定题目 4：?通讯录【问题描述】该设计采用菜单作为应用程序的主要界面， 用控制语句来改变程序执行的顺序， 控制 语句

7、是实现结构化程序设计的基础。 该设计的任务是利用一个简单实用的菜单， 通过菜单单 项进行选择， 实现和完成通讯录管理中常用的几个不同的功能。 通讯者所包含信息请自行设 定【任务要求】 菜单内容： （0）通讯录链表的建立 （1 ）通讯者结点的插入（2）通讯者结点的查询（3）通讯者结点的删除（4）通讯录链表的输出（5）退出管理系统 设计要求： 使用 05 来选择菜单项，其他输入则不起作用。功能函数设计5 个不同功能的算法实现编程题，目的是练习利用链表结构来解决实际应用问题的能力，进步理解和熟悉线形表的链式存储结构。【测试数据】 自行设定，注意边界等特殊情况。题目 6：约瑟夫环【问题描述】编号是1,

8、 2,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码(正整 数)。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自 1开始顺序报数，报到m时停止报数。报 m的人出列，将他的密码作为新的 m值，从他在顺时针方向的 下一个人开始重新从 1 报数， 如此下去， 直到所有人全部出列为止。 设计一个程序来求出出 列顺序。【任务要求】 利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。 输入数据：输入 m的初值，n，输入每个人的密码，建立单循环链表。 输出形式：建立一个输出函数，将正确的输出序列【测试数据】 m的初值为20，n=7,7个人的密码依次为 3，1，7,

9、2，4，7, 4。题目 7：运动会分数统计【问题描述】参加运动会有n个学校，学校编号为 1 n。比赛分成 m个男子项目，和 w个女子 项目。项目编号为男子 1m女子m+1m+w不同的项目取前五名或前三名积分；取前五名的积分分别为： 7、5、3、2、1 ，前三名的积分分别为： 5、3、2；哪些取前五名或前 三名由学生自己设定。( m=20,n=20)【任务要求】功能要求： 1). 可以输入各个项目的前三名或前五名的成绩；2) 能统计各学校总分，3) 可以按学校编号、学校总分、男女团体总分排序输出；4) . 可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名 的学校。规定：输

10、入数据形式和范围： 20 以内的整数(如果做得更好可以输入学校的名称，运 动项目的名称)输出形式：有中文提示，各学校分数为整型界面要求： 有合理的提示， 每个功能可以设立菜单， 根据提示，可以完成相关的功能要 求。存储结构： 学生自己根据系统功能要求自己设计， 但是要求运动会的相关数据要存储在 数据文件中。（数据文件的数据读写方法等相关内容在 c 语言程序设计的书上， 请自学解决） 请在最后的上交资料中指明你用到的存储结构；【测试数据】1、全部合法数据；2、整体非法数据；3、局部非法数据。 进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明；题目 9：银行业务模拟与离散事件

11、模拟【问题描述】假设某银行有4个窗口对外接待客户，从早晨银行开门（开门9: 00am,关门5: 00pm）起不断有客户进入银行。 由于每个窗口在某个时刻只能接待一个客户， 因此在客户人数众多 时需要在每个窗口前顺次排队, 对于刚进入银行的客户 （建议: 客户进入时间使用随机函数 产生）,如果某个窗口的业务员正空闲,则可上前办理业务；反之,若4 个窗口均有窗户所占,他便会排在人数最少的队伍后面。【任务要求】 编制一个程序以模拟银行的这种业务活动并计算一天中客户在银行逗留的平均时间。 建议有如下设置:客户到达时间随机产生,一天客户的人数设定为 100人。 银行业务员处理时间随机产生,平均处理时间1

12、0 分钟。将一天的数据（包括业务员和客户）以文件方式输出。【测试数据】 由随机数产生器生成题目 13:二叉树的基本操作（建立、求二叉树树深度、遍历）任务要求】 要求输入二树的各个结点，求二叉树的树深度，并能够输出指定遍历方式（层序、先序、中 序、后序）的遍历序列；分别建立；建立二叉树存储结构的的输入函数、求二叉树的树深度 的函数、遍历序列的函数层序遍历（用队列的方法实现） 中序遍历（ 用递归和非递归的方法一起都实现） 先序遍历（ 用递归和非递归的方法一起都实现） 后序遍历（ 用递归和非递归的方法一起都实现）题目 14：纸牌游戏任务【问题描述】编号为 1-52 张牌，正面向上，从第 2张开始，以

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

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

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

16、的编 / 译码系统。试为这样的信息收发站写一个哈夫曼码的编 / 译码系统。【任务要求】一个完整的系统应具有以下功能：I :初始化（Initialization）。从终端读入字符集大小n,以及n个字符和n个权值，建立哈夫曼树，并将它存于文件 hfmTree 中。E：编码（Encoding ）。利用以建好的哈夫曼树（如不在内存，则从文件hfmTree中读入），对文件 ToBeTran 中的正文进行编码,然后将结果存入文件 CodeFile 中。D：译码（Decoding ）。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件 TextFile 中。P:打印代码文件（Print

17、 ）。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件 CodePrin 中。T：打印哈夫曼树（Tree Printing ）。将已在内存中的哈夫曼树以直观的方式（树或凹入表 形式）显示在终端上,同时将此字符形式的哈夫曼树写入文件TreePrint 中。【测试数据】利用教科书P169第15题中的数据调试程序。用下表给出的字符集和频度的实际统计数据建立哈夫曼树,并实现以下报文的编码和译码：“THIS PROGRAM IS MY FAVORIT”E。字符空格ABCDEFGHIJKLM频度1866413223210321154757153220字符NO

18、PQRSTUVWXYZ频度5763151485180238181161题目18:构造可以使n个城市连接的最小生成树【问题描述】给定一个地区的n个城市间的距离网，用Prim算法和Kruskal算法建立最小生成树，并计算得到的最小生成树的代价。【任务要求】输入：表示城市间距离网的邻接矩阵（要求至少6个城市，10条边）城市间的距离网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树的代价。输出：最小生成树中包括的边及其权值，并显示得到的最小生成

19、树的代价。题目19：交通咨询系统中的最短路径【问题描述】建立交通图的存储结构、解决单源最短路径问题、再实现两个地点最短路径问题，也就是实现迪杰斯特拉和弗洛伊德方法【测试数据】自行设定交通图，交通站点不少于6个题目21:长整数四则运算【问题描述】设计一个实现任意长的整数进行加法运算的演示程序。【任务要求】利用双向循环链表实现长整数的存储，每个结点含一个整形变量。任何整形变量的范围是-（2A15 - 1） （2A15 - 1）。输入和输出形式：按中国对于长整数的表示习惯，每四位一组，组间用逗号隔开。【测试数据】（1）0 ； 0;应输出“ 0”。（2）-2345,6789 ； -7654,3211

20、;应输出“ -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，才能保证两数相加

21、不会溢出，但若这样存放，即相当于按 32768 进制存放， 在十进制与 32768 进制数之间的转换十分不方便， 故可以 在每个结点中仅存十进制的 4 位，即不超过 9999 的非负整数，整个链表表示为万进制。（2）可以利用头结点数据域的符号代表长整数的符号。用其绝对值表示元素结点数目。相 加过程中不要破坏两个操作数链表。 两操作数的头指针存于指针数组中是简化程序结构的一 种方法。不能给长整数位数规定上限。题目 23：图书管理系统【问题描述】 设计一个计算机管理系统完成图书管理基本业务。【任务要求】1）每种书的登记内容包括书号、书名、着作者、现存量和库存量；2）对书号建立索引表（线性表）以提高

22、查找效率；3）系统主要功能如下：*采编入库：新购一种书，确定书号后，登记到图书帐目表中，如果表中已有，则只将库存 量增加；* 借阅：如果一种书的现存量大于0，则借出一本，登记借阅者的书证号和归还期限，改变现存量；*归还：注销对借阅者的登记，改变该书的现存量。【进一步完成内容】1）系统功能的进一步完善；2）索引表采用树表。3）设计内容4）程序流程图5）源程序6）软件测试报告（包括所用到的数据及结果）【问题描述】利用哈希表进行存储。【任务要求】 任务要求：针对一组数据进行初始化哈希表，可以进行显示哈希表，查找元素，插入元素， 删除元素，退出程序操作。设计思想：哈希函数用除留余数法构造，用线性探测再

23、散列处理冲突。 设计目的：实现哈希表的综合操作 简体中文控制台界面：用户可以进行创建哈希表，显示哈希表，查找元素，插入元素，删除 显示元素：显示已经创建的哈希表。 查找元素：查找哈希表中的元素，分为查找成功和查找不成功。 插入元素：在哈希表中，插入一个元素，分为插入成功和失败。 删除元素：在已有的数据中，删除一个元素。退出系统：退出程序。【测试数据】 自行设定，注意边界等特殊情况。题目 25：模拟旅馆管理系统的一个功能床位的分配与回收【问题描述】某旅馆有n个等级的房间，第I等级有ai个房间，每个等级有 bi个床位（1 i n）。试 模拟旅馆管理系统中床位分配和回收的功能，设计能为单个旅客分配床

24、位，在其离店便回 收床位（供下次分配）的算法。【任务要求】（ 1 ）输入数据 分配时，输入旅客姓名、年龄、性别、到达日期和所需房间等级。 回收时，输入房间等级、房间号和床位号。（ 2 ）输出数据 分配成功时打印旅客姓名、年龄、到达日期、房间等级、房间号码和床位号码。 分配不成功时，如所有等级均无床位，则打印“客满”信息；如旅客需要的等级均无空床 位，则打印“是否愿意更换等级？”的询问信息。若旅客愿意更换，则重新输入有关信息， 再进行分配，否则分配工作结束。题目 26：地图着色问题【问题描述】已知中国地图 , 对各省进行着色 ,要求相邻省所使用的颜色不同 , 并保证使用的颜色总数最少 提示【任务

25、要求】（1） 数据结构的设计： 地图可以采用图的数据结构，每个省为一个节点，边表示对应的两个省相邻。（2） 算法设计：设计着色算法，保证邻接点不是同一种颜色。（3）地图数据的输入采取从文件中读取。（4）结果输出方式可以采用图形方式或文本方式。题目 27：俄罗斯套娃问题【问题描述】 伊万洛夫在比武大会上力克群雄，成为新一届“草原雄鹰”，为部落赢得了莫大荣誉。首领 决定要重重奖赏，他对伊万洛夫说： “孩子，你是知道的，面前的这片草原，南北向和东西 向的道路纵横交错。 现在，路口放着纯金打造的俄罗斯娃娃， 重量大小不等，重的都能装下 轻的。 你可以沿着道路飞奔，拾取路口的娃娃，要求是任何时刻必须是一

26、个套娃，装好后就不能再拆开了。注意不要走重复路。” 请你为伊万洛夫规划路线，使得他能够有最大的收获。【任务要求】Input:输入包括多组测试用例；每个测试用例开始是一对整数 , R表示东西向道路数，C表示南北向道路总数；接下来R行，每行包括 C个正整数（或0） Wr,c，分别表示第r条东西向道路与第 c 条南北向道路交叉处路口放置的俄罗斯娃娃的重量（或表示没有放置娃娃）。Output:输出能有最大收获的路径规划。假设 1：2 71 2 13 6 7 12 1114 3 4 5 8 9 10输出：1 2 3 4 5 6 7 8 9 10 11 12假设 2：5511615141321724231231825221141920211056789输出：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）从0,0出发 ;2）路线不能重复 ;3）不要求最后回到出发点。题目 28：扫雷【问题描述】做一个 N x M 的扫雷游戏，每个方格包 含两种状态：关闭（ closed ）和打开（ opened）， 初始化时每个方格都是关闭的，一个打开的方格也会 包含两种状态：一个数字（ clue ）和 一个雷（bomb）。你可以打开（ope n） 个方格，如果你打开的是一个bomb,那么就失败；否则就