2017年数据结构课程设计题目及报告范例

1. 运动会分数统计

【问题描述】

参加运动会的n个学校编号为1～n。比赛分成m个男子项目和w个女子项目，项目编号分别为1～m和m+1～m+w。由于各项目参加人数差别较大，有些项目取前五名，得分顺序为7，5，3，2，1；还有些项目只取前三名，得分顺序为5，3，2。写一个统计程序产生各种成绩单和得分报表。 【基本要求】

1) 可以输入各个项目的前三名或前五名的成绩； 2) 能统计各学校总分，

3) 可以按学校编号或名称、学校总分、男女团体总分排序输出； 4) 可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前

三或前五名的学校。 5) 数据存入文件并能随时查询

6) 规定：输入数据形式和范围：可以输入学校的名称，运动项目的名称 输出形式：有中文提示，各学校分数为整型。

界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。

存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。

测试数据： 【测试数据】

要求使用1、全部合法数据；2、整体非法数据；3、局部非法数据。进行程序测试，以保证程序的稳定。

例如，对于n=4，m=3，w =2，编号为奇数的项目取前五名，编号为偶数的项目取前三名，设计一组实例数据。 【实现提示】

可以假设n≤20，m≤30，w≤20，姓名长度不超过 20 个字符。每个项目结束时，将其 编号、类型符(区分取前五名还是前三名) 输入，并按名次顺序输入

1

运动员姓名、校名(和成 绩)。 【选作内容】

允许用户指定某项目采取其他名次取法。

2. 集合的并、交和差运算

【问题描述】

编制一个能演示执行集合的并、交和差运算的程序。 【基本要求】

(1) 集合的元素限定为小写字母字符 [‘a’..’z’] 。 (2) 演示程序以用户和计算机的对话方式执行。 【测试数据】

(1)Set1=\，Set2=\，

Set1∪Set2=\，Setl ∩Set2=\，Set1-Set2=\。 (2)Set1= \，Set2=\，

Set1∪Set2=\，Setl ∩Set2=\，Set1-Set2=\。 【实现提示】

以有序链表表示集合。 【选作内容】

(1) 集合的元素判定和子集判定运算。 (2) 求集合的补集。

(3) 集合的混合运算表达式求值。

(4) 集合的元素类型推广到其他类型 ， 甚至任意类型。

3. 一元稀疏多项式计算器

【问题描述】

设计一个一元稀疏多项式简单计算器。 【基本要求】

一元稀疏多项式简单计算器的基本功能是： (1) 输入并建立多项式 ；

2

(2) 输出多项式，输出形式为整数序列：n，cl，el，c2，e2，…，cn，en，其中n是多项式的项数，ci 和ei，分别是第 i 项的系数和指数，序列按指数降序排列；

(3) 多项式a和b相加，建立多项式a +b； (4) 多项式a和b相减，建立多项式a -b 。 【测试数据】

(1)(2x+5x8－3.1x11) + (7－5x8+11x9)=(－3.lx11+11x9+2x+7) (2)(6x-3－x+4.4x2－1.2x9) －(-6x-3+5.4x2－x2+7.8x15)

=(-7.8x15-1.2x9+12x-3-x)

(3)(1 +x + x2+x3+x4+x5)+(-x3－x4)=(1+x+x2+x5) (4)(x+x3)+(-x－x3)=0

(5)(x+x100)+(x100 +x200)=(x+2x100+x200) (6)(x+x2+x3)+0=x+x2+x3

(7) 互换上述测试数据中的前后两个多项式 【实现提示】

用带表头结点的单链表存储多项式。 【选作内容】

(1) 计算多项式在x处的值。 (2) 求多项式 a 的导函数a? 。 (3) 多项式a和b相乘，建立乘积多项式ab 。

(4) 多项式的输出形式为类数学表达式。例如 ，多项式 -3x8+6x3－18 的输出形式为

?3x?8?6x?3?18，x15+(－8)x7－14的输出形式为x?15?8x?7?14。注意，数

值为1的非零次项的输出形式中略去系数1，如项1x8的输出形式为x8，项 －1x3的输出形式为－x3。

(5) 计算器的仿真界。

3

4. 池塘夜降彩色雨

【问题描述】

设计一个程序，演示美丽的“池塘夜雨”景色：色彩缤纷的雨点飘飘洒洒地从天而降， 滴滴入水有声，溅起圈圈微澜。 【基本要求】

(1) 雨点的空中出现位置、降范过程的可见程度、入水位置、颜色、最大水

圈等，都是随机确定的 ；

(2) 多个雨点按照各自的随机参数和存在状态，同时演示在屏幕上。 【测试数据】

适当调整控制雨点密度、最大水圈和状态变化的时间间隔等参数。 【实现提示】

(1) 每个雨点的存在周期可分为三个阶段：从天而降、入水有声和圈圈微澜，

需要一

个记录存储其相关参数、当前状态和下一状态的更新时刻。

(2) 在图形状态编程。雨点下降的可见程度应是断断续续、依稀可见；圈圈

水波应是

由里至外逐渐扩大和消失。

