1、浙大计算机学院考研复试上机试题及参考答案浙江大学计算机复试上机 2005-2007（由林子整理 ）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
2、 + five six =zero seven + eight nine =zero + zero =输出样例：9096#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; /* 输入字符串，足够大容量
3、*/char temp6; /* 临时字符串，用于检索数字，如one-1 */char result30; /* 转换后的表达式参数，如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)
4、;+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 空格分隔。注意：在裁判的标准测试输
5、入中，所有记录保证完整，每个人的签到时间在签离时间之前，且没有多人同时签到或者签离的情况。输入样例：31ME25321 00:00:00 23:59:59EE301218 08:05:35 20:56:35MA301134 12:35:45 21:40:42 3CS301111 15:30:28 17:00:10SC3021234 08:00:00 11:25:25CS301133 21:45:00 21:58:40输出样例：ME25321 ME25321EE301218 MA301134SC3021234 CS301133#include #include #include typedef
6、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); /
7、* 读入该天的进出人员数 */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)第三题：
8、分数统计( 12 分)题目要求：今天的上机考试虽然有实时的 Ranklist ，但上面的排名只是根据完成的题数排序，没有考虑每题的分值，所以并不是最后的排名。给定录取分数线，请你写程序找出最后通过分数线的考生，并将他们的成绩按降序打印。输入格式：测试输入包含若干场考试的信息。每场考试信息的第 1 行给出考生人数 N （ 0 N 1000 ） 、考题数 M （ 0 M = 10） 、分数线（正整数） G；第 2 行排序给出第 1 题至第 M题的正整数分值；以下 N行，每行给出一名考生的准考证号（长度不超过 20 的字符串）、该生解决的题目总数 m、以及这 m道题的题号（题目号由 1 到 M）。当
9、读入的考生人数为 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 20 10 10 10CS000000000000000001 0CS000000000000000002 2 1 20输出样例：3CS003 60C
10、S001 37CS004 3701CS000000000000000002 20#include #include #include typedef structchar 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
11、; /* 用于排序 */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 个考生 */*/scanf(%d, & (pMarkListi) );for(i=0, n=0; iN; +i) /* 读入 N个考生信息， i 用于计数 N次， cnt 用于计算上线考生记录 */s
12、canf(%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; jpStuinfok.score)k = j;tmp = pStuinfok;pStuinfok = pStuinfoi;pStuinfoi = tmp;for(i=0; in; i+=k) /* 相同总分考生再按照准考证号排序 */* 统
13、计相同分数考生人数 k */for(k=1,j=i+1; jn; +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 0)c = b;tmp = pStuinfoa;pStuinfoa =pStuinfoc;pStuinfoc = tmp;输出，上线人数 */准考证号和总分数 */printf(%s %dn,pStuinfoi.id,pStuinfoi.score);free(pMarkLi
14、st);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。在今年的数据结构考卷中，要求编写程序得到最大和，现在增加一个要求，即还需要输出该子序列的第一个和最后一个元素。输入格式
15、： 测试输入包含若干测试用例， 每个测试用例占 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
16、 -2-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 )MaxSum = TmpMaxSum = last = LONG_MIN; pList = (long int *)malloc( K * size
17、of(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
18、 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 分)题目要求： 某省调查城镇交通状况， 得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通(但不一定有直接的道路相连，只要互相间接
19、通过道路可达即可)。问最少还需要建设多少条道路？输入格式：测试输入包含若干测试用例。每个测试用例的第 1行给出两个正整数，分别是城镇数目 N ( 1000 ) 和道路数目M； 随后的 M行对应 M条道路， 每行给出一对正整数， 分别是该条道路直接连通的两个城镇的编号。为简单起见，城镇从 1 到N编号。当 N为 0时，输入结束，该用例不被处理。输出格式：对每个测试用例，在 1 行里输出最少还需要建设的道路数目。输入样例：1 34 33 31223521 23 5999 00输出样例：102998#include#include using namespace std;int n, visited
20、1024;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 ;i=numroad;i+)cinab;connectab = connectba = 1;for(j=1 ;j=numtown;j+)con
21、nectij = 0;for(i=1 ;i=numtown;i+)visitedi = 0;for(i=1 ;i=numroad;i+)cinab;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 。
22、输入格式： 测试输入包含若干测试用例， 每个测试用例占一行，格式为 A B K，相邻两数字有一个空格间隔。当 A和 B同时为0 时输入结束，相应的结果不要输出。输出格式：对每个测试用例输出 1 行，即 A+B的值或者是 -1输入样例：I2 1II21 1108 8 236 64 30 0 1输出样例：3-1-1100#include #include int main(void)unsigned int a, b, k;unsigned char ch150, ch250;doscanf(%d %d %d, &a, &b, &k);if( a=0&b=0 | k8 ) break;sprint
23、f(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,0000000 0,8);if(strncmp(ch1,ch2,k)=0)printf(%dn,-1);elseprintf(%dn,a+b);while(1);return 0;2006 年浙江大学计算机学院考研复试上机试题及参考答案(2/5)大中小第二题：统计同成绩学生人数（ 12 分
24、）题目要求：读入 N名学生的成绩，将获得某一给定分数的学生人数输出。输入格式：测试输入包含若干测试用例，每个测试用例的格式为第 1 行： N第 2 行： N 名学生的成绩，相邻两数字用一个空格间隔。第 3 行：给定分数当读到 N=0时输入结束。其中 N不超过 1000，成绩分数为（包含） 0 到 100 之间的一个整数。输出格式： 对每个测试用例， 将获得给定分数的学生人数输出。输入样例：380 60 9060285 66 0560 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(p
