数据结构课程设计题目-2017.doc

题目：以下21个题目任选其一,标明限选1人的题目只能有一个人选做，未特别标注的题目可以2个人选同一题目，但是要求题目相同的同学独立完成自己选作的题目。1. Joseph环（限选1人）问题描述编号是1，2，,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。基本要求利用单线性表的顺序和链式两种存储结构模拟此过程，按照出列的顺序输出各个人的编号。其中要求顺序表的删除不移动数据元素。测试数据：m的初值为20，n=7 ,7个人的密码依次为3，1，7，2，4，7，42.运动会分数统计问题描述参加运动会有n个学校，学校编号为1n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1m，女子m+1m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。（m=20,n20）个学生的m(m3)门考试的成绩表，每个学生的信息由学号、姓名以及各科成绩组成。对学生的考试成绩进行有关统计，并打印统计表。（由于学生人数和成绩每次输入内容较多，建议采用文件的形式存储n个学生的成绩表）基本要求程序运行时显示一个简单的菜单，例如：（1）信息输入（INPUT）：对n个学生的信息进行输入；建议存入文件。 （2）总分统计（COUNT）：统计出每个学生的总分。 （3）总分排序（SORT）：按总数高低次序，打印出名次表，分数相同的为同一名次； （4）查询(QUERY）：给出至少2种查询方式。如按学号查询，输入一个学号后，显示出该学生的有关信息。（5）列表显示（LIST）：给出两种列表显示方式，按学号排列显示和按名次显示。按名次打印出每个学生的学号、姓名、总分以及各科成绩。15.活期储蓄帐目管理【问题描述】 活期储蓄处理中，储户开户、销户、存入、支出活动频繁。设计一个活期储蓄账目管理系统。【基本要求】1) 能比较迅速地找到储户的帐户，以实现存款、取款记账；2) 能比较简单，迅速地实现插入和删除，以实现开户和销户的需要。16.家谱管理系统 【问题描述】实现具有下列功能的家谱管理系统1). 输入文件以存放最初家谱中各成员的信息，成员的信息中均应包含以下内容：姓名、出生日期、婚否、地址、健在否、死亡日期（若其已死亡），也可附加其它信息、但不是必需的。2). 实现数据的存盘和读盘。3). 显示家谱。4). 按照出生日期查询成员名单。5). 按照姓名查询，输出成员信息（包括其本人、父亲、孩子的信息）。6). 修改某成员信息。7).打开一家谱时，提示当天生日的健在成员。【基本要求】建立至少20个成员的数据，以较为直观的方式显示结果，并提供文稿形式以便检查。界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。存储结构：学生自己根据系统功能要求自己设计，但是要求相关数据要存储在数据文件中。测试数据：要求使用1、全部合法数据；2、局部非法数据。进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明；17. 迷宫问题【问题描述】迷宫实验是取自心理学的一个古典实验。在该实验中，把一只老鼠从一个无顶大盒子的门放入，在盒中设置了许多墙，对行进方向形成了多处阻挡。盒子仅有一个出口，在出口处放置一块奶酪，吸引老鼠在迷宫中寻找道路以到达出口。对同一只老鼠重复进行上述实验，一直到老鼠从入口到出口，而不走错一步。老鼠经多次实验终于得到它学习走迷宫的路线。设计一个计算机程序对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。【实现提示】可以利用一个二维数组mazeij表示迷宫，其中1=i=m,1=j=n,m和n分别代表迷宫的行数和列数。 数组元素值为1表示该位置是墙壁，不能通行；元素值为0表示该位置是通路。假定从maze11出发，出口位于mazemn，移动方向可以是8个方向（东、东南、南、西南、西、西北、北和东北）。计算机解迷宫时，通常用的是“穷举求解”的方法，即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止。为了保证在任何位置上都能沿原路退回，需要用一个后进先出的栈结构来保存从入口到当前位置的路径。18. 双层停车场管理（限选1人） 【问题描述】有一个两层的停车场，每层有 6 个车位，当第一层车停满后才允许使用第二层。(停车 场可用一个二维数组实现， 每个数组元素存放一个车牌号)每辆车的信息包括车牌号， 层号， 车位号，停车时间共 4 项。其中停车时间按分钟计算。 【基本要求】（1）假设停车场初始状态为第一层已经停有 4 辆车，其车位号依次为 14，停车时间依次 为 20，15，10，5。即先将这四辆车的信息存入文件“car.dat”中( 数组的对应元素也要 进行赋值 ) （2）停车操作：当一辆车进入停车场时，先输入其车牌号，再为它分配一个层号和一个车 位号(分配前先查询车位的使用情况， 如果第一层有空则必须停在第一层)， 停车时间设为 5， 最后将新停入的汽车的信息添加文件“car.dat”中，并将在此之前的所有车的停车时间加 5。 （2）收费管理(取车)：当有车离开时，输入其车牌号，先按其停车时间计算费用，每 5 分 钟 0.2 元。(停车费用可设置一个变量进行保存)，同时从文件“car.dat”中删除该车的信 息， 并将该车对应的车位设置为可使用状态(即二维数组对应元素清零)。 按用户的选择来判 断是否要输出停车收费的总计。 （4）输出停车场中全部车辆的信息。 （5）退出系统。19. 仓库管理系统（限选1人）【问题描述】建立一个仓库管理程序，可以按顺序和货物名称查询仓库存储情况，也可以增加或删除货物信息、实现货物的入库出库，要求能用文件保存仓库货品信息。【基本要求】1） 记录货物编号，货物名称，货物数量。2） 能够实现按货物编号、按货物名称查询仓库中货物的库存情况。3） 能够实现货物入库、出库，并及时更新库存数量。20. 敢死队问题（限选1人）【问题描述】 有M个敢死队员要炸掉敌人的一碉堡，谁都不想去，排长决定用轮回数数的办法来决定哪个战士去执行任务。如果前一个战士没完成任务，则要再派一个战士上去。现给每个战士编一个号，大家围坐成一圈，随便从某一个战士开始计数，当数到5时，对应的战士就去执行任务，且此战士不再参加下一轮计数。如果此战士没完成任务，再从下一个战士开始数数，被数到第5时，此战士接着去执行任务。以此类推，直到任务完成为止。 排长是不愿意去的，假设排长为1号，请你设计一程序，求出从第几号战士开始计数才能让排长最后一个留下来而不去执行任务。【基本要求】至少采用两种不同的数据结构的方法实现。21. 学生搭配问题（限选1人）【问题描述】一班有m个女生,有n个男生(m不等于n),现要开一个舞会. 男女生分别编号坐在舞池的两边的椅子上.每曲开始时,依次从男生和女生中各出一人配对跳舞, 本曲没成功配对者坐着等待下一曲找舞伴.【基本要求】 请设计一系统模拟动态地显示出上述过程,要求如下:1) 输出每曲配对情况，男女生要有编号和姓名。2) 计算出任何一个男生(编号为X)和任意女生(编号为Y),在第K曲配对跳舞的情况.至少求出K的两个值.3) 尽量设计出多种算法及程序,可视情况适当加分提示:用队列来解决比较方便.要求：在做课程设计时，要求按下列步骤实施：1问题分析 根据设计题目的要求，充分地分析和理解问题，弄清问题要求什么，包括功能要求，性能要求和约束，以及基本数据特性，数据间的联系等。2数据结构与算法设计 针对要解决的问题，考虑各种可能的数据结构，并且力求从中选出最佳方案（必须连同算法实现一起考虑），确定主要的数据结构及全程变量，对引入的每种数据结构和全程变量要详细说明其功用、初值和操作特点。 算法设计分概要设计和详细设计。概要设计着重解决程序的模块设计问题。这包括考虑如何把被开发的问题自顶向下分解成若干模块，并决定模块间的接口，即模块间的相互关系以及模块之间的信息交换问题。详细设计则要决定每个模块内部的具体算法，包括输入、处理和输出，可用伪码描述，在此过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，不必过早陷入语言细节。3程序编码。把详细设计的结果进一步求精为程序设计语言程序。此时，要考虑语言的细节，加入必要的注解，使程序中逻辑概念清楚。4测试用例设计准备典型测试数据和调试方案。测试数据要有代表性、敏感性。测试方案包括模块测试和模块集成测试。5静态检查在上机之前，认真的静态检查是必不可少的。静态检查主要有两种方法，一是用一组测试数据手工执行程序；二是通过阅读或给别人讲解自己的程序而深入全面地理解程序逻辑。 6程序调试与测试。采用自底向上，分模块进行，即先调试低层函数。能够熟练掌握调试工具的各种功能，设计测试数据确定疑点，通过修改程序来证实它或绕过它。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果。 7结果分析。程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法的时间、空间复杂性分析。课程设计报告由封面（统一给）和正文组成。封面：包括实验环节名称、学号、姓名、班级、指导教师、完成日期。正文：应包括以下几部分内容：（1）问题描述：描述要求编程解决的问题。（2）基本要求：给出程序要达到的具体的要求。（3） 测试数据：设计测试数据，或具体给出测试数据。要求测试数据能全面地测试所设计程序的功能。（4）算法思想：描述解决相应问题算法的设计思想。（5）模块划分：描述所设计程序的各个模块（即函数）功能。（