(3) 每个雨点发生时，生成其记录，并预置下一个雨点的发生时间。 (4) 用一个适当的结构管理当前存在的雨点，使系统能利用它按时更新每个雨点的状态，一旦有雨点的水圈全部消失，就从结构中删去。 【选作内容】

(1) 增加“电闪雷鸣”景象。

(2) 增加风的效果，展现“风雨飘摇”的情景。

(3) 增加雨点密度的变化：时而“和风细雨”， 时而“暴风骤雨”。 (4) 将“池塘”改为“荷塘”，雨点滴在荷叶上的效果是溅起四散的水珠，响声也不同。

4

5. 银行业务模拟

【问题描述】

客户业务分为两种。第一种是申请从银行得到一笔资金，即取款或借款。第二种是向银行投入一笔资金，即存款或还款。银行有两个服务窗口，相应地有两个队列。客户到达银行后先排第一个队。处理每个客户业务时，如果属于第一种，且申请额超出银行现存资金总额而得不到满足，则立刻排入第二个队等候，直至满足时才离开银行；否则业务处理完后立刻离开银行。每接待完一个第二种业务的客户，则顺序检查和处理(如果可能)第二个队列中的客户，对能满足的申请者予以满足，不能满足者重新排到第二个队列的队尾。注意，在此检查过程中，一旦银行资金总额少于或等于刚才第一个队列中最后一个客户(第二种业务)被接待之前的数额，或者本次已将第二个队列检查或处理了一遍，就停止检查(因为此时已不可能还有能满足者)转而继续接待第一个队列的客户。任何时刻都只开一个窗口。假设检查不需要时间。营业时间结束时所有客户立即离开银行。 写一个上述银行业务的事件驱动模拟系统，通过模拟方法求出客户在银行内逗留的平均时间。

【基本要求】

利用动态存储结构实现模拟。 【测试数据】

一天营业开始时银行拥有的款额为10000(元)，营业时间为600(分钟)。其他

模拟参

量自定，注意测定两种极端的情况：一是两个到达事件之间的间隔时间很短，而客户的交易时间很长，另一个恰好相反，设置两个到达事件的间隔时间很长，而客户的交易时间很短。

【实现提示】

事件有两类：到达银行和离开银行。初始时银行现存资金总额为total。开始营业后的第一今事件是客户到达，营业时间从0到closetime。到达事件发生时随机地设置此客户的交易时间和距下一到达事件之间的时间间隔。每个客户要办理的款额也是随机确定的，用负值和正值分别表示第一类和第二类业务。变量total，closetime以及上述两个随机量的上下界均交互地从终端读入，作为模拟参数。

5

【基本要求】

(1)输出文件中字与字之间只留一个空格符,即实现多余空格符的压缩。 (2)在输出文件中,任何完整的字仍不能分割在两行,行尾不齐没关系,但行首要对齐(即左对齐)。

(3)如果所要求的每页页底所空行数不少于3,则将页号印在页底空行中第2行的中间位置上,否则不印。

(4)版面要求的参数要包含：

页长(PageLength)一一每页内文字(不计页号)的行数。 页宽(PageWedth)一一每行内文字所占最大字符数。 左空白(LeftMargin)-一一每行文字前的固定空格数。 头长(HeadingLength)一一每页页顶所空行数。

脚长(FootingLength)一一每页页底所空行数(含页号行)。 起始页号(StartingPageNumber)一一首页的页号。 【测试数据】

略。注意在标点之后加上空格符。 【实现提示】

可以设:左空白数×2+页宽<=160,即行印机最大行宽,从而只要设置这样大的一个行缓冲区就足够了,每加工完一行,就输出一行。

如果输入文件和输出文件不是由程序规定死,而是可由用户指定,则有两种做法:一是像其他参量一样,将文件名交互地读入字符串变量中;更好的方式是让用户通过命令行指定,具体做法依机器的操作系统而定。

应该首先实现GetAWord(w)这一操作,把诸如行尾处理、文件尾处理、多余空格符压缩等一系列\低级\事务留给它处理,使系统的核心部分集中对付排版要求。

每个参数都可以实现缺省值②设置。上述排版参数的缺省值可以分别取56,60,10,5,5和1。 【选作内容】

(1)输入文件名和输出文件名要由用户指定。

(2)允许用户指定是否右对齐,即增加一个参量\右对齐否

11

\缺省值可设为\。右对齐指每行最后一个字的字尾要对齐,多余的空格要均匀分布在本行中各字之间。

(3)实现字符填充(characterstuffing)技术。\作为分段控制符之后,限制了原文中不能有这样的字。现在去掉这一限制:如果原文中有这样的字,改用两个\并列起来 表示一个\字。当然,如果原文中此符号夹在字中,就不必特殊处理了。

(4)允许用户自动按多栏印出一页。

12. 简单行编辑程序

【问题描述】

文本编辑程序是利用计算机进行文字加工的基本软件工具,实现对文本文件的插入、删除等修改操作。限制这些操作以行为单位进行的编辑程序称为行编辑程序。

被编辑的文本文件可能很大,全部读入编辑程序的数据空间(内存)的作法既不经济,也不总能实现。一种解决方法是逐段地编辑。任何时刻只把待编辑文件的一段放在内存,称为活区。试按照这种方法实现一个简单的行编辑程序。设文件每行不超过320个字符,很少超过80个字符。 【基本要求】

