2015课程设计题目

题目：以下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，4

2.运动会分数统计

[问题描述]

参加运动会有n个学校，学校编号为1„„n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1„„m，女子m+1„„m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。（m

[基本要求]

(1)可以输入各个项目的前三名或前五名的成绩；

(2)能统计各学校总分

(3)可以按学校编号、学校总分、男女团体总分排序输出；

(4)可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。

规定：输入数据形式和范围：20以内的整数（如果做得更好可以输入学校的名称，运动项目的名称）

输出形式：有中文提示，各学校分数为整形

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

存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。（数据文件的数据读写方法等相关内容在c语言程序设计的书上，请自学解决）请在最后的上交资料中指明你用到的存储结构；

测试数据：要求使用1、全部合法数据；2、整体非法数据；3、局部非法数据。进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明；

3.航空客运订票系统

[问题描述]

通过此系统可以实现如下功能：

录入：可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）

查询：可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；可以输入起飞抵达城市，查询飞机航班情况；

订票：（订票情况可以存在一个数据文件中，结构自己设定）可以订票，如果该航班已经无票，可以提供相关可选择航班；

退票： 可退票，退票后修改相关数据文件；

客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。

修改航班信息： 当航班信息改变可以修改航班数据文件

[基本要求]

根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能；

4.模拟旅馆管理系统的一个功能——床位的分配与回收

[问题描述]

某旅馆有n个等级的房间，第I等级有ai个房间，每个等级有bi个床位（1≤i≤n）。试模拟旅馆管理系统中床位分配和回收的功能，设计能为单个旅客分配床位，在其离店便回收床位（供下次分配）的算法。

[基本要求]

（1）输入数据

分配时，输入旅客姓名、年龄、性别、到达日期和所需房间等级。

回收时，输入房间等级、房间号和床位号。

（2）输出数据

分配成功时打印旅客姓名、年龄、到达日期、房间等级、房间号码和床位号码。

分配不成功时，如所有等级均无床位，则打印“客满”信息；如旅客需要的等级均无空床位，则打印“是否愿意更换等级？”的询问信息。若旅客愿意更换，则重新输入有关信息，再进行分配，否则分配工作结束。

5.停车场管理（限选1人）

[问题描述]

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

[测试数据]

设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’表示输入结束。

[基本要求]

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

6.校园导游程序

[问题描述]

用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。

[基本要求]

（1） 查询各景点的相关信息；

（2） 查询图中任意两个景点间的最短路径。

（3） 查询图中任意两个景点间的所有路径。

（4） 增加、删除、更新有关景点和道路的信息。

7.哈夫曼编/译码器（限选1人）

[问题描述]

打开一篇英文文章，统计该文章中每个字符出现的次数，然后以它们作为权值，设计一个哈夫曼编/译码系统。

[基本要求]

以每个字符出现的次数为权值，建立哈夫曼树，求出哈夫曼编码，对文件yuanwen中的正文进行编码，将结果存到文件yiwen中，再对文件yiwen中的代码进行译码，结果存到textfile中。

8.学生成绩管理系统（限选1人）

[问题描述]

编写一个简单的学生信息管理程序，能实现对学生信息的简单管理。

[基本要求]

建立一个4个学生的信息登记表，每个学生的信息包括：学号，姓名，和3门课程的成绩（FOX,C,ENGLISH）。

程序运行时显示一个简单的菜单，例如：

（1）信息输入（INPUT）

（2）总分统计（COUNT）

（3）总分排序（SORT）

