数据结构题目汇总

1、序号题目内容难度1飞机订票系统设计一小型飞机订票系统，系统主要功能如下：1. 录入航班情况，修改航班信息；2. 查询：查询航线情况（如，输入航班号，起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓等）；3订票：实现订票功能，如果该航班已经无票，可以提供相关可选择航班；4退票：可退票，退票后修改相关数据文件；根据以上功能说明，自己设计航班信息，订票信息的存储结构。B-2宿舍管理软件采用简单交互方式设计一小型宿舍管理软件，系统主要功能如下：1. 录入及修改学生信息；2. 查询：按照姓名、学号和房间号等查询；3删除：可按照某条件实现批量删除功能。注：学生基本信息：姓名，学生证件号，房间号

2、，专业，班级和性别等。存储结构可以选用单链表或循环链表，也可根据功能需要自己设计。B-3图书借阅管理软件设计一小型图书借阅管理软件，系统主要功能如下：1. 录入新到图书的基本信息；2. 查询：按照作者、书名和出版社等查询，查找算法要求使用折半查找算法；3借阅：借阅人，借阅数量，期限等。对书号建立索引表（线性表）以提高查找效率，存储结构自定。B-4学生成绩管理设计一小型成绩管理软件，系统主要功能如下：1. 录入、修改和删除学生信息；2. 查询：按照姓名或学号查询，查找算法要求使用折半查找算法；3学生成绩排序、分类，平均成绩计算等。 注：学生基本信息：姓名，学生证件号，专业，班级和性别等。B-5同

3、学通讯录设计一小型同学通讯录，系统主要功能如下：1. 录入、修改及删除同学信息；2. 查询：按照姓名、城市等查询，查找算法可以使用折半查找；3排序：按照同学姓名排序，排序方法不唯一。 注：同学基本信息：姓名，性别，电话，E-MAIL和城市等。存储结构可以选用单链表或循环链表，也可根据功能需要自己设计。B-6工资管理软件设计一个职工工资管理软件，存储结构自定。系统主要功能如下：1. 新职工信息的录入;2调离和死亡等职工信息的删除；2. 职工某些信息的修改；3. 职工信息的查找。B-7航班信息的查询与检索1. 建立：建立一个线性表的存储结构。2. 录入功能：输入航班信息。3. 排序：按航班号进行排

4、序。3. 查询功能：输入航班号显示相应数据元素。输入起点站显示相应数据元素。输入终点站显示相应数据元素。输入起飞时间显示相应数据元素。输入到达时间显示相应数据元素。B-8火车售票系统1. 列车基本信息管理：输入所有列班信息。每条路线所涉及的信息有：终点站名、车次号、车厢号、开车周日（星期几）、乘员定额、余票量、已订票的客户名单（包括姓名、订票量、座位等级1，2或3）以及等候替补的客户名单（包括姓名、所需的票量）。2列车基本信息查询：按车次号查找，按抵达站查找，按路线查找三种查找方式进行查找。3. 订票管理：客户对想要购买的票进行订票。3. 退票管理：将不想要的票进行退票。B-9小型学生运动会成

5、绩管理软件设计一款小型学生运动会成绩管理软件，记录某校运动会上全部运动项目，各系获得的分数及排名的情况，包括50、100、200，400，1500米，跳高，跳远，标枪，铅球铁饼等。进入系统后可以输入和修改某个项目的结果情况，可以按各系院编号输出总分；按总分排序；按男团体总分排序 ；按系院编号查询；按项目编号查询；按女团体总分排序。B-10个人帐簿管理系统设计个人帐簿管理系统记录某人每月的全部收入及各项开支情况，包括食品消费，房租，子女教育费用，水电费，医疗费，储蓄等。进入系统后可以输入和修改某月的收支情况，可以对每月的开支从小到大进行排序，可以根据输入的月份查询每月的收支情况。B-11一元多项