实现以下4条基本编辑命令:

(1) 行插入。格式:i<行号><回车><文本>.<回车>

将<文本>插入活区中第<行号>行之后。 (2) 行删除。格式:d<行号l>[<空格><行号2>]<回车>

删除活区中第<行号l>行(到第<行号2>行)。例如:\和\。 (3) 活区切换。格式n<回车>

将活区写入输出文件,并从输入文件中读入下一段,作为新的活区。 (4) 活区显示。格式:p<回车>

逐页地(每页20行)显示活区内容,每显示一页之后请用户决定是否继续显示以后备页(如果存在)。印出的每一行要前置行号和一个空格符,行号固定占4位,增量为1。

12

各条命令中的行号均须在活区中各行行号范围之内,只有插入命令的行号可以等于活区第一行行号减1,表示插入当前屏幕中第一行之前,否则命令参数非法。 【测试数据】

自行设定,注意测试将活区删空等特殊情况。 【实现提示】

(1)设活区的大小用行数ActiveMULen(可设为100)来描述。考虑到文本文件行长通常为正态分布,且峰值在60到70之间,用320×ActiveMULen大小的字符数组实现存储将造成大量浪费。可以以标准行块为单位为各行分配存储,每个标准行块可含81个字符。这些行块可以组成一个数组,也可以利用动态链表连接起来。一行文字可能占多个行块。行尾可用一个特殊的ASCII字符(如(012)8)标识。此外,还应记住活区起始行号。行插入将引起随后各行行号的顺序下推。

(2)初始化函数包括:请用户提供输入文件名(空串表示无输入文件)和输出文件名,两者不能相同。然后尽可能多地从输入文件中读入各行,但不超过ActiveMULen-LX的值可以自定,例如20。

(3)在执行行插入命令的过程中,每接收到一行时都要检查活区大小是否已达ActiveMaxLen。如果是,则为了在插入这一行之后仍保持活区大小不超过ActiveMaxLen应将插入点之前的活区部分中第一行输出到输出文件中;若插入点为第一行之前,则只得将新插入的这一行输出。

(4)若输入文件尚未读完,活区切换命令可将原活区中最后几行留在活区顶部,以保持阅读连续性;否则,它意味着结束编辑或开始编辑另一个文件。

(5)可令前三条命令执行后自动调用活区显示。 【选作内容】

(1)对于命令格式非法等一切错误作严格检查和适当处理。

(2)加入更复杂的编辑操作,如对某行进行串替换；在活区内进行模式匹配等，格式可以为S<行号>@<串1>@<串2><回车>和m<串><回车>。

13

13. 串基本操作的演示

【问题描述】

如果语言没有把串作为一个预先定义好的基本类型对待,又需要用该语言写一个涉及串操作的软件系统时,用户必须自己实现串类型。试实现串类型,并写一个串的基本操作的演示系统。 【基本要求】

在教科书4.2.2节用堆分配存储表示实现HString串类型的最小操作子集的基础上,实现串抽象数据类型的其余基本操作(不使用C语言本身提供的串函数)。参数合法性检查必须严格。

利用上述基本操作函数构造以下系统:它是一个命令解释程序,循环往复地处理用户键入的每一条命令,直至终止程序的命令为止。命令定义如下:

(1)赋值。 格式: A <串标识> <回车>

用<串标识>所表示的串的值建立新串,并显示新串的内部名和串值。例:A ‘Hi!’

(2)判相等。格式: E <串标识1> <串标识2> <回车> 若两串相等,则显示\否则显示\。 (3)联接。 格式:C <串标识1> <串标识2> <回车> 将两串拼接产生结果串,它的内部名和串值都显示出来。 (4)求长度。格式:L〈串标识> <回车> 显示串的长度。

(5)求子串。格式:S <串标识> +<数1>+<数2><回车>

如果参数合法,则显示子串的内部名和串值。<数>不带正负号。 (6)子串定位。格式:I <串标识1> <串标识2> <回车> 显示第二个串在第一个串中首次出现时的起始位置。

(7)串替换。格式: R <串标识1> <串标识2> <串标识3> <回车> 将第一个串中所有出现的第二个串用第三个串替换,显示结果串的内部名和串值,原串不变。

(8)显示。格式:P <回车>

14

显示所有在系统中被保持的串的内部名和串值的对照表。 (9)删除。格式:D <内部名> <回车> 删除该内部名对应的串,即赋值的逆操作。 (10)退出。格式:Q <回车> 结束程序的运行。

在上述命令中,如果一个自变量是串,则应首先建立它。基本操作函数的结果(即函数值)如果是一个串,则应在尚未分配的区域内新辟空间存放。 【测试数据】

自定。但要包括以下几组:

(1)E ‘’ ‘’<回车>,应显示\。

(2)E ‘abc’ ‘abcd’<回车>,应显示\。 (3)C ‘ ‘ ‘ ‘ <回车>,应显示\。

(4)I ‘a’ ‘’ <回车>,应报告:参数非法。 (5)R ‘aaa’ ‘aa’ ‘b’<回车>,应显示'ba’

