浙大计算机学院考研复试上机试题及参考答案.doc

浙江大学计算机复试上机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 =输出样例：39096#include #include #include #include int main(void)const char data126 = zero, one, two, three, four,five, six, seven, eight, nine, +, =;unsigned a, b;/* 转换后的表达式参数,如a+b(123+456)*/unsigned i, j, k;/* 临时变量，作为下标*/char str100;/* 输入字符串，足够大容量*/char temp6;/* 临时字符串，用于检索数字，如one-1*/char result30;/* 转换后的表达式参数，如123+456=*/doa = 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; istrlen(str); +i)for(j=0;!isspace(stri)&istrlen(str);+i,+j) /* 提取一个单词 */tempj = stri;tempj = 0; /* 字符串结束标记 */for(j=0; j12; j+)/* 把这个单词转换为数字 */if(strcmp(temp, dataj) = 0)if( j 0 )。下面列出了N天的记录。每天的记录在第一行给出记录的条目数M ( 0 )，下面是M行，每行的格式为证件号码 签到时间 签离时间其中时间按“小时:分钟:秒钟”（各占2位）给出，证件号码是长度不超过15的字符串。输出格式：对每一天的记录输出1行，即当天开门和关门人的证件号码，中间用1空格分隔。注意：在裁判的标准测试输入中，所有记录保证完整，每个人的签到时间在签离时间之前，且没有多人同时签到或者签离的情况。输入样例：31ME3021112225321 00:00:00 23:59:592EE301218 08:05:35 20:56:35MA301134 12:35:45 21:40:423CS301111 15:30:28 17:00:10SC3021234 08:00:00 11:25:25CS301133 21:45:00 21:58:40输出样例：ME3021112225321 ME3021112225321EE301218 MA301134SC3021234 CS301133#include #include #include typedef structchar id16;/* 证件号码长度不超过15位 */char cometime9;/* 时间格式00:00:00 */char leavetime9;/* 时间格式00:00:00 */Record;int main()int N, M, i;/* 记录的总天数N，每天记录的条目数M */Record *pTimeList;/* 记录该天出入人员的证件号码、进入时间、离开时间 */int first, last;/* 记录每天开门的人和关门的人 */scanf(%d,& N);/* 读入记录的总天数 */while(N-)scanf(%d, & M);/* 读入该天的进出人员数 */pTimeList = (Record *)malloc(M*sizeof(Record);for(i=0,first=0,last=0; i 0 )first = i;if( strcmp( pTimeListlast.leavetime, pTimeListi.leavetime) 0)last = i; /* for i */printf(%s %sn, pTimeListfirst.id, pTimeListlast.id);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 2510 10 12 13 15CS004 3 5 1 3CS003 5 2 4 1 3 5CS002 2 1 2CS001 3 2 3 51 2 4010 30CS001 1 22 3 2010 10 10CS000000000000000001 0CS000000000000000002 2 1 20输出样例：3CS003 60CS001 37CS004 3701CS000000000000000002 20#include #include #include typedef struct char id21;/* 准考证号(=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 ) & N!=0 )/* 读入考生人数N */ scanf(%d%d, &M, &G);/* 读入题目数量和分数线 */ pMarkList = (int *)malloc(M*sizeof(int);/* M道题目的分数 */ pStuinfo = (StuInfo *)malloc(N*sizeof(StuInfo);/* N个考生 */ for(i=0; iM; +i)/* 读入M题每题分数 */ scanf(%d, & (pMarkListi) ); for(i=0, n=0; iN; +i)/* 读入N个考生信息，i用于计数N次，cnt用于计算上线考生记录 */ scanf(%s%d, & (pStuinfon.id), &m);/* 准考证号，解出的题目数量m */ for(pStuinfon.score=0,j=0; j= G)/* 如果考生上线则记录下来 */ n+; /* 否则不予记录，便于排序 */ for(i=0; in-1; +i)/* 输入完毕，对上线考生先按分数排序，降序 */ for(k=i, j=i+1; j pStuinfok.score) k = j;tmp = pStuinfok;pStuinfok = pStuinfoi;pStuinfoi = tmp; for(i=0; in; i+=k) /* 相同总分考生再按照准考证号排序 */ /* 统计相同分数考生人数k */ for(k=1,j=i+1; jn; +j) if(pStuinfoi.score = pStuinfoj.score) k+; else break; /* 下标i到i+k的考生分数相同，对这k个考生排序，升序 */ for(a=i; a=i+k-1; a+) for(c=a, b=a+1; b 0) c = b;tmp = pStuinfoa;pStuinfoa = pStuinfoc;pStuinfoc = tmp; printf(%dn,n);/* 排序完毕，按照要求输出，上线人数 */ for(i=0; in; +i)/* 和每个上线考生的准考证号和总分数 */ printf(%s %dn,pStuinfoi.id,pStuinfoi.score); free(pMarkList); free(pStuinfo); 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 -210-10 1 2 3 4 -5 -23 3 7 -2165 -8 3 2 5 01103-1 -5 -23-1 0 -20输出样例：20 11 1310 1 410 3 510 10 100 -1 -20 0 0#include #include #include int main()long int K, last; /* 输入数据个数K1000；最大子序列最后一个元素的下标last */long int ThisSum, MaxSum, TmpMaxSum, index, *pList;while( scanf(%d, &K) & K )ThisSum = 0;MaxSum = TmpMaxSum = last = LONG_MIN;pList = (long int *)malloc( K * sizeof(long int) );for(index = 0; index MaxSum)/* 输入含有正数时，忽略最大子序列中首尾0的影响 */MaxSum = ThisSum;/* 更新MaxSum */if( MaxSum TmpMaxSum )/* 最大值更新时，更新最大子序列最后的数字 */* 保证最大子序列起始位置在输入串的最前面 */TmpMaxSum = MaxSum;last = index;if( ThisSum = 0; index- )TmpMaxSum += pListindex;if(TmpMaxSum = MaxSum)break;if( MaxSum 0 ) /* K个数字都是负数，定义最大和为0，输出首尾元素 */printf(%ld %ld %ldn, 0, pList0, pListK-1);elseprintf(%ld %ld %ldn, MaxSum, pListindex, pListlast );free(pList);return 0; 2005年浙江大学计算机学院考研复试上机试题及参考答案(5/5) 第五题：畅通工程（15分）题目要求：某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？输入格式：测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是城镇数目N ( 1000 )和道路数目M；随后的M行对应M条道路，每行给出一对正整数，分别是该条道路直接连通的两个城镇的编号。为简单起见，城镇从1到N编号。当N为0时，输入结束，该用例不被处理。输出格式：对每个测试用例，在1行里输出最少还需要建设的道路数目。输入样例：4 21 34 33 31 22 35 21 23 5999 00输出样例：102998#include#includeusing namespace std;int n, visited1024;vectorvector connect(1024,vector(1024);int dfs(int a)int i;visiteda=1;for(i=1;inumtown & numtown!=0)cinnumroad;n = numtown;for(i=1;i=numtown;i+)for(j=1;j=numtown;j+)connectij = 0;for(i=1;i=numtown;i+)visitedi = 0;for(i=1;iab;connectab = connectba = 1;for(j=1;j=numtown;j+)connectij = 0;for(i=1;i=numtown;i+)visitedi = 0;for(i=1;iab;connectab = connectba = 1;for(i=1;i=numtown;i+)if (visitedi=0)dfs(i);count+;coutcountendl;return 0; 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 111 21 1108 8 236 64 30 0 1输出样例：3-1-1100#include #include int main(void)unsigned int a, b, k;unsigned char ch150, ch250;do scanf(%d %d %d, &a, &b, &k); if( a=0&b=0 | k8 ) break; sprintf(ch1, %d, a); sprintf(ch2, %d, b); strrev(ch1);strrev(ch2); if(strlen(ch1)k)strncat(ch1+strlen(ch1)-1,00000000,8); if(strlen(ch2)k)strncat(ch2+strlen(ch2)-1,00000000,8); if(strncmp(ch1,ch2,k)=0) printf(%dn,-1); else printf(%dn,a+b);while(1);return 0; 2006年浙江大学计算机学院考研复试上机试题及参考答案(2/5) 2007-03-31 21:44:14 大 中 小 第二题：统计同成绩学生人数（12分）题目要求：读入N名学生的成绩，将获得某一给定分数的学生人数输出。输入格式：测试输入包含若干测试用例，每个测试用例的格式为第1行：N第2行：N名学生的成绩，相邻两数字用一个空格间隔。第3行：给定分数当读到N=0时输入结束。其中N不超过1000，成绩分数为（包含）0到100之间的一个整数。输出格式：对每个测试用例，将获得给定分数的学生人数输出。输入样例：380 60 9060285 660560 75 90 55 75750输出样例：102#include #include int main(void)unsigned N, score, num, i;unsigned pList1000;doscanf(%d,&N);if(N=0) break;for(i=0;iN;i+) scanf(%d, &pListi);scanf(%d,&score);for(num=0,i=0;iN;i+) if(pListi=score) num+;printf(%dn, num);while(1);return 0; 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,14,2,0 1,2,01 10,6,4,2,10 0输出样例：1,0,11,1,1,01,0,0,0,0,0=我的代码=测试用例和输出结果：1,0 2,11,0,14,2,0 1,2,01,1,1,01 10,6,4,2,11,0,0,0,0,00,1,0,1 0,0,1,11,2,00,0,0,0,1 1,0,01,0,10,0,0,1 0,0,0,0,0,11,096,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,11,96,88,82,78,72,70,66,60,58,52,46,42,40,36,30,28,22,18,16,12,10,6,4,2,00,0,0 0,1,0Press any key to continue#include #include #include #define N 25int IsPrime(int n)int i;if(n2)return 0;for(i=2; in; i+)if(n%i=0) return 0;return 1;int main(void)char op1300, op2300, *p;int i, j, index, num, num1, num2, cnt, breakflag;int PrimeListN+1, op1ListN, op2ListN, OutputListN+1;for(i = 0, j = 0; i N+1; j+)/* 计算每一位的进制 */if(IsPrime(j) PrimeListi+ = j;doif(scanf(%s%s, op1, op2) = EOF)break;for(i=0; iN; i+)OutputListi = op1Listi = op2Listi = 0;OutputListN = 0;num1 = 0; breakflag = 1; p = strtok(op1,);while(p) /* 求出第一个输入火星数的数组 */if( ( op1Listnum1+ = atoi(p) ) != 0)breakflag = 0;p = strtok(NULL,);if(breakflag) break; /* 第一个输入为0，退出循环；如果放到ZOJ2529，删除本行 */num2 = 0; breakflag = 1; p = strtok(op2,);while(p) /* 求出第二个输入火星数的数组 */if( ( op2Listnum2+ = atoi(p) ) != 0)breakflag =0;p = strtok(NULL,);if(breakflag) break; /* 第二个输入为0，退出循环；如果放到ZOJ2529，删除本行 */num1-,num2-;/* preset num1 and num2 start from zero */if(num1 = 0; -i)op1Listi + num2 - num1 = op1Listi;op1Listi = 0;if(num1 num2)for(i = num2; i = 0; -i)op2List i + num1 - num2 = op2Listi;op2Listi = 0;cnt = (num1 num2) ? num1 : num2; /* cnt为两个火星数的较大位数，便于确定输出位数 */for( index=0, i=cnt; i=0 ; i-, index+ )num = op1Listi + op2Listi + OutputListindex;if( num - PrimeListindex = 0 )OutputListindex = num - PrimeListindex;OutputListindex+1+;if( index + 1 cnt ) cnt+; /* 最高位进位 */elseOutputListindex = num;while( OutputListcnt=0 & cnt ) cnt-; /* omit leading zeros */for( ; cnt =0 ; cnt- )printf(%d%c, OutputListcnt, (cnt=0)?n:,);while(1);return 0; 2006年浙江大学计算机学院考研复试上机试题及参考答案(4/5) 第4题：简单计算器（7分）题目要求：读入一个只包含 +, -, *, / 的正整数计算表达式，计算该表达式的值。输入格式：测试输入包含若干测试用例，每个测试用例占一行，每行不超过80个字符，整数和运算符之间用一个空格分隔。没有非法表达式。当一行中只有0时输入结束，相应的结果不要输出。输出格式：对每个测试用例输出1行，即该表达式的值，精确到小数点后2位。输入样例：1 + 24 + 2 * 5 - 7 / 110输出样例：3.0013.36#include #include #include #include #define EmptyStack (-1)typedef float ElementType;typedef struct StackRecord 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-ArrayS-TopOfStack -;ElementType Top(Stack S) if(IsEmpty(S) printf(Stack is empty ! n); return 0; else return S-ArrayS-TopOfStack;#define NUM 1#define OPRAND 0#define UNKNOWN -1struct List int type; char opcode; float operand;int main(void) unsigned char str81; /* index */ unsigned int num, p, index; float operand1,operand2; struct List pList100; /* 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;index100;index+) pListindex.type = UNKNOWN; pListindex.opcode = 0; pListindex.operand = 0; /* create postfix */ for(index=0;indexstrlen(str);index+) /* create number */ if(isdigit(strindex) num = num*10 + strindex - 0; else num = 0; /* save number */ if(isdigit(strindex)&(!isdigit(strindex+1) pListp.type = NUM; pListp.operand = (float)num; p+; /* push operand */ if(strindex=*|strindex=/) while(!IsEmpty(S) & (Top(S)=* | Top(S)=/) pListp.type = OPRAND; pListp.opcode = (char)Pop(S); p+; Push(strindex,S); if(strindex=+|strindex=-) while(!IsEmpty(S) pListp.type = OPRAND; pListp.opcode = (char)Pop(S); p+; Push(strindex, S); while(!IsEmpty(S) pListp.type = OPRAND; pListp.opcode = (char)Pop(S); p+; /* calc postfix */ for(p=0; pListp.type!=UNKNOWN; p+) if(pListp.type = NUM) Push(pListp.operand, S); else if(pListp.type = OPRAND) operand2 = Pop(S); operand1 = Pop(S); switch(pListp.opcode) case + : Push( operand1 + operand2, S); break; case - : Push(