数据结构课程设计题目

《数据结构课程设计题目》由会员分享，可在线阅读，更多相关《数据结构课程设计题目（34页珍藏版）》请在装配图网上搜索。

1、数据结构课程设计题目1.运动会分数统计（限1 人完成）任务：参加运动会有n个学校，学校编号为1n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1m，女子m+1m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。（m=20,n=20）功能要求：1)可以输入各个项目的前三名或前五名的成绩；2)能统计各学校总分，3)可以按学校编号或名称、学校总分、男女团体总分排序输出；4)可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。5)数据存入文件并能随时查询 6)规定：输入

2、数据形式和范围：可以输入学校的名称，运动项目的名称输出形式：有合理的提示，各学校分数为整形界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。（数据文件的数据读写方法等相关内容在c语言程序设计的书上，请自学解决）请在最后的上交资料中指明你用到的存储结构；测试数据：要求使用1、全部合法数据；2、整体非法数据；3、局部非法数据。进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明；2.飞机订票系统（限1 人完成）任务：通过此系统可以实现如下功能：录入：可以录入航班情

3、况（数据可以存储在一个数据文件中，数据结构、具体数据自定）查询：可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；可以输入起飞抵达城市，查询飞机航班情况；订票：（订票情况可以存在一个数据文件中，结构自己设定）可以订票，如果该航班已经无票，可以提供相关可选择航班；退票： 可退票，退票后修改相关数据文件；客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。修改航班信息：当航班信息改变可以修改航班数据文件要求：根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能；3.文章编辑（限1 人完成）功能：输入一页文字，程序可以统

4、计出文字、数字、空格的个数。静态存储一页文章，每行最多不超过80个字符，共N行；要求（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在文章中出现的次数，并输出该次数；（3）删除某一子串，并将后面的字符前移。存储结构使用线性表，分别用几个子函数实现相应的功能；输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。输出形式：（1）分行输出用户输入的各行字符；（2）分4行输出全部字母数、数字个数、空格个数、文章总字数（3）输出删除某一字符串后的文章；4.宿舍管理查询软件（限1 人完成）1)任务：为宿舍管理人员编写一个宿舍管理查询软件, 程序设计要求：A.

5、采用交互工作方式B.建立数据文件，数据文件按关键字（姓名、学号、房号）进行排序(冒泡、选择、插入排序等任选一种)2)查询菜单: (用二分查找实现以下操作)A.按姓名查询 B.按学号查询 C.按房号查询3)打印任一查询结果（可以连续操作）5.校园导航问题（限1 人完成）设计要求：设计你的学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）。6.教学计划编制问题（限1 人完成） 问题描述 大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等，每个专业开设的

6、课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。基本要求 （1）输入参数包括：学期总数，一学期的学分上限，每门课的课程号(固定占3位的字母数字串)、学分和直接先修课的课程号。（2）允许用户指定下列两种编排策略之一：一是使学生在各学期中的学习负担尽量均匀；二是使课程尽可能地集中在前几个学期中。（3）若根据给定的条件问题无解，则报告适当的信息；否则将教学计划输出到用户指定的文件中。计划的表格格式自行设计。测试数据学期总数：6；学分上限：10；该专业共开设12门课，课

7、程号从C01到C12，学分顺序为2,3,4,3,2,3,4,4,7,5,2,3。先修关系如下：课程编号课程名称先决条件C1程序设计基础无C2离散数学C1C3数据结构C1，C2C4汇编语言C1C5语言的设计和分析C3，C4C6计算机原理C11C7编译原理C5，C3C8操作系统C3，C6C9高等数学无C10线性代数C9C11普通物理C9C12数值分析C9，C10，C1实现提示可设学期总数不超过12，课程总数不超过100。如果输入的先修课程号不在该专业开设的课程序列中，则作为错误处理。应建立内部课程序号与课程号之间的对应关系。7.图书借阅管理系统（限1 人完成） 主要分为两大功能：1)图书管理(增加

8、图书、查询图书、删除图书、图书借阅、还书)；2)会员管理(增加会员、查询会员、删除会员、借书信息)；8.学生成绩管理（限1 人完成） 实现功能：输入、输出、插入、删除、查找、追加、读入、显示、保存、拷贝、排序、索引、分类合计、退出。9.活期储蓄帐目管理（限1 人完成） 活期储蓄处理中，储户开户、销户、存入、支出活动频繁，系统设计要求：1)能比较迅速地找到储户的帐户，以实现存款、取款记账；2)能比较简单，迅速地实现插入和删除，以实现开户和销户的需要。10.二叉排序树的实现（限1 人完成） 用顺序和二叉链表作存储结构 1)以回车(n)为输入结束标志,输入数列L，生成一棵二叉排序树T；2)对二叉排序

9、树T作中序遍历，输出结果；3)输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历(执行操作2)；否则输出信息“无x”；11.最小生成树问题（限1 人完成）设计要求：在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用多种。求解算法多种。12.通讯录的制作（限1 人完成）设计目的：用数据结构中的双向链表作数据结构，结合C语言基本知识。编写一个通讯录管理系统。以把所学数据结构知识应用到实际软件开发中去。设计内容：本系统应完成一下几方面的功能：1)输入信息enter();2)显示信息display( );3)查找以姓名作为关键字 search( );4)