(6)R ‘aaabc’ ‘a’ ‘aab’<回车>,应显示’aabaabaabbc’。 (7)R ‘Faaaaaaaa’ ‘aaaa’ ‘ab’,<回车>,应显示’abab’。 【实现提示】

【选作内容】

(1) 串头表改用单链表实现。

(2) 对命令的格式(即语法)作严格检查,使系统既能处理正确的命令,也能处理错误的命令。注意,语义检查(如某内部名对应的串已被删除而无定义等)和基本操作参数合法性检查仍应留给基本操作去做。

(3) 支持串名。将串名(可设不超过6个字符)存于串头表中。命令(1)(3)(5)要增加命令参数<结果串名>;命令(7)中的<串标识1> 改为<串名>,并用此名作为结果串名,删除原被替串标识,用<串名>代替<串标识>定义和命令解释中的内部名。每个命令执行完毕时立即自动删除无名串。

15

置的。 【测试数据】

入库书号:35，16，18，70，5，50，22，60，13，17，12，45，25，毡，15，90，30，7然后清除:45，90，50，22，42

其余数据自行设计。由空树开始，每插入删除一个关键字后就显示B树的状态。 【实现提示】

(1)24树的查找算法是基础，入库和清除操作都要调用。难点在于删除关键字的算法，因而只要算法对2-3树适用就可以了，暂时不必追求高阶B树也适用的删除算法。

(2)每种书的记录可以用动(或静)态链式结构。借阅登记信息可以链接在相应的那种书的记录之后。

【选作内容】

(l)将一次会话过程(即程序一次运行)中的全部人机对话记入一个日志文件

\中去。

(2)增加列出某著者全部著作名的操作。思考如何提高这一操作的效率，参阅

教科书12.6.2节。

(3〉增加列出某种书状态的操作。状态信息除了包括这种书记录的全部信息

外还包括最早到期(包括已逾期)的借阅者证号，日期可用整数实现，以求简化。

(4)增加预约借书功能。

24. 多关键字排序

【问题描述】

多关键字的排序有其一定的实用范围。例如:在进行高考分数处理时，除了需对总分进行排序外，不同的专业对单科分数的要求不同，因此尚需在总分相同的情况下，按用户提出的单科分数的次序要求排出考生录取的次序。 【基本要求】

(1)假设待排序的记录数不超过10000，表中记录的关键字数不超过5，各个关键字的范围均为0至100。按用户给定的进行排序的关键字的优先关系，输出

26

排序结果。

(2)约定按LSD法进行多关键字的排序。在对各个关键字进行排序时采用两种策略:其一是利用稳定的内部排序法，其二是利用\分配\和\收集\的方法。并综合比较这两种策略。 【测试数据】

由随机数产生器生成。 【实现提示】

用5至8组数据比较不同排序策略所需时间。由于是按LSD方法进行排序，则对每个关键字均可进行整个序列的排序，但在利用通常的内部排序方法进行排序时，必须选用稳定的排序方法。借助\分配\和\收集\策略进行的排序，如同一趟\基数排序\，由于关键字的取值范围为0至100，则分配时将得到104个链表。 【选作内容】

增添按MSD策略进行排序，并和上述两种排序策略进行综合比较。

27

25手机通讯录的制作

设计目的：用〈〈数据结构〉〉中的双向链表作数据结构。编写一个手机通讯录管理系统。以把所学数据结构知识应用到实际软件开发中去。 设计内容：本系统应完成一下几方面的功能： （1）. 添加信息

（2）. 显示信息：它可以按按固定电话排列、按手机、联系人名字的拼音顺序排列。 （3）. 查找：可以不同的关键字作为查找的依据，进行查找; （4）. 编辑信息 （5）. 删除信息

（6）. 保存到文件：将以上信息保存到文件，以便下次运行程序时能载入此通信录 设计要求：

（1）. 每条信息至包含 ：姓名（NAME ）,手机号，固定电话号，电子邮箱，QQ号码，城

市（CITY）邮编（EIP）几项

（2）. 作为一个完整的系统，应具有友好的界面和较强的容错能力 （3）. 上机能正常运行，并写出课程设计报告

26 奇数阶幻方求解

要求必须在空间复杂度为O(N)的要求下实现N阶幻方的输出。 Problem description

幻方是一种很有意思的数字矩阵，在很早著名的九宫八卦阵就与幻方有关。 幻方的定义为：

1 到 N*N 的整数填入N*N的方格中，每行和每列以及对角线的数字之和必须是相等的。 你作为八卦公司的顶级程序员，现在需要你解决一个问题，将任意奇数阶的幻方找出来。 Input

输入包括多个测试集，每行为一个正奇数N(1 <= N < 1000)，0作为输入的结束且不需要处理。

28

Output

对于输入的每一个N， 输出一个它所对应的N阶幻方，如果存在多个，任意一个即可。 每个幻方为N*N的矩阵，

对于每个幻方，每行输出幻方的一行，每行中的数字之间用一个或多个空格分开。不同的幻方之间用一个空行分开。

Sample Input 1 3 0

Sample Output 1

27 算术表达式与二叉树

【问题描述】

一个表达式和一棵二叉树之间，存在着自然的对应关系。写一个程序，实现基于二叉树表示的算术表达式的操作。 【任务要求】

假设算术表达式Expression内可以含有变量（a～z）、常量（0～9）和二元运算符（+，-，*，/，^(乘幂)）。实现以下操作：

1) ReadExpre(E)—以字符序列的形式输入语法正确的前缀表达式并构造表达式E。 2) WriteExpre(E)—用带括弧的中缀表达式输出表达式E。 3) Assign(V,c)—实现对变量V的赋值（V=c），变量的初值为0。 4) Value(E)—对算术表达式E求值。