（4）查询(QUERY）

其中：

（1）对4个学生的信息进行输入；

（2）对每个学生的3门课程统计总分；

(3)对4个学生的总分按降序排序并显示出来；

(4)查询输入一个学号后，显示出该学生的有关信息；

9.员工管理系统

[问题描述]

每个员工的信息包括：编号、姓名、性别、出生年月、学历、职务、电话、住址等。系统能够完成员工信息的查询、更新、插入、删除、排序等功能。

[基本要求]

（1） 排序：按不同关键字，对所有员工的信息进行排序。

（2） 查询：按特定条件查找员工。

（3） 更新：按编号对某个员工的某项信息进行修改。

（4） 插入：加入新员工的信息。

（5） 删除：按编号删除已离职的员工的信息。

10.商品货架管理（限选1人）

[问题描述]

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

[基本要求]

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

11.哈希表的设计与实现

[问题描述] 设计哈希表实现电话号码查询系统。

[基本要求]

1、设每个记录有下列数据项：电话号码、用户名、地址；

2、从键盘输入各记录，分别以电话号码和用户名为关键字建立哈希表；

3、采用再哈希法解决冲突；

4、查找并显示给定电话号码的记录；

5、查找并显示给定用户名的记录。

6、在哈希函数确定的前提下，尝试各种不同类型处理冲突的方法（至少两种），考察平均查找长度的变化。

12.通讯录管理系统

该系统至少应具有如下功能：

1．输入记录 要求随时都能使用该项功能实现记录的输入，一次可以输入一条记录，也可以输入多条记录。

2．输出 （1）按自然顺序输出

（2）按某种排序顺序输出。至少两种。

3．查询 至少提供两种查询方式。

4．修改 至少提供两种修改方式。

5．删除 既能一次删除一条记录，也能一次删除多条记录。

6．退出 通讯录管理结束后，正常退出系统。

要求：

1．每个记录至少包含如下信息：姓名、电话、所在城市、所在单位、年龄、E-mail、备注等。

2．以采单方式实现功能选择控制。

3．编写功能独立的函数实现各功能。

4．记录最大个数100。

13.内部排序算法比较（限选1人）

[问题描述]

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

[基本要求]

（1） 对以下几种常用的内部排序算法进行比较：直接插入排序；折半折入排序；希尔排序；起泡排序；快速排序；简单选择排序；堆排序；归并排序；基数排序。

（2）待排序表的表长不少于100；其中的数据要用伪随机数产生程序产生；至少要用5组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字移动次数（关键字交换计为3次移动）。

[测试数据]

由随机产生器决定。

14.统计成绩（限选1人）

[问题描述]

给出n个学生的m门考试的成绩表，每个学生的信息由学号、姓名以及各科成绩组成。对学生的考试成绩进行有关统计，并打印统计表。

[基本要求]

（1） 按总数高低次序，打印出名次表，分数相同的为同一名次；

（2） 按名次打印出每个学生的学号、姓名、总分以及各科成绩。

15.活期储蓄帐目管理

【问题描述】 活期储蓄处理中，储户开户、销户、存入、支出活动频繁。设计一个活期储蓄账目管理系统。

【基本要求】

1) 能比较迅速地找到储户的帐户，以实现存款、取款记账；

2) 能比较简单，迅速地实现插入和删除，以实现开户和销户的需要。

16.家谱管理系统

【问题描述】实现具有下列功能的家谱管理系统

1). 输入文件以存放最初家谱中各成员的信息，成员的信息中均应包含以下内容： 姓名、出生日期、婚否、地址、健在否、死亡日期（若其已死亡），也可附加其它信息、但不是必需的。

2). 实现数据的存盘和读盘。

3). 显示家谱。

4). 按照出生日期查询成员名单。

5). 按照姓名查询，输出成员信息（包括其本人、父亲、孩子的信息）。

6). 修改某成员信息。

7).打开一家谱时，提示当天生日的健在成员。

【基本要求】

建立至少20个成员的数据，以较为直观的方式显示结果，并提供文稿形式以便检查。

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

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

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

测试数据及测试结果请在上交的资料中写明；

17. 迷宫问题

【问题描述】

迷宫实验是取自心理学的一个古典实验。在该实验中，把一只老鼠从一个无顶大盒子的门放入，在盒中设置了许多墙，对行进方向形成了多处阻挡。盒子仅有一个出口，在出口处放置一块奶酪，吸引老鼠在迷宫中寻找道路以到达出口。对同一只老鼠重复进行上述实验，一直到老鼠从入口到出口，而不走错一步。老鼠经多次实验终于得到它学习走迷宫的路线。设计一个计算机程序对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。

【实现提示】

可以利用一个二维数组maze[i][j]表示迷宫，其中1

18. 双层停车场管理（限选1人）

【问题描述】

有一个两层的停车场，每层有 6 个车位，当第一层车停满后才允许使用第二层。 (停车 场可用一个二维数组实现， 每个数组元素存放一个车牌号)每辆车的信息包括车牌号， 层号， 车位号，停车时间共 4 项。其中停车时间按分钟计算。

【基本要求】

（1）假设停车场初始状态为第一层已经停有 4 辆车，其车位号依次为 1—4，停车时间依次 为 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）模块划分：描述所设计程序的各个模块（即函数）功能。

（6）数据结构：给出所使用的基本抽象数据类型,所定义的具体问题的数据类型,以及新定义的抽象数据类型。

（7）测试

测试数据、测试结果的分析与讨论，测试过程中遇到的主要问题及是如何解决的,对设计与实现的回顾讨论和分析；算法的时空分析(包括基本操作和其他算法的时间复杂度和空间复杂度的分析)；

（8）心得

包括程序的改进设想、经验和体会。

（9）源程序：给出所有源程序清单，要求程序有充分的注释语句，至少要注释每个函数参数的含义和函数返回值的含义。