程序与算法综合设计课程设计指导书

程序与算法综合设计

课程设计指导书

合肥工业大学 计算机与信息学院 2012年6月

一、概述

课程设计是对学生的一种全面综合训练，是与课堂听讲、自学和练习相辅相成的、必不可少的一个教学环节。通常，课程设计中的问题比平时的习题复杂的多，也更接近实际。课程设计着眼于原理与应用的结合点，使学生学会如何把书上学到的知识用于解决实际问题，培养软件工作所需要的动手能力；另一方面，能使书上的知识变“活”，起到深化理解和灵活掌握教学内容的目的。平时的习题较偏重于如何编写功能单一的“小”算法，局限于一个或两个知识点，而课程设计题是软件设计的综合训练，包括问题分析，总体结构设计，用户界面设计、程序设计基本技能和技巧，多人合作，以至一整套软件工作规范的训练和科学作风的培养。此外，还有很重要的一点是：计算机是比任何教师更严厉的检查者。

为达到上述目的，使学生更好地掌握程序设计的基本方法和C++语言的应用，本课程安排了课程设计环节，提供了各类题目供学生选择。每个设计题采取了统一的格式，由问题描述、基本要求、测试数据、实现提示和选做内容等五个部分组成。问题描述旨在为学生建立问题提出的背景，指明问题“是什么”。基本要求则对问题进一步求精，划出问题的边界，指出具体的参量或前提条件，并规定该题的最低限度要求。测试数据部分旨在为检查学生上机作业提供方便。在实现提示部分，对实现中的难点及其解法思路等问题作了简要提示，提示的实现方法未必是最好的，学生不应拘泥与此，而应努力设计和开发更好的方法和结构。选做部分向那些尚有余力的读者提出了更高的要求，同时也能开拓其它读者的思路，在完成基本要求时就力求避免就事论事的不良思想方法，尽可能寻求具有普遍意义的解法，使得程序结构合理，容易修改、扩充和重用。

二、总体要求

1. 系统分析与系统设计

“分析就是在采取行动之前，对问题的研究”（Demarco,1978）。系统分析在软件开发过程中是非常重要的，其任务就是通过对问题本身的研究，产生一个系统需要做什么的规范的、一致的和可行的需求说明。在此基础上，确定系统中所需考虑的类（对象）、类之间的关系、本系统中各个类所涉及的属性及针对这些属性的操作。类及类之间的关系可用类图来表示，对象之间的消息传递可用箭头表示，另外一些重要的操作应给出规格说明。

2．详细设计与编码

对类中的属性和操作从实现的角度（如可扩充、在派生类中能否直接使用或只需少量修改、访问的效率和方便性等）进一步考察；对类中的操作（即方法）进一步求精：用if、while、for和赋值语句加上自然语言写出算法框架；同时考虑能否使用已有类库（包括直接使用或通过派生）以减少编程的工作量和提高程序的可靠性。

编码，即程序设计，是对详细设计的结果的进一步求精，用面向对象语言（如C++）表达出来。在充分理解和把握语言运行机制的基础上，编写出正确的、清晰的、易读易改和高效率的程序。另外，在标识符的命名、代码的长度（一个方法长度一般不超过40行，否则应划分为两个或多个方法）、程序书写的风格（如缩进格式、空格（空行）的应用、注释等）方面也应注意，遵循统一的规范。

3．上机调试和测试

上机时要带一本面向对象语言的教材，若有开发环境的用户指南（手册）及类库（库函数）手册则更好。应仔细阅读程序编译和连接时的错误信息（通常是英文的），弄清其确切含义，提高调试效率。要学习并掌握开发环境所提供的调试工具。

经过调试，能够运行的的程序并非就是一个正确的程序。实际上，在上机之前，就应根据系统的需求设计相应的测试数据集，特别是一些异常情况的处理（如用户输入数据未按指定格式、数据极大或极小时程序如何处理等一些极端的情况）。

4．课程设计报告

课程设计报告的内容及要求：

一. 需求和规格说明

描述问题，简述题目要解决的问题是什么？规定软件做什么。原题条件不足时补全 二. 设计

1．设计思想：程序结构（如类图），重要的数据结构。主要算法思想（文字描述，不要画框图）

2．设计表示：类名及其作用，类中数据成员名称及作用，类中成员函数原型及其功能，可以用表格形式表达。

3．实现注释：各项要求的实现程度、在完成基本要求的基础上还实现了什么功能？ 4．详细设计表示：主要算法的框架及实现此算法的成员函数接口。 三. 用户手册

即使用说明（包括数据输入时的格式要求）。 四. 调试及测试

调试过程中遇到的主要问题是如何解决的；对设计和编码的回顾讨论和分析；程序运行的时空效率分析；测试数据集；运行实例；改进设想；经验和体会等。

附录

源程序清单：打印文本和磁盘文件，磁盘文件是必须的。源程序要加注释，除原有注释外再用钢笔加一些必要的注释和断言。

测试数据：即列出测试数据集

运行结果：上面测试数据输入后程序运行的结果

注意事项：

1. 以上要求为一般的要求，针对具体问题和具体的开发过程，某些方面可以做适当的增减。

2. 各种文档资料要在程序开发过程中逐渐形成,而不是最后补写（但不排斥最后誉清）。

3. 各种文档要以统一格式的稿纸用钢笔书写，也可录入计算机用Word及其它文字编辑软件排版后打印输出。

三、课程设计示例

封面：

课程设计报告 设计题目： 学生姓名： 专 业： 班 级： 学 号： 指导教师： 完成日期： 小型公司人员信息管理 合肥工业大学计算机与信息学院

（一） 需求和规格说明

某小型公司，主要有四类人员：经理、技术人员、销售经理和推销员。要求存

储这些人员的姓名、编号、级别、当月薪水，计算月薪总额并显示全部信息。

人员编号基数为1000，每输入一个人员的信息，编号顺序加1。 程序要对所有人员有提升级别的功能。为简单起见，所有人员的初始级别均为1级，然后进行升级，经理升为4级，技术人员和销售经理升为3级，推销员仍为1级。

月薪计算办法是：经理拿固定月薪8000元；技术人员按每小时100元领取月薪；推销员的月薪按该推销员当月销售额的4%提成；销售经理既拿固定月薪也领取销售提成，固定月薪为5000元，销售提成为所管辖部门当月销售总额的5?。

（二） 设计

根据上述需求，设计一个基类employee,然后派生出technician（技术人员）类、manager（经理）类和salesman（推销员）类。由于销售经理（salesmanager）既是经理又是销售人员，兼具两类人员的特点，因此同时继承manager和salesman两个类。

在基类中，除了定义构造函数和析构函数以外，还应统一定义对各类人员信息都应有的操作，这样可以规范各派生类的基本行为。但是各类人员的月薪计算方法不同，不能在基类employee中统一定义计算方法。各类人员信息的显示内容也不同，同样不能在基类中统一定义显示方法。因此，在employee类中用纯虚函数的方式定

义了计算月薪函数pay()和显示信息函数displayStatus()，然后在派生类中再根据各自的同名函数实现具体的功能。