5) CompoundExpr（P，E1，E2）--构造一个新的复合表达式（E1）P（E2） 【测试数据】

1) 分别输入0；a；-91；+a*bc；+*5^x2*8x；+++*3^x3*2^x2x6并输出。 2) 每当输入一个表达式后，对其中的变量赋值，然后对表达式求值。

28 内部排序算法比较

【问题描述】

在教科书中，各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机数据比较各种算法的关键字比较次数和关键字移动次数，以取得直观感受。

29

【任务要求】

1) 对以下7种常用的内部排序算法进行比较：冒泡排序、直接插入排序、简单选择排

序、希尔排序、堆排序、归并排序、快速排序。

2) 待排序表的表长不小于100；其中的数据要用伪随机数程序产生；至少要用5组不

同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字的移动次数（关键字交换计为3次移动）。

3) 最后要对结果作出简单分析，包括对各组数据得出结果波动大小的解释。 【测试数据】

由随机数产生器生成

29 动态查找表

【问题描述】

利用二叉排序树完成动态查找表的建立、指定关键字的查找、插入与删除指定关键字结点。

【任务要求】

算法输入：指定一组数据。

算法输出：显示二叉排序树的中序遍历结果、查找成功与否的信息、插入和删除后的中序遍历结果(排序结果)。

算法要点：二叉排序树建立方法、动态查找方法,对树进行中序遍历。 【测试数据】

自行设定，注意边界等特殊情况。

30 joseph环

【问题描述】

编号是1，2，……,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。

【任务要求】

利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。

测试数据： m的初值为20，n=7 ,7个人的密码依次为3，1，7，2，4，7，4，首先m=6,则正确的输出是什么？ 要求：

输入数据：建立输入处理输入数据，输入m的初值，n ，输入每个人的密码，建立单循环链表。

输出形式：建立一个输出函数，将正确的输出序列 【测试数据】

自行设定，注意边界等特殊情况。

30

31 哈希表应用

【问题描述】

利用哈希表进行存储。 【任务要求】

任务要求：针对一组数据进行初始化哈希表，可以进行显示哈希表，查找元素，插入元素，删除元素，退出程序操作。

设计思想：哈希函数用除留余数法构造，用线性探测再散列处理冲突。 设计目的：实现哈希表的综合操作

简体中文控制台界面：用户可以进行创建哈希表，显示哈希表，查找元素，插入元素，删除元素。

显示元素：显示已经创建的哈希表。

查找元素：查找哈希表中的元素，分为查找成功和查找不成功。 插入元素：在哈希表中，插入一个元素，分为插入成功和失败。 删除元素：在已有的数据中，删除一个元素。 退出系统：退出程序。 【测试数据】

自行设定，注意边界等特殊情况。

32 商品货架管理

[问题描述]

商品货架可以看成一个栈，栈顶商品的生产日期最早，栈底商品的生产日期最近。 上货时，需要倒货架，以保证生产日期较近的商品在较下的位置。 [基本要求]

针对一种特定商品，实现上述管理过程。 [实现提示]

用栈模拟货架和周转空间。 [测试数据]

由学生依据软件工程的测试技术自己确定。注意测试边界数据，如空栈。

33 停车场管理

[问题描述]

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

31

[测试数据]

设n=2,输入数据为：（‘A’，1，5），（‘A’，2，10），（‘D’，1，15），（‘A’，3， 20）， （‘A’，4，25），（‘A’，5，30），（‘D’，2，35），（‘D’，4，40），（‘E’，0，0）。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，其中，‘A’表示到达；‘D’表示离去，‘E’表示输入结束。 [基本要求]

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

[实现提示]

需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。

34 稀疏矩阵的完全链表表示及其运算

[问题描述]

稀疏矩阵的每个结点包含down，right，row，col和value五个域。用单独一个结点表示一个非零项，并将所有结点连接在一起，形成两个循环链表。使得第一个表即行表，把所有结点按照行序（同一行内按列序）用right域链接起来。使得第二个表即列表，把所有结点按照列序（同一列内按行序）用down链接起来。这两个表共用一个头结点。另外，增加一个包含矩阵维数的结点。稀疏矩阵的这种存储表示称为完全链表表式。

实现一个完全链表系统进行稀疏矩阵运算，并分析下列操作函数的计算时间和额外存储空间的开销。

（2）设计目的

认识和掌握稀疏矩阵的完全链表表示；能够建立并运用这种存储结构 (3) 基本要求

