浙大计算机学院考研复试上机试题

1、浙江大学计算机复试上机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=threefour+fivesix=zeroseven+eightnine=z

2、ero+zero=输出样例：39096#include<stdio.h>#include<string.h>#include<ctype.h>#include<malloc.h>intmain（void）constchardata126="zero","one","two","three","four","five","six","seven","eight",&quo

3、t;nine","+","="unsigneda,b;/*转换后的表达式参数，如a+b（123+456）*/unsignedi,j,k;/*临时变量，作为下标*/charstr100;/*输入字符串，足够大容量*/chartemp6;/*临时字符串，用于检索数字，如"one"->'1'*/charresult30;/*转换后的表达式参数，如"123+456="*/doa=b=i=j=k=0;/*初始化变量*/memset(str,0,sizeof(str);memset(temp,0

4、,sizeof(temp);memset(result,0,sizeof(result);gets(str);/*获取输入字符串，不能使用scanf,因为有空格*/for(i=0,k=0;i<strlen(str);+i)for(j=0;!isspace(stri)&&i<strlen(str);+i,+j)/*提取一个单词*/tempj=stri;tempj=0;/*字符串结束标记*/for(j=0;j<12;j+)/*把这个单词转换为数字*/if(strcmp(temp,dataj)=0)if(j<=9)resultk+=j+'0"

5、if(j=10)resultk+="+'if(j=11)resultk+='='break;/*找到匹配数字就不必再搜索了*/)resultk=0;/*字符串结束标记，result形式"123+456="*/sscanf(result,"%d+%d=",&a,&b);/*用sscanf来获得a,b的值*/if(a=0&&b=0)break;/*A,B同时为零则退出程序*/elseprintf("%dn",a+b);/*while(1);打印输出A+B的数值*/retur

6、n0;2005年浙江大学计算机学院考研复试上机试题及参考答案（2/5）第二题：谁是开门关门的人？（10分）题目要求：每天第一个到机房的人要把门打开，最后一个离开的人要把门关好。现有一堆杂乱的机房签到、签离记录，请根据记录找出当天开门和关门的人。输入格式：测试输入的第一行给出记录的总天数N（>0）o下面列出了N天的记每天的记录在第一行给出记录的条目数M（>0）,下面是M行，每行的格式为证件号码签到时间签离时间其中时间按“小时：分钟：秒钟”（各占2位）给出，证件号码是长度不超过15的字符串。输出格式：对每一天的记录输出1行，即当天开门和关门人的证件号码，中间用1空格分隔。注意：在裁判的

7、标准测试输入中，所有记录保证完整，每个人的签到时间在签离时间之前，且没有多人同时签到或者签离的情况。输入样例：31ME302111222532100:00:0023:59:592EE30121808:05:3520:56:35MA30113412:35:4521:40:423CS30111115:30:2817:00:10SC302123408:00:0011:25:25CS30113321:45:0021:58:40输出样例：ME3021112225321ME3021112225321EE301218MA301134SC3021234CS301133#include<stdio.h&g

8、t;#include<malloc.h>#include<string.h>typedefstructcharid16;/*证件号码长度不超过15位*/charcometime9;/*时间格式00:00:00*/charleavetime9;/*时间格式00:00:00*/Record;intmain()intN,M,i;/*记录的总天数N,每天记录的条目数M*/Record*pTimeList;/*记录该天出入人员的证件号码、进入时间、离开时间*/intfirst,last;/*记录每天开门的人和关门的人*/scanf("%d",&N);/

9、*读入记录的总天数*/while(N-)scanf("%d",&M);/*读入该天的进出人员数*/pTimeList=(Record*)malloc(M*sizeof(Record);for(i=0,first=0,last=0;i<M;+i)scanf("%s%s%s",pTimeListi.id,pTimeLetime,pTimeListi.leavetime);if(i=0)continue;elseif(strcmp(pTimeLetime,pTimeLetime)>0)

10、first=i;if(strcmp(pTimeListlast.leavetime,pTimeListi.leavetime)<0)last=i;/*fori*/printf("%s%sn",pTimeListfirst.id,pTimeListlast.id);free(pTimeList);/*forN*/2005年浙江大学计算机学院考研复试上机试题及参考答案（3/5）第三题：分数统计（12分）题目要求：今天的上机考试虽然有实时的Ranklist，但上面的排名只是根据完成的题数排序，没有考虑每题的分值，所以并不是最后的排名。给定录取分数线，请你写程序找出最后通过分

11、数线的考生，并将他们的成绩按降序打印。输入格式：测试输入包含若干场考试的信息。每场考试信息的第1行给出考生人数N（0<N<1000）、考题数M（0<M<=10）、分数线（正整数）G;第2行排序给出第1题至第M题的正整数分值；以下N行，每行给出一名考生的准考证号（长度不超过20的字符串）、该生解决的题目总数m以及这m道题的题号（题目号由1到M）。当读入的考生人数为0时，输入结束，该场考试不予处理。输出格式：对每场考试，首先在第1行输出不低于分数线的考生人数n,随后n行按分数从高到低输出上线考生的考号与分数，其间用1空格分隔。若有多名考生分数相同，则按他们考号的升序输出。输

12、入样例：45251010121315CS0043513CS003524135CS002212CS001323512401030CS001122320101010CS0000000000000000010CS0000000000000000022120输出样例：3CS00360CS00137CS0043701CS00000000000000000220#include<stdio.h>#include<malloc.h>#include<string.h>typedefstructcharid21;/*准考证号(<=20字符)*/intscore;/*该

13、考生总分*/intmain()intN,M,G,n;/*int*pMarkList;/*/StuInfo;考生人数，题目数，分数线，上线考生数量第1题至第M题的正整数分值*/StuInfo*pStuinfo;/*考生信息*/临时变量*/StuInfotmp;/*用于排序*/while(scanf("%d",&N)&&N!=0)/*读入考生人数N*/(scanf("%d%d",&M,&G);/*读入题目数量和分数线*/pMarkList=(int*)malloc(M*sizeof(int);/*M道题目的分数*/pS

14、tuinfo=(StuInfo*)malloc(N*sizeof(StuInfo);/*N个考生*/for(i=0;i<M;+i)/*读入M题每题分数*/scanf("%d",&(pMarkListi);for(i=0,n=0;i<N;+i)/*读入N个考生信息，i用于计数N次,cnt用于计算上线考生记录*/(scanf("%s%d",&(pStuinfon.id),&m);/*准考证号，解出的题目数量m*/for(pStuinfon.score=0,j=0;j<m;+j)/*读入答出的m题的题号*/(scanf

15、("%d",&a);/*读入答对题的题号*/pStuinfon.score+=pMarkLista-1;/*因为题号是从1开始的；计算该考生的总分*/)if(pStuinfon.score>=G)/*如果考生上线则记录下来*/n+;/*否则不予记录，便于排序*/for(i=0;i<n-1;+i)/*输入完毕，对上线考生先按分数排序，降序*/(for(k=i,j=i+1;j<n;+j)if(pStuinfoj.score>pStuinfok.score)k=j;tmp=pStuinfok;pStuinfok=pStuinfoi;pStuinfo

16、i=tmp;for(i=0;i<n;i+=k)/*相同总分考生再按照准考证号排序*/(/*统计相同分数考生人数k*/for(k=1,j=i+1;j<n;+j)(if(pStuinfoi.score=pStuinfoj.score)k+;elsebreak;/*下标i到i+k的考生分数相同，对这k个考生排序，升序*/for(a=i;a<=i+k-1;a+)(for(c=a,b=a+1;b<=i+k;b+)if(strcmp(pStuinfoc.id,pStuinfob.id)>0)c=b;tmp=pStuinfoa;pStuinfoa=pStuinfoc;pStui

17、nfoc=tmp;)printf("%dn",n);/*排序完毕，按照要求输出，上线人数*/for(i=0;i<n;+i)/*和每个上线考生的准考证号和总分数*/printf("%s%dn",pStuinfoi.id,pStuinfoi.score)；free(pMarkList);free(pStuinfo);)return0;)2005年浙江大学计算机学院考研复试上机试题及参考答案（4/5）第四题：最大连续子序列（13分）题目要求：给定K个整数的序列N1,N2,.,NK,其任意连续子序列可表示为Ni,Ni+1,.,Nj，其中1<=i<

18、;=j<=K。最大连续子序列是所有连续子序列中元素和最大的一个，例如给定序列-2,11,-4,13,-5,-2,其最大连续子序列为11,-4,13,最大和为20。在今年的数据结构考卷中，要求编写程序得到最大和，现在增加一个要求，即还需要输出该子序列的第一个和最后一个元素。输入格式：测试输入包含若干测试用例，每个测试用例占2行，第1行给出正整数K（<10000）,第2行给出K个整数，中间用空格分隔。当K为0时，输入结束，该用例不被处理。输出格式：对每个测试用例，在1行里输出最大和、最大连续子序列的第一个和最后一个元素，中间用空格分隔。如果最大连续子序列不唯一，则输出序号i和j最小的那

19、个(如输入样例的第2、3组)。若所有K个元素都是负数，则定义其最大和为0,输出整个序列的首尾元素。输入样例：6-211-413-5-210-101234-5-2337-2165-832501103-1-5-23-10-20输出样例：201113101410351010100-1-2000#include<stdio.h>#include<malloc.h>#include<limits.h>intmain()longintK,last;/*输入数据个数K<1000；最大子序列最后一个元素的下标last*/longintThisSum,MaxSum,Tm

20、pMaxSum,index,*pList;while(scanf("%d",&K)&&K)ThisSum=0;MaxSum=TmpMaxSum=last=LONG_MIN;pList=(longint*)malloc(K*sizeof(longint);for(index=0;index<K;index+)scanf("%d”,&(pListindex);ThisSum+=pListindex;if(ThisSum>MaxSum)/*输入含有正数时，忽略最大子序列中首尾0的影响*/MaxSum=ThisSum;/*更新M

21、axSum*/if(MaxSum>TmpMaxSum)/*最大值更新时，更新最大子序列最后的数字*/*保证最大子序列起始位置在输入用的最前面*/TmpMaxSum=MaxSum;last=index;)if(ThisSum<0)ThisSum=0;)/*tracebacktofindfirstnumberofthemaxsubsequence*/for(TmpMaxSum=0,index=last;index>=0;index-)TmpMaxSum+=pListindex;if(TmpMaxSum=MaxSum)break;)if(MaxSum<0)/*K个数字都是负数

22、，定义最大和为0,输出首尾元素*/printf("%ld%ld%ldn",0,pList0,pListK-1);elseprintf("%ld%ld%ldn",MaxSum,pListindex,pListlast);free(pList);)return0;)2005年浙江大学计算机学院考研复试上机试题及参考答案（5/5）第五题：畅通工程（15分）题目要求：某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）

23、。问最少还需要建设多少条道路？输入格式：测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是城镇数目N（<1000）和道路数目M;随后的M行对应M条道路，每行给出一对正整数，分别是该条道路直接连通的两个城镇的编号。为简单起见，城镇从1到N编号。当N为0时，输入结束，该用例不被处理。输出格式：对每个测试用例，在1行里输出最少还需要建设的道路数目输入样例：421343331 22 35 2123599900输出样例：102998#include<iostream>#include<vector>usingnamespacestd;intn,visite

24、d1024;vector<vector<int>>connect(1024,vector<int>(1024);intdfs(inta)inti;visiteda=1;for(i=1;i<=n;i+)if(connectai=1&&visitedi=0)dfs(i);return(0);intmain(intargc,char*argv)inti,j,a,b,count=-1;intnumtown,numroad;while(cin>>numtown&&numtown!=0)cin>>numroa

25、d;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;i<=numroad;i+)cin>>a>>b;connectab=connectba=1;for(j=1;j<=numtown;j+)connectij=0;for(i=1;i<=numtown;i+)visitedi=0;for(i=1;i<=numroad;i+)(cin>>a>>b;

26、connectab=connectba=1;)for(i=1;i<=numtown;i+)if(visitedi=0)(dfs(i);count+;)cout<<count<<endl;)return0;)2006年浙江大学计算机学院考研复试上机试题及参考答案(1/5)第一题：A+B（16分）题目要求：读入两个小于10000的正整数A和B,计算A+B。需要注意的是：如果A和B的末尾K（不超过8）位数字相同，请直接输出-1。输入格式：测试输入包含若干测试用例，每个测试用例占一行，格式为"ABK”,相邻两数字有一个空格间隔。当A和B同时为0时输入结束，相应的

27、结果不要输出。输出格式：对每个测试用例输出1行，即A+B的值或者是-1输入样例：I 21II 2111088236643001输出样例：3-1-1100#include<stdio.h>#include<string.h>intmain(void)(unsignedinta,b,k;unsignedcharch150,ch250;doscanf("%d%d%d",&a,&b,&k);if(a=0&&b=0|k>8)break;sprintf(ch1,"%d",a);sprintf(ch

28、2,"%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);elseprintf("%dn",a+b);while(1);return0;2006年浙江大学计算机学院考研

29、复试上机试题及参考答案（2/5）2007-03-3121:44:14太史小第二题：统计同成绩学生人数（12分）题目要求：读入N名学生的成绩，将获得某一给定分数的学生人数输出输入格式：测试输入包含若干测试用例，每个测试用例的格式为第1行：N第2行：N名学生的成绩，相邻两数字用一个空格间隔。第3行：给定分数当读到N=0时输入结束。其中N不超过1000,成绩分数为(包含)0到100之间的一个整数。输出格式：对每个测试用例，将获得给定分数的学生人数输出。输入样例：38060906028566056075905575750输出样例：102#include<stdio.h>#include&l

30、t;malloc.h>intmain(void)unsignedN,score,num,i;unsignedpList1000;doscanf("%d",&N);if(N=0)break;for(i=0;i<N;i+)scanf("%d”,&pListi);scanf("%d”,&score);for(num=0,i=0;i<N;i+)if(pListi=score)num+;printf("%dn",num);while(1);return0;2006年浙江大学计算机学院考研复试上机试题及参

31、考答案（3/5）第三题：火星A+B（7分）（ZOJACM2529）题目要求：读入两个不超过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时输入结束，相应的结果不要输出。

32、输出格式：对每个测试用例输出1行，即火星表示法的A+B的值。输入样例：1,02,14,2,01,2,0110,6,4,2,100输出样例：1,0,11,1,1,01,0,0,0,0,0=我的代码=测试用例和输出结果：1,02,11.0,14,2,01,2,01,1,1,0110,6,4,2,11,0,0,0,0,00,1,0,10,0,1,11,2,00,0,0,0,11,0,01,0,10,0,0,10,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,196,88,82,78,7

33、2,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,00,1,0Pressanykeytocontinue#include<stdio.h>#include<string.h>#include<stdlib.h>#defineN25intIsPrime(intn)inti;if(n<2)return0;for(i=2;i<n;i+)if

34、(n%i=0)return0;return1;intmain(void)charop1300,op2300,*p;inti,j,index,num,num1,num2,cnt,breakflag;intPrimeListN+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;i<N;i+)OutputListi=op1Listi=op2Li

35、sti=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,退出循环；如果放到删除本行*/num2=0;breakflag=1;p=strtok(op2,",");while(p)/*求出第二个输入火星数的数组*/(if(op2Listnum2+=atoi(

36、p)!=0)breakflag=0;p=strtok(NULL,",");)if(breakflag)break;/*第二个输入为0,退出循环；如果放到删除本行*/num1-,num2-;/*presetnum1andnum2startfromzero*/if(num1<num2)/*把输入的两个火星数数按位序对齐，两个if一个*/for(i=num1;i>=0;-i)(op1Listi+num2-num1=op1Listi;op1Listi=0;)ZOJ2529,ZOJ2529,操作只执行if(num1>num2)for(i=num2;i>=0;-

37、i)(op2Listi+numl-num2=op2Listi;op2Listi=0;)cnt=(numl>num2)?numl: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+;/*最高位进位*/)elseOutputLi

38、stindex=num;)while(OutputListcnt=0&&cnt)cnt-;/*omitleadingzeros*/for(;cnt>=0;cnt-)printf("%d%c",OutputListcnt,(cnt=0)?'n':',');while(1);return0;2006年浙江大学计算机学院考研复试上机试题及参考答案（4/5）第4题：简单计算器（7分）题目要求：读入一个只包含+,-,*,/的正整数计算表达式，计算该表达式的值。输入格式：测试输入包含若干测试用例，每个测试用例占一行，每行不超过80个

39、字符，整数和运算符之间用一个空格分隔。没有非法表达式。当一行中只有0时输入结束，相应的结果不要输出。输出格式：对每个测试用例输出1行，即该表达式的值，精确到小数点后2位。输入样例：1 +24+2*5-7/110输出样例：3.0013.36#include<string.h>#include<ctype.h>#include<stdio.h>#include<malloc.h>#defineEmptyStack(-1)typedeffloatElementType;typedefstructStackRecordintCapacity;intTopOfStack;ElementType*Array;*Stack;StackCreateStack(intStackSize)StackSS=(Stack)malloc(sizeof(structStackRecord);S->Capacity=StackSize;S->Top