编程要求：
（1）层次一：编写“数独计算器”
显示一个空白的9×9大正方形，请玩家自己输入要求解的题目，然后系统帮助玩家解答。
（2）层次二：加入“数独题目生成器”
系统自动生成数独题目，玩家进行解答，系统可判定玩家答案的正确性。玩家也可以查看解答。
（3）层次三：附加要求
在层次二的基础上，可以让玩家选择题目难度，生成不同难度级别的数独题目；可以设置提示功能，在玩家解题过程中帮他提示错误或给出若干空格的解答；可以根据题目难度和解题时间，对玩家的水平进行打分； 题12：中国邮路问题
邮递员的工作是每天在邮局里选出邮件，然后送到他所管辖的客户中，再返回邮局。自然地，若他要完成当天的投递任务，则他必须要走过他所投递邮件的每一条街道至少一次。问怎样的走法使他的投递总行程为最短？这个问题就称为中国邮路问题。
R13房屋12R1413房屋11R153房屋15房屋5房屋R9R10118房屋10R5房屋1713房屋4房屋5R11R777房屋R12R4房屋912房屋R6房屋86R87房屋R2R1房屋R3图7 中国邮路问题示意图
编程要求：
（1）层次一：只求解用户输入的图形的中国邮路问题
要求用户输入图形，求解输入的图形的中国邮路问题，要求能显示图形和最终结果。
（2）层次二：加入图形编辑器
系统自动生成图形，系统求解生成的图形的中国邮路问题，要求能显示图形
和最终结果。
（3）层次三：附加要求 能够图形显示求解过程。 题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：构造哈夫曼树
设计程序以实现构造哈夫曼树的哈夫曼算法，要求如下： （1）可以使用实验工具的有关功能。 （2）要能演示构造过程。
（3）求解出所构造的哈夫曼树的带权路径长度。 题16：解压缩软件
采用哈夫曼编码思想实现文件的压缩和恢复功能，并提供压缩前后的占用空间之比。要求如下：
（1）描述压缩基本符号的选择方法。
（2）运行时的压缩原文件的规模应不小于5K。 （3）提供恢复文件与原文件的相同性对比功能。 题17：排序算法实验分析
给出一组实验来比较下列排序算法的时间性能：插入排序、冒泡排序、选择排序、快速排序、堆排序、希尔排序、归并排序、基数排序（其它排序也可以作为比较的对象）。要求如下：
（1）时间性能包括平均时间性能、最好情况下的时间性能、最差情况下的时间性能等。
（2）实验数据应具有说服力，包括： 规模范围要大（如从100到10000）
数据的初始特性类型要多，因而需要具有随机性,也可由机器随机生成； 实验数据的组数要多，即同一规模的数组要多选几种不同类型的数据来实验。
实验结果要能以清晰的形式给出，如图、表等。
（3）算法所用时间必须是机器时间，也可以包括比较和交换元素的次数。 （4）实验分析及其结果要能以清晰的方式来描述，如数学公式或图表等。 （5）要给出实验的方案及其分析。 题18：小型文本编辑器
设计一个文本编辑器，使其具有通常编辑器所应具备的基本功能。 要求如下：
（1）要求该编辑器在串基本抽象数据型上构建。
（2）编辑器应具备如字符串查找、剪切、粘贴、替换、字数统计、行数统计等基本功能。
（3）具备图形化界面。 题19：电梯模拟系统
设计一个模拟电梯工作过程的图形演示系统。要求所设计的电梯能符合市场上大多数系统的要求。
设计概要：两部以上的电梯；相应优先级及规则确定。 题20：决策树构造
简介：决策树是通过一系列规则对数据进行分类的过程。它提供一种在什么条件下会得到什么值的类似规则的方法。它是一个从上到下、分而治之的归纳过程，是决策树的一个经典的构造算法。应用于很多预测的领域，如通过对信用卡客户数据构建分类模型，可预测下一个客户他是否属于优质客户。
分类过程：分类是数据挖掘、机器学习和模式识别中一个重要的研究领域。数据分类是一个两步过程。第一步，使用已知类别标记的训练数据集建立一个分类模型。例如：图8是一个决策树模型。第二步，对未知标记的数据使用模型进行分类。例如，根据图8的决策树模型，运用自顶而下的属性测试过程，将表2中的样例1-6分别分类为“Y”、“Y”、“Y”、“Y”、“N”、“N”。
天况
晴 湿度
多云
Y
雨
风况
大 N
正常
Y
有 N
无
Y
图8 一个决策树模型的例子
决策树算法（ID3算法）描述：
输入：训练样例集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
举例：对表1运用算法构建决策树