10、删除信息delete( );5)存盘save ( );6)装入load( ) ;设计要求：1)每条信息至包含 ：姓名（NAME ）街道（STREET）城市（CITY）邮编（EIP）国家（STATE）几项2)作为一个完整的系统，应具有友好的界面和较强的容错能力3)上机能正常运行，并写出课程设计报告13.哈夫曼编码/译码器（限1 人完成）【问题描述】设计一个利用哈夫曼算法的编码和译码系统，重复地显示并处理以下项目，直到选择退出为止。【基本要求】1)将权值数据存放在数据文件(文件名为data.txt，位于执行程序的当前目录中) 2)分别采用动态和静态存储结构3)初始化：键盘输入字符集大小n、n个字符

11、和n个权值，建立哈夫曼树；4)编码：利用建好的哈夫曼树生成哈夫曼编码；5)输出编码；6)设字符集及频度如下表：字符 空格 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 【进一步完成内容】1)译码功能；2)显示哈夫曼树；3)界面设计的优化。14.图书管理系统（限1 人完成）【问题描述】设计一个计算机管理系统完成图书管理基本业务。【基本要求】1)每种书的登记内容包括书号、书名

12、、著作者、现存量和库存量；2)对书号建立索引表（线性表）以提高查找效率；3)系统主要功能如下：*采编入库：新购一种书，确定书号后，登记到图书帐目表中，如果表中已有，则只将库存量增加；*借阅：如果一种书的现存量大于0，则借出一本，登记借阅者的书证号和归还期限，改变现存量；*归还：注销对借阅者的登记，改变该书的现存量。【进一步完成内容】1)系统功能的进一步完善；2)索引表采用树表。3)设计内容4)程序流程图5)源程序6)软件测试报告（包括所用到的数据及结果）15.散列（哈希）表的设计与实现（限1 人完成）【问题描述】设计散列表实现电话号码查找系统。【基本要求】1)设每个记录有下列数据项：电话号码、

13、用户名、地址；2)从键盘输入各记录，分别以电话号码和用户名为关键字建立散列表；3)采用一定的方法解决冲突；4)查找并显示给定电话号码的记录；5)查找并显示给定用户名的记录。【进一步完成内容】1)系统功能的完善；2)设计不同的散列函数，比较冲突率；3)在散列函数确定的前提下，尝试各种不同类型处理冲突的方法，考察平均查找长度的变化。16.利用栈求表达式的值，可供小学生作业，并能给出分数。（限1 人完成）要求：建立试题库文件，随机产生n个题目；题目涉及加减乘除，带括弧的混合运算；随时可以退出；保留历史分数，能回顾历史，给出与历史分数比较后的评价17.二叉树的中序、前序、后序的递归、非递归遍历算法，层

14、次序的非递归遍历算法的实现，应包含建树的实现。（限1 人完成）要求：遍历的内容应是千姿百态的。树与二叉树的转换的实现。以及树的前序、后序的递归、非递归遍历算法，层次序的非递归遍历算法的实现，应包含建树的实现。要求：遍历的内容应是千姿百态的。18.学生搭配问题（限1 人完成）一班有m个女生,有n个男生(m不等于n),现要开一个舞会. 男女生分别编号坐在舞池的两边的椅子上.每曲开始时,依次从男生和女生中各出一人配对跳舞, 本曲没成功配对者坐着等待下一曲找舞伴. 请设计一系统模拟动态地显示出上述过程,要求如下:1)输出每曲配对情况2)计算出任何一个男生(编号为X)和任意女生(编号为Y),在第K曲配对

15、跳舞的情况.至少求出K的两个值.3)尽量设计出多种算法及程序,可视情况适当加分提示:用队列来解决比较方便.19.猴子吃桃子问题（限1 人完成） 有一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半且再多吃一个，到了第10天就只余下一个桃子。用多种方法实现求出原来这群猴子共摘了多少个桃子。要求：1)采用数组数据结构实现上述求解2)采用链数据结构实现上述求解3)采用递归实现上述求解20.数制转换问题（限1 人完成） 任意给定一个M进制的数x ，请实现如下要求1)求出此数x的10进制值（用MD表示）2)实现对x向任意的一个非M进制的数的转换。3)至少用两种或两种以上的方法实现上述要求（用栈解决，用数组

16、解决，其它方法解决）。21.排序综合（限1 人完成） 利用随机函数产生N个随机整数（20000以上），对这些数进行多种方法进行排序。要求：1)至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中。2)统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。3)如果采用4种或4种以上的方法者，可适当加分。22.图的遍历的实现（限1 人完成）要求：1)先任意创建一个图；2)图的DFS,BFS的递归和非递归算法的实现3)要求用有向图和无向图分别实现4)要求用邻