由于salesmanager的两个基类又有公共基类employee，为避免二义性，这里将employee类设计为虚基类。

系统类图

employee char *name int individualEmpNo; int grade; float accumPay; static int employeeNo; virtual void pay(); void promote(int); vitual void displayStatus(); technician float hourlyRate int workHours virtual void pay(); vitual void displayStatus(); manager float monthlyPay virtual void pay(); vitual void displayStatus(); salesman float CommRate; float sales; virtual void pay(); vitual void displayStatus(); salesmanager virtual void pay(); vitual void displayStatus();

属性和方法定义 类名 employee 成员类别 属性 类型 char * int int float int 方法 void void void

类名 technician 成员名 name individualEmpNo grade accumPay employeeNo pay() promote(int) DisplayStatus() 雇员姓名 个人编号 级别 月薪总额 本公司雇员编号目前最大值 计算月薪函数（为纯虚函数） 升级函数 显示人员信息（为纯虚函数） 描述 每小时酬金 当月工作时数 accumPay=hourlyRate*workHours 显示技术人员信息 固定月薪数 AccumPay=monthlyPay 显示经理信息 按销售额提取酬金百分比 当月销售额 accumPay=sales*CommRate 显示推销员信息 accumPay=monthlyPay+CommRate*sales 显示销售经理信息 描述 成员类别 属性 类型 float int void void 成员名 hourlyRate workHours pay() DisplayStatus() monthlyPay pay() DisplayStatus() CommRate sales pay() DisplayStatus() pay() DisplayStatus() 方法 manager 属性 方法 float void void salesman 属性 float float 方法 void void salesmanager 属性 方法 void void

（三） 用户手册

程序运行时，首先提示输入雇员姓名。 对于经理直接输出其工资及其它信息；

对于技术人员，程序提示输入其本月工作时数，然后输出其工资及其它信息； 对于推销员，程序提示输入其本月销售额，然后输出其工资及其它信息； 对于销售经理，程序提示输入其管辖部门本月销售总额，然后输出其工资及其它信息。

（四） 调试及测试

由于公司每增加一个雇员，无论他（她）是哪一类人员,其编号均是顺序加1，也就是employee类的所有派生类对象创建时，都要访问同一个employeeNo，因此将employeeNo定义为静态数据成员。

运行实例：

please input employee's name: zhang please input employee's name: wang please input employee's name: Li please input employee's name: zhao

input zhang the workHours of this month: 56 Technician: zhang No: 1001 month salary: 5600

Technician: zhang No: 1001 grade: 3 this month salary: 5600 Manager: wang No: 1002 month salary: 8000

Manager: wang No: 1002 grade: 4 this month salary: 8000 input Li the sales of this month: 47900 Salesman: Li No: 1003 month salary: 1916

Salesman: Li No: 1003 grade: 1 this month salary: 1916

input zhao the total sales of the department of this month: 123654 salesman: zhao No: 1004 month salary: 5618.27 salesmanager: zhao No: 1004 grade: 3 this month salary: 5618.27

进一步改进

（1）目前程序中，经理月薪，技术人员的小时酬金和销售人员的销售额提成比例均是固定的，这不适应不同公司的需要，可考虑用带参数的构造函数来解决。

（2）销售经理月薪计算中，要输入其管辖部门当月销售总额。实际上，这可以通过将本部门所有推销员销售额相加而得到。可以考虑在推销员类中增加所属部门等属性来完成这方面的功能。

附录??源程序

题1：（90分）

目的：字符串是一种基础且广泛使用的数据结构，与字符串相关的题目既可以考察基本程序设计能力和技巧，也可以考查较强算法设计能力。 题目：求字符串之间距离

要求：设有字符串X，称在X的头尾及中间插入任意多个空格后构成的新字符串为X的扩展串，如字符串X为“abcbcd”，则字符串“abcb□cd”，“□a□bcbcd□”和“abcb□cd□”都是X的扩展串，这里“□”代表空格字符。 如果A1是字符串A的扩展串，B1是字符串B的扩展串，A1与B1具有相同的长度，那么定义字符串A1与B1的距离为相应位置上的字符的距离总和，而两个非空格字符的距离定义为它们的ASCII码的差的绝对值，而空格字符与其它任意字符之间的距离为已知的定值K，空格字符与空格字符的距离为0。在字符串A、B的所有扩展串中，必定存在两个等长的扩展串A1、B1，使得A1与B1之间的距离达到最小，将这一距离定义为字符串A、B的距离。请编写程序，求出字符串A、B的距离。

题2：（95分（全部完成）/90分（完成1和2））

目的：后缀表达式不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行（不再考虑运算符的优先规则，如：2 1 + 3 *,即(2 + 1) * 3. 通过本课程设计，应使学生掌握后缀表达式的特点、栈的基本方法和基本原理，培养学生运用语言编程及调试的能力，运用数据结构解决简单的实际问题的能力，为后续计算机专业课程的学习打下坚实的基础。 题目：后缀表达式计算器

要求：实现一个简单的后缀表达式计算器。假定表达式里的基本数值为实数，可用的运算符包括+,-,*,/,^，其中的 ^ 表示求幂运算。

1) 假定输入表达式里的数和运算符之间都有空格，这样可以简化输入的处理； 2) 输入的算术表达式以分号为结束符。计算器应该能输入并计算一系列表达式，遇到一行的第一个字符就是分号时程序结束。

3）上题的计算器增加一元函数功能，允许表达式里写sin, cos, tan, log（自然对数）等函数，还可以考虑加入自定义的其他数学函数。（选做）

题3：（90分）

目的：很多精妙的数学理论往往都以有趣的游戏形式表现出来，正是这些有趣的小游戏使得高深的数学理论被广泛的传播和接受。通过编程实现这些“数学游戏”可以提高学生的编程技巧和算法设计能力，提高解决实际问题的能力。 题目：两个小游戏 要求：

（1） 猜数字（文曲星游戏）

电脑随机生成一个0~9999之间的整数，若为23，则记为0023。玩家去猜，电脑将对玩家的答案做个评价，然后玩家再按电脑的评价重新猜，一共8次机会，猜对为赢。

比如：

电脑随机生成7859，若玩家第一次输入：1234，程序返回0A0B，A代表数

字和位置都猜对，B代表数字猜对，但位置不对。

若玩家第二次输入：5678，则返回0A2B，因为78都是原整数中的，但是位置不对。

若玩家第三次输入：0896，则返回1A1B……

依次，直至玩家输入7859，返回4A0B并终止程序。 记住，只有8次机会哦。

（2） 生命游戏（经典游戏，实现起来不难，正因为实现简单却变化繁复所以才成为经典）

http://baike.http://www.wodefanwen.com//view/162057.htm

我们可以把计算机中的宇宙想象成是一堆方格子构成的封闭空间，尺寸为N的空间就有N*N个格子。而每一个格子都可以看成是一个生命体，每个生命都有生和死两种状态，如果该格子生就显示蓝色，死则显示白色。每一个格子旁边都有邻居格子存在，如果我们把3*3的9个格子构成的正方形看成一个基本单位的话，那么这个正方形中心的格子的邻居就是它旁边的8个格子。

