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

《数据结构程序设计题目共29题.pdf》由会员分享，可在线阅读，更多相关《数据结构程序设计题目共29题.pdf（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构程序设计题目 I 目 录 题目 1：设计一元多项式简单计算.1 题目 2：链表应用 1.1 题目 3：链表应用 2.1 题目 4：通讯录.2 题目 5：停车场管理系统.错误!未定义书签。题目 6：约瑟夫环.3 题目 7：运动会分数统计.3 题目 8：文学研究助手问题.3 题目 9：银行业务模拟与离散事件模拟.4 题目 10：学生信息管理系统任务（用顺序表/链表）.错误!未定义书签。题目 11：文章编辑功能.错误!未定义书签。题目 12：实验室管理.错误!未定义书签。题目 13：二叉树的基本操作（建立、求二叉树树深度、遍历）.4 题目 14：纸牌游戏任务.5 题目 15：算术表达式求值.

2、5 题目 16：内部排序算法比较.5 题目 17：哈夫曼树的构造和哈夫曼编码/译码.6 题目 18：构造可以使 n 个城市连接的最小生成树.7 题目 19：交通咨询系统中的最短路径.7 题目 20：集合的交、并、差运算.错误!未定义书签。题目 21：长整数四则运算.7 题目 22：机订票系统.错误!未定义书签。题目 23：图书管理系统.8 题目 24：哈希表应用.8 题目 25：模拟旅馆管理系统的一个功能床位的分配与回收.9 题目 26：地图着色问题.9 题目 27：俄罗斯套娃问题.10 题目 28：扫雷.11 题目 29：用 C 语言设计一个日历系统.11 数据结构程序设计题目 1 题目 1

3、：设计一元多项式计算【任务要求】（1）能够按照指数降序排列建立并输出多项式；（2）能够完成两个多项式的相加、相减，并将结果输入；实现提示：可选择带头结点的单向循环链表 或单链表存储多项式，头结点可存放多项式的参数，如项数等。要求：在上交资料中请写明：存储结构、多项式相加的基本过程的算法（可以使用程序流程图）、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；【测试数据】自行选择 题目 2：链表应用 1【任务要求】实现两个链表的合并 基本功能要求：（1）建立两个链表 A 和 B，链表元素个数分别为 m 和 n 个。（2）假设元素分别为(x1,x2,xm)，和(y1,y2,yn

4、)。把它们合并成一个线形表 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）逆转该线性

5、链表；数据结构程序设计题目 2（2）删除线性链表中从左往右第一个数据为 data 的链结点；（3）删除从第 I 个链结点开始的连续 k 个结点。【任务要求】设计一组输入数据并编写完整的程序。调试程序并对相应的输出作出分析；修改输入数据，预期输出并验证输出的结果。【提示】1）逆转一个链表是指在不增加新结点的前提下，依次改变链表中结点的连接方向。2)删除数据结点时，首先判断链表是否为空，若非空，先判断第一个结点是否满足条件，若是则删除；否则从第二个结点开始顺序查找，直到找到为止，然后删除；对任何不满足条件的情况都报告相应提示信息。3）从第 I 个结点开始连续删除 k 个结点时，考虑以下两种情况：当

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

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

8、求】利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。输入数据：输入 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=2

9、0）【任务要求】功能要求：1).可以输入各个项目的前三名或前五名的成绩；2)能统计各学校总分，3)可以按学校编号、学校总分、男女团体总分排序输出；4).可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。规定：输入数据形式和范围：20 以内的整数（如果做得更好可以输入学校的名称，运动项目的名称）输出形式：有中文提示，各学校分数为整型 数据结构程序设计题目 4 界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。（数据文件的数据读写方法等相关内容在 c

10、语言程序设计的书上，请自学解决）请在最后的上交资料中指明你用到的存储结构；【测试数据】1、全部合法数据；2、整体非法数据；3、局部非法数据。进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明；题目 9：银行业务模拟与离散事件模拟【问题描述】假设某银行有 4 个窗口对外接待客户，从早晨银行开门（开门 9：00am，关门 5：00pm）起不断有客户进入银行。由于每个窗口在某个时刻只能接待一个客户，因此在客户人数众多时需要在每个窗口前顺次排队，对于刚进入银行的客户（建议：客户进入时间使用随机函数产生），如果某个窗口的业务员正空闲，则可上前办理业务；反之，若 4 个窗口均有窗户所占

