吉林大学计算机学院研究生入学复试 2011 年上机考试试题    日期：2010/3/31；    时间：15:00‐17:30；    注 1：本套题目共 5 题，具体考试方法和评分标准参见考试细则。  注 2：若干题目中给出了一种可能的程序框架，供考生参考。考生也可完全抛开 提示代码自由编写，只要能够实现题目要求即可。  一、 字符串的反码（总分 15 分，纸面程序 10 分）  对于一个二进制数，将其每一位取反，称之为这个数的反码。下面我们定义 一个字符的反码。如果这是一个小写字符，则它和字符’a’的距离与它的反码和字 符’z’的距离相同；如果是一个大写字符，则它和字符’A’的距离与它的反码和字符’Z’ 的距离相同；如果不是上面两种情况，它的反码就是它自身。  举几个例子，’a’的反码是’z’；’c’的反码是’x’；’W’的反码是’D’；’1’的反码还是  1’；’$’的反码还是  ’$’。  一个字符串的反码定义为其所有字符的反码。我们的任务就是计算出给定字 符串的反码。  输入：输入每行都是一个字符串，字符串长度不超过 80 个字符，且不包括 空格、回车和制表符等空白字符。如果输入只有!，表示输入结束，不需要处理。  ===样例输入===  输出：对于输入的每个字符串，输出其反码，每个数据占一行。  Hello JLU-CCST-2011 ! Svool QOF-XXHG-2011   ===样例输出===  ====提示：一种可能实现的 C 语言的程序主体结构如下：====  #include int main(){ char str[100]; while(1){ scanf("%s", str); if (str[0] == '!' && str[1]==0) break; //此处进行处理，计算反码 printf("%s\n", str); } return 0; }   1 / 4  

二、数字之和（总分 15 分，纸面程序 10 分）  对于给定的正整数 n，计算其十进制形式下所有位置数字之和，并计算其平 方的各位数字之和。  输入：每行输入数据包括一个正整数 n(0 using namespace std; int sum_digits(int n){ //实现计算各位数字之和的程序 }   int main(){ int n, s1, s2; while(1){ cin >> n; if (n == 0) break; s1 = sum_digits(n); s2 = sum_digits(n*n); cout << s1 << ' ' << s2 << endl; } return 0; }     2 / 4  

三、搬水果（总分 20 分，纸面程序 15 分）  在一个果园里，小明已经将所有的水果打了下来，并按水果的不同种类分成 了若干堆，小明决定把所有的水果合成一堆.  每一次合并，小明可以把两堆水果合并到一起，消耗的体力等于两堆水果的 重量之和。当然经过 n‐1 次合并之后，就变成一堆了。小明在合并水果时总共消 耗的体力等于每次合并所耗体力之和。  假定每个水果重量都为 1，并且已知水果的种类数和每种水果的数目，你的 任务是设计出合并的次序方案，使小明耗费的体力最少，并输出这个最小的体力 耗费值。  例如有 3 种水果，数目依次为 1，2，9。可以先将 1，2 堆合并，新堆数目为 3，耗费体力为 3。然后将新堆与原先的第三堆合并得到新的堆，耗费体力为 12。 所以小明总共耗费体力=3+12=15，可以证明 15 为最小的体力耗费值。    输入：  每组数据输入包括两行,第一行是一个整数 n(1<=n<=10000),表示水果的种类 数，如果 n 等于 0 表示输入结束，且不用处理。第二行包含 n 个整数，用空格分 隔，第 i 个整数(1<=ai<=1000)是第 i 种水果的数目。  输出：  对于每组输入，输出一个整数并换行，这个值也就是最小的体力耗费值。输 入数据保证这个值小于 2^31。    ===样例输入===  3  9 1 2  0  ===样例输出===  15  四、堆栈的使用（总分 25 分，纸面程序 20 分）  堆栈是一种基本的数据结构。堆栈具有两种基本操作方式，push 和 pop。Push 一个值会将其压入栈顶，而 pop 则会将栈顶的值弹出。现在我们就来验证一下堆 栈的使用。  输入：对于每组测试数据，第一行是一个正整数 n，0

===样例输入===  3  A  P 5  A  4  P 3  P 6  O  A  0  ===样例输出===（注意最后还有一个空行）  E  5    3    五、连通图（总分 25 分，纸面程序 20 分）  给定一个无向图和其中的所有边，判断这个图是否所有顶点都是连通的。  输入：每组数据的第一行是两个整数 n 和 m（0< n <=1000）。n 表示图的顶点 数目，m 表示图中边的数目。如果 n 为 0 表示输入结束。随后有 m 行数据，每 行有两个值 x 和 y（0