浙江大学计算机复试上机2005-2007 （由林子整理 QQ：170479150）
2005年浙江大学计算机学院考研复试上机试题及参考答案(1/5) 第一题：A+B(10分) [结题]
题目要求：读入两个小于100的正整数A和B，计算A+B。 需要注意的是：A和B的每一位数字由对应的英文单词给出。
输入格式：测试输入包含若干测试用例，每个测试用例占一行，格式为\"A + B =\"，相邻两字符串有一个空格间隔。当A和B同时为0时输入结束，相应的结果不要输出。
输出格式：对每个测试用例输出1行，即A+B的值。 输入样例： one + two =
three four + five six = zero seven + eight nine = zero + zero = 输出样例： 3 90 96
#include int main(void) { const char data[12][6] = {\"zero\\"one\\"two\\"four\ \"five\ unsigned a, b; /* 转换后的表达式参数,如a+b(123+456) */ unsigned i, j, k; /* 临时变量，作为下标 */ char str[100]; /* 输入字符串，足够大容量 */ char temp[6]; /* 临时字符串，用于检索数字，如\"one\"->'1' */ char result[30]; /* 转换后的表达式参数，如\"123+456=\" */ do{ a = b = i = j = k = 0; /* 初始化变量 */ memset(str, 0, sizeof(str)); memset(temp, 0, sizeof(temp)); memset(result, 0, sizeof(result)); gets(str); /* 获取输入字符串，不能使用scanf，因为有空格 */ for(i=0, k=0; i temp[j] = 0; /* 字符串结束标记 */ for(j=0; j<12; j++) /* 把这个单词转换为数字 */ if(strcmp(temp, data[j]) == 0) { if( j <= 9 ) result[k++] = j + '0'; if( j == 10 ) result[k++] = '+'; if( j == 11 ) result[k++] = '='; break; /* 找到匹配数字就不必再搜索了 */ } } result[k] = 0; /* 字符串结束标记，result形式\"123+456=\" */ sscanf(result,\"%d+%d=\用sscanf来获得a,b的值 */ if( a==0 && b==0 ) break; /* A,B同时为零则退出程序 */ else printf(\"%d\\n\打印输出 A + B 的数值 */ }while(1); return 0; } 2005年浙江大学计算机学院考研复试上机试题及参考答案(2/5) 第二题：谁是开门关门的人？（10分） 题目要求：每天第一个到机房的人要把门打开，最后一个离开的人要把门关好。现有一堆杂乱的机房签到、签离记录，请根据记录找出当天开门和关门的人。 输入格式：测试输入的第一行给出记录的总天数N ( > 0 )。下面列出了N天的记录。 每天的记录在第一行给出记录的条目数M ( > 0 )，下面是M行，每行的格式为 证件号码 签到时间 签离时间 其中时间按“小时:分钟:秒钟”（各占2位）给出，证件号码是长度不超过15的字符串。 输出格式：对每一天的记录输出1行，即当天开门和关门人的证件号码，中间用1空格分隔。 注意：在裁判的标准测试输入中，所有记录保证完整，每个人的签到时间在签离时间之前， 且没有多人同时签到或者签离的情况。 输入样例： 3 1 ME3021112225321 00:00:00 23:59:59 2 EE301218 08:05:35 20:56:35 MA301134 12:35:45 21:40:42 3 CS301111 15:30:28 17:00:10 SC3021234 08:00:00 11:25:25 CS301133 21:45:00 21:58:40 输出样例： ME3021112225321 ME3021112225321 EE301218 MA301134 SC3021234 CS301133 #include char id[16]; /* 证件号码长度不超过15位 */ char cometime[9]; /* 时间格式00:00:00 */ char leavetime[9]; /* 时间格式00:00:00 */ }Record; int main() { int N, M, i; /* 记录的总天数N，每天记录的条目数M */ Record *pTimeList;/* 记录该天出入人员的证件号码、进入时间、离开时间 */ int first, last; /* 记录每天开门的人和关门的人 */ scanf(\"%d\读入记录的总天数 */ while(N--) { scanf(\"%d\读入该天的进出人员数 */ pTimeList = (Record *)malloc(M*sizeof(Record)); for(i=0,first=0,last=0; i if( strcmp( pTimeList[first].cometime, pTimeList[i].cometime ) > 0 ) first = i; if( strcmp( pTimeList[last].leavetime, pTimeList[i].leavetime) < 0) last = i; } } /* for i */ printf(\"%s %s\\n\ free(pTimeList); } /* for N */ } 2005年浙江大学计算机学院考研复试上机试题及参考答案(3/5) 第三题：分数统计（12分） 题目要求：今天的上机考试虽然有实时的Ranklist，但上面的排名只是根据完成的题数排序，没有考虑每题的分值，所以并不是最后的排名。给定录取分数线，请你写程序找出最后通过分数线的考生，并将他们的成绩按降序打印。 输入格式：测试输入包含若干场考试的信息。每场考试信息的第1行给出考生人数N ( 0 < N < 1000 )、考题数M ( 0 < M < = 10)、分数线（正整数）G；第2行排序给出第1题至第M题的正整数分值；以下N行，每行给出一名考生的准考证号（长度不超过20的字符串）、该生解决的题目总数m、以及这m道题的题号（题目号由1到M）。 当读入的考生人数为0时，输入结束，该场考试不予处理。 输出格式：对每场考试，首先在第1行输出不低于分数线的考生人数n，随后n行按分数从高到低输出上线考生的考号与分数，其间用1空格分隔。若有多名考生分数相同，则按他们考号的升序输出。 输入样例： 4 5 25 10 10 12 13 15 CS004 3 5 1 3 CS003 5 2 4 1 3 5 CS002 2 1 2 CS001 3 2 3 5 1 2 40 10 30 CS001 1 2 2 3 20 10 10 10 CS000000000000000001 0 CS000000000000000002 2 1 2 0 输出样例： 3 CS003 60 CS001 37 CS004 37 0 1 CS000000000000000002 20 #include char id[21]; /* 准考证号(<=20字符) */ int score; /* 该考生总分 */ }StuInfo; int main() { int N, M, G, n; /* 考生人数，题目数，分数线，上线考生数量 */ int *pMarkList; /* 第1题至第M题的正整数分值 */ StuInfo *pStuinfo; /* 考生信息 */ int i,j,k,a,b,c,m; /* 临时变量 */ StuInfo tmp; /* 用于排序 */ while( scanf(\"%d\读入考生人数N */ { scanf(\"%d%d\读入题目数量和分数线 */ pMarkList = (int *)malloc(M*sizeof(int)); /* M道题目的分数 */ pStuinfo = (StuInfo *)malloc(N*sizeof(StuInfo)); /* N个考生 */ for(i=0; i for(pStuinfo[n].score=0,j=0; j if(pStuinfo[n].score >= G) /* 如果考生上线则记录下来 */ n++; /* 否则不予记录，便于排序 */ } for(i=0; i for(k=i, j=i+1; j tmp = pStuinfo[k]; pStuinfo[k] = pStuinfo[i]; pStuinfo[i] = tmp; } for(i=0; i for(k=1,j=i+1; j break; } /* 下标i到i+k的考生分数相同，对这k个考生排序，升序 */ for(a=i; a<=i+k-1; a++) { for(c=a, b=a+1; b<=i+k; b++) if(strcmp(pStuinfo[c].id, pStuinfo[b].id) > 0) c = b; tmp = pStuinfo[a]; pStuinfo[a] = pStuinfo[c]; pStuinfo[c] = tmp; } } printf(\"%d\\n\排序完毕，按照要求输出，上线人数 */ for(i=0; i return 0; } 2005年浙江大学计算机学院考研复试上机试题及参考答案(4/5) 第四题：最大连续子序列（13分） 题目要求：给定K个整数的序列{ N1, N2, ..., NK }，其任意连续子序列可表示为{ Ni, Ni+1, ...,Nj }，其中 1 <= i <= j <= K。最大连续子序列是所有连续子序列中元素和最大的一个，例如给定序列{ -2, 11, -4, 13, -5, -2 }，其最大连续子序列为{ 11, -4, 13 }，最大和为20。在今年的数据结构考卷中，要求编写程序得到最大和，现在增加一个要求，即还需要输出该子序列的第一个和最后一个元素。 输入格式：测试输入包含若干测试用例，每个测试用例占2行，第1行给出正整数K( < 10000)，第2行给出K个整数，中间用空格分隔。当K为0时，输入结束，该用例不被处理。 输出格式：对每个测试用例，在1行里输出最大和、最大连续子序列的第一个和最后一个元素，中间用空格分隔。如果最大连续子序列不唯一，则输出序号i和j最小的那个（如输入样例的第2、3组）。若所有K个元素都是负数，则定义其最大和为0，输出整个序列的首尾元素。 输入样例： 6 -2 11 -4 13 -5 -2 10 -10 1 2 3 4 -5 -23 3 7 -21 6 5 -8 3 2 5 0 1 10 3 -1 -5 -2 3 -1 0 -2 0 输出样例： 20 11 13 10 1 4 10 3 5 10 10 10 0 -1 -2 0 0 0 #include long int K, last; /* 输入数据个数K<1000；最大子序列最后一个元素的下标last */ long int ThisSum, MaxSum, TmpMaxSum, index, *pList; while( scanf(\"%d\ { ThisSum = 0; MaxSum = TmpMaxSum = last = LONG_MIN; pList = (long int *)malloc( K * sizeof(long int) ); for(index = 0; index < K; index++) { scanf( \"%d\ ThisSum += pList[index]; if(ThisSum > MaxSum) /* 输入含有正数时，忽略最大子序列中首尾0的影响 */ { MaxSum = ThisSum;/* 更新MaxSum */ if( MaxSum > TmpMaxSum ) /* 最大值更新时，更新最大子序列最后的数字 */ { /* 保证最大子序列起始位置在输入串的最前面 */ TmpMaxSum = MaxSum; last = index; } } if( ThisSum < 0 ) ThisSum = 0; } /* trace back to find first number of the max subsequence */ for( TmpMaxSum = 0, index = last; index >= 0; index-- ) { TmpMaxSum += pList[index]; if(TmpMaxSum == MaxSum) break; } if( MaxSum < 0 ) /* K个数字都是负数，定义最大和为0，输出首尾元素 */ printf(\"%ld %ld %ld\\n\ else printf(\"%ld %ld %ld\\n\ free(pList); } return 0; } 2005年浙江大学计算机学院考研复试上机试题及参考答案(5/5) 第五题：畅通工程（15分） 题目要求：某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？ 输入格式：测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是城镇数目N ( < 1000 )和道路数目M；随后的M行对应M条道路，每行给出一对正整数，分别是该条道路直接连通的两个城镇的编号。为简单起见，城镇从1到N编号。当N为0时，输入结束，该用例不被处理。 输出格式：对每个测试用例，在1行里输出最少还需要建设的道路数目。 输入样例： 4 2 1 3 4 3 3 3 1 2 2 3 5 2 1 2 3 5 999 0 0 输出样例： 1 0 2 998 #include using namespace std; int n, visited[1024]; vector int i; visited[a]=1; for(i=1;i<=n;i++) if (connect[a][i]==1 && visited[i]==0) dfs(i); return(0); } int main(int argc, char* argv[]) { int i,j,a,b,count = -1; int numtown,numroad; while(cin>>numtown && numtown!=0){ cin>>numroad; n = numtown; for(i=1;i<=numtown;i++) for(j=1;j<=numtown;j++) connect[i][j] = 0; for(i=1;i<=numtown;i++) visited[i] = 0; for(i=1;i<=numroad;i++) { cin>>a>>b; connect[a][b] = connect[b][a] = 1; } for(j=1;j<=numtown;j++) connect[i][j] = 0; for(i=1;i<=numtown;i++) visited[i] = 0; for(i=1;i<=numroad;i++) { cin>>a>>b; connect[a][b] = connect[b][a] = 1; } for(i=1;i<=numtown;i++) if (visited[i]==0) { dfs(i); count++; } cout< 2006年浙江大学计算机学院考研复试上机试题及参考答案(1/5) 第一题：A+B(16分) 题目要求：读入两个小于10000的正整数A和B，计算A+B。需要注意的是：如果A和B的末尾K（不超过8）位数字相同，请直接输出-1。 输入格式：测试输入包含若干测试用例，每个测试用例占一行，格式为\"A B K\"，相邻两数字有一个空格间隔。当A和B同时为0时输入结束，相应的结果不要输出。 输出格式：对每个测试用例输出1行，即A+B的值或者是-1。 输入样例： 1 2 1 11 21 1 108 8 2 36 64 3 0 0 1 输出样例： 3 -1 -1 100 #include int main(void) { unsigned int a, b, k; unsigned char ch1[50], ch2[50]; do{ scanf(\"%d %d %d\ if( a==0&&b==0 || k>8 ) break; sprintf(ch1, \"%d\ strrev(ch1);strrev(ch2); if(strlen(ch1) 2006年浙江大学计算机学院考研复试上机试题及参考答案(2/5) 2007-03-31 21:44:14 大 中 小 第二题：统计同成绩学生人数（12分） 题目要求：读入N名学生的成绩，将获得某一给定分数的学生人数输出。 输入格式：测试输入包含若干测试用例，每个测试用例的格式为 第1行：N 第2行：N名学生的成绩，相邻两数字用一个空格间隔。 第3行：给定分数 当读到N=0时输入结束。其中N不超过1000，成绩分数为（包含）0到100之间的一个整数。 输出格式：对每个测试用例，将获得给定分数的学生人数输出。 输入样例： 3 80 60 90 60 2 85 66 0 5 60 75 90 55 75 75 0 输出样例： 1 0 2 #include unsigned N, score, num, i; unsigned pList[1000]; do { scanf(\"%d\ if(N==0) break; for(i=0;i 2006年浙江大学计算机学院考研复试上机试题及参考答案(3/5) 第三题：火星A+B （7分）（ZOJ ACM 2529） 题目要求：读入两个不超过25位的火星正整数A和B，计算A+B。需要注意的是：在火星上，整数不是单一进制的，第n位的进制就是第n个素数。例如：地球上的10进制数2，在火星上记为“1,0”，因为火星个位数是2进制的；地球上的10进制数38，在火星上记为“1,1,1,0”，因为火星个位数是2进制的，十位数是3进制的，百位数是5进制的，千位数是7进制的„„ 输入格式：测试输入包含若干测试用例，每个测试用例占一行，包含两个火星正整数A和B，火星整数的相邻两位数用逗号分隔，A和B之间有一个空格间隔。当A或B为0时输入结束，相应的结果不要输出。 输出格式：对每个测试用例输出1行，即火星表示法的A+B的值。 输入样例： 1,0 2,1 4,2,0 1,2,0 1 10,6,4,2,1 0 0 输出样例： 1,0,1 1,1,1,0 1,0,0,0,0,0 =========================我的代码============================= 测试用例和输出结果： 1,0 2,1 1,0,1 4,2,0 1,2,0 1,1,1,0 1 10,6,4,2,1 1,0,0,0,0,0 0,1,0,1 0,0,1,1 1,2,0 0,0,0,0,1 1,0,0 1,0,1 0,0,0,1 0,0,0,0,0,1 1,0 96,88,82,78,72,70,66,60,58,52,46,42,40,36,30,28,22,18,16,12,10,6,4,2,1 96,88,82, 78,72,70,66,60,58,52,46,42,40,36,30,28,22,18,16,12,10,6,4,2,1 1,96,88,82,78,72,70,66,60,58,52,46,42,40,36,30,28,22,18,16,12,10,6,4,2,0 0,0,0 0,1,0 Press any key to continue #include int IsPrime(int n) { int i; if(n<2) return 0; for(i=2; i char op1[300], op2[300], *p; int i, j, index, num, num1, num2, cnt, breakflag; int PrimeList[N+1], op1List[N], op2List[N], OutputList[N+1]; for(i = 0, j = 0; i < N+1; j++) /* 计算每一位的进制 */ if(IsPrime(j)) PrimeList[i++] = j; do { if(scanf(\"%s%s\ break; for(i=0; i num1 = 0; breakflag = 1; p = strtok(op1,\ while(p) /* 求出第一个输入火星数的数组 */ { if( ( op1List[num1++] = atoi(p) ) != 0) breakflag = 0; p = strtok(NULL,\ } if(breakflag) break; /* 第一个输入为0，退出循环；如果放到ZOJ2529，删除本行 */ num2 = 0; breakflag = 1; p = strtok(op2,\ while(p) /* 求出第二个输入火星数的数组 */ { if( ( op2List[num2++] = atoi(p) ) != 0) breakflag =0; p = strtok(NULL,\ } if(breakflag) break; /* 第二个输入为0，退出循环；如果放到ZOJ2529，删除本行 */ num1--,num2--; /* preset num1 and num2 start from zero */ if(num1 < num2) /* 把输入的两个火星数数按位序对齐，两个if操作只执行一个 */ for(i = num1; i >= 0; --i) { op1List[i + num2 - num1] = op1List[i]; op1List[i] = 0; } if(num1 > num2) for(i = num2; i >= 0; --i) { op2List[ i + num1 - num2] = op2List[i]; op2List[i] = 0; } cnt = (num1 > num2) ? num1 : num2; /* cnt为两个火星数的较大位数，便于确定输出位数 */ for( index=0, i=cnt; i>=0 ; i--, index++ ) { num = op1List[i] + op2List[i] + OutputList[index]; if( num - PrimeList[index] >= 0 ) { OutputList[index] = num - PrimeList[index]; OutputList[index+1]++; if( index + 1 > cnt ) cnt++; /* 最高位进位 */ } else OutputList[index] = num; } while( OutputList[cnt]==0 && cnt ) cnt--; /* omit leading zeros */ for( ; cnt >=0 ; cnt-- ) printf(\"%d%c\ }while(1); return 0; } 2006年浙江大学计算机学院考研复试上机试题及参考答案(4/5) 第4题：简单计算器（7分） 题目要求：读入一个只包含 +, -, *, / 的正整数计算表达式，计算该表达式的值。 输入格式：测试输入包含若干测试用例，每个测试用例占一行，每行不超过80个字符，整数和运算符之间用一个空格分隔。没有非法表达式。当一行中只有0时输入结束，相应的结果不要输出。 输出格式：对每个测试用例输出1行，即该表达式的值，精确到小数点后2位。 输入样例： 1 + 2 4 + 2 * 5 - 7 / 11 0 输出样例： 3.00 13.36 #include int Capacity; int TopOfStack; ElementType *Array; }*Stack; Stack CreateStack(int StackSize) { Stack S S = (Stack)malloc(sizeof(struct StackRecord)); S->Capacity = StackSize; S->TopOfStack = EmptyStack; S->Array = (ElementType*)malloc(sizeof(ElementType)*StackSize); return S; } void DisposeStack(Stack S) { if(S!=NULL) /* be aware of order ! */ { free(S->Array); free(S); } } /* if stack is empty, return 1 */ int IsEmpty(Stack S) { return S->TopOfStack == EmptyStack; } /* if stack is full, return 1 */ int IsFull(Stack S) { return S->TopOfStack >= S->Capacity; } void Push(ElementType X, Stack S) { if(IsFull(S)) printf(\"Stack is full ! \\n\"); else S->Array[++S->TopOfStack] = X; } ElementType Pop(Stack S) { if(IsEmpty(S)) { printf(\"Stack is empty ! \\n\"); return 0; } return S->Array[S->TopOfStack --]; } ElementType Top(Stack S) { if(IsEmpty(S)) { printf(\"Stack is empty ! \\n\"); return 0; } else return S->Array[S->TopOfStack]; } #define NUM 1 #define OPRAND 0 #define UNKNOWN -1 struct List { int type; char opcode; float operand; }; int main(void) { unsigned char str[81]; /* index */ unsigned int num, p, index; float operand1,operand2; struct List pList[100]; /* p */ Stack S; do{ /* get input expression */ gets(str); if(strcmp(str,\"0\")==0) break; /* initialize */ S = CreateStack(100); num = p = index = 0; for(index=0;index<100;index++) { pList[index].type = UNKNOWN; pList[index].opcode = 0; pList[index].operand = 0; } /* create postfix */ for(index=0;index if(isdigit(str[index])) num = num*10 + str[index] - '0'; else num = 0; /* save number */ if(isdigit(str[index])&&(!isdigit(str[index+1]))) { pList[p].type = NUM; pList[p].operand = (float)num; p++; } /* push operand */ if(str[index]=='*'||str[index]=='/') { while(!IsEmpty(S) && (Top(S)=='*' || Top(S)=='/')) { pList[p].type = OPRAND; pList[p].opcode = (char)Pop(S); p++; } Push(str[index],S); } if(str[index]=='+'||str[index]=='-') { while(!IsEmpty(S)) { pList[p].type = OPRAND; pList[p].opcode = (char)Pop(S); p++; } Push(str[index], S); } } while(!IsEmpty(S)) { pList[p].type = OPRAND; pList[p].opcode = (char)Pop(S); p++; } /* calc postfix */ for(p=0; pList[p].type!=UNKNOWN; p++) { if(pList[p].type == NUM) Push(pList[p].operand, S); else if(pList[p].type == OPRAND) { operand2 = Pop(S); operand1 = Pop(S); switch(pList[p].opcode) { case '+' : Push( operand1 + operand2, S); break; case '-' : Push( operand1 - operand2, S); break; case '*' : Push( operand1 * operand2, S); break; case '/' : Push( operand1 / operand2, S); break; } } } printf(\"%.2f\\n\ DisposeStack(S); }while(1); return 0; } 2006年浙江大学计算机学院考研复试上机试题及参考答案(5/5) 第5题：畅通工程 （8分） [prim算法，最小生成树] 题目要求：某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。 输入格式：测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 )；随后的N(N-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。当N为0时，输入结束，该用例不被处理。 输出格式：对每个测试用例，在1行里输出最小的公路总长度。 输入样例： 3 1 2 1 1 3 2 2 3 4 4 1 2 1 1 3 4 1 4 1 2 3 3 2 4 2 3 4 5 0 输出样例： 3 5 #include #define inf 1000000000 int prim(int n,int mat[][MAXN]) { int min[MAXN],ret=0; int v[MAXN],i,j,k; for (i=0;i int main() { int n,d[MAXN][MAXN],a,b,c; while(cin>>n&&n) { for(int i=n*(n-1)/2;i;--i) { cin>>a>>b>>c; d[a-1][b-1]=d[b-1][a-1]=c; } cout< 2007年浙江大学计算机学院考研复试上机试题及参考答案(1/6) 标题：● 2007考研上机考试题目1--最小长方形(35分) Time limit: 1 Seconds Total Submit: 1216 Accepted Submit: 210 题目要求：给定一系列2维平面点的坐标(x, y)，其中x和y均为整数，要求用一个最小的长方形框将所有点框在内。长方形框的边分别平行于x和y坐标轴，点落在边上也算是被框在内。 具体的输入输出格式规定如下： 输入格式：测试输入包含若干测试用例，每个测试用例由一系列坐标组成，每对坐标占一行，其中|x|和|y|小于 231；一对0 坐标标志着一个测试用例的结束。注意(0, 0)不作为任何一个测试用例里面的点。一个没有点的测试用例标志着整个输入的结束。 输出格式：对每个测试用例，在1行内输出2对整数，其间用一个空格隔开。第1对整数是长方形框左下角的坐标，第2对整数是长方形框右上角的坐标。 输入样例： 12 56 23 56 13 10 0 0 12 34 0 0 0 0 输出样例： 12 10 23 56 12 34 12 34 #include int x1,y1,x2,y2,x,y; while(cin>>x>>y&&(x||y)){ x1=x2=x; y1=y2=y; while(cin>>x>>y&&(x||y)) x1=x1 cout< 2007年浙江大学计算机学院考研复试上机试题及参考答案(2/6) ● 2007考研上机考试题目2--统计字符(25分) Time limit: 1 Seconds Total Submit: 820 Accepted Submit: 199 题目要求：统计一个给定字符串中指定的字符出现的次数 具体的输入输出格式规定如下： 输入格式：测试输入包含若干测试用例，每个测试用例包含2行，第1行为一个长度不超过5的字符串，第2行为一个长度不超过80的字符串。注意这里的字符串包含空格，即空格也可能是要求被统计的字符之一。当读到'#'时输入结束，相应的结果不要输出。 输出格式：对每个测试用例，统计第1行中字符串的每个字符在第2行字符串中出现的次数，按如下格式输出： c0 n0 c1 n1 c2 n2 ... 其中ci是第1行中第i个字符，ni是ci出现的次数。 输入样例： I THIS IS A TEST i ng this is a long test string # 输出样例： I 2 i 3 5 n 2 g 2 注：第2个测试用例中，空格也是被统计的字符之一。 #include string pat,line; while(getline(cin,pat)&&pat!=\"#\"){ int co[5]={0,0,0,0,0}; getline(cin,line); for(int i=0,j;i 2007年浙江大学计算机学院考研复试上机试题及参考答案(3/6) ● 2007考研上机考试题目3--游船出租(18分) Time limit: 1 Seconds Total Submit: 706 Accepted Submit: 84 题目要求：现有公园游船租赁处请你编写一个租船管理系统。当游客租船时，管理员输入船号并按下S键，系统开始计时；当游客还船时，管理员输入船号并按下E键，系统结束计时。船号为不超过100的正整数。当管理员将0作为船号输入时，表示一天租船工作结束，系统应输出当天的游客租船次数和平均租船时间。 注意：由于线路偶尔会有故障，可能出现不完整的纪录，即只有租船没有还船，或者只有还船没有租船的纪录，系统应能自动忽略这种无效纪录。 具体的输入输出格式规定如下： 输入格式：测试输入包含若干测试用例，每个测试用例为一整天的租船纪录，格式为 船号（1~100） 键值（S或E） 发生时间（小时:分钟） 每一天的纪录保证按时间递增的顺序给出。当读到船号为-1时，全部输入结束，相应的结果不要输出。 输出格式：对每个测试用例输出1行，即当天的游客租船次数和平均租船时间（以分钟为单位的精确到个位的整数时间）。 输入样例： 1 S 08:10 2 S 08:35 1 E 10:00 2 E 13:16 0 S 17:00 0 S 17:00 3 E 08:10 1 S 08:20 2 S 09:00 1 E 09:20 0 E 17:00 -1 输出样例： 2 196 0 0 1 60 #include int n,t[100],h,m,co=0,to=0; char cmd[10],tt[10]; for(memset(t,-1,sizeof(t));cin>>n&&n>=0;){ cin>>cmd>>tt; if(n>0){ sscanf(tt,\"%d:%d\ if(cmd[0]=='S')t[n-1]=h*60+m; else if(t[n-1]>=0)++co,to+=h*60+m-t[n-1],t[n-1]=-1; }else{ cout< 2007年浙江大学计算机学院考研复试上机试题及参考答案(4/6) ● 2007考研上机考试题目4--EXCEL排序(18分) Time limit: 1 Seconds Total Submit: 415 Accepted Submit: 85 题目要求：Excel可以对一组纪录按任意指定列排序。现请你编写程序实现类似功能。 具体的输入输出格式规定如下： 输入格式：测试输入包含若干测试用例。每个测试用例的第1行包含两个整数 N <=100000) 和 C，其中 N 是纪录的条数，C 是指定排序的列号。以下有 N行，每行包含一条学 生纪录。每条学生纪录由学号（6位数字，同组测试中没有重复的学号）、姓名（不超过8位且不包含空格的字符串）、成绩（闭区间[0, 100]内的整数）组成，每个项目间用1个空格隔开。当读到 N=0 时，全部输入结束，相应的结果不要输出。 输出格式：对每个测试用例，首先输出1行“Case i:”，其中 i 是测试用例的编号（从1开始）。随后在 N 行中输出按要求排序后的结果，即：当 C=1 时，按学号递增排序；当C=2时，按姓名的非递减字典序排序；当 C=3 时，按成绩的非递减排序。当若干学生具有相同姓名或者相同成绩时，则按他们的学号递增排序。 输入样例： 3 1 000007 James 85 000010 Amy 90 000001 Zoe 60 4 2 000007 James 85 000010 Amy 90 000001 Zoe 60 000002 James 98 4 3 000007 James 85 000010 Amy 90 000001 Zoe 60 000002 James 90 0 0 输出样例： Case 1: 000001 Zoe 60 000007 James 85 000010 Amy 90 Case 2: 000010 Amy 90 000002 James 98 000007 James 85 000001 Zoe 60 Case 3: 000001 Zoe 60 000007 James 85 000002 James 90 000010 Amy 90 #include int n,c,aa[100010][2],ref[100010],ca=0; char ss[100010][10]; bool cmp(int a,int b) { if(c==3&&aa[a][1]!=aa[b][1])return aa[a][1] while(cin>>n>>c&&n){ printf(\"Case %d:\\n\ for(int i=0;i return 0; } 2007年浙江大学计算机学院考研复试上机试题及参考答案(5/6) ● 2007考研上机考试题目5--畅通工程(12分) Time limit: 1 Seconds Total Submit: 326 Accepted Submit: 56 题目要求：省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）。经过调查评估，得到的统计表中列出了有可能建设公路的若干条道路的成本。现请你编写程序，计算出全省畅通需要的最低成本。 具体的输入输出格式规定如下： 输入格式：测试输入包含若干测试用例。每个测试用例的第1行给出评估的道路条数 N、村庄数目M ( < 100 )；随后的 N行对应村庄间道路的成本，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间道路的成本（也是正整数）。为简单起见，村庄从1到M编号。当N为0时，全部输入结束，相应的结果不要输出。 输出格式：对每个测试用例，在1行里输出全省畅通需要的最低成本。若统计数据不足以保证畅通，则输出“?”。 输入样例： 3 3 1 2 1 1 3 2 2 3 4 1 3 2 3 2 0 100 输出样例： 3 ? #include int n,m,aa[110][110],v[110],min[110],ret,i,j,k,inf=(100<<16)+100; while(cin>>m>>n&&m){ memset(aa,100,sizeof(aa)); while(m--){ cin>>i>>j>>k; aa[j-1][i-1]=aa[i-1][j-1]=k; } for(ret=i=0;i 2007年浙江大学计算机学院考研复试上机试题及参考答案(6/6) ● 2007考研上机考试题目6--最大报销额(12分) Time limit: 1 Seconds Total Submit: 155 Accepted Submit: 3 题目要求：现有一笔经费可以报销一定额度的发票。允许报销的发票类型包括买图书（A类）、文具（B类）、差旅（C类），要求每张发票的总额不得超过1000元，每张发票上，单项物品的价值不得超过600元。现请你编写程序，在给出的一堆发票中找出可以报销的、不超过给定额度的最大报销额。 具体的输入输出格式规定如下： 输入格式：测试输入包含若干测试用例。每个测试用例的第1行包含两个正数 Q 和 N，其中Q 是给定的报销额度，N（<=30）是发票张数。随后是 N 行输入，每行的格式为： m Type_1:price_1 Type_2:price_2 ... Type_m:price_m 其中正整数 m 是这张发票上所开物品的件数，Type_i 和 price_i 是第 i 项物品的种类和价值。物品种类用一个大写英文字母表示。当N为0时，全部输入结束，相应的结果不要输出。 输出格式：对每个测试用例输出1行，即可以报销的最大数额，精确到小数点后2位。 输入样例： 200.00 3 2 A:23.50 B:100.00 1 C:650.00 3 A:59.99 A:120.00 X:10.00 1200.00 2 2 B:600.00 A:400.00 1 C:200.50 1200.50 3 2 B:600.00 A:400.00 1 C:200.50 1 A:100.00 100.00 0 输出样例： 123.50 1000.00 1200.50 #include double dfs(int cur,double v) { if(cur>=n)return v; double ret=0,ret2=dfs(cur+1,v); if(v+a[cur]<=sum+1e-8)ret=dfs(cur+1,v+a[cur]); return ret>ret2?ret:ret2; } int main() { cout.precision(2);cout.setf(ios::fixed); while(cin>>sum>>nn&&nn){ for(n=0;nn--;n+=a[n]<=1000+1e-8&&bb<=600+1e-8){ for(cin>>m,a[n]=bb=0;m--;){ cin>>ss; sscanf(ss+2,\"%lf\ bb=bb>b?bb:b; a[n]+=(ss[0]>='A'&&ss[0]<='C'?b:1001); } } cout< 因篇幅问题不能全部显示，请点此查看更多更全内容