17、接矩阵、邻接表多种结构存储实现23. 文本文件单词的检索与计数设计要求与分析：要求编程建立一个文本文件，每个单词不包含空格且不跨行，单词由字符序列构成且区分大小写；统计给定单词在文本文件中出现的总次数；检索输出某个单词出现在文本中的行号、在该行中出现的次数以及位置。该设计要求可分为三个部分实现：其一，建立文本文件，文件名由用户用键盘输入；其二，给定单词的计数，输入一个不含空格的单词，统计输出该单词在文本中的出现次数；其三，检索给定单词，输入一个单词，检索并输出该单词所在的行号、该行中出现的次数以及在该行中的相应位置。（1）.建立文本文件（2）给定单词的计数（3）检索单词出现在文本文件中的行号、

18、次数及其位置（4）主控菜单程序的结构 头文件包含 菜单选项包含 建立文件、单词定位、单词计数、退出程序 选择1-4执行相应的操作，其他字符为非法。 24.任意长的整数加法（限1 人完成）问题描述：设计一个程序实现两个任意长的整数的求和运算。基本要求：利用双向循环链表，设计一个实现任意长的整数进行加法运算的演示程序。要求输入和输出每四位一组，组间用逗号隔开。如：1，0000，0000，0000，0000。25.串的查找和替换 （限1 人完成）问题描述：打开一篇英文文章，在该文章中找出所有给定的单词，然后对所有给定的单词替换为另外一个单词，再存盘。26.约瑟夫环 （限1 人完成）问题描述：编号为1

19、，2 n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数的上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他的顺时针方向上的下一个开始重新从1报数，如此下去，直至所有人全部出列为止，设计一个程序求出出列顺序。 基本要求：1、利用单循环链表作为存储结构模拟此过程；2、键盘输入总人数、初始报数上限值m及各人密码；3、按照出列顺序输出各人的编号。 27.客户消费积分管理系统（限1 人完成）问题描述：针对客户的消费情况，进行客户管理，根据客户的消费积分对客户实行不同程度的打折优惠。基本要求：1. 采用

20、一定的存储结构进行客户信息的存储；2. 对客户的信息可以进行修改、删除、添加；3. 能够根据消费情况进行客户积分的计算；4. 根据积分情况实行不同程度的打折优惠；28.产品进销存管理系统（限1 人完成）问题描述：针对某一种行业的库房的产品进销存情况进行管理。基本要求：1. 采用一定的存储结构对库房的货品及其数量进行分类管理；2. 可以进行产品类的添加、产品的添加、产品数量的添加；3. 能够查询库房每种产品的总量、进货日期、销出数量、销售时间等；29. 特殊矩阵的压缩存储算法的实现（限1 人完成）问题描述：对于特殊矩阵可以通过压缩存储减少存储空间。基本要求：1.针对多种特殊矩阵进行压缩存储，并能

21、显示压缩后的相关地址和值；2.输入在原来特殊矩阵中的地址，要求能从压缩后的矩阵中读出相应的值；30.算术表达式的求解（限1 人完成）问题描述：给定一个算术表达式，通过程序求出最后的结果。基本要求：1 从键盘输入要求解的算术表达式；2 采用栈结构进行算术表达式的求解过程；3 能够判断算术表达式正确与否；4 对于错误表达式给出提示；5 对于正确的表达式给出最后的结果；31.实时监控报警系统（限1 人完成）问题描述：建立一个报警和出警管理的系统基本要求：1. 采用一定的存储结构存储报警信息，要求有内容、时间；2. 有一次的出警就应该在待处理的信息中删除这条信息；3. 记录出警信息；4. 待处理信息过

22、多时会发出警告；32. 车厢调度 （限1 人完成）一列货运列车共有n节车厢，每节车厢将停放在不同的车站。假定n个车站的编号分别为1 n，货运列车按照第n站至第1站的次序经过这些车站。车厢的编号与它们的目的地相同。为了便于从列车上卸掉相应的车厢，必须重新排列车厢，使各车厢从前至后按编号1到n的次序排列。当所有的车厢都按照这种次序排列时，在每个车站只需卸掉最后一节车厢即可。我们在一个转轨站里完成车厢的重排工作，在转轨站中有一个入轨、一个出轨和k个缓冲铁轨（位于入轨和出轨之间），每个缓冲铁轨的容量小于总车厢个数的1/k。图5-5a 给出了一个转轨站，其中有k= 3个缓冲铁轨H1，H2和H3，每个缓冲

23、铁轨的容量为2个车厢。开始时，n节车厢的货车从入轨处进入转轨站，转轨结束时各车厢从右到左按照编号1至编号n的次序离开转轨站（通过出轨处）。在图5-5a 中，n= 9，车厢从后至前的初始次序为5，8，1，7，4，2，9，6，3。如下图所示，给出了按所要求的次序重新排列后的结果。具有三个缓冲铁轨的转轨站 a) 开始 b) 结束要求：对于给定的初始状态与终止状态，判断是否能在指定缓冲铁轨的容量条件下调度成功，如果能，请输出调度的过程。33.迷宫问题（栈）问题描述：以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路

