题目一运动会分数统计 1
题目二约瑟夫环 2
题目三停车场管理 3
题目四一元稀疏多项式计算器 4
题目五离散事件模拟 5
题目六魔王语言解释 6
题目七马踏棋盘 7
题目八迷宫问题 8
题目九校园导游咨询 9
题目十全国交通咨询模拟 10
题目十一最小生成树问题 11
题目十二文学研究助手 12
一、 实验目的:
1) 熟练掌握线性表的两种存储方式。
2) 掌握链表的操作和应用。
3) 掌握指针、结构体的应用。
4)按照不同的学校,不同项目和不同的名次要求,产生各学校的成绩单、团体总分报表。
二、实验内容:
问题描述】参加运动会的n个学校编号为1~n。比赛分成m个男子项目和w个女子项目,项目编号分别为1~m和m+1~m+w。由于各项目参加人数差别较大,有些项目取前五名,得分顺序为7,5,3,2,1;还有些项目只取前三名,得分顺序为5,3,2。
写一个统计程序产生各种成绩单和得分报表。
基本要求】产生各学校的成绩单,内容包括各校所取得的每项成绩的项目号、名次(成绩)、姓名和得分;产生团体总分报表,内容包括校号、男子团体总分、女子团体总分和团体总分。
测试数据】对于n=4,m=3,w=2,编号为奇数的项目取前五名,编号为偶数的项目取前三名,设计一组实例数据。
实现提示】可以假设m≤20,m≤30,w≤20,姓名长度不超过20个字符。每个项目结束时,将其编号、类型符(区分取前五名还是前三名)输入,并按名次顺序输入运动员姓名、校名(和成绩)。
选作内容】允许用户指定某些项目可采取其他名次取法。
一、 实验目的:
1) 熟练线性表链式存储表示。
2) 掌握单向循环链表的基本操作。
3) 采用单向循环链表存储结构模拟约瑟夫环的过程,按照出列的顺序印出各人的编号。
二、 实验内容:
问题描述】约瑟夫(joseph)问题的一种描述是:编号为1,2,…,n的n个人按顺时针方向围坐一圈,每人持有一个密码(正整数)。一开始任选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始顺序报数,报到m时停止报数。
报m的人出列,将他的密码作为新的m值,从他在顺时针方向上的下一个人开始重新从1报数,如此下去,直至所有人全部出列为止。试设计一个程序求出出列顺序。
基本要求】利用单向循环链表存储结构或顺序存储结构模拟此过程,按照出列的顺序印出各人的编号。
测试数据】m的初值为20;n=7,7个人的密码依次为:3,1,7,2,4,8,4,首先m值为6(正确的出列顺序应为6,1,4,7,2,3,5)。
实现提示】程序运行后,道德要求用户指定初始报数上限值,然后读取各人的密码。可n≤30。此题所用的循环链表中不需要“头结点”,请注意空表和非空表的界限。
选作内容】向上述程序中添加在顺序结构上实现的部分。
一、 实验目的:
1) 熟练掌握栈顺存和链存两种存储方式。
2) 掌握栈的基本操作及应用。
3) 以栈模拟停车场,以队列模拟车场外的便道,按照从终端读入的输入数据序列进行模拟管理。
二、实验内容:
问题描述】设停车场是一个可停放n辆汽车的长通道,且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序,依次由北向南排列(大门在最南端,最先到达的第一辆车信放在车场的最北端),若车场内已停满n辆汽车,则后来的汽车只能在门外的便道上等候,一旦有车开走,则排在便道上的第一辆车即可开入;当停车场内某辆车要离开时,在它之后进入的车辆必须先退出车场为它让路,待该辆车开出大门外,其他车辆再按原次序进入车场院,每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。
基本要求】以栈模拟停车场,以队列模拟车场外的便道,按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项:汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。
对每一组输入数据进行操作后的输出信息为:若是车辆到达,则输出汽车在停车场内或便道上的停车位置;若是车辆离去,则输出汽车在停车场内停留的时间和应交纳的费用(在便道上停留的时间不收费)。栈以顺序结构实现,队列以链表结构实现。
测试数据】设n=2,输入数据为:(a,1,5),(a,1,15),(a,3,20),(a,4,25),(a,5,30),(d,2,35),(d,4,40),(e,0,0)。其中:
a表示到达(arrival);d表示离去(departure);e表示输入结束(end)。
实现提示】需另设一个栈,临时停放为给要离去的汽车让路而从停车场退出来的汽车,也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车,包含两个数据项:
汽车的牌照号码和进入停车场的时刻。
选作内容】1) 两个栈共享空间,思考应开辟数组的空间是多少?
2) 汽车可有不同种类,则他们的占地面积不同收费标准也不同,如1辆客车和1。5辆小汽车的占地面积相同,1辆十轮卡车占地面积相当于3辆小汽车的占地面积。
3) 汽车可以直接从便道开走,此时排在它前面的汽车要先开走让路,然后再依次排到队尾。
4) 停放在便道上的汽车也收费,收费标准比停放在停车场的车低,请思考如何修改结构以满足这种要求。
一、 实验目的:
1) 熟练掌握线性表链式存储。
2) 掌握有序链表的操作及应用。
3) 利用带表头结点的单链表存储多项式,设计一个一元稀疏多项式简单计算器实现多项式的加减运算。
二、实验内容:
问题描述】设计一个一元稀疏多项式简单计算器。
基本要求】一元稀疏多项式简单计算器的基本功能是:
1) 输入并建立多项式;
2) 输出多项式,输出形式为整数序列:n,c1,e1,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.1x11+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和b相乘,建立乘积多项式ab。
3) 多项式的输出形式为类数学表达式。例如,多项式-3x8+6x3-18的输出形式为-3x^8+6x^3-18,x15+(-8)x7-14的输出形式为x^15-8x^7-14。注意,系数值为1的非零次项的输出形式中略去系数1,如项1x8的输出形式为x8,项-x3的输出形式为-x3。
4) 计算器的**界面。
一、 实验目的:
1) 熟练掌握队列的两种存储方式。
2) 掌握队列的基本操作及应用。
3) 利用链式存储线性表和队列实现银行业务模拟程序。
二、实验内容:
问题描述】客户业务分为两种。第一种是申请从银行得到一笔资金,即取款或借款。第二种是向银行投入一笔资金,即存款或还款。
银行有两个服务窗口,相应地有两个队列。客户到达银行后先排第一个队。处理每个客户业务时,如果属于第一种,且申请额超出银行现存资金总额而得不到满足,则立刻排入第二个队等候,直至满足时才离开银行;否则业务处理完后立刻离开银行。
每接待完一个第二种业务的客户,则顺序检查和处理(如果可能)第二个队列中的客户,对能满足的申请者予以满足,不能满足者重新排到第二个队列的队尾。注意,在此检查过程中,一旦银行资金总额少于或等于刚才第一个队列中最后一个客户(第二种业务)被接待之前的数额,或者本次已将第二个队列检查或处理了一遍,就停止检查(因为此时已不可能还有能满足者)转而继续接待第一个队列的客户。任何时刻都只开一个窗口。
假设检查不需要时间。营业时间结束时所有客户立即离开银行。
写一个上述银行业务的事件驱动模拟系统,通过模拟方法求出客户在银行内逗留的平均时间。
基本要求】利用动态存储结构实现模拟。
测试数据】一天营业开始时银行拥有的款额为10000(元),营业时间为600(分钟)。其他模拟参量自定,注意测定两种极端的情况:一是两个到达事件之间的间隔时间很短,而客户的交易时间很长,另一个恰好相反,设置两个到达事件的间隔时间很长,而客户的交易时间很短。
实现提示】事件有两类:到达银行和离开银行。初始时银行现存资金总额为total。
开始营业后的第一个事件是客户到达,营业时间从0到closetime。到达事件发生时随机地设置此客户的交易时间和距下一到达事件之间的时间间隔。每个客户要办理的款额也是随机确定的,用负值和正值分别表示第一类和第二类业务。
变量total, closetime以及上述两个随机量的上下界均交互地从终端读入,作为模拟参数。
两个队列和一个事件表均要用动态存储结构实现。注意弄清应该在什么条件下设置离开事件,以及第二个队列用怎样的存储结构实现时可以获得较高的效率。注意:事件表是按时间顺序有序的。
一、 实验目的:
1) 熟练掌握栈与队列的基本操作及应用。
2) 利用栈和队列的基本操作实现对魔王语言的翻译。
二、实验内容:
问题描述】有一个魔王总是使用自己的一种非常精练而抽象的语言讲话,没有人能听得懂,但他的语言是可以逐步解释**能听懂的语言因为他的语言是由以下两种形式的规则由人的语言逐步抽象上去的:
1)αβ1β2…βm
2)(θ1δ2…δn)θδnδn-1…θδ1θ
在这两种形式中,从左到右均表示解释。试写一个魔王语言折解释系统,把他的话解释**能听得懂的话。
基本要求】用下述两条具体规则和上述规则形式(2)实现。设大写字母表示魔王语言的词汇;小写字母表示人的语言词汇;希腊字母表示可以用大写字母或小写字母代换的变量。魔王语言可含人的词汇。
数据结构课程设计题目
题目1实现两个链表的合并。要求 编一程序将a表和b表归并成一个新的递增有序的单链表c 值相同的元素均保留在c表中 并要求利用原表的空间存放c。测试数据 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,8...
数据结构课程设计题目
题目1 图的遍历。功能 实现图的深度优先,广度优先遍历算法,并输出原图结构及遍历结果。分步实施 1 初步完成总体设计,搭好框架 2 完成最低要求 两种必须都要实现,写出画图的思路 3 进一步要求 画出图的结构,有兴趣的同学可以进一步改进图的效果。要求 1 界面友好,函数功能要划分好。2 总体设计应画...
数据结构课程设计题目
数据结构课程设计 题目与要求。一 实验学时 两周。二 要求 1 题目从以下题目中选择,完成程序设计及设计文档。2 程序的要求 实现的功能要求尽量完善。完善基本功能的基础上,再扩充其它功能。3 课程设计说明书的格式要求 a4纸打印,格式设置统。一 规范 美观。三 题目。1.运动会分数统计 限1 人完成...