6、式加（减）法计算设计一个一元多项式简单的加(减)法计算器，系统主要功能如下：1. 从键盘输入多项式，并以文件形式存储；2. 实现两个多项式相加,并建立输出多项式；3实现两个多项式相减,并建立输出多项式。注：可选择带头结点的单循环链表或单向链表存储多项式。B-12看 病 排 队用队列模拟上述看病排队候诊的问题，建立两个队列分别对应两个不同的优先级别，按照从终端读入的输入数据的方式进行模拟管理。（1）新的病人挂号然后加入队列候诊，护士根据病情指定其优先级。（2）医生根据优先级别为病人进行诊治。（3）病人出队。B-13自动括号匹配器的设计假设一个算术表达式中可包含三种括号：圆括号，方括号和花括号且这

7、三种括号可按任意次序嵌套使用。试利用栈的运算，编写判别给定表达式中所含括号是否正确配对出现的算法。B-14约瑟夫环编号为1，2 n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数的上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他的顺时针方向上的下一个开始重新从1报数，如此下去，直至所有人全部出列为止，设计一个程序求出出列顺序。B-15串的查找和替换打开一篇英文文章，在该文章中找出所有给定的单词，然后对所有给定的单词替换为另外一个单词，再存盘。B-16纸牌游戏编号为1-52张牌，正面向上，从第

8、2张开始，以2为基数，是2的倍数的牌翻一次，直到最后一张牌；然后，从第3张开始，以3为基数，是3的倍数的牌翻一次，直到最后一张牌；然后从第4张开始，以4为基数，是4的倍数的牌翻一次， 直到最后一张牌；.再依次5的倍数的牌翻一次，1的，1的直到 以52为基数的 翻过，输出：这时正面向上的牌有哪些？B-17专利信息检索系统专利信息的数据量很大，为了提高检索速度，对专利题目建立关键词索引表,并能根据关键词进行快速检索。指定一个文本文件, 文件中按行存放着若干专利的题目，对这些专利题目建立关键字索引, 并能够根据关键字进行快速检索。自拟定提取关键字的算法,要有一定的合理性。B-18舞伴配对程序假设在某

9、场舞会上，男士和女士进入舞厅时分别排成两队。跳舞开始时，依次从男队和女队的开始位置各出一个配成舞伴。若两初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。编写程序模拟上述舞伴配对程序。B-19扑克牌的排序编写算法能够用基数排序算法对扑克牌进行排序。应能够选择按花色优先或按面值优先，初始扑克牌牌序要求能自动的生成（随机生成）。B-20离散事件的模拟假设某银行有四个窗口对外接待客户，从早晨银行开门起不断有客户进入银行。由于每个窗口在某个时刻只能接待一个客户，因此在客户人数众多时需在每个窗口前顺次排队，对于刚进入银行的客户，如果某个窗口的业务员正空闲，则可上前办理业务，反之，若四个窗口均有客户

10、所占，他便会排在人数最少的队伍后面。这个程序以模拟银行的这种业务活动并计算一天中客户在银行逗留的平均时间。B-21实现并演示堆排序的排序算法和排序过程从键盘输入以整数序列, 可以动态演示堆排序算法对该整数序列进行排序的过程,并输出排序后的结果。B-22实现并演示快速排序的排序算法和排序过程从键盘输入以整数序列,可以动态演示快速排序算法对该整数序列进行排序的过程,并输出排序后的结果。B-23实现并演示希尔排序的排序算法和排序过程从键盘输入以整数序列,可以动态演示希尔排序算法对该整数序列进行排序的过程,并输出排序后的结果。B-24实现并演示归并排序的排序算法和排序过程从键盘输入以整数序列,可以动态

11、演示归并排序算法对该整数序列进行排序的过程,并输出排序后的结果。B-25英文词频统计程序设计一个程序，统计一篇英文文章中每个单词出现频率，然后根据用户输入的两个阈值a和b，将词频大于a的和词频小于b的所有单词输出。B-26排序综合利用随机函数产生N个随机整数（N2000000），对这些数进行多种方法进行排序。要求：1.要求采用所学的全部七种排序方法实现上述问题求解（具体有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中。2.统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。B-27基于双向循环链表

