湖南省第二届“软考杯”大学生程序设计大赛试题

湖南省第二届“软考杯”大学生程序设计大赛试题 试题1人类的大脑是按功能分区的。正常人的大脑分区都是活跃的,分区之间有着广泛的神经连接 而脑病患者的某些大脑分区则是不活跃的,处于“睡眠”状态。最近的研究发现:如果某个“睡眠 分区X与其它至少3个活跃分区保持连接1年时间,则分区X会“苏醒”过来,恢复成活跃状态。“苏 醒”后的分区不会再转入“睡眠”状态 有位病人的大脑分区都处于“睡眠状态”。经用一种新方法治疗后,其中3个分区同时“苏醒”过 来。根据上文的结论,若不再进行治疗则其它分区经过多少年也能全部“苏醒”过来? 输入 输入文件的第1行仅包含1个整数M,取值范围是3,26],它表示病人大脑的分区数 第2行也只包含1个非负整数N,它表示分区之间的连接数(如果分区A与分区B相连,则分区B也 与分区A相连。由于这样的连接是等价的,所以只计数1次) 第3行包含3个相邻的英文字母,分别代表刚刚同时“苏醒”的3个分区。 第4行中包含N个用空格分割的字符串,每个字符串包含2个英文字母,分别代表2个相连接的分区 输出 如果该病人的大脑分区经过若干年后能够全部“苏醒”,请在输出文件中按格式输出一行 “ WAKE UP IN n YEARS”(其中n指分区全部“苏醒”需要的年数) 如果该病人的大脑分区无法全部“苏醒”,请在输出文件中按格式输出一行: THIS BRAIN NEVER WAKES U 示例 输入: 输出: WAKE UP IN 3 YEARS AB AC AH BD BC BF CD CF CH DF FH 试题2测绘人员将卫星拍摄的地面遥感图像转换成了数值方阵。方阵中的每个元素都是正整数,代 表某单位面积土地上的植物类型。元素为质数时对应土地上的植物为稀有类型,元素为合数时对应土 地上的植物为常见类型。 为保护稀有植物,林业局雇佣你编写程序分析上述数值方阵,从中检测出稀有植物区和非稀有植 物区。划分区域的原则是:如果数值方阵中的两个元素同为质数或同为合数,而且它们共行相邻或共 列相邻,则这两个元素同属一个区域 输入:输入文件中包含若干待分析的数值方阵。方阵的每一行占据文件的每一行,同一行的方阵元素 之间用空格分隔。每个数值方阵的前一行包含且仅包含一个正整数,代表该方阵的行数。文件的结尾 行包含且仅包含一个负整数。数值方阵的行数不会超过100,元素的值不会大于10000000 输出:针对输入文件中的每一个数值方阵分别输出如下信息

湖南省第二届“软考杯”大学生程序设计大赛试题 试题 1 人类的大脑是按功能分区的。正常人的大脑分区都是活跃的，分区之间有着广泛的神经连接； 而脑病患者的某些大脑分区则是不活跃的，处于“睡眠”状态。最近的研究发现：如果某个“睡眠” 分区 X 与其它至少 3 个活跃分区保持连接 1 年时间，则分区 X 会“苏醒”过来，恢复成活跃状态。“苏 醒”后的分区不会再转入“睡眠”状态。 有位病人的大脑分区都处于“睡眠状态”。经用一种新方法治疗后，其中 3 个分区同时“苏醒”过 来。根据上文的结论，若不再进行治疗则其它分区经过多少年也能全部“苏醒”过来？ 输入： 输入文件的第 1 行仅包含 1 个整数 M，取值范围是[3, 26]，它表示病人大脑的分区数。 第 2 行也只包含 1 个非负整数 N，它表示分区之间的连接数（如果分区 A 与分区 B 相连，则分区 B 也 与分区 A 相连。由于这样的连接是等价的，所以只计数 1 次）。 第 3 行包含 3 个相邻的英文字母，分别代表刚刚同时“苏醒”的 3 个分区。 第 4 行中包含 N 个用空格分割的字符串，每个字符串包含 2 个英文字母，分别代表 2 个相连接的分区。 输出： 如果该病人的大脑分区经过若干年后能够全部“苏醒”，请在输出文件中按格式输出一行： “WAKE UP IN n YEARS” （其中 n 指分区全部“苏醒”需要的年数） 如果该病人的大脑分区无法全部“苏醒”，请在输出文件中按格式输出一行： “THIS BRAIN NEVER WAKES UP” 示例 输入： 6 11 HAB AB AC AH BD BC BF CD CF CH DF FH 输出： WAKE UP IN 3 YEARS 试题 2 测绘人员将卫星拍摄的地面遥感图像转换成了数值方阵。方阵中的每个元素都是正整数，代 表某单位面积土地上的植物类型。元素为质数时对应土地上的植物为稀有类型，元素为合数时对应土 地上的植物为常见类型。 为保护稀有植物，林业局雇佣你编写程序分析上述数值方阵，从中检测出稀有植物区和非稀有植 物区。划分区域的原则是：如果数值方阵中的两个元素同为质数或同为合数，而且它们共行相邻或共 列相邻，则这两个元素同属一个区域。 输入：输入文件中包含若干待分析的数值方阵。方阵的每一行占据文件的每一行，同一行的方阵元素 之间用空格分隔。每个数值方阵的前一行包含且仅包含一个正整数，代表该方阵的行数。文件的结尾 行包含且仅包含一个负整数。数值方阵的行数不会超过 100，元素的值不会大于 100000000。 输出：针对输入文件中的每一个数值方阵分别输出如下信息：