每个格子的生死遵循下面的原则：

1． 如果一个细胞周围有3个细胞为生（一个细胞周围共有8个细胞），则该细胞为生（即该细胞若原先为死，则转为生，若原先为生，则保持不变） 。

2． 如果一个细胞周围有2个细胞为生，则该细胞的生死状态保持不变；

3． 在其它情况下，该细胞为死（即该细胞若原先为生，则转为死，若原先为死，则保持不变设定图像中每个像素的初始状态后依据上述的游戏规则演绎生命的变化，由于初始状态和迭代次数不同，将会得到令人叹服的优美图案）。

题4：（95分）

目的：二叉树是常用的重要非线性数据结构，在客观世界中有着广泛的应用。通过本题可以加深对于二叉树这一数据结构的理解。掌握二叉树的存储结构及各种操作。

题目：二叉树结点染色问题

要求：一棵二叉树可以按照如下规则表示成一个由0、1、2组成的字符序列，我们称之为“二叉树序列S”：

例如，下图所表示的二叉树可以用二叉树序列S=21200110来表示。

任务是要对一棵二叉树的节点进行染色。每个节点可以被染成红色、绿色或蓝色。并且，一个节点与其子节点的颜色必须不同，如果该节点有两个子节点，那么这两个子节点的颜色也必须不相同。给定一棵二叉树的二叉树序列，请求出这棵树中最多和最少有多少个点能够被染成绿色。

题5：（85分）

目的：通过本课程设计，应使学生掌握队列的基本方法和基本原理，培养学生运用语言编程及调试的能力，运用数据结构解决简单的实际问题的能力，为后续计算机专业课程的学习打下坚实的基础。 题目：打印机任务队列

要求：打印机的打印队列中，每一个打印任务都有一个优先级，为1~9的一个整数（9的优先级最高，1的优先级最低），打印按如下方法进行.

（1）取出打印队列中队首的打印任务J；

（2）如果打印队列中存在优先级高于J的打印任务，则将J移动到打印队列的队尾；否则，打印J.

现在的问题是，要确定你要打印的文件何时打印完毕。给定当前打印队列（一个优先级队列）和你的打印任务在当前打印队列中的位置，确定你的打印任务完成时需要多长时间。为了简化问题，假定没有新的打印任务加入到打印队列中；并且，假定完成任何一个打印任务均需要1min时间，向打印队列中加入一个打印任务或从打印队列中移除一个打印任务不需要时间。

例如，当前打印队列为“1 1 9 1 1 1”且你的打印任务在队首时，需要5min.

题6：（90分）

目的：通过本课程设计，培养学生算法设计的能力，运用语言编程及调试的能力，运用计算机解决实际问题的能力，为后续计算机专业课程的学习打下坚实的基础。

题目：输出满足条件整数

要求：从小到大输出满足如下条件的整数：

① 是7和7的倍数 ② 包含7的数字 ③ ≤ N，N为给定的正整数

例如（17，27，37...70，71，72，73...）

题7：布尔表达式（90分）

目的：本课程设计是求中缀算术表达式真值问题。求中缀算术表达式值的问题是数据结构中栈的一个典型应用。通过本题，学生应掌握中缀表达式和后缀表达式的转换方法和后缀表达式求值问题。 题目：布尔表达式真值问题

要求：已知某种类型的布尔表达式由“V”、“F”、“！”、“&”和“|”组成，其中，“V”代表真值True，“F”代表真值False，“！”代表逻辑非运算，“&”代表逻辑或运算。并且，运算符“！”、“&”和“|”的优先级为：“！”最高，“|”最低，“&”介于“！”和“|”之间。你的任务是，计算给定布尔表达式的真值。

例如，布尔表达式“(V|V)&F&(F|V)”的真值为“F”.

题8：谣言传播（90分）

目的：通过本课程设计，应使学生掌握如何用图结构解决实际问题的能力，加深对于图结构的理解和认识。掌握图的存储方法和关于图的经典算法。提高学生的程序设计能力。

题目：谣言传播问题

要求：股票经纪人往往对谣言很敏感，你老板希望你能找到一个好方法向他们散布谣言，从而使他在股市占有战术优势。为了达到最有效果，需要谣言传播的尽量快。不幸的是，股票经纪人只相信从他们信任的信源传播来的消息，因此，在你散布谣言之前，需要对他们的联系网进行详细考察。对于一个股票经纪人，他需要一定时间才能将信息传送给他联系人，给你这些信息，你的任务是，决定选谁作为第一个传送谣言的人，以使谣言传遍所有人的时间最短，当然，如果谣言不能传遍所有人的话，你也要给出说明。

例如，假设共有3个联系人，联系人1传递信息给联系人2和3所有的时间分别为4和5；联系人2传送信息给联系人1和3所有的时间分别为2和6；联系人3传送信息给联系人1和2所有的时间均为2，则选择联系人3作为第一个传送谣言的人，可以使谣言传遍所有的人时间最短，为2.

（选择有向图中的一个源点，使它到其余各顶点的最短路径中最长的一条路径最短）

题9：分形（95分）

目的：递归是基本的算法思想和设计方法之一，也是数据结构重点讲授的部分，是许多算法的基础，对它们的理解和运用直接关系着其他算法的理解和应用。因此，熟练掌握递归是十分重要的。通过本题，应使学生加深对于递归方法的理解，提高运用递归解决问题的能力。 题目：盒子分形

要求：分形是一种具有自相似性的现象，在分形中，每一组成部分都在特征上和

整体相似，只不过仅仅是缩小了一些而已，一种盒子分形定义如下： （1）规模为1的盒子分形为

X

（2）规模为2的盒子分形为 X X X X X

（3）若用B(n - 1)表示规模为n-1的盒子分形，则规模为n的盒子分形为 B(n - 1) B(n - 1) B(n - 1) B(n - 1) B(n - 1) 你的任务是，输出规模为n的盒子分形。例如，规模为3的盒子分形输出如下：

X X X X

X X X X X X X X X X X

X X X X

X X X X X X

题10：网络布线(95分)

计算机网络要求网络中的计算机被连接起来，本问题考虑一个“线性”的网络，在这一网络中计算机被连接到一起，并且除了首尾的两台计算机只分别连接着一台计算机外，其它任意一台计算机恰连接着两台计算机。图1中用圆点表示计算机，它们的位置用直角坐标表示。网络连接的计算机之间的距离单位为英尺。

由于很多原因，我们希望使用的电缆长度应可能地短。你的问题是去决定计算机应如何被连接以使你所使用的电缆长度最短。在设计方案施工时，电缆将埋在地下，因此连接两台计算机所要用的电缆总长度等于计算机之间的距离加上额外的16英尺电缆，以从地下连接到计算机，并为施工留一些余量。

下图是计算机的最优连接方案，这样一个方案用电缆的总长度是 (4 + 16) + (5 + 16) + (5.38 + 16) + (11.18 + 16) = 90.01英尺