11、，他便会排在人数最少的队伍后面。【任务要求】编制一个程序以模拟银行的这种业务活动并计算一天中客户在银行逗留的平均时间。建议有如下设置：客户到达时间随机产生，一天客户的人数设定为 100 人。银行业务员处理时间随机产生，平均处理时间 10 分钟。将一天的数据（包括业务员和客户）以文件方式输出。【测试数据】由随机数产生器生成 题目 13：二叉树的基本操作（建立、求二叉树树深度、遍历）【任务要求】数据结构程序设计题目 5 要求输入二树的各个结点，求二叉树的树深度，并能够输出指定遍历方式（层序、先序、中序、后序）的遍历序列；分别建立；建立二叉树存储结构的的输入函数、求二叉树的树深度的函数、遍历序列的函

12、数 层序遍历（用队列的方法实现）中序遍历（用递归和非递归的方法一起都实现）先序遍历（用递归和非递归的方法一起都实现）后序遍历（用递归和非递归的方法一起都实现）题目 14：纸牌游戏任务【问题描述】编号为 1-52 张牌，正面向上，从第 2 张开始，以 2 为基数，是 2 的倍数的牌翻一次，直到最后一张牌；然后，从第 3 张开始，以 3 为基数，是 3 的倍数的牌翻一次，直到最后一张牌；然后从第 4 张开始，以 4 为基数，是 4 的倍数的牌翻一次，直到最后一张牌；.再依次 5 的倍数的牌翻一次，6 的，7 的 直到 以 52 为基数的 翻过，输出：这时正面向上的牌有哪些？【任务要求】采用合适的数

13、据结构输出最后正面向上的牌，并将以 252 奇数翻牌的过程显示出来 题目 15：算术表达式求值【问题描述】在计算机中，算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同的优先级，又要考虑括号，因此，算术表达式的求值不可能严格地从左到右进行。因而在程序设计时，借助栈实现。【任务要求】算法输入：一个算术表达式，由常量、变量、运算符和括号组成（以字符串形式输入）。为简化，规定操作数只能为正整数，操作符为+、-*、/，用#表示结束。算法输出：表达式运算结果。算法要点：设置运算符栈和运算数栈辅助分析算符优先关系。在读入表达式的字符序列的同时，完成运算符和运算数的识别处理，以及相应运算。题

14、目 16：内部排序算法比较【问题描述】数据结构程序设计题目 6 编制一个演示内部排序算法比较的程序。利用随机函数产生 30000 个随机整数，利用冒泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、归并排序和堆排序等排序方法进行排序，并统计每一种排序上机所花费的时间。【任务要求】算法输入：以菜单的形式选择排序方法 算法输出：不同情况下关键字参加的比较次数和关键字的移动次数，每一种排序上机所花费的时间。算法要点：（1）利用随机函数产生 30000 个随机整数。（2）利用不同排序方法排序并统计两类次数，列表显示（3）程序以对话方式执行。题目 17：哈夫曼树的构造和哈夫曼编码/译码【问题描述】

15、利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。【任务要求】一个完整的系统应具有以下功能：I：初始化（Initialization）。从终端读入字符集大小 n，以及 n 个字符和 n 个权值，建立哈夫曼树，并将它存于文件 hfmTree 中。E：编码（Encoding）。利用以建好的哈夫曼树（如不在内存，则从文件 hfmTree 中读入），对文件

16、ToBeTran 中的正文进行编码，然后将结果存入文件 CodeFile 中。D：译码（Decoding）。利用已建好的哈夫曼树将文件 CodeFile 中的代码进行译码，结果存入文件 TextFile 中。P：打印代码文件（Print）。将文件 CodeFile 以紧凑格式显示在终端上，每行 50 个代码。同时将此字符形式的编码文件写入文件 CodePrin 中。T：打印哈夫曼树（Tree Printing）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件 TreePrint 中。【测试数据】利用教科书 P169 第 15 题中的数据调试

17、程序。用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“THIS PROGRAM IS MY FAVORITE”。数据结构程序设计题目 7 字符 空格 A B C D E F G H I J K 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 1 48 51 80 23 8 18 1 16 1 题目 18：构造可以使 n 个城市连接的最小生成树 【问题描述】给定一个地区的 n 个城市间的距离网，用 Prim 算法和 Kruskal

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

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”。数据结构程序设计题目 8（4）1,0001,0001；-1,

20、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）可以利用

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

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