1该数值方阵的序号(按照其在输入文件中的位置从1计起)。格式是:“ Area n:”(n代表 方阵序号) 稀有植物区域的数目和每个稀有植物区域的面积(按升序排列)。格式是: “ M unique vegetation regions:ala2…”(M为区域数目,al,a2,等代表每个区域的 面积) 3非稀有植物区域的数目。格式是:“ K non-unique vegetation regions”(K为区域数目) 具体的输出格式请参考示例。 示例 输入: 输出: Area 1 249 2 unique vegetation regions: 2 3 17637 1 non-unique vegetation regions 29811 Area 2 4 2 non-unique vegetation regions 572133 461l17 891329 试题3某年轻导演准备拍摄一部名为《温柔石头》的喜剧电影。由于预算紧张导演绞尽脑汁想节省 开支。作为剧务的你提醒他:“演员的出场费很高,能不能让他们一人分演多个角色?充分挖掘他们的 潜力,也可以节省我们的开支嘛!”导演大呼“有创意”,并顺手把剧本塞给你,“你研究研究剧本, 最少需要几个演员”,说着就准备出门去再拉几个广告赞助商,临走前他又补充了几点要求 男演员只能演男角色,女演员只能演女角色 2角色的扮演者确定下来后,在演出的过程中就不能中途更改。 3如果两个角色会同时在一个场景中出现,则这两个角色必须由两个不同的演员扮演。 导演走后,你翻开剧本看了看,发现了一张场景清单,也就是本题目的输入文件。 输入:输入文件的第一行包含用空格分隔的3个正整数,M,F和S。其中M代表剧中的男角色数目, 取值在[1,10之间:F代表剧中的女角色数目,取值在[,10之间;S代表剧中的场景数目,取值在[1,100 之间。第二行和第三行分别列出了男角色和女角色的名字,每个名字都是一个英文字符串,名字之间 有空格分隔。下面的S行分别描述了每个场景中出现的角色数和角色名(有空格分隔)。 输出:本剧需要的男女演员的最少数目,具体格式如下 “ You need x actors and y actresses”其中x和y分别代表男、女演员的最少数目 示例 输入 输出: 436 You need 3 actors and 2 actresses

1 该数值方阵的序号（按照其在输入文件中的位置从 1 计起）。格式是：“Area n:” (n 代表 方阵序号) 2 稀有植物区域的数目和每个稀有植物区域的面积（按升序排列）。格式是： “M unique vegetation regions: a1 a2 ...” (M 为区域数目，a1, a2,...等代表每个区域的 面积) 3 非稀有植物区域的数目。格式是：“K non-unique vegetation regions” (K 为区域数目) 具体的输出格式请参考示例。 示例 输入： 3 2 4 9 17 6 37 29 8 11 4 2 3 12 15 5 7 21 33 4 6 11 17 8 9 13 29 -1 输出： Area 1: 2 unique vegetation regions: 2 3 1 non-unique vegetation regions Area 2: 2 unique vegetation regions: 4 4 2 non-unique vegetation regions 试题 3 某年轻导演准备拍摄一部名为《温柔石头》的喜剧电影。由于预算紧张导演绞尽脑汁想节省 开支。作为剧务的你提醒他：“演员的出场费很高，能不能让他们一人分演多个角色？充分挖掘他们的 潜力，也可以节省我们的开支嘛！”导演大呼“有创意”，并顺手把剧本塞给你，“你研究研究剧本，看 最少需要几个演员”，说着就准备出门去再拉几个广告赞助商，临走前他又补充了几点要求： 1 男演员只能演男角色，女演员只能演女角色。 2 角色的扮演者确定下来后，在演出的过程中就不能中途更改。 3 如果两个角色会同时在一个场景中出现，则这两个角色必须由两个不同的演员扮演。 导演走后，你翻开剧本看了看，发现了一张场景清单，也就是本题目的输入文件。 输入：输入文件的第一行包含用空格分隔的 3 个正整数，M, F 和 S。其中 M 代表剧中的男角色数目， 取值在[1, 10]之间；F 代表剧中的女角色数目，取值在[1, 10]之间；S 代表剧中的场景数目，取值在[1, 100] 之间。第二行和第三行分别列出了男角色和女角色的名字，每个名字都是一个英文字符串，名字之间 有空格分隔。下面的 S 行分别描述了每个场景中出现的角色数和角色名（有空格分隔）。 输出：本剧需要的男女演员的最少数目，具体格式如下： “You need x actors and y actresses” 其中 x 和 y 分别代表男、女演员的最少数目 示例 输入： 4 3 6 输出： You need 3 actors and 2 actresses

Tarzan jim John Tom Lucy Cynthia Jane 3 Jim John Tom 2 Tarzan lucy 2 Jane Cynthia 2 Jim jane 2 Tarzan jim 2 Tarzan jane 试题4“树”在计算机科学中是一种非常重要的数据结构。它的应用极为广泛,从计算机图形学中 的空间层次剖分到人工智能中的状态搜索都离不开它。二叉树是一种特殊的树,它的每个节点最多只 有左、右两个子树,如图1所示。 8 11 图 我们用二元组(n,s)来表示二叉树中的任意节点。其中n代表该节点的值,s代表从根节点到该节点 的路径字符串,字符串中只包含'L和R'两种字符,分别指“左子树”和“右子树”。图1中值为13 的节点用(13RL)表示,值为2的节点用(2,LLR)表示;根节点用(5)表示,空路径字符串表示它是根节 点。如果每个节点到根节点的路径上都没有缺少节点,而且每个节点只被赋值一次,则称这样的二叉 树是“完备描述”的。本题目要求你判断给定二叉树是否是“完备描述”的,如果是,输出其节点值 的按层次遍历序列(即先上层后下层、从左至右地遍历)。图1中的二叉树,其节点值的按层次遍历序 列为:5,4,8,11,13,4,7,2,1 输入:输入文件中包含多个二叉树的节点序列,每个节点用上述(ns)形式描述,节点值都是正整数 节点之间以空格分隔,节点内部没有空格。每个二叉树至少包含一个节点,树的结尾处以两个英文括 号字符“(”标记,括号之内没有空格。 输出:针对输入文件中的每个二叉树,分别输出其对应的信息。对于完备描述的二叉树,输出其节点 值的按层次遍历序列。每个二叉树的遍历序列值占据一行,且值与值之间用空格分隔。对于不完备描 述的二又树,则在新的一行中输出字符串“ not complete

Tarzan Jim John Tom Lucy Cynthia Jane 3 Jim John Tom 2 Tarzan Lucy 2 Jane Cynthia 2 Jim Jane 2 Tarzan Jim 2 Tarzan Jane 试题 4 “树”在计算机科学中是一种非常重要的数据结构。它的应用极为广泛，从计算机图形学中 的空间层次剖分到人工智能中的状态搜索都离不开它。二叉树是一种特殊的树，它的每个节点最多只 有左、右两个子树，如图 1 所示。 图 1 我们用二元组(n,s)来表示二叉树中的任意节点。其中 n 代表该节点的值，s 代表从根节点到该节点 的路径字符串，字符串中只包含’L’和’R’两种字符，分别指“左子树”和“右子树”。图 1 中值为 13 的节点用(13,RL)表示，值为 2 的节点用(2, LLR)表示；根节点用(5,)表示，空路径字符串表示它是根节 点。如果每个节点到根节点的路径上都没有缺少节点，而且每个节点只被赋值一次，则称这样的二叉 树是“完备描述”的。本题目要求你判断给定二叉树是否是“完备描述”的，如果是，输出其节点值 的按层次遍历序列（即先上层后下层、从左至右地遍历）。图 1 中的二叉树，其节点值的按层次遍历序 列为：5, 4, 8, 11, 13, 4, 7, 2, 1。 输入：输入文件中包含多个二叉树的节点序列，每个节点用上述(n,s)形式描述，节点值都是正整数。 节点之间以空格分隔，节点内部没有空格。每个二叉树至少包含一个节点，树的结尾处以两个英文括 号字符“()”标记，括号之内没有空格。 输出：针对输入文件中的每个二叉树，分别输出其对应的信息。对于完备描述的二叉树，输出其节点 值的按层次遍历序列。每个二叉树的遍历序列值占据一行，且值与值之间用空格分隔。对于不完备描 述的二叉树，则在新的一行中输出字符串“not complete

示例 输入 输出: (11,LL)(7,LLL)(8,R) 54811134721 (5,)(4,L)(13,RL)(2,LLR)(1RRR)(4,RR)O not complete (3,L)(4R)O 试题5在海量的信息面前我们已经离不开搜索引擎。最近你发现某著名搜索引擎 Bangle的搜索结果 不尽人意,比如你按关键词搜索“ crazy stone”本意是想搜索一个名为《 crazy stone》的电影,结果 Bangle 的10万条返回信息大部分是你不需要的。 Bangle倾向于把所有包含“ crazy”和“ stone”两个关键的 网页都返回给你,而不管这两个关键词在上下文中的距离有多远。比如某网页的第一段出现了100个 “ crazy”,在间隔了5600个词后又出现了100个“sone”,结果这个网页被 Bangle放在搜索结果列表 的第10位,而它对你来说其实没用。因此,你希望改进现有的搜索引擎,使用户能更明确地控制搜索。 你的设想是:在关键词的前面添加一个距离阈值,限定关键词之间的最大允许距离。比如“0 crazy stone”表示“cray”和“ stone”两个关键词在文中必须是相邻出现的,“2 crazy stone”表示这两个关键 词在文中出现的间隔不能大于2个词。标点和空格不算入间隔,关键词的出现次序也不做限制。我们 称这种距离阈值加若干关键词的组合为“搜索元语”。对于搜索元语“2 crazy stone”而言“ The director of Crazy Stone is very young….”和“ Why to say the stone is crazy.”两段短文都是合格的。采用这种方 法,用户就能更好地控制搜索精度,减少垃圾结果。 你的任务就是编程实现上述想法。根据搜索元语判断短文是否满足要求。如果搜索元语中关键词 的个数大于2,则只需其中任意两个关键词在文中的出现距离不大于距离阈值,就认为该短文是满足 搜索要求的。关键词的出现次序不做限定 输入:输入文件中包含不多于50条搜索元语和不多于250段短文。 每条搜索元语占据一行,以“P”开头,后面依次跟一个非负整数代表距离阈值和若干小写 的字符串代表关键词,并有空格分隔。 2每段短文都以“T”开头,以“”结尾。“”只会出现在短文的末尾。每段短文的长度都不 大于255个字符,可能占据多行。每行最多80个字符,短文的每个后续行开头都至少有一个 空格。 3在读取短文时请忽略所有非字母字符,比如原始短文“ Dont rock- the boat as Metaphor in 1984”应该被读取为“ Dont Rock the Boat as Metaphor in”,“HP2l00X”应该被读取为“HPX”。 文件的结尾行包含单独的字符“#”。 输出:输出文件中的每一行对应输入文件中的一条搜索元语。每行以对应搜索元语的序号开始(搜索 元语的序号是指搜索元语在输入文件中出现的次序,从1开始编号),后面紧跟一个冒号及空格,然后 是以升序排列的符合该搜索元语要求的短文序号,短文的序号是指短文在输入文件中出现的次序,从 1开始编号。短文的序号之间以逗号分隔,不含空格。 示例 输 输出: 1:1,2 P: 3 concepts conceptions

示例 输入： (11,LL) (7,LLL) (8,R) (5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) () (3,L) (4,R) () 输出： 5 4 8 11 13 4 7 2 1 not complete 试题 5 在海量的信息面前我们已经离不开搜索引擎。最近你发现某著名搜索引擎 Baigle 的搜索结果 不尽人意，比如你按关键词搜索“crazy stone”本意是想搜索一个名为《crazy stone》的电影，结果 Baigle 的 10 万条返回信息大部分是你不需要的。Baigle 倾向于把所有包含“crazy”和“stone”两个关键的 网页都返回给你，而不管这两个关键词在上下文中的距离有多远。比如某网页的第一段出现了 100 个 “crazy”，在间隔了 5600 个词后又出现了 100 个“stone”，结果这个网页被 Baigle 放在搜索结果列表 的第 10 位，而它对你来说其实没用。因此，你希望改进现有的搜索引擎，使用户能更明确地控制搜索。 你的设想是：在关键词的前面添加一个距离阈值，限定关键词之间的最大允许距离。比如“0 crazy stone”表示“crazy”和“stone”两个关键词在文中必须是相邻出现的，“2 crazy stone”表示这两个关键 词在文中出现的间隔不能大于 2 个词。标点和空格不算入间隔，关键词的出现次序也不做限制。我们 称这种距离阈值加若干关键词的组合为“搜索元语”。对于搜索元语“2 crazy stone”而言“The director of Crazy Stone is very young....”和“Why to say the stone is crazy...”两段短文都是合格的。采用这种方 法，用户就能更好地控制搜索精度，减少垃圾结果。 你的任务就是编程实现上述想法。根据搜索元语判断短文是否满足要求。如果搜索元语中关键词 的个数大于 2，则只需其中任意两个关键词在文中的出现距离不大于距离阈值，就认为该短文是满足 搜索要求的。关键词的出现次序不做限定。 输入：输入文件中包含不多于 50 条搜索元语和不多于 250 段短文。 1 每条搜索元语占据一行，以“P:”开头，后面依次跟一个非负整数代表距离阈值和若干小写 的字符串代表关键词，并有空格分隔。 2 每段短文都以“T:”开头，以“|”结尾。“|”只会出现在短文的末尾。每段短文的长度都不 大于 255 个字符，可能占据多行。每行最多 80 个字符，短文的每个后续行开头都至少有一个 空格。 3 在读取短文时请忽略所有非字母字符，比如原始短文“Don't Rock -- the Boat as Metaphor in 1984”应该被读取为“Dont Rock the Boat as Metaphor in”，“HP2100X”应该被读取为“HPX”。 文件的结尾行包含单独的字符“#”。 输出：输出文件中的每一行对应输入文件中的一条搜索元语。每行以对应搜索元语的序号开始（搜索 元语的序号是指搜索元语在输入文件中出现的次序，从 1 开始编号），后面紧跟一个冒号及空格，然后 是以升序排列的符合该搜索元语要求的短文序号，短文的序号是指短文在输入文件中出现的次序，从 1 开始编号。短文的序号之间以逗号分隔，不含空格。 示例 输入： P: 0 rock art P: 3 concepts conceptions 输出： 1: 1,2 2:

art rock metaphor concepts 3:1,2,3,4 T: Rock Art of the Maori T: Jazz and rock- Art Brubeck and Elvis Presley T: Don't Rock ---the Boat as Metaphor in 1984, Concepts and( Mis)-Conceptions of an Art Historian. I T: Carved in Rock, The Art and Craft of making promises believable when your phone bills have gone through the roof 试题6当我们给大洋彼岸的朋友发出一封emal或给家乡的亲人发送一条手机短信时,我们一般不会 担心对方收到错误的信息。然而,无论 email还是手机短信在抵达目的地前都必需化为电信号穿越无 数的电缆和设备,甚至化作无形的电磁波在天空中传播,衰减和噪音时刻都威胁着你发出的信息。为 了保证通信的正确性,必需及时发现传输错误并予以纠正,这是现代通信技术中的重要研究内容。 般的解决思路是在原始信息的后面附加一些校验信息,通过这些校验信息来判断传输的正确性。循环 冗余码CRC就是这样一种信息校验方法。它的思路是 待传输的信息是由字节序列组成的,可以看作是一个很长的正二进制数B。当传输B时,在其后 附上两个字节的CRC校验值组成B'。CRC校验值不是任意取的,它要使B'能被一个16位的预定义 值g整除。信息的接收方也知道g,因此对方只需把接收值除以g看余数是否为零就能判断传输的正 确性。在本题中我们设定g=34943(十进制)。你的任务是编写程序计算任意输入信息对应的CRC校 验值。 输入:输入文件中每一行的内容(不包括换行符)就代表一条待传输的信息。每一条待传输信息包含 不多于1024个ASCI字符。首字符为“#”的行代表输入的结束 输出:输出文件的每一行包含两个16进制数(以空格分隔)代表输入文件中对应行中待传输信息的两 字节CRC校验值。每个校验值应该在十进制数的0到34942之间 示例 输入: 输出: this is a test 试题7按规矩客户应该在SENY公司把货物发出之后的30天之内付清货款,否则SENY公司就有遭 客户赖帐的风险。为了规避风险,SENY公司与一家商业保险公司签订了协议,协议规定:保险公司 为SENY的每个客户提供一定额度的支付担保,担保额度与对应客户的财政记录有关 但在实际运营中,如果某客户的欠款额已经高出保险公司所能提供的担保额度,为了留住客户, SENY公司还是会继续跟该客户交易并发货。当然,此时超出保险公司担保额度以上的欠款将由SENY

P: 1 art rock metaphor concepts T: Rock Art of the Maori| T: Jazz and Rock - Art Brubeck and Elvis Presley| T: Don't Rock --- the Boat as Metaphor in 1984, Concepts and (Mis)-Conceptions of an Art Historian.| T: Carved in Rock, The Art and Craft of making promises believable when your `phone bills have gone through the roof| # 3: 1,2,3,4 试题 6 当我们给大洋彼岸的朋友发出一封 email 或给家乡的亲人发送一条手机短信时，我们一般不会 担心对方收到错误的信息。然而，无论 email 还是手机短信在抵达目的地前都必需化为电信号穿越无 数的电缆和设备，甚至化作无形的电磁波在天空中传播，衰减和噪音时刻都威胁着你发出的信息。为 了保证通信的正确性，必需及时发现传输错误并予以纠正，这是现代通信技术中的重要研究内容。一 般的解决思路是在原始信息的后面附加一些校验信息，通过这些校验信息来判断传输的正确性。循环 冗余码 CRC 就是这样一种信息校验方法。它的思路是： 待传输的信息是由字节序列组成的，可以看作是一个很长的正二进制数 B。当传输 B 时，在其后 附上两个字节的 CRC 校验值组成 B’。CRC 校验值不是任意取的，它要使 B’能被一个 16 位的预定义 值 g 整除。信息的接收方也知道 g，因此对方只需把接收值除以 g 看余数是否为零就能判断传输的正 确性。在本题中我们设定 g = 34943（十进制）。你的任务是编写程序计算任意输入信息对应的 CRC 校 验值。 输入：输入文件中每一行的内容（不包括换行符）就代表一条待传输的信息。每一条待传输信息包含 不多于 1024 个 ASCII 字符。首字符为“#”的行代表输入的结束。 输出：输出文件的每一行包含两个 16 进制数（以空格分隔）代表输入文件中对应行中待传输信息的两 字节 CRC 校验值。每个校验值应该在十进制数的 0 到 34942 之间。 示例 输入： this is a test A # 输出： 77 FD 00 00 0C 86 试题 7 按规矩客户应该在 SENY 公司把货物发出之后的 30 天之内付清货款，否则 SENY 公司就有遭 客户赖帐的风险。为了规避风险，SENY 公司与一家商业保险公司签订了协议，协议规定：保险公司 为 SENY 的每个客户提供一定额度的支付担保，担保额度与对应客户的财政记录有关。 但在实际运营中，如果某客户的欠款额已经高出保险公司所能提供的担保额度，为了留住客户， SENY 公司还是会继续跟该客户交易并发货。当然，此时超出保险公司担保额度以上的欠款将由 SENY