编程要求：

基本要求：

输入网络中的计算机总数和每台计算机的坐标。

输出使电缆长度最短的连接方案。给出最优连接方案中每两台相邻计算机之间的距离，以及总的电缆长度。

提高要求：

参考图2，用图形化的方式显示结果，包括点的坐标、最优路径、相邻计算机之间的距离。

题11：数独游戏

在一个9×9的大正方形中，包含9个3×3的小正方形。如图3所示。可以看到，其每行、每列、每个小正方形，都有9个空格。

要求只用1到9这些数字，填满大正方形中所有的81个空格，同时满足： （1）在每列的9个空格中分别填入1到9，且每个数字在此列中只能出现一次； （2）在每行的9个空格中分别填入1到9，且每个数字在此行中只能出现一次；

（3）在每个小正方形的9个空格中分别填入1到9，且每个数字在此正方形中只能出现一次；

游戏一开始会给定了某些空格的值。参加游戏的人根据这些已知的值以及上面的约束条件，推理出剩余的空格的值。

数独题目示例

解题结果

编程要求：

层次一：只编写“数独计算器”

显示一个空白的9×9大正方形，请玩家自己输入要求解的题目，然后系统帮助玩家解答。

层次二：加入“数独题目生成器”

系统自动生成数独题目，玩家进行解答，系统可判定玩家答案的正确性。玩家也可以查看解答。

层次三：附加要求

在层次二的基础上，可以让玩家选择题目难度，生成不同难度级别的数独题目；可以设置提示功能，在玩家解题过程中帮他提示错误或给出若干空格的解答；可以根据题目难度和解题时间，对玩家的水平进行打分；

题12：中国邮路问题：

邮递员的工作是每天在邮局里选出邮件，然后送到他所管辖的客户中，再返回邮局。自然地，若他要完成当天的投递任务，则他必须要走过他所投递邮件的每一条街道至少一次。问怎样的走法使他的投递总行程为最短？这个问题就称为中国邮路问题。

编程要求：

12R13房屋R1413房屋11R153房屋15R9房屋1081117R10房屋4房屋R5房屋13R115房屋房屋5R12R6房屋8R4房屋912房屋6R7777房屋R8R2房屋R1房屋R3

层次一：只求解用户输入的图形的中国邮路问题

要求用户输入图形，求解输入的图形的中国邮路问题，要求能显示图形和最终结果。

层次二：加入图形编辑器 系统自动生成图形，系统求解生成的图形的中国邮路问题，要求能显示图形和最终结果。

层次三：附加要求

能够图形显示求解过程。

题13：最大匹配问题：

问题描述：

写出求一个二分图的最大匹配的算法，并用于解决下面的问题。 第二次世界大战时期，英国皇家空军从沦陷国征募了大量外籍飞行员。由皇家空军派出 的每一架飞机都需要配备在航行技能和语言上能互相配合的2 名飞行员，其中1 名是英国飞行员，另1 名是外籍飞行员。在众多的飞行员中，每一名外籍飞行员都可以与其他若干名英国飞行员很好地配合。如何选择配对飞行的飞行员才能使一次派出最多的飞机。对于给定的外籍飞行员与英国飞行员的配合情况，试设计一个算法找出最佳飞行员配对方案，使皇家空军一次能派出最多的飞机。

编程任务：

对于给定的外籍飞行员与英国飞行员的配合情况，编程找出一个最佳飞行员配对方案， 使皇家空军一次能派出最多的飞机。

数据输入：

由文件input.txt提供输入数据。文件第1 行有2 个正整数m和n。n是皇家空军的飞行员总数(n<100)；m是外籍飞行员数。外籍飞行员编号为1~m；英国飞行员编号为m+1~n。 接下来每行有2 个正整数i和j，表示外籍飞行员i可以和英国飞行员j配合。文件最后以2 个-1 结束。

结果输出：

程序运行结束时，将最佳飞行员配对方案输出到文件output.txt 中。第1 行是最佳飞行员配对方案一次能派出的最多的飞机数M。接下来M 行是最佳飞行员配对方案。每行有2个正整数i和j，表示在最佳飞行员配对方案中，飞行员i和飞行员j 配对。

如果所求的最佳飞行员配对方案不存在，则输出‘No Solution!’。

输入文件示例： input.txt 5 10 1 7 1 8 2 6 2 9 2 10 3 7 3 8 4 7 4 8

5 10

-1 -1

输出文件示例： output.txt 4 1 7 2 9 3 8 5 10

题14：最佳匹配问题：

问题描述：

羽毛球队有男女运动员各n人。给定2 个n×n矩阵P和Q。P[i][j]是男运动员i和女运动员j配对组成混合双打的男运动员竞赛优势；Q[i][j]是女运动员i和男运动员j配合的女运动员竞赛优势。由于技术配合和心理状态等各种因素影响，P[i][j]不一定等于Q[j][i]。男运动员i和女运动员j配对组成混合双打的男女双方竞赛优势为P[i][j]*Q[j][i]。设计一个算法，计算男女运动员最佳配对法，使各组男女双方竞赛优势的总和达到最大。

编程任务：

设计一个优先队列式分支限界法，对于给定的男女运动员竞赛优势，计算男女运动员最佳配对法，使各组男女双方竞赛优势的总和达到最大。

数据输入：

第一行有1 个正整数n (1≤n≤20)。接下来的2n行，每行n个数。前n行是p，后n行是q。

结果输出：

将计算出的男女双方竞赛优势的总和的最大值输出。

样例输入： 3

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

样例输出：52

课题15：（75分）设计程序以实现构造哈夫曼树的哈夫曼算法，要求如下： （1）可以使用实验工具的有关功能。 （2）要能演示构造过程。

（3）求解出所构造的哈夫曼树的带权路径长度。

课题16：（85分）采用哈夫曼编码思想实现文件的压缩和恢复功能，并提供压缩前后的占用空间之比。

要求：

（1）描述压缩基本符号的选择方法。

（2）运行时的压缩原文件的规模应不小于5K。 （3）提供恢复文件与原文件的相同性对比功能。

课题18：（75分）给出一组实验来比较下列排序算法的时间性能：

快速排序、堆排序、希尔排序、冒泡排序、归并排序（其它排序也可以作为比较的对象）

要求：

（1）时间性能包括平均时间性能、最好情况下的时间性能、最差情况下的时间性能等。 （2）实验数据应具有说服力，包括：

规模范围要大（如从100到10000）

数据的初始特性类型要多，因而需要具有随机性；

实验数据的组数要多，即同一规模的数组要多选几种不同类型的数据来实验。 实验结果要能以清晰的形式给出，如图、表等。

（3）算法所用时间必须是机器时间，也可以包括比较和交换元素的次数。 （4）实验分析及其结果要能以清晰的方式来描述，如数学公式或图表等。 （5）要给出实验的方案及其分析。

课题19：（85分）设计一个模拟电梯工作过程的图形演示系统。要求所设计的电梯能符合市场上大多数系统的要求。