建立一个用户友好、菜单式系统进行下列操作，并使用合当的测试数据测试该系统。 读取一个稀疏矩阵建立其完全链表表示 输出一个稀疏矩阵的内容 删除一个稀疏矩阵 两个稀疏矩阵相加 两个稀疏矩阵相减 两个稀疏矩阵相乘 稀疏矩阵的转置 （4）实现提示 链表上的操作。

35 电视大赛观众投票及排名系统（排序应用）

32

【问题描述】

在很多的电视大赛中，通常当选手表演结束后，现场观众通过手中的按键对参赛选手进行投票，然后对选手获得的票数进行统计，从高到低进行降序排序，从而自动产生冠军、亚军和季军。现在要求编写一程序模拟实现上述系统的功能。 【实现提示】

在本例中，首先输入参赛选手的人数（范围为1-9个），然后根据人数通过malloc函数来开辟存放选手信息的顺序表。将选手的编号和姓名依此存入顺序表单元中，观众通过按键进行投票，按’1’为1号选手投票，按’2’为2号选手投票，以此类推，以按’0’作为投票结束标志。投票结束后进行排序，在此采用希尔排序，然后为每个选手计算名次，得票相同的名次也相同，

（1）存储类型的定义

参赛选手信息存储类型的定义： typedef struct node{

char name[8]; /*选手姓名*/ int num; /*选手编号*/ int score; /*选手得分*/ int tax; /*选手名次*/ }Node;

36 学生搭配问题。

一班有m个女生,有n个男生（m不等于n），现要开一个舞会。男女生分别编号坐在舞池的两边的椅子上。每曲开始时，依次从男生和女生中各出一人配对跳舞，本曲没成功配对者坐着等待下一曲找舞伴。

请设计一系统模拟动态地显示出上述过程，要求如下： （1）输出每曲配对情况；

（2）计算出任何一个男生（编号为X）和任意女生（编号为Y），在第K曲配对跳舞的情况.至少求出K的两个值；

（3） 尽量设计出多种算法及程序。 提示：用队列来解决比较方便.

37 敢死队问题

有M个敢死队员要炸掉敌人的一碉堡，谁都不想去，排长决定用轮回数数的办法来决定哪个战士去执行任务。如果前一个战士没完成任务，则要再派一个战士上去。现给每个战士编一个号，大家围坐成一圈，随便从某一个战士开始计数，当数到5时，对应的战士就去执行任务，且此战士不再参加下一轮计数。如果此战士没完成任务，再从下一个战士开始数数，被数到第5时，此战士接着去执行任务。以此类推，直到任务完成为止。

排长是不愿意去的，假设排长为1号，请你设计一程序，求出从第几号战士开始计数才能让排长最后一个留下来而不去执行任务。

要求：至少采用两种不同的数据结构的方法实现。

33

38 数制转换问题

任意给定一个M进制的数x ，请实现如下要求 : 1) 求出此数x的10进制值（用MD表示）

2) 实现对x向任意的一个非M进制的数的转换。

3) 至少用两种或两种以上的方法实现上述要求（用栈解决，用数组解决，其它方法解决）。

39迷宫问题（栈）

以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 要求：

首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i,j,d）的形式输出，其中：（i,j）指示迷宫中的一个坐标，d表示走到下一坐标的方向，如：对于下列数据的迷宫，输出的一条通路为：（1，1，1），（1,2,2）,(3,2,3),(3,1,2),?。 测试数据：

迷宫的测试数据如下：左下角（1，1）为入口，右下角（8，9）为出口。 实现提示：

计算机解迷宫通常用的是“穷举求解”方法，即从入口出发，顺着某个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设的迷宫没有通路。 可以二维数组存储迷宫数据，通常设定入口点的下标为（1，1），出口点的下标为（n,n）。为处理方便起见，可在迷宫的四周加一圈障碍。对于迷宫中任一位置，均可约定有东、南、西、北四个方向可通。 选做内容：（1）编写递归形式的算法，求得迷宫中所有可能的通路；（2）以方阵形式输出迷宫及其通路。

40 迷宫问题（队列）（同上）

以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 要求：

首先实现一个以链表作存储结构的队列，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i,j,d）的形式输出，其中：（i,j）指示迷宫中的一个坐标，d表示走到下一坐标的方向，如：对于下列数据的迷宫，输出的一条通路为：（1，1，1），（1,2,2）,(3,2,3),(3,1,2),?。 测试数据：

迷宫的测试数据如下：左下角（1，1）为入口，右下角（8，9）为出口。 实现提示：

计算机解迷宫通常用的是“穷举求解”方法，即从入口出发，顺着某个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设的迷宫没有通路。 可以二维数组存储迷宫数据，通常设定入口点的下标为（1，1），出口点的下标为（n,n）。为处理方便起见，可在迷宫的四周加一圈障碍。对于迷宫中任一位置，均可约定有东、南、

34

西、北四个方向可通。 选做内容：

（1）编写递归形式的算法，求得迷宫中所有可能的通路； （2）以方阵形式输出迷宫及其通路。

41 最短路