12、的通讯录的设计利用双向循环链表作为存储结构设计并实现一个通讯录程序。可以实现信息的添加、插入、删除、查询和统计等功能B-1大整数计算器由于整形数据存储位数有限，因此引入串的概念，将整型数据用字符串进行存储，利用字符串的一个字符存储大整数的一位数值，然后根据四则运算规则对相应位依次进行运算，同时保存进位，从而实现大整数精确的运算。B2关键词提取程序设计一个简单的英文关键词提取程序，可实现对一段英文短文中出现的频率最高的三个到五个词或短语进行提取。要求：1.从文件中读取一篇英文短文（300词以内），并显示在屏幕上。2.按照出现频率顺序显示三个到五个词语，并注明出现的次数。B3停车场管理程序设停车场

13、内只有一个可停入n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在最北端），若停车场内已停满n辆汽车，则后来的汽车只能停在门外的过道止等候，一旦停车场内有车开走，则排在过道上的第一辆车即可开入；当停车场内某车辆要离开时，由于停车场是狭长的通道，在它之后开入车辆必须先退出停车场为它让路，待该辆车开出大门外后，为它让路的车辆再按原次序进入停车场。每辆车按其在停车场停留的时间付费，车辆停在停车场内时需要计时收费，而停在过道上不收费。按这个要求，设计一个停车场管理程序。B4求解马踏棋盘问题国际象棋共有8行8列，

14、共64个单元格，无论将马放于棋盘的哪个单元格，都可以让马踏遍棋盘的每个单元格。马只能走日字，当马位于棋盘中间位置时，马可以向8个方向跳动，当马位于棋盘的边或角时，马可以跳动的方向将少于8个。另外，当马所跳向的8 个方向中的某一个或几个方向若已经被马走过，也将跳至马下一步要走的位置。B5黑白棋游戏程序黑白棋，又叫翻转棋、苹果棋或奥赛罗棋。棋盘共有8行8列共64格。开局时棋盘正中央的4格先放黑白相隔的4枚棋子，黑白子为交叉放置。通常黑子先行。双方轮流落子。只要落子和棋盘上任一枚己方的棋子在一条线上（横、直、斜线皆可）夹着对方棋子，就能将对方的这些棋子转变为己方的棋子（翻面即可）。如果在任一位置落子

15、都不能夹住对手的任一颗棋子，就要让对手下棋。当双方皆不能下子时，或者64个方格全部占满后，游戏就结束，子多一方获胜。B6文字编辑软件设计一小型文字编辑软件，系统主要功能如下：1. 从键盘输入文字，以文本文件形式存储；2. 统计该文本文件中英文字母数、空格数及整篇文章总字数；3统计某一字符串在文章中出现的次数，并输出该次数；4删除某一子串，并将后面的字符前移。注：存储结构使用线性表，分别用几个子函数实现相应的功能。B7字符串的排序与查找生成一个百万级的字符串集合，在该集合上演示快速排序，并计算集合规模对排序效率的影响。然后在生成的有序集上进行快速字符串查找，要求采用字符串分段hash算法实现。B

16、8最小矩形面积问题在一个二维平面中有N个点（点的数量不超过50个），每个点用二维坐标表示，例如，有4个点，且这4个点的坐标分别为：P1（1，1），P2（2，2），P3（3，6），P4（0，7）可以在二维平面中绘制一个矩形，使所有N个点都落在该矩形中。若要使用N个点都落在绘制的矩形中，则绘制一个非常大的矩形即可。也可以绘制多个矩形来覆盖所有点。现在要求在输入文件中给出N个点的坐标和绘制矩形数量K（1K3），请编程进行计算，怎么才能使得覆盖所有点的K个矩形的面积和最小B9应用堆实现一个优先队列优先队列priority queue 是一种可以用于很多场合的数据结构，该结构支持如下基本操作：Inser