设计概要：几部电梯；相应优先级及规则确定；

课题20：（95分）决策树构造算法的实现

(1) 简介：决策树是通过一系列规则对数据进行分类的过程。它提供一种在什么条件下会得

到什么值的类似规则的方法。它是一个从上到下、分而治之的归纳过程，是决策树的一个经典的构造算法。应用于很多预测的领域，如通过对信用卡客户数据构建分类模型，可预测下一个客户他是否属于优质客户。

(2) 分类过程：分类是数据挖掘、机器学习和模式识别中一个重要的研究领域。数据分类是

一个两步过程。第一步，使用已知类别标记的训练数据集建立一个分类模型。例如：图1是一个决策树模型。第二步，对未知标记的数据使用模型进行分类。例如，根据图1的决策树模型，运用自顶而下的属性测试过程，将表2中的样例1-6分别分类为“Y”、“Y”、“Y”、“Y”、“N”、“N”。

天况

晴 湿度

多云

Y

雨

风况

大 N

正常

Y

有 N

无

Y

图1. 一个决策树模型的例子

(3) 算法描述：

输入：训练样例集S，未标记的节点T，属性集A 输出：以T为根的决策树

① 如果S中所有样例都是正例，则标记节点T为“Y”，并结束； ② 如果S中所有样例都是反例，则标记节点T为“N”，并结束；

③ 否则，从A中选择一个属性X，(可随机选)标记节点T为X;

④ 设X的所有取值为V1, V2,?,Vn，依据这些取值将S划分为n个子集 S1, S2, ?, Sn，建T的n个孩子节点Ti，并分别以Vi作为从T到Ti的分支标号; ⑤ 对每对（Si，Ti，A-{X}），递归调用ID3算法建立一棵以Ti为根的子树； END

(4) 举例：对下表运用算法构建决策树

表1. 一个训练数据集

编号 天况 1 2 3 4 5 6 7 8 9 10 11 12 13 晴 晴 多云 雨 雨 雨 多云 晴 晴 雨 晴 多云 多云 温度 热 热 热 中 冷 冷 冷 中 冷 中 中 中 热 湿度 风况 大 大 大 大 正常 正常 正常 大 正常 正常 正常 大 正常 无 有 无 无 无 有 有 无 无 无 有 有 无 分类 N N Y Y Y N Y N Y Y Y Y Y 雨 中 大 有 14 N 对下列样例输入使用构建的决策树模型预测其分类属性： 表2. 一个待分类的数据集 编号 天况 1 2 3 晴 晴 雨 温度 热 热 热 湿度 风况 正常 正常 正常 无 有 无 分类 ？ ？ ？ 4 5 晴 晴 中 冷 正常 大 无 有 ？ ？ 晴 冷 大 无 ？ 6 (5) 要求：①设计合理的数据结构，编程实现决策树构造算法；②给定训练数据集，运用构建的决策树模型，设计合理的文件格式，保存于外存之中；③设计决策树分类算法，根

据保存在外存的决策树模型，实现决策树的分类过程，完成对未知类别属性数据样例的分类。

课题21：（95分） 关联规则求解算法Apriori的实现

简介：关联分析是数据挖掘中的一个重要任务，Apriori算法是一种典型的关联分析算法。多用于超市的销售决策，如通过统计一段时间内，用户买商品A和B同时发生的概率，得出了顾客买A则很可能会买B的一条规则。

本课题要求对给定的训练数据，实现Apriori算法，构件关联规则集合。 Apriori算法描述如下：

输入：训练样例集S，属性集A，支持度阈值minsup，置信度阈值minconf 输出：关联规则集 （1）令 k=1

（2）生成长度为1的频繁项集

（3）重复以下操作直到不在生成新的频繁项集

（a）剪除一些候选项集，它们包含非频繁的长度为K子集 （b）从长度为k的频繁项集中生成长度为k+1的候选项集 （c）通过扫描数据库，计算每个候选项集的支持度

（d）除去那些非频繁的候选项集，只留下那些频繁的候选项集

END 示例：

基本概念表：关联规则的简单例子 TID 网球拍 网 球 运动鞋 羽毛球 1 2 3 4 5 6

1 1 1 1 0 1

1 1 0 0 1 1

1 0 0 1 1 0

0 0 0 0 1 0

用一个简单的例子说明。表1是顾客购买记录的数据库D，包含6个事务。项集I={网球拍,网球,运动鞋,羽毛球}。考虑关联规则（频繁二项集）：网球拍与网球，事务1,2,3,4,6包含网球拍，事务1,2,6同时包含网球拍和网球，支持度(X^Y)/D=0.5，置信度(X^Y)/X=0.6。若给定最小支持度α = 0.5，最小置信度β = 0.6，认为购买网球拍和购买网球之间存在关联。

＊ ＠ ＊

课题48（85分）

模拟人工洗牌

＠ ＊ ＊ 编写一个模拟人工洗牌的程序，将洗好的牌分别发给四个人。

使用结构card 来描述一张牌，用随机函数来模拟人工洗牌的过程，最后将洗好的52张牌顺序分别发给四个人。

对每个人的牌要按桥牌的规则输出。即一个人的牌要先按牌的花色（顺序为梅花、方块、红心和黑桃）进行分类，同一类的牌要再按A、K、Q、J、?、3、2牌的大小顺序排列。另发牌应按四个人的顺序依次分发。

注：C++随机数函数有： void srand(unsigned seed)

功能：函数可以设置rand函数所用得到随机数产生算法的种子值。任何大于1的种子值都会将rand随机数产生函数所产生的虚拟随机数序列重新设置一个起始点。

int rand(void)

功能：此函数可以产生介于0到32767间的虚拟随机数，所谓虚拟随机数的意思就是因为当只设置相同的启动种子值，所产生的数值序列都是可预测的。要产生不可预测的数值序列，必须通过srand函数不断改变随机数的启始种子值，已产生最佳的随机数。

头文件：stdlib.h

课题49（85分）

设计一个程序，该程序输入一个英语单词和它的释义（应考虑一个单词可以有多个释义）。将单词和它的释义分别存放在文件word.dat和meaning.dat中。文件word.dat中存储的数据的结构为：

class index { public:

char word[20]; streampos offset; };

其中，数据成员offset用于记录单词word的释义在文件meaning.dat中的位置。用户输入一个单词，屏幕输出该单词的释义。

提倡用MFC的对话框做简单的输入输出交互界面。

要求：①设计合理的数据结构，编程实现算法；②给定训练数据集，设计合理的文件格式，保存于外存之中；③设计apriori算法，保存关联规则在外存中。

课题22：（85分）程序开始运行时显示一个迷宫地图，迷宫中央有一只老鼠，迷宫的右下方有一个粮仓。游戏的任务是使用键盘上的方向键操纵老鼠在规定的时间内走到粮仓处。

要求：

1) 老鼠形象可辨认，可用键盘操纵老鼠上下左右移动； 2) 迷宫的墙足够结实，老鼠不能穿墙而过；