【问题描述】 给定一个计算机网络以及机器间的双向连线列表，每一条连线允许两端的计算机进行直接的文件传输，其他计算机间若存在一条连通路径，也可以进行间接的文件传输。请写出程序判断：任意指定两台计算机，它们之间是否可以进行文件传输？

【输入要求】 输入若干测试数据组成。对于每一组测试，第1行包含一个整数N（≤10000），即网络中计算机的总台数，因而每台计算机可用1到N之间的一个正整数表示。接下来的几行输入格式为I C1 C2或者 C或者C C1C2或者S，其中C1和C2是两台计算机的序号，I表示在C1和C2间输入一条连线，C表示检查C1和C2间是否可以传输文件，S表示该组测试结束。当N为0时，表示全部测试结束，不要对该数据做任何处理。 【输出要求】 1 5 4 2 3 9 8 7 6 500m 200m 200m 100m 200m 50m 100m 500m 700m 100m 100m

对每一组C开头的测试，检查C1和C2间是否可以传输文件，若可以，则在一行中输出“yes”，否则输出“no”。当读到S时，检查整个网络。若网络中任意两机器间都可以传输文件，则在一行中输出“The network is connected.”，否则输出“There are k components.”,其中k是网络中连通集的个数。两组测试数据之间请输出一空行分隔。

42 拦截导弹

问题描述

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

输入格式

一行，为导弹依次飞来的高度

输出格式

两行，分别是最多能拦截的导弹数与要拦截所有导弹最少要配备的系统数

样例输入

389 207 155 300 299 170 158 65

样例输出

6 2

43 二叉搜索树

35

判断两序列是否为同一个二叉搜索树序列

要求：输入：开始一个数n，(1<=n<=20) 表示有n个序列需要判断，n= 0 的时候输入结束。接下去一行是一个序列，序列长度小于10，包含(0~9)的数字，没有重复数字，根据这个序列可以构造出一颗二叉搜索树。接下去的n行有n个序列，每个序列格式跟第一个序列一样，请判断这两个序列是否能组成同一颗二叉搜索树。

输出：如果序列相同则输出YES，否则输出NO Sample Input 2

567432 543267 576342 0

Sample Output YES NO

44 会议中心

会议中心 Siruseri政府建造了一座新的会议中心。许多公司对租借会议中心的会堂很感兴趣，他们希望能够在里面举行会议。

对于一个客户而言，仅当在开会时能够独自占用整个会堂，他才会租借会堂。会议中心的销售主管认为：最好的策略应该是将会堂租借给尽可能多的客户。显然，有可能存在不止一种满足要求的策略。

例如下面的例子。总共有4个公司。他们对租借会堂发出了请求，并提出了他们所需占用会堂的起止日期（如下表所示）。

开始日期 结束日期 公司1 4 9 公司2 9 11 公司3 13 19 公司4 10 17

上例中，最多将会堂租借给两家公司。租借策略分别是租给公司1和公司3，或是公司2和公司3，也可以是公司1和公司4。注意会议中心一天最多租借给一个公司，所以公司1和公司2不能同时租借会议中心，因为他们在第九天重合了。

销售主管为了公平起见，决定按照如下的程序来确定选择何种租借策略：首先，将租借给客户数量最多的策略作为候选，将所有的公司按照他们发出请求的顺序编号。对于候选策略，将策略中的每家公司的编号按升序排列。最后，选出其中字典序最小[1]的候选策略作为最终的策略。

例中，会堂最终将被租借给公司1和公司3：3个候选策略是{(1,3),(2,3),(1,4)}。而在字典序中(1,3)<(1,4)<(2,3)。

你的任务是帮助销售主管确定应该将会堂租借给哪些公司。

输入格式

输入的第一行有一个整数N，表示发出租借会堂申请的公司的个数。第2到第N+1行每

36

行有2个整数。第i+1行的整数表示第i家公司申请租借的起始和终止日期。对于每个公司

9

的申请，起始日期为不小于1的整数，终止日期为不大于10的整数。

输出格式

输出的第一行应有一个整数M，表示最多可以租借给多少家公司。第二行应列出M个数，表示最终将会堂租借给哪些公司。

数据规模和约定

对于50%的输入，N≤3000。在所有输入中，N≤200000。

样例输入

4 4 9 9 11 13 19 10 17

样例输出

2 1 3

[1] 字典序指在字典中排列的顺序，如果序列l1是序列l2的前缀，或者对于l1和l2的第一个不同位置j，l1[j]

45 串数

一个A和两个B一共可以组成三种字符串:\给定若干字母和它们相应的个数,计算一共可以组成多少个不同的字符串.

要求：输入：每组测试数据分两行,第一行为n(1<=n<=26),表示不同字母的个数,第二行为n个数A1,A2,...,An(1<=Ai<=12),表示每种字母的个数.测试数据以n=0为结束. 输出：对于每一组测试数据,输出一个m,表示一共有多少种字符串. Sample Input 2 1 2 3

2 2 2 0

Sample Output 3 90

46 树的应用

要实现树与二叉树的转换的实现。以及树的前序、后序的递归、非递归算法，层次序的非递归算法的实现，应包含建树的实现。

47 求先序排列

37

问题描述

给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，长度<=8）。

输入格式