23、中的元素，分为查找成功和查找不成功。插入元素：在哈希表中，插入一个元素，分为插入成功和失败。删除元素：在已有的数据中，删除一个元素。退出系统：退出程序。【测试数据】自行设定，注意边界等特殊情况。题目 25：模拟旅馆管理系统的一个功能床位的分配与回收【问题描述】某旅馆有 n 个等级的房间，第 I 等级有 ai 个房间，每个等级有 bi 个床位（1in）。试模拟旅馆管理系统中床位分配和回收的功能，设计能为单个旅客分配床位，在其离店便回收床位（供下次分配）的算法。【任务要求】（1）输入数据 分配时，输入旅客姓名、年龄、性别、到达日期和所需房间等级。回收时，输入房间等级、房间号和床位号。（2）输出数据

24、 分配成功时打印旅客姓名、年龄、到达日期、房间等级、房间号码和床位号码。分配不成功时，如所有等级均无床位，则打印“客满”信息；如旅客需要的等级均无空床位，则打印“是否愿意更换等级？”的询问信息。若旅客愿意更换，则重新输入有关信息，再进行分配，否则分配工作结束。题目 26：地图着色问题 数据结构程序设计题目 10【问题描述】已知中国地图,对各省进行着色,要求相邻省所使用的颜色不同,并保证使用的颜色总数最少提示【任务要求】（1）数据结构的设计：地图可以采用图的数据结构，每个省为一个节点，边表示对应的两个省相邻。（2）算法设计：设计着色算法，保证邻接点不是同一种颜色。（3）地图数据的输入采取从文件中

25、读取。（4）结果输出方式可以采用图形方式或文本方式。题目 27：俄罗斯套娃问题【问题描述】伊万洛夫在比武大会上力克群雄，成为新一届“草原雄鹰”，为部落赢得了莫大荣誉。首领决定要重重奖赏，他对伊万洛夫说：“孩子，你是知道的，面前的这片草原，南北向和东西向的道路纵横交错。现在，路口放着纯金打造的俄罗斯娃娃，重量大小不等，重的都能装下轻的。你可以沿着道路飞奔，拾取路口的娃娃，要求是任何时刻必须是一个套娃，装好后就不能再拆开了。注意不要走重复路。”请你为伊万洛夫规划路线，使得他能够有最大的收获。【任务要求】Input:cross.txt 输入包括多组测试用例；每个测试用例开始是一对整数，R 表示东西向

26、道路数，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 数据结构程序设计题目 11 假设 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 输

27、出：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的一个整数，该数字表示其所有 邻居方格（neighbo

28、ring squares）所包含的雷数。【任务要求】1.能 够打开一个方格，一个已打开的方格不能再关闭。2.能够标记一个方格，标记方格的含义是 对该方格有雷的预测（并不表示真的一定有雷），当一个方格标记后该方格不能被打开，只能执行取消 标记的操作，只能在取消后才能打开一个方格。3.能够给出游戏结果（输、赢、剩余的雷数、用掉 的时间按秒计）。在一个 10*10 的方格中，随机分布 10 个地雷，并在其它没有地雷的格中显示该方格周围相邻的方格中共有几枚地雷。题目 29：用 C 语言设计一个日历系统 数据结构程序设计题目 12【问题描述】1）输入任一年将显示出该年的所有月份日期，对应的星期 2）注意

29、闰年情况 其显示格式要求如下：1）中文英文都可以，2）下一行显示星期，从周日到周六，中英文都可以 3）下一行开始显示日期从 1 号开始，并按其是周几实际情况与上面的星期数垂直对齐 当输入 2004 显示如下：Input the year:2004 Input the file name:a The calendar of the year 2004.Januray 1 February 2 Sun Mon Tue Wed Thu Fri Sat Sun Mon Tue Wed Thu Fri Sat 1 2 3 1 2 3 4 5 6 7 4 5 6 7 8 9 10 8 9 10 11 12

30、 13 14 11 12 13 14 15 16 17 15 16 17 18 19 20 21 18 19 20 21 22 23 24 22 23 24 25 26 27 28 25 26 27 28 29 30 31 29 =March 3 April 4 Sun Mon Tue Wed Thu Fri Sat Sun Mon Tue Wed Thu Fri Sat 1 2 3 4 5 6 1 2 3 7 8 9 10 11 12 13 4 5 6 7 8 9 10 14 15 16 17 18 19 20 11 12 13 14 15 16 17 21 22 23 24 25 26 27 18 19 20 21 22 23 24 28 29 30 31 25 26 27 28 29 30 =