3) 正确检测结果，若老鼠在规定时间内走到粮仓处，提示成功，否则提示失败； 4) 添加编辑迷宫功能，可修改当前迷宫，修改内容：墙变路、路变墙； 5) 找出走出迷宫的所有路径，以及最短路径；

利用序列化功能实现迷宫地图文件的存盘和读出等功能。

课题23：（75分）选择合适的存储结构表示广义表，并能实现下列运算要求： （1）用大写字母表示广义表，用小写字母表示原子，并提供设置广义表的值的功能。 （2）取广义表L的表头和表尾的函数head(L)和tail(L)。 （3）能用这两个函数的复合形式求出广义表中的指定元素。

（4）由广义表的字符串形式到广义表的转换函数Lists Str_ToLists_(S)；例如 Str_ToLists_(“ (a,(a,b),c)”)的值为一个广义表。

（5）由广义表到广义表的字符串形式的转换函数char * Lists_To_Str(L)。 （6）最好能设置多个广义表。

课题24---25提示

简单路径：如果一条路径上的顶点除了起点和终点可以相同外，其它顶点均不相同，则称此路径为一条简单路径；起点和终点相同的简单路径称为回路（或环）。 课题24：（90分）

1）求出无向图中从起点到终点的所有简单路径。其中起点和终点可以由用户自行设

定。

2）求出无向图中从起点到终点的指定长度（如K）的所有简单路径。其中起点和终

点可以由用户自行设定。 课题25：（90分）

1）求出有向图中从起点到终点的所有简单路径。其中起点和终点可以由用户自行设

定。

2）求出有向图中从起点到终点的指定长度（如K）的所有简单路径。其中起点和终

点可以由用户自行设定。

课题26 （95分）《指针式时钟》问题分析,功能分析 （1）正确显示系统时钟；

（2）能准确定位时钟刻度和时分秒针的位置； （3）能随窗口大小的变化而变化。 算法设计及程序设计中技术重点:

在应用程序中，经常有一些任务在后台处理，实现方式有两种：计时器和OnIdle循环处理。计时器是程序中最常用的后台任务机制之一，其时间间隔最低约55毫秒，被广泛用于时钟、磁盘备份程序或需要在某一时刻运行的程序等。

多媒体计时器能编程设定1毫秒或者更小，它是诸如MIDI序列发生器之类的专用型应用程序的理想选择，在Windows API 中有很多查询时钟的函数，利用它们就可以编写出高精度的计时器。

使用计时器只需要了解两个函数：CWnd：：SetTimer（）函数用来设置一个计时器以指定的时间间隔触发，CWnd：：SetTimer（）函数用来使一个正在运行的计时器停止。计时器以两种方式通知应用程序计时器间隔时间已到：发送WM-TIMER消息和调用应用程序定义的回调函数。其中前者相对比较简单，但对于多个计时器则应使用回调函数。计时器消息发送给应用程序时都是低优先级，因此只有当消息对列中没有其他消息时才回处理它们。

计时器消息不能在消息队列中积存，这避免了出现永远无法清空消息队列的状态。尽管如此，Windows应用程序决不应该花费过量的时间来处理消息，除非该处理过程已经委派给辅助线程。如果主线程运行时间过长而没有检查消息队列，则程序的响应能力会受到影响。

程序运行结果图

课题27（90分）、设计某单位职工工资管理系统，功能如下：

对于每位职工存储以下信息：职工编号、基本工资、津贴、岗位津贴、应发数、个人所得税、应扣数、实发数。个人所得税计算方法设为：工资少于2000元的部分为0，2000—3000元部分为5%，3000—4000部分为10%，4000—5000部分为15%，5000元以上部分为20%。

（1）创建存储职工工资信息的存储文件； （2）添加某职工的工资信息； （3）删除某职工的工资信息；

（4）修改某职工的部分工资信息（当月开始增加或减少某些项工资或扣款数变化）； （5）输出指定编号职工的工资信息（查询用）

（6）输出全体职工的工资信息（发工资用）。 课程设计要求：

1．分析问题，给出数学模型，选择数据结构. 2．设计算法，给出算法描述 3．给出源程序清单

4. 编辑、编译、调试源程序 5. 撰写课程设计报告

课题28 （90分）学生成绩管理系统需求与功能分析 学生成绩管理系统的数据结构表如下：

序号 字段名 数据类型 长度 含义 1 class2 char 20 班级 2 num int 学号 3 name char 10 姓名 4 cprog float C程序设计 5 media flaot 多媒体技术 6 eng float 大学英语 7 math float 高等数学 8 sport float 大学体育 9 ave float 平均成绩 10 order int 名次

要求完成学生成绩的录入、统计、查询、修改、删除、输出。

课题29 （95分）散列表的设计与实现 任务：设计散列表实现电话号码查找系统。

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

（2) 从键盘输入各记录，以用户名（汉语拼音形式）为关键字建立散列表； （3) 采用一定的方法解决冲突； （4) 查找并显示给定电话号码的记录； 可以选作内容： （1) 系统功能的完善；

（2) 设计不同的散列函数，比较冲突率；

（3) 在散列函数确定的前提下，尝试各种不同类型处理冲突的方法，考察平均查找长度的变化。

课题30 （90分）宿舍管理查询软件

任务：为宿舍管理人员编写一个宿舍管理查询软件, 程序设计要求：

（1）采用交互工作方式

（2）可以增加、删除、修改信息

（3）建立数据文件 ，数据文件按关键字（姓名、学号、房号）进行排序(选择、快速排序、堆排序等任选一种)

(4) 查询: a.按姓名查询 ;b.按学号查询 ;c按房号查询 (5) 打印任一查询结果（可以连续操作）

课题31 （80分）求解2个字符串的最长公共子串。输入的2个字符串可以从键盘读入，也可以从两个文本文件中读入。

实现提示：可以采用动态规划法和后缀树算法，分析算法的时间复杂和空间复杂度。

课题32（95分）给出一篇英文文章，文件不小于5M的大小。统计其中的每个不同英文单词和总单词的数量。

实现提示：分别用链表和哈希表来实现，注意要给出不同大小文件耗费的时间，对时间性能进行进一步分析。关于英文文章，请自动生成文本文件。也可以从网络上下载几篇英文的文章，然后合并生成。

课题33（90分） 本科生导师制问题

问题描述：在高校的教学改革中，有很多学校实行了本科生导师制。一个班级的学生被分给几个老师，每个老师带领n个学生，如果老师还带研究生，那么研究生也可直接负责本科生。

本科生导师制问题中的数据元素具有如下形式：

⑴ 导师带研究生：（老师,((研究生1,(本科生1, …, 本科生m)), … )) ⑵ 导师不带研究生： (老师,(本科生1, …, 本科生m)) 导师的自然情况只包括姓名、职称； 研究生的自然情况只包括姓名、班级； 本科生的自然情况只包括姓名、班级。 功能要求：要求完成以下功能：