两行，每行一个字符串，分别表示中序和后序排列

输出格式

一个字符串，表示所求先序排列

样例输入

BADC BDCA

样例输出

ABCD

48 大臣的旅费

问题描述

很久以前，T王国空前繁荣。为了更好地管理国家，王国修建了大量的快速路，用于连接首都和王国内的各大城市。

为节省经费，T国的大臣们经过思考，制定了一套优秀的修建方案，使得任何一个大城市都能从首都直接或者通过其他大城市间接到达。同时，如果不重复经过大城市，从首都到达每个大城市的方案都是唯一的。

J是T国重要大臣，他巡查于各大城市之间，体察民情。所以，从一个城市马不停蹄地到另一个城市成了J最常做的事情。他有一个钱袋，用于存放往来城市间的路费。

聪明的J发现，如果不在某个城市停下来修整，在连续行进过程中，他所花的路费与他已走过的距离有关，在走第x千米到第x+1千米这一千米中（x是整数），他花费的路费是x+10这么多。也就是说走1千米花费11，走2千米要花费23。

J大臣想知道：他从某一个城市出发，中间不休息，到达另一个城市，所有可能花费的路费中最多是多少呢？

输入格式

输入的第一行包含一个整数n，表示包括首都在内的T王国的城市数 城市从1开始依次编号，1号城市为首都。

接下来n-1行，描述T国的高速路（T国的高速路一定是n-1条）

每行三个整数Pi, Qi, Di，表示城市Pi和城市Qi之间有一条高速路，长度为Di千米。

输出格式

输出一个整数，表示大臣J最多花费的路费是多少。

样例输入1

5 1 2 2 1 3 1 2 4 5 2 5 4

样例输出1

135

输出格式

38

大臣J从城市4到城市5要花费135的路费。

49 小朋友排队

问题描述

n 个小朋友站成一排。现在要把他们按身高从低到高的顺序排列，但是每次只能交换位置相邻的两个小朋友。

每个小朋友都有一个不高兴的程度。开始的时候，所有小朋友的不高兴程度都是0。

如果某个小朋友第一次被要求交换，则他的不高兴程度增加1，如果第二次要求他交换，则他的不高兴程度增加2（即不高兴程度为3），依次类推。当要求某个小朋友第k次交换时，他的不高兴程度增加k。

请问，要让所有小朋友按从低到高排队，他们的不高兴程度之和最小是多少。

如果有两个小朋友身高一样，则他们谁站在谁前面是没有关系的。

输入格式

输入的第一行包含一个整数n，表示小朋友的个数。

第二行包含 n 个整数 H1 H2 ? Hn，分别表示每个小朋友的身高。

输出格式

输出一行，包含一个整数，表示小朋友的不高兴程度和的最小值。

样例输入

3 3 2 1

样例输出

9

样例说明

首先交换身高为3和2的小朋友，再交换身高为3和1的小朋友，再交换身高为2和1的小朋友，每个小朋友的不高兴程度都是3，总和为9。

50 接水问题

问题描述

学校里有一个水房，水房里一共装有m 个龙头可供同学们打开水，每个龙头每秒钟的 供水量相等，均为1。 现在有n 名同学准备接水，他们的初始接水顺序已经确定。将这些同学按接水顺序从1 到n 编号，i 号同学的接水量为wi。接水开始时，1 到m 号同学各占一个水龙头，并同时打 开水龙头接水。当其中某名同学j 完成其接水量要求wj 后，下一名排队等候接水的同学k 马上接替j 同学的位置开始接水。这个换人的过程是瞬间完成的，且没有任何水的浪费。即 j 同学第x 秒结束时完成接水，则k 同学第x+1 秒立刻开始接水。若当前接水人数n’不足m， 则只有n’个龙头供水，其它m?n’个龙头关闭。 现在给出n 名同学的接水量，按照上述接水规则，问所有同学都接完水需要多少秒。

输入格式

第1 行2 个整数n 和m，用一个空格隔开，分别表示接水人数和龙头个数。 第2 行n 个整数w1、w2、??、wn，每两个整数之间用一个空格隔开，wi 表示i 号同 学的接水量。

39

输出格式

输出只有一行，1 个整数，表示接水所需的总时间。

样例输入

5 3

4 4 1 2 1

样例输出

4

样例输入

8 4

23 71 87 32 70 93 80 76

样例输出

163

输入输出样例 1 说明

第1 秒，3 人接水。第1 秒结束时，1、2、3 号同学每人的已接水量为1，3 号同学接完

水，4 号同学接替3 号同学开始接水。

第2 秒，3 人接水。第2 秒结束时，1、2 号同学每人的已接水量为2，4 号同学的已接

水量为1。

第3 秒，3 人接水。第3 秒结束时，1、2 号同学每人的已接水量为3，4 号同学的已接

水量为2。4 号同学接完水，5 号同学接替4 号同学开始接水。

第4 秒，3 人接水。第4 秒结束时，1、2 号同学每人的已接水量为4，5 号同学的已接

水量为1。1、2、5 号同学接完水，即所有人完成接水。 总接水时间为4 秒。

40

本文来源：https://www.bwwdw.com/article/lx03.html