24、的结论。基本要求：首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i,j,d）的形式输出，其中：（i,j）指示迷宫中的一个坐标，d表示走到下一坐标的方向，如：对于下列数据的迷宫，输出的一条通路为：（1，1，1），（1,2,2）,(3,2,3),(3,1,2),。测试数据：迷宫的测试数据如下：左下角（1，1）为入口，右下角（8，9）为出口。实现提示：计算机解迷宫通常用的是“穷举求解”方法，即从入口出发，顺着某个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口

25、，则所设的迷宫没有通路。可以二维数组存储迷宫数据，通常设定入口点的下标为（1，1），出口点的下标为（n,n）。为处理方便起见，可在迷宫的四周加一圈障碍。对于迷宫中任一位置，均可约定有东、南、西、北四个方向可通。选做内容：（1）编写递归形式的算法，求得迷宫中所有可能的通路；（2）以方阵形式输出迷宫及其通路。34. 病毒测试程序本题的任务是：当整个网络被感染后，计算有多少台机器被某个特定变种所感染。输入要求：输入由若干组测试数据组成。每组数据的第1行包含2个整数M和N（1M,N500），接下来是一个M*N的矩阵表示网络的初始感染状态，其中的正、负整数的意义如题目描述中所定义。下面一行给出一个正整数

26、Q，是将要查询的变种的个数。接下去的Q行里，每行给出一个变种的类型。当M或N为0时，表示全部测试结束，不要对该数据做任何处理。输出要求：对每一组测试，在一行里输出被某个特定变种所感染的机器数量。35.并查集：检查网络题目要求：给定一个计算机网络以及机器间的双向连线列表，每一条连线允许两端的计算机进行直接的文件传输，其他计算机间若存在一条连通路径，也可以进行间接的文件传输。请写出程序判断：任意指定两台计算机，它们之间是否可以进行文件传输？输入要求：输入若干测试数据组成。对于每一组测试，第1行包含一个整数N（10000），即网络中计算机的总台数，因而每台计算机可用1到N之间的一个正整数表示。接下来

27、的几行输入格式为I C1 C2或者 C或者C C1C2或者S，其中C1和C2是两台计算机的序号，I表示在C1和C2间输入一条连线，C表示检查C1和C2间是否可以传输文件，S表示该组测试结束。当N为0时，表示全部测试结束，不要对该数据做任何处理。输出要求：对每一组C开头的测试，检查C1和C2间是否可以传输文件，若可以，则在一行中输出“yes”，否则输出“no”。当读到S时，检查整个网络。若网络中任意两机器间都可以传输文件，则在一行中输出“The network is connected.”，否则输出“There are k components.”,其中k是网络中连通集的个数。两组测试数据之间请

28、输出一空行分隔。36.广义表的应用由于广义表在结构上较线性表复杂得多，因此，广义表的运算也不如线性表简单。本设计要求实现的广义表的建立、查找、输出、取表头和取表尾以及求深度、求逆表等。本设计用一个主控菜单程序控制，共分为6个子系统。（1）.建立广义表（2）输出广义表（3）结点的查找（4）求广义表表头（5）求广义表表尾（6）求广义表的深度37.网络流：宇宙旅行题目要求：在走遍了地球上的所有景点以后，旅游狂人开始计划他的宇宙旅行项目。经过谨慎调查，他目前掌握了一张各卫星空间站可以临时容纳的旅客人数列表。但旅客从一个星球飞往另一个星球时，需要在若干卫星空间站临时停靠中转，而这些空间站不能接待任何旅客

29、驻留，旅客必须立刻转乘另一艘飞船离开，所以空间站不能接待超过自己最大容量的旅客流。为了估计预算，现在旅游狂人需要知道终点星球的接待站应该设计多大容量，才能使得每艘飞船在到达时都可以保证让全部旅客下船。输入要求：输入若干组测试数据组成。每组测试数据的第1行包含旅行的起点星球和终点星球的名称和一个不超过500的正整数N（N为0标志全部测试结束，不要对该数据做任何处理）。接下来的N行里，数据格式为：sourcei capacityi ，其中sourcei和destinationi是卫星空间站的名称或起点、终点星球的名称，正整数capacityi是飞船从sourcei到destinationi一次能运

30、载的最大旅客流量。每个名称是由AZ之间三个大写字母组成的字符串，例如：ZJU。测试数据中不包含任何到达起点星球的信息以及任何从终点星球出发的信息。输出要求：对每一组测试，在一行里输出终点星球接待站应具有的最小容量，使得每艘飞船在到达时都可以保证让全部旅客下船。38.猴子选大王任务：一堆猴子都有编号，编号是1，2，3 .m ,这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。输入数据：输入m,n m,n 为整数，nm输出形式：中文提示按照m个猴子，数n 个数的方法，输出为大王的猴子是几号 ，建立一个