17、t (S, x) 将元素x 插入集合SMinimum (S) 返回S 中最小的关键字Extract Min (S) 删除S 中的最小关键字可设计要求以堆作为辅助结构实现一个优先队列。要将堆结构嵌入到队列结构中，以作为其数据组织的一部分。此处由于要用堆实现队列，所以堆结构的存储表示要求用数组。B10医院选址问题n个村庄之间的交通图可以用有向网图来表示，图中边<vi, vj>上的权值表示从村庄i到村庄j的道路长度。现在要从这n个村庄中选择一个村庄新建一所医院，问这所医院应建在哪个村庄，才能使所有的村庄离医院都比较近？B11行编辑程序设计一个简单的行编辑程序。程序包括5个基本命令：E（行

18、编辑）, W（写入文件），#（退格）, （清除整行）和Q（存盘退出）。程序运行后提示用户输入命令：当用户输入“E”命令，开始编辑一行文本，程序为用户申请一个临时存放空间（栈），存储用户当前输入字符；当用户输入一个退格命令“#”，以表示当前栈顶字符无效；如果错误较多，可以键入退行符“”，清除栈中整行；当行输入完毕后，输入“W”命令，则将该行写入文件中。文件编辑结束后，输入“Q”命令，存盘退出。B12迷宫的生成与路由设计算法生成一个N×M(N 行M 列)的迷宫，并完成迷宫的组织和存储。实现两种不同的迷宫路由算法：广度优先，深度优先算法。要求：1N 和M 是用户可配置的，缺省值为50 和5

19、0。2迷宫的入口和出口分别在第0 行和第N-1 行上，随机选择。3生成的迷宫要求是连通的。B13集合运算求解设全集为字母集合，以链表代表一个子集，设计一组函数完成两个集合的并、交、差、异或和补五种运算，并演示其使用效果。B14索引顺序表表创建设计一个索引顺序表并给出查找算法。要求：索引表和数据表必须采用顺序存储存储结构实现；B15图的建立及输出建立图的存储结构（图的类型可以是有向图、无向图、有向网、无向网，学生可以任选两种类型），能够输入图的顶点和边的信息，并存储到相应存储结构中，而后输出图的邻接矩阵。B1二叉排序树的实现用顺序和二叉链表做存储结构，以回车('n')为输入结束标

20、志,输入数列L，生成一棵二叉排序树T。对二叉排序树T作中序遍历，输出结果；对二叉排序树T作先序遍历，输出结果；输入元素x,查找二叉排序树T，若存在含x的结点,则删除该结点，并作中序遍历；A-2哈夫曼编码/译码器设计一个利用哈夫曼算法的编码和译码系统，通过键盘输入权值数据，并以文件形式存储，从屏幕输出相应的哈夫曼树。利用建好的哈夫曼树生成哈夫曼编码，并通过屏幕输出相应的编码。A-3二叉排序树的插入、删除算法1. 给定一组关键字，生成一棵二叉排序树2. 删除该二叉排序树中的指定节点，删除后二叉排序树性质不发生变化3. 用直观、易于理解的形式来演示二叉排序树的插入、删除过程A-4二叉树遍历程序设计一

21、个程序：输入一个二叉树,对该树分别以先序、中序和后序三种方式进行遍历每个节点，并输出遍历结果，要求采用非递归算法。A-5树与二叉树转换利用双亲表示法创建一棵树，将该树转换为二叉链表表示，并给出转换后的二叉树的先序、中序和后序遍历结果以及对该二叉树进行中序遍历线索化。要求：给出树的双亲表示和二叉链表表示的存储结构；要求二叉树三种遍历要采用非递归算法；A-6图的基本操作编写算法能够建立带权图，输出该带权图各顶点的度，关联的所有边和边上的权值。输出该带权图的深度、广度优先遍历序列，并能够删除该带权图的任一顶点和该顶点关联的所有边。A-1Prim算法生成最小生成树在n个城市之间建设网络，只需保证连通即