⑴ 插入：将某位本科生或研究生插入到广义表的相应位置； ⑵ 删除：将某本科生或研究生从广义表中删除； ⑶ 查询：查询导师、本科生（研究生）的情况； ⑷ 统计：某导师带了多少个研究生和本科生； ⑸ 输出：将某导师所带学生情况输出。

课题34（80分）

实现二叉树到其对应的Mirror Tree（镜像树）转化。所谓镜像树如下图所示

课题35（80分） 堆栈应用题 要求：

一、设计一个堆栈类，实现对于软件操作中常用的撤销/重做(Undo/Redo)的支持。 二、使用控制台或者图形界面，测试这个堆栈类的使用。 解题思路：

可以在标准的堆栈操作函数里实现对于临时文件名的出入栈，文件名作为临时文件名命名的规则可以这样形式：file0.tmp,file1.tmp??。为了使得临时文件名能够循坏，可以使得加入的临时文件名的编号与堆栈的指针编号相同，例如当栈顶位置为6时，进栈的临时文件名可为：file6.tmp。

课题36（80分） 矩阵位置旋转算法

要求：

一、设计一个矩阵类，实现矩阵的90度、180度、270度的旋转。 二、使用控制台或者图形界面，测试这个矩阵类的使用。

解题思路：

矩阵里面的数据是离散的，可以用坐标来表示，例如(0,0)、(2,3)??等，根据此坐标和整个矩阵的宽度和高度计算旋转后的此坐标新的坐标，填入新矩阵相应新坐标位置。

课题37（85分） 记事簿应用题 要求：

一、设计一个记事簿类，实现文字输入、文字删除、复制、粘贴、打开、保存的功

能。

二、使用控制台或者图形界面，测试这个记事簿类的使用。 解题思路：

记事簿的文字存储，可以申请连续内存存储来存储字符，同时设置一个数组来存贮关于行的信息，例如第一行的字符数等。复制和粘贴功能的实现是因为有一个共同的申

请的存储区域，当复制时就从存储区域复制字符，粘贴时则相反操作。

课题38（90分） 集合运算 问题描述：

设有两个用单链表表示的集合A、B，其元素类型是int且以非递减方式存储，其头结点分别为a、b。要求下面各问题中的结果集合同样以非递减方式存储，结果集合不影响原集合。 实现要求：

⑴ 编写集合元素测试函数IN_SET，如果元素已经在集合中返回0，否则返回1； ⑵ 编写集合元素输入并插入到单链表中的函数INSERT_SET，保证所输入的集合中的元素是唯一且以非递减方式存储在单链表中；

⑶ 编写集合元素输出函数，对建立的集合链表按非递增方式输出； ⑷ 编写求集合A、B的交C=A∩B的函数，并输出集合C的元素； ⑸ 编写求集合A、B的并D=A∪B的函数，并输出集合D的元素；

⑹ 求集合A与B的对称差E=(A-B)∪(B-A) 的函数，并输出集合D的元素； ⑺ 设计一个菜单，具有输入集合元素、求集合A、B的交C、求集合A、B的并D、求集合A与B的对称差E、退出等基本的功能。

测试数据：由读者自定，但集合A、B的元素个数不得少于16个。

课题39（90分） 矩阵的操作

设有两个矩阵A=(aij)m×n，B=(bij)p×q。 实现要求：

⑴ 编写矩阵输入函数INPUT_MAT，通过该函数完成矩阵的输入并返回保存矩阵的三元组（不能使用全局变量）；

⑵ 编写矩阵输出函数OUTPUT_MAT，通过该函数完成矩阵的输出，输出的形式是标准的矩阵形式（即二维数组的形式）；

⑶ 求矩阵的转置，矩阵的转置A=(aji)n×m，转置前输出原矩阵，转置后输出转置矩阵； ⑷ 求矩阵A、B的和。矩阵A和B能够相加的条件是：m=p，n=q；矩阵A和B如果不能相加，请给出提示信息；若能够相加，则求和矩阵C并输出C；

C=A+B=(cij)m×n，其中cij=aij+bij

⑸ 求矩阵A、B的差。矩阵A和B能够相减的条件是：m=p，n=q；矩阵A和B如果不能相减，请给出提示信息；若能够相减，则求差矩阵C并输出C；

C=A-B=(cij)m×n，其中cij=aij-bij

⑹ 求矩阵A、B的积。矩阵A和B能够相乘的条件是：p=n；矩阵A和B如果不能相乘，请给出提示信息；若能够相乘，则求积矩阵D并输出D；

’

D=A×B=(dij)m×q，其中dij=∑aik×bkj，k=1,2,??,n

⑺ 设计一个菜单，具有求矩阵的转置、求矩阵的和、求矩阵的积、退出等基本的功能。在求矩阵的和或求矩阵的积时要求能够先提示输入两个矩阵的，然后再进行相应的操作。

课题40（90分） 保龄球计分

【问题描述】打保龄球是用一个滚球去撞击10个站立的瓶，将瓶击倒。一局分10 轮，每轮可滚球1 次或多次，以击到的瓶数为依据计分，一局得分为10轮得分之和，而每轮的得分不仅与本轮的滚球情况有关，还可能与后一轮或两轮的滚球情况有关，即：某轮某次滚球击倒的瓶数不仅要计入本轮得分，还可能会计入前一轮或两轮得分。计分规则如下： a) 若某一轮的第一次滚球就击倒全部10个瓶，则本轮不再滚球（若是第10轮还需加2次滚球），该轮得分为本次击倒瓶数10与以后2次滚球所击倒瓶数之和。

b) 若某一轮的第一次滚球未击倒全部10个球，则对剩下未击倒的瓶再滚球一次，如果这2次滚球击倒全部10个瓶，则本轮不再滚球（若是第10轮还需加1次滚球），该轮得分为这2次击倒瓶数10与以后1次滚球所击倒瓶数之和。

c) 若某一轮2次滚球未击倒全部10个瓶，则本轮不在滚球，该轮得分为这2次滚球所击倒瓶数之和。 【实现提示】

a) 模拟10个人各打一局保龄球比赛过程，统计每局各轮得分和累计总分。 b) 逐人逐轮逐次输入一次滚球击倒的瓶数。 c) 对10人的得分由低到高排序并显示。 d) 最后，把排序的存入文件中。 【测试数据】自定模拟数据

课题41（90分） 车位管理

随着家庭购买汽车的增加，停车场车位紧张的问题越来越突出。请根据题目要求完成简单的车位管理程序。

1．停车场有若干停车位（为说明问题，假定为3个），每个位置可以存放不同种类的汽车，包括卡车Truck，客车Carriage和小轿车Car，但同一时刻一个位置只能存放0或1辆汽车。

2．管理系统模拟实际车辆停车的情况：

① 停车：新来车辆时如果有空位，按顺序为该车分配停车位，并自动记录开始停车的时间（用系统的时间）；

② 计费：车辆开走时，输入车位编号，自动记录结束停车的时间（用系统的时间）；计算出相应停车费；

③ 显示：显示停车场中各类车辆的信息。 ④ 保存

⑤ 退出

3．定义描述停车场的类Park，其中有3个位置用于存放各类车辆。