31、函数来实现此功能 39.纸牌游戏任务：编号为1-52张牌，正面向上，从第2张开始，以2为基数，是2的倍数的牌翻一次，直到最后一张牌；然后，从第3张开始，以3为基数，是3的倍数的牌翻一次，直到最后一张牌；然后从第4张开始，以4为基数，是4的倍数的牌翻一次， 直到最后一张牌；.再依次5的倍数的牌翻一次，6的，7的 直到 以52为基数的 翻过，输出：这时正面向上的牌有哪些？ 40.拓扑排序问题描述 建立图的存储结构，能够输入图的顶点和边的信息，并存储到相应存储结构中，再编写函数实现图的拓扑排序。基本要求 选择邻接表作为有向图的存储结构模拟整个过程，并输出拓扑排序的顶点序列。测试数据 利用下图中的数据

32、调试程序41.走迷宫程序开始运行时显示一个迷宫地图，迷宫中央有一只老鼠，迷宫的右下方有一个粮仓。游戏的任务是使用键盘上的方向键操纵老鼠在规定的时间内走到粮仓处。要求：1) 老鼠形象可辨认，可用键盘操纵老鼠上下左右移动；2) 迷宫的墙足够结实，老鼠不能穿墙而过；3) 正确检测结果，若老鼠在规定时间内走到粮仓处，提示成功，否则提示失败；4) 找出走出迷宫的所有路径，以及最短路径。42.敢死队问题 有M个敢死队员要炸掉敌人的一碉堡，谁都不想去，排长决定用轮回数数的办法来决定哪个战士去执行任务。如果前一个战士没完成任务，则要再派一个战士上去。现给每个战士编一个号，大家围坐成一圈，随便从某一个战士开始计

33、数，当数到5时，对应的战士就去执行任务，且此战士不再参加下一轮计数。如果此战士没完成任务，再从下一个战士开始数数，被数到第5时，此战士接着去执行任务。以此类推，直到任务完成为止。 排长是不愿意去的，假设排长为1号，请你设计一程序，求出从第几号战士开始计数才能让排长最后一个留下来而不去执行任务。43.HTML文档标记匹配算法要求：输入一段HTML代码，判断该代码是否符合HTML的语法提示：HTML文档由不同的标记划分为不同的部分与层次。与括号类似，这些标记需要成对出现，对于名为的起始标记，相应的结束标记为。常用的HTML标记：l :HTML文档l :文档标题l :文档体l :节的头部l :居中对

34、齐l :左对齐l :段落l 。HTML语言有合理的嵌套，如 44.分配策略有n个人去分m个蛋糕，每个蛋糕的底面积不等。（假设蛋糕的高度是相同的）要求，1：一个人只能从某块蛋糕中分到其中的一块，不能从2个以上的不同蛋糕中分得蛋糕。2：要求每个人分到的蛋糕块体积相同，同时，每个分到的蛋糕的体积是最大的。对于给定的n，m以及m各蛋糕的底面积，求分配的方案，以及每人能分到多大面积的蛋糕。例如：假定有6个人分3块蛋糕，每块底面积的大小分别为：3，9，7。那么最终的分配方案为：1人分半径为3蛋糕，2人分半径为7的蛋糕，3人分半径为9的蛋糕，每人能分到面积为3的蛋糕。45.语言中平衡符号的问题要求：设C语言

35、程序代码中包含如下符号/* */，（），编写程序检测一段C代码中上述符号是否正确。46.烫手山芋问题一群小孩编号为1，2，n(n0)围成一圈，有一个刚出锅的山芋在他们之间传递。假设刚开始由1号拿着山芋，然后依次计数把山芋交给下一个小孩，当数到某个特定的k时，拿着山芋的小孩退出游戏，然后从下一个小孩重新开始计数，如此不断，最后剩下的那个孩子就是幸运者。要求设计一个程序模拟次过程，并给出不同的n，k组合下那个幸运者是谁？47.入学考试问题某地大学入学考试，相关信息如下：(1)参加人数：10万。(2)共有8门考试课程，每门课程满分均为100分，所有课程成绩均进行了4舍5入的处理，考生的总分也照此处理

36、。(3)所有考生的考试成绩保存在文件scores.txt中，文件格式如下：每个考生成绩一行，每行格式如下：最开始为考生姓名，然后为每门课程的分数，考生姓名与课程分数之间，以及不同课程分数之间均用一个英文逗号隔开，如：张三,98,92,60,54,87,75,86,92个别考生成绩行的格式可能会有误。(4)共招收三个批次的学生，第一批次30000人，第二批次60000人，第三批次10000人。录取顺序为：第一批次，第二批次，第三批次。程序要求：(1)确定每一批次的录取分数线，并将批次、分数线、实际录取人数输出到文本文件soutput.txt中，每一批次录取信息占一行，格式自定。确定分数线时，如果

37、在分数线处有多名考生，则将这些考生全部录取，即每一批次的实际录取人数可能会超过预定人数。例如：假定在确定第一批次分数线时，有7800人的总分高于等于750分，有8050人的总分高于等于749分，则第一批次分数线应确定为749分，实际录取人数为8050人。(2)如果考生成绩行的格式不对，则丢弃该考生的成绩，不作为确定分数线的依据，但要求将该考生姓名输出到文本文件serror.txt中，格式自定。(3)将总分为650分的考生姓名输出到文本文件soutput.txt中，格式自定。(4)将第三批次录取的所有考生的平均成绩（4舍5入）输出到文本文件soutput.txt中，格式自定。(5)要求将下面两个

