1、教育部教育管理信息中心 第 六 届全国 信息技术应用水平 大赛 决 赛试题 Java 程序设计 请仔细阅读并严格遵守 以下要求： 请 创建以“ 准考证号 _用户名 ”命名的文件夹（形式如： 433034683_xxxx）， 将考试结果严格按 试题 上的要求进行命名并 直接保存 在该文件夹下。 注意 ： 文件夹的保存路径请听从监考老师的安排。请不要在该文件夹下创建任何子文件夹，所有考试结果 直接 保存即可 。 答卷完毕后，请将该 文件夹用 Winrar 压缩工具打包，再通过 决 赛考试结果上传系统 将 压缩包 上传到指定服务器，并在原机器上保留备份 。 注意 ： 压缩打包时， 请务必选 中 文件
2、夹 （如前面创建的 “ 433034683_xxxx” 文件夹）进行压缩，而不是选中文件夹下的考试结果进行压缩。 请务必按照试卷要求提交指定的文件，不得包含非题目要求的过程文件和临时文件，不得包含 本试题文件和试题素材 。 注意：凡违反上述规定的考生，其成绩一律按零分处理。 题目命名要求： 请将编写好的源程序以 T+题号 的方式 命名，例如第 1 题的源程序保存为“ T1.java” ） ，题目本身有命名要求的除外。 1、 某新建小区要修建多个公共设施，供小区内的居民使用， 要求 任意 2 个公共设施 之间都要可以互通， 可以 直接铺一 条小路， 也可以不直接连通， 只要能间接通过 小路 可达
3、即可 。现得到小区物业修路费用统计表，表中列出了任意两公共设施间修建 小路 的费用，以及该 小路 是否已经修通的状态。具体要求如下： a) 公共设施 数目 N（ 1 N 20）； b) 两个相同 公共设施 间费用为 0； c) 状态为“已经修通”的 公共设施 间 小路 成本为 0； 现请 设计算法，并 编写程序计算出 实现目标 需要的最低成本 ，并输出结果 。 测试数据文件 说明： 测试输入文件命名为 “ T1_input.in” ， 每一个 测试输入 文件 包含 一个 测试用例。每个测试用例的第 1 行给出 公共设施的 数目 N ( 1 N 20 )；随后的 N(N-1)/2 行对应 公共设
4、施 间教育部教育管理信息中心 修建小路 的 费用 及修建状态，每行给 4 个正整数， 数值之间 以空格分开，前两个数值代表 两个 公共设施 的编号（从 1 编号到 N），以及修建状态： 1 表示已建， 0 表示未建 ，依次是 两 公共设施 间 小路 的 修建费用 。 样例： 输入文件： 3 2 1 0 1 3 1 0 2 3 2 0 4 输出： 最低成本 ： * （ 1）请根据以上要求设计最佳算法，并加以 文字 说明； （ 2）编程实现算法，并以样例文件进行测试，输出结果； （ 3） 按照下面给定的三个测试数据进行测试，并输出结果。 测试数据一： 4 1 2 0 6 1 3 0 3 1 4 1
5、 8 2 3 0 5 2 4 0 3 3 4 0 4 测试数据二： 5 1 2 0 3 1 3 0 2 1 4 0 4 1 5 1 1 2 3 0 2 2 4 0 3 2 5 0 1 3 4 1 5 3 5 0 4 4 5 0 2 测试数据三： 6 1 2 0 4 1 3 0 2 1 4 0 5 教育部教育管理信息中心 1 5 1 7 1 6 0 3 2 3 0 2 2 4 0 6 2 5 1 2 2 6 0 1 3 4 1 5 3 5 0 4 3 6 0 5 4 5 1 2 4 6 0 3 5 6 0 1 （本题 60 分，要求 1 占 20 分，要求 2 占 10 分，要求 3 占 30
6、分） 2、 某 军事基地的 卫星测控站 ， 需要 实时采集 卫星的 数据 并进行 测控 ，测控站要求站内 工作人员 ，每天要 24 小时不间断测控，由于测控站内 需要 每天都有部分 人员 值班，所以 每天安排值班 人员 是一件很重要的事情， 不同时间段对 值班 人员数也有要求， 具体要求如下表所示： 班次 1 2 3 4 5 6 起止时间 6-10 时 10-14 时 14-18 时 18-22 时 22-2 时 2-6 时 最少 人员 数 50 65 60 45 30 25 每班值班的 工作人员 分别在 6,10,14,18,22,2 时开始上班，连续工作 8 小时。测控站站长需要确定每个班次应派多少 人员 值班，才能既满足要求又使每天上班的人数最少。 （ 1）请根据以上要求设计最佳算法，并加以 文字 说明； （ 2）编程实现算法，并输出 每天上班的最少人数； （ 3） 按照下面给定的 新的排班要求运行算法， 并输出 每天上班的最少人数 。 班次 1 2 3 4 5 6 起止时间 6-10 时 10-14 时 14-18 时 18-22 时 22-2 时 2-6 时 最少人员数 30 25 50 45 20 35 （本题 60 分，要求 1 占 20 分，要求 2 占 20 分，要求 3 占 20 分）