4．定义基类Automobile，至少包括纯虚函数Pay用于显示车辆信息并交纳相应停车费。 5．定义派生类Truck,Carriage和Car，这些车辆除了拥有车牌号、之外，

Truck还拥有载重量（浮点数，单位吨）属性，Carriage还拥有乘坐人数（整数，单位座）属性，Car还拥有排气量（浮点数，单位L）属性。具体实现上述纯虚函数Pay，显示每类车辆的相应信息，并给出计价提示，其中Truck收费2元/小时，Carriage收费1.5元/小时，Car收费1元/小时。

课题42（95分） 学生成绩管理系统： 问题描述：

主要功能是对批量学生的各门成绩进行录入、修改、查询、统计等，要求方便快速。记录学生的学号、姓名、班级、性别、联系电话以及课程和成绩；可以对学生的成绩按学号和姓名进行查寻；输出显示学生成绩；并实现排序、统计及格率和优秀率功能。 编程任务：

(1)界面基本要求：

**************************** 学生成绩管理系统

****************************

************************************ ** F1 --帮助 ** ** F2 --输入数据并存入文件 ** ** F3 --根据学号查询成绩 ** ** F4 --根据姓名查询成绩 ** ** F5 --输出文件内容 ** ** F6 –成绩排序 ** ** F7 --统计及格和优秀人数 ** ** ESC--退出系统 ** ************************************

另：提倡用MFC的对话框做简单的输入输出交互界面。

(2)功能要求：

1)帮助:系统使用方法的相关信息。

2)输入数据并存入文件：输入相关信息，并实现文件流的读写操作。 3)根据学号查询成绩：输入学号，查询学生的各门成绩

4)根据姓名查询成绩：输入姓名，查询学生的各门成绩 5)输出文件内容：屏幕输出显示所有学生的成绩

6) 成绩排序：对某门成绩或总分进行快速排序，显示、保存 7)统计及格和优秀人数：统计及格和优秀率。 8)退出

课题43（90分） 英文单词填空游戏

问题描述：这是一款帮助学生背单词的小软件。建立单词库，可从单词库中随机抽取单词，并随机隐去该单词中的一些字母，在屏幕上显示带空格的单词，用户对空格处的字母进行补全，程序判断填补是否正确，并统计正确率。 编程任务：

(1) 建立单词库，并可以方便地对单词库进行增加、删除。 (2) 随机读取一个单词。

(3) 随机隐去单词中的一些字母，规则是：长度为2～4空一个字母，5～7空二个字母，8～

10空三个字母，11以上空四个字母。用随机数方式确定隐去哪几个位上的字母，并在屏幕上显示带空格单词。

(4) 用户填充空格处的字母，程序判断填充是否正确。

(5) 当用户结束游戏时，统计正确率，并输出相应的鼓励语句。

课题44（85分） 数值排序问题

问题描述：实现常用排序算法：插入排序、冒泡排序、选择排序、快速排序、堆排序、归并排序、基数排序和希尔排序，输出有序数列，并输出排序次数。 编程任务：

(1) 实现上述各种排序算法。 (2) 用文件方式输入无序数据。

(3) 用大量不同规模、不同混乱程序数列进行实验，输出有序数列和排序次数。 (4) 分析各种排序算法的时间性能特点。

课题45（95分） 城市管理

问题描述：用无序表实现一个城市数据库。每条数据库记录包括城市名（任意长的字符串）和城市的坐标（用整数x和y表示）。实现数据的插入、删除、查询功能，并实现指定距离内的所有城市。设计算法实现指定一定数目的具体城市，寻找遍历这些城市并回到出发点的最佳路径，观察随着城市数目的增加，算法执行效率的变化。 编程任务：

(1) 用列表对城市进行记录和管理，实现城市的增加、删除和查询功能，并实现文件保存和

读取

(2) 计算城市之间距离，统计输出距离某城市一定范围内的所有城市。 (3) 实现一定规模城市的遍历最佳路径选择。

(4) 分析随着城市数目增加时，算法执行效果的改变，深刻理解旅行商问题。

课题46（95分）

实现简单的数字图像处理

一幅图像是包含位置集和颜色集的数据。考虑二维灰度图像，位置集就是一个矩阵的行列，矩阵的内容为颜色值，颜色为0~255间的整数，表示该位置的灰度等级，0为黑色，255为白色。

图像处理就是与该矩阵相关的计算，一种常见的计算就是通过一点和周围8个点的信息，共同决定该点的新值：如一点的新值为改点和周围8点颜色之和的平均，这一操作可用下图表示。

1/9 1/9 1/9 1/9 1/9 1/9 如果将上述操作变为下图

1/9 1/9 1/9 这样处理后图像会变得平滑，因此，称为平滑操作。

-1 -1 -1 -1 9 -1 -1 -1 -1 操作后图像的边缘变得更加突出，被称为锐化操作。 实现上述图像的平滑和锐化操作。 编程任务：

(1) 常见格式图像的读写(灰度图) (2) 设计上述平滑算子和锐化算子 (3) 实现平滑操作和锐化操作

(4) 观察处理后图像的变化，分析算子的作用。

课题47（85分）

编一棋盘游戏程序，人为一方，计算机为一方，人下时字符 * 将放在所指定的位置，而计算机下时字符 @ 将放在某一空格位置。行、列、或两对角线有连续三个相同字符一方为胜方，也有平局情况。要求能动态演示。

＊ ＠ ＊

课题48（85分）

模拟人工洗牌

＠ ＊ ＊ 编写一个模拟人工洗牌的程序，将洗好的牌分别发给四个人。

使用结构card 来描述一张牌，用随机函数来模拟人工洗牌的过程，最后将洗好的52张牌顺序分别发给四个人。

对每个人的牌要按桥牌的规则输出。即一个人的牌要先按牌的花色（顺序为梅花、方块、红心和黑桃）进行分类，同一类的牌要再按A、K、Q、J、?、3、2牌的大小顺序排列。另发牌应按四个人的顺序依次分发。

注：C++随机数函数有： void srand(unsigned seed)

功能：函数可以设置rand函数所用得到随机数产生算法的种子值。任何大于1的种子值都会将rand随机数产生函数所产生的虚拟随机数序列重新设置一个起始点。

int rand(void)

功能：此函数可以产生介于0到32767间的虚拟随机数，所谓虚拟随机数的意思就是因为当只设置相同的启动种子值，所产生的数值序列都是可预测的。要产生不可预测的数值序列，必须通过srand函数不断改变随机数的启始种子值，已产生最佳的随机数。

头文件：stdlib.h

课题49（85分）

设计一个程序，该程序输入一个英语单词和它的释义（应考虑一个单词可以有多个释义）。将单词和它的释义分别存放在文件word.dat和meaning.dat中。文件word.dat中存储的数据的结构为：

class index { public:

char word[20]; streampos offset; };

其中，数据成员offset用于记录单词word的释义在文件meaning.dat中的位置。用户输入一个单词，屏幕输出该单词的释义。

提倡用MFC的对话框做简单的输入输出交互界面。

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