38、时间值（单位为秒）输出到文件soutput.txt的最后：从打开scores.txt文件到读完所有考生成绩的时间；从打开scores.txt文件到程序结束的时间。48.括号嵌套问题某个序列完全由圆括号组成，一个“（”和一个“）”称为一对括号，且序列中的括号成对出现。设n为序列中出现的括号对数，k为序列中括号的最大嵌套深度；那么，序列“()()()()()”的n为8，k为3。1、请编程判断任意给定的圆括号序列，是否是一个深度为k的序列。 要求：（1）先输入嵌套深度k，然后输入任意一个序列，最后给出判定结果（是，不是，或者输入序列中的括号不配对） （2）可以反复输入数据，当k为0时，程序结束。wh

39、ile(k!=0)输入示例：3()()()()()2()()()()()5()()()()()输出的判定结果：测试1：YES测试2：NO测试3：括号不配对2、编程输出括号对数为n，嵌套深度为k的所有序列。(1=k=nn时，程序结束。输出结果示例（n=5，k=3）：1: ()()()2: ()()()3: ()()()4: ()()5: ()()()6: ()()()7: ()()8: ()()()9: ()()()10: ()()()11: ()()()12: ()()()13: ()()14: ()()()15: ()()()16: ()()()17: ()()()18: ()()()5对括

40、号，3层嵌套问题,共求出18种情况3、求解括号对数为n，嵌套深度为k的序列的总数（不输出具体序列）。(1=k=n=30)输入示例：321532011输出结果：32：3种153：497845种2011：94817125种49.树重建 给出一棵标号树的BFS序列和DFS序列，设计一个算法重新建立这棵树（结点数n1000）。当某结点被扩展时，它的所有孩子应该按照编号从小到大的顺序访问。例如一棵树的BFS序列为43512876，DFS序列为43172658，则一棵满足条件的树如右图所示。输入格式第一行输入结点数n。第二行n个用空格隔开的整数，描述这棵树的BFS序列；第三行n个用空格隔开的整数，描述这棵

41、树的DFS序列。输出格式一共输出n-1行，每行两个整数i,j描述一条边，表示第i个结点与第j个结点之间连一条边。样例输入84 3 5 1 2 8 7 64 3 1 7 2 6 5 8样例输出4 55 84 33 22 63 11 7提示：我们曾经遇到过相似的题目，给出一棵二叉树的先序，中序，后续遍历中的其中两种，要你还原这棵二叉树。而这题改为了给出DFS和BFS序列，虽然形式上变了，但是原理还是相似的，我们只需抓住树的性质和充分利用这两个序列的特性就能把这种题目解决。 拿题目数据做例子。首先，无论是BFS（广度优先搜索）序列还是DFS（深度优先搜索）序列，第一个点都必定是根结点。接着我们看BF

42、S序列，跟在根结点4后面的连续若干个结点就是4的儿子结点，但是究竟有多少个是4的儿子呢？首先，题目中的一个条件说：“某结点被扩展时，它的所有孩子应该按照编号从小到大的顺序访问”，因此4的儿子应该是按由小到大出现在BFS序列中的。后面31，所以1就肯定不是4的儿子。然而即使后面若干个数满足升序的条件，也不一定全都是4的儿子，这时我们就要借助DFS序列了。因为DFS的规律是遍历完一棵子树才到另一棵，所以4的儿子在DFS序列中也是按由小到大出现，只是它们之间可能被若干个结点隔开罢了。根据这两个条件，我们就能判断哪些是4的儿子了。例如在BFS序列中紧挨着4出现的3,5，在DFS序列中也是按照由小到大的

43、顺序先出现3，再出现5，因此3,5都是4的儿子。 接下来怎么做呢？由于4的儿子都确定了，剩下的就是把4的每一棵子树都确定下来，而这就是一个子问题了。若我们确定了根结点有k个儿子，若第i个儿子在DFS中的位置为P1，第i+1个儿子在DFS中的位置为P2，则在DFS序列中位置P1与P2之间的所有结点就是以第i个儿子为根的子树的结点。而我们可以建立一个队列，每确定一个结点就把它加到队列里面去，模拟BFS的过程。在模拟广搜的过程中，若当前要处理的结点为k，由于以k为根的整棵子树在DFS序列中是连续的一段，而究竟是那一段在前面的广搜过程中是可以顺带求出的。然后我们利用BFS序列和DFS序列中连续的一段确

44、定出k的所有儿子，并加到广搜队列里面。直到广搜结束，问题就解决了。50.背包问题的求解假设有一个能装入总体积为T的背包和n件体积分别为w1 , w2 , , wn 的物品，能否从n件物品中挑选若干件恰好装满背包，即使w1 +w2 + + wn=T，要求找出所有满足上述条件的解。例如：当T=10，各件物品的体积1，8，4，3，5，2时，可找到下列4组解：（1，4，3，2）（1，4，5）（8，2）（3，5，2）。提示：可利用回溯法的设计思想来解决背包问题。首先将物品排成一列，然后顺序选取物品装入背包，假设已选取了前i 件物品之后背包还没有装满，则继续选取第i+1件物品，若该件物品太大不能装入，则弃

45、之而继续选取下一件，直至背包装满为止。但如果在剩余的物品中找不到合适的物品以填满背包，则说明刚刚装入背包的那件物品不合适，应将它取出弃之一边，继续再从它之后的物品中选取，如此重复，直至求得满足条件的解，或者无解。由于回溯求解的规则规则是后进先出因此自然要用到栈。51.全国交通咨询模拟【问题描述】处于对不同目的的旅客对交通工具有不同的要求。例如，因公出差的旅客希望在旅途中的时间尽可能短，出门旅游的游客则希望旅费尽可能省，而老年旅客则要求中转次数最少。编制一个全国城市间的交通咨询程序，为旅客提供两种或三种最优决策的交通咨询。【基本要求】（1）提供对城市信息进行编辑（如：添加或删除）的功能。 （2）

46、城市之间有两种交通工具：火车和飞机。提供对列车时刻表和飞机航班进行编辑（增设或删除）的功能。 （3）提供两种最优决策：最快到达或最省钱到达。全程只考虑一种交通工具。 （4）旅途中耗费的总时间应该包括中转站的等候时间。 （5）咨询以用户和计算机的对话方式进行。由用户输入起始站、终点站、最优决策原则和交通工具，输出信息：最快需要多长时间才能到达或者最少需要多少旅费才能到达，并详细说明依次于何时乘坐哪一趟列车或哪一次班机到何地。【测试数据】【实现提示】（1）对全国城市交通图和班车时刻表及飞机航班表的编辑，应该提供文件形式输入和键盘输入两种方式。飞机航班表的信息应包括：起始站的出发时间、终点站的到达时

47、间和票价；列车时刻表则需根据交通图给出各个路段的详细信息，例如：对于从北京到上海的火车，需给出北京至天津、天津至徐州及徐州至各段的出发时间、到达时间和票价信息。 （2）以邻接表作交通图的存储结构，表示边的结点内除含有邻接点的信息外，包括交通工具、路程中消耗的时间和花费以及出发和到达的时间等多项属性。52.LZW压缩器/解压器【问题描述】为了节省存储空间，常常需要把文本文件采用压缩编码的方式储存。例如：一个包含1000个x的字符串和2000个y的字符串的文本文件在不压缩时占用的空间为3002字节（每个x或每个y占用一个字节，两个字节用来表示串的结尾）。同样是这个文件，采用游程长度编码（run-l

48、ength coding），可以存储为字符串1000x2000y，仅为10个字母，占用12个字节。若采用二进制表示游程长度（1000和2000）可以进一步节约空间。如果每个游程长度占用2个字节，则可以表示的最大游程长度为2*pow(16)，这样，上例中的字符串只需要用8个字节来存储。当要读取编码文件时，需要对其进行解码。由压缩器（compressor）对文件进行编码，由解压器（decompressor）进行解码。（1）长度-游程编码的压缩/解压；+（2）LZW压缩/解压（散列）；（1）长度-游程编码的压缩/解压；+（3）霍夫曼编码压缩/解压 (霍夫曼树) 【基本要求】要求选用二种压缩/解压策略

49、实现压缩/解压器（1）为必选。输入的为本文文件（.txt），输出的为一种自定义的文件（.nz）。考虑当构成文本的字符集合为a,b,c,z,0,1,2,9时，请用实例测试你的压缩/解压器。你的压缩器会不会出现抖动？（压缩后的文本比原来的还要大）。扩充构成文本的字符集合以便使它适应更一般的情况。【实现提示】LZW：由Lempel、Ziv和Welch这三位科学家所开发的技术。该方法把文本的字符串映射为编码，首先，为该文本中所有可能出现的字母分别分配一个代码。例如：要压缩的对象是aaabbbbbbbaabaaba，由a和b组成。为a分配代码0,为b分配代码1。字符串和编码的关系被存储在字典中。字典如下

50、：Key 01234567CodeAbAaaabbbbbbbbbaaaba LZW压缩器不断的在输入文件中寻找在字典中出现的最长的前缀p,并输出其相应的代码。若输入文件的下一个字符为c，则为pc分配下一个代码，并插入字典，这种策略称为LZW规则。相反，在解压时，编码表由压缩文件重新构造，LZW原则使这种重建成为可能。 如上例子，压缩时，文件中第一个在字典中出现的最长前缀是a, 输出其编码0,然后为字符串aa分配代码2，并插入到字典中。余下的字符串在字典中出现的最长前缀是aa,输出aa的对应代码2，同时为字符串aab分配代码3并将其插入到字典中。依次类推，由此，输出0214537 解压时，要输入

51、代码，然后用代码所表示的文本来替换这些代码。代码到文本的映射可按下面的方法重建：首先把分配给单一字母的代码插入到字典中。象前面一样，字典的入口为key-code对。然而此时是根据给定的代码（key）去寻找相应的入口（而不是根据文本Code）。压缩文件中的第一个代码对应于单一的字母，因此可以由该字母代替。对于压缩文件中的其他代码p,要考虑两种情况：1）在字典中；2）不在字典中。在1）情况下，找到p对应的文本text(p)输出。并且，根据压缩原理可知，若在压缩文件中代码q写在p之前且text(q)是与q对应的文本，则压缩器会为文本text(q)（其后紧跟fc(p)，text(p)的第一个字符）分配

52、一新代码。因此在字典中插入序偶（下一个代码，text(q)fc(p)）。 情况2）时，只有在当前文本段形如text(q)text(q)fc(q)且text(p)=text(q)fc(q)时才会发生。相应的压缩文件段是qp。在压缩过程中，为text(q)fc(q)分配的代码为p。在解压过程中，在用text(q)代替q后，又遇到代码p。然而，此时字典中没有与p对应的文本。因为这种情况只在解压文本段为text(p)text(q)fc(q)时才发生，因此可以对p解码。当遇到一个没有定义代码文本对的代码p时，p对应的文本为text(q)fc(q)，其中q为p前面的代码。如上例子：首先，初始化字典，在其中

53、插入(0,a),(1,b)。压缩的第一个代码为0,则用a代替之。下一个代码2未定义，因为前一个代码为0，且text(0)=a,fc(0)=a,则text(2)=text(0)fc(0)=aa。因此用aa代替2,并把(2,aa)插入字典中。下个代码1由b来替换，并把(3,text(2)fc(1)=(3,aab)插入字典中。依次类推，得解压结果。53.奇数阶幻方求解要求必须在空间复杂度为O(N)的要求下实现N阶幻方的输出。Problem description 幻方是一种很有意思的数字矩阵，在很早著名的九宫八卦阵就与幻方有关。幻方的定义为： 1 到 N*N 的整数填入N*N的方格中，每行和每列以及

54、对角线的数字之和必须是相等的。你作为八卦公司的顶级程序员，现在需要你解决一个问题，将任意奇数阶的幻方找出来。 Input 输入包括多个测试集，每行为一个正奇数N(1 = N 1000)，0作为输入的结束且不需要处理。 Output 对于输入的每一个N， 输出一个它所对应的N阶幻方，如果存在多个，任意一个即可。每个幻方为N*N的矩阵，对于每个幻方，每行输出幻方的一行，每行中的数字之间用一个或多个空格分开。不同的幻方之间用一个空行分开。 Sample Input 130 Sample Output 14 9 23 5 78 1 654.偶数阶幻方求解对于给定的n，求出（2*n）*(2*n)的幻方的

55、所有情况。但是要去除所有等价的情形，所谓等价，就是通过旋转或翻转后相同的情形。55.城市链表问题描述将若干城市的信息，存入一个带头结点的单链表。结点中的城市信息包括：城市名，城市的位置坐标。要求能够利用城市名和位置坐标进行有关查找、插入、删除、更新等操作。基本要求（1） 给定一个城市名，返回其位置坐标；（2） 给定一个位置坐标P和一个距离D，返回所有与P的距离小于等于D的城市。测试数据由学生依据软件工程的测试技术自己确定。注意测试边界数据。56.约瑟夫生死者游戏问题描述约瑟夫（Joeph）问题的一种描述是：编号为1,2,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个

56、正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。基本要求利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。测试数据m的初值为20；密码：3，1，7，2，4，8，4（正确的结果应为6，1，4，7，2，3，5）。实现提示程序运行后首先要求用户指定初始报数上限值，然后读取各人的密码。设n30。选作内容向上述程序中添加在顺序结构上实现的部分。57.停车场管理问题描述设停车场内只有一个可停放n辆汽车的狭长通

57、道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门外，其它车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。测试数据设n=2,输入数据为：（A，1，5），（A，2，10），（D，1，15），（A，3， 20）， （A，4，25），（

58、A，5，30），（D，2，35），（D，4，40），（E，0，0）。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，其中，A表示到达；D表示离去，E表示输入结束。基本要求以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，对每一组输入数据进行操作后的输出数据为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车离去；则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表实现。实

59、现提示需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。选作内容（1） 两个栈共享空间，思考应开辟数组的空间是多少？（2） 汽车可有不同种类，则它们的占地面积不同，收费标准也不同，如1辆客车和1.5辆小汽车的占地面积相同，1辆十轮卡车占地面积相当于3辆小汽车的占地面积。（3） 汽车可以直接从便道上开走，此时排在它前面的汽车要先开走让路，然后再依次排到队尾。（4） 停放在便道上的汽车也收费，收费标准比停放在停车场的车低，请思考如何修改结构以满足这种要求。58.简单行编辑程序问题描述文本编辑程序是利用计算机进行文字加工的基本软件工具，实现对文本文件的插入、删除等修改操作。限制这些操作以行为单位进行的编辑程序称为行编辑程序。被编辑的文本文件可能很大，全部读入编辑程序的数据空间（内存）的做法既不经济，也不总能实现。一种解决方法是逐段地编辑。任何时刻只把待编辑文件的一段放在内存，称为活区。试按照这种方法实现一个简单的行编辑程序。设文件每行不