22、可，求最经济的架设方法。利用Prim算法输出n个城市之间网络图，输出n个节点的最小生成树。其中，n个城市表示n个节点，两个城市间如果有路则用边连接，生成一个n个节点的边权图，要求键盘输入。A2最短路径求解从键盘输入一个图，节点代表城市，节点间的边代表城市间距离，现指定图中任意两个城市，求出连接这两个城市的最短行走路线。A3连通图着色求解从键盘输入一个无向图，给图上的每一个节点标记一种颜色，在保证任何相邻节点颜色不同的同时，求解出该图所需要的最少颜色数，并给出每个节点的具体颜色。A4哈斯图中特殊元素求解给定一个有向图，代表一个由特定偏序关系的导出的哈斯图，指定一个节点子集，求解该子集对应的极大元

23、、极小元、最大元、最小元、上界、下界、上确界、下确界八种特殊元素。A5实现求关键路径的算法自拟定合适的方式从键盘上输入一个AOE网, 并用合适的存储结构存储该AOE网. 然后求出该AOE网的关键路径。A6实现求有向图强连通分量的算法以合适方便的方式输入一有向图,并建立有向图的合适的存储结构. 判断该有向图是否强连通,如果是强连通图,则求出该图的所有的强连通分量并输出字符。A7二叉排序树的平衡化从键盘输入一个整数序列,根据该整数序列构造一棵平衡的二叉排序树。注意在构造二叉排序树时,要按照整数序列中整数的输入顺序插入节点。利用中序遍历算法输出经过平衡化的二叉排序树，输出时，输出每个节点的平衡因子。

24、A8KRUSKAL算法求最小生成树以合适方便的方式输入一个边带权值的无向图，采用邻接表存储结构存储该无向图，然后根据KRUSKAL算法求该无向图的最小生成树并输出A9求有向图中所有简单回路以合适方便的方式输入一有向图，并建立有向图的邻接表存储结构，然后求该有向图中所有的简单回路。输入有向图的方式要尽量简单方便，要能够形象方便地观察有向图的图形结构。A10有向图的拓扑排序以合适方便的方式输入一个有向图，采用邻接表存储结构存储该有向图，然后对该有向图进行拓扑排序，如果该有向图有环存在，程序需要给出图中有环的输出结果，否则输出对图进行拓扑排序的结果。A11稀疏矩阵运算稀疏矩阵是指那些多数元素为零的矩

25、阵。利用“稀疏”特点进行存储和计算可以大大的节省存储空间，提高计算效率。写一个以十字链表为存储结构的稀疏矩阵相加的程序。两个稀疏矩阵以元素值三元组的形式从终端读入，结果矩阵则以通常的阵列形输出。A12偏序关系中特殊元素判定给定一个有向图，代表一个由特定偏序关系的导出的哈斯图，指定一个节点子集，求解该子集对应的极大元、极小元、最大元、最小元、上界、下界、上确界、下确界八种特殊元素。A13利用弗洛伊德(Floyd)算法求解最短路径给出一张无向图，图上的每个顶点表示一个城市，顶点之间的边表示城市间存在路径，边上的权值表示城市间的路径长度。利用弗洛伊德(Floyd)算法求解最短路径求解任意两个城市之间

26、的最短路径问题。A14检测数据库死锁的等待图法事务等待图是一个有向图G=(T,U)。 T为结点的集合，每个结点表示正运行的事务；U为边的集合，每条边表示事务等待的情况。若T1等待T2,则T1、T2之间划一条有向边，从T1指向T2。事务等待图动态地反映了所有事务的等待情况，如果发现图中存在回路，则表示系统中出现了死锁。A15识别广义表头、尾演示写一个程序，建立广义表的存储结构，演示在此存储结构上实现的广义表求头/求尾操作序列的结果。广义表允许多行输入，其中可以任意输入空格符；广义表存储结构自定；对广义表的操作为一个由t和h组成的字符串；A16二叉排序Hash树的建立随机生成一整数作为树的结点关键字，建立一棵二叉排序Hash树，其中树中结点的Hash值计算方法为：(1)左右孩子都存在时，HashHash(H