华东师范大学计算机机试真题

1、华东师范大学计算机机试真题2009机试 2计算和的数位 2大写改小写 3素数对 4求最大公约数和最小公倍数 6排序后求位置处的数 7* 路由器连接 8* 编译原理 10* 分开连接 13 2010机试 17ECNU 勺含义 17空瓶换啤酒 18统计字符 20 2010机试热身 21粽子买三送一，买五送21工程流水线问题 222011试 24helloworld24Specialjudge 26查询成282011 机试热身 30贪吃蛇 30仰望星空 34* 编辑距离 362012试 38字母排序 38幸运数 39十六进制的加法 42电话号码簿合并排序 42* 五子棋 43* 正则表达式匹配 45

2、2013机试 46斐波那契数列的素数个数 46*将a字符变成b字符最少修改次数 . 472013 机试热身 49去重排序 49蛇形图案 51数学手稿 542009机试计算和的数位Sum of digitDescriptionWrite a program which computes the digit number of sum of two integers a and b.InputThe first line of input gives the number of cases, N(1 ? N ? 100). N test cases follow.Each test case co

3、nsists of two integers a and b which are separeted by a space in a line.(0=a,b=100000000).OutputFor each test case, print the number of digits of a + b.Sample Input35 71 991000 999Sample Output234#include int main()int n;int a,b;int sum;while(scanf(%d,&n)!=EOF)while(n-)int an=0;scanf(%d%d,&a,&b);sum

4、=a+b;while(sum)an+;sum/=10;printf(%dn,an+); return 0;大写改小写CapitalizeDescriptionWrite a program which replace all the lower-case letters of a given text with the correspondingcaptital letters.InputA text including lower-case letters, periods, and space.OutputOutput The converted text.Sample Inputwelc

5、ome to east china normal university.Sample OutputWELCOME TO EAST CHINA NORMAL UNIVERSITY.#include#includechar str1000;int main()int l;while(gets(str)l=strlen(str);int i;for(i=0;i=a&stri=z) printf(%c,stri-32); else printf(%c,stri);printf(n);return 0;素数对Primes PairDescriptionWe arrange the numbers bet

6、ween 1 and N (1 = N = 10000) in increasing order and decreasingorder like this:1 2 3 4 5 6 7 8 9 . . . N N . . . 9 8 7 6 5 4 3 2 1Two numbers faced each other form a pair. Your task is to compute the number of pairs P suchthat both numbers in the pairs are prime.InputThe first line of input gives th

7、e number of cases, C (1 ? C ? 100).C test cases follow.Each test case consists of an integer N in one line.OutputFor each test case, output P . Sample Input414751Sample Output022#include#includebool prime10005;void init()int i;int j;prime0=prime1=false;/ 不是素数prime2=true;/ 是素数for(i=3;i=10005;i+=2)pri

8、mei=true;/ 是素数primei+1=false;/ 不是素数除 0 和 2 之外的偶数都不是素数for(i=3;i=10005;i+=2)if(primei=true)/ 是素数j=i+i;while(j=10005) primej=false;/ 不是素数j+=i;int main()int c;int n;init();/ 初始化while(scanf(%d,&c)!=EOF)while(c-)scanf(%d,&n); int sum=0;int i;for(i=2;i=n/2;i+)if(primei=true&primen+1-i=true) sum+;sum*=2;if(

9、n%2=1)/n 为奇数if(primen/2+1=true)sum+=1;printf(%dn,sum); return 0;求最大公约数和最小公倍数GCD and LCMDescriptionWrite a program which computes the greatest common divisor (GCD) and the least commonmultiple (LCM) of given a and b (0 a, b ? 44000).InputThe first line of input gives the number of cases, N(1 ? N ? 10

10、0). N test cases follow.Each test case contains two interger a and b separated by a single space in a line.OutputFor each test case, print GCD and LCM separated by a single space in a line.Sample Input28 65000 3000Sample Output2 241000 15000#include int getgcd(int a,int b) int gcd;int t1,t2;t1=a;t2=

11、b;gcd=t1%t2;while(gcd!=0)t1=t2;t2=gcd;gcd=t1%t2;return t2;int main()int n;int a,b;while(scanf(%d,&n)!=EOF)while(n-)scanf(%d%d,&a,&b);printf(%d %dn,getgcd(a,b),a*b/(getgcd(a,b);return 0;排序后求位置处的数Sort it DescriptionThere is a database,partychen want you to sort the database s datain the order from the

12、 least up to the greatest element,then do the query: Which element is i-th by its value?- with i being a natural number in a range from 1 to N.It should be able to process quickly queries like this.InputThe standard input of the problem consists of two parts. At first, a database is written, and the

13、n theres a sequence of queries. The format of database is very simple: in the first line theres a number N (1=N=100000), in the next N lines there are numbers of the database one in each line in an arbitrary order. A sequence of queries is written simply as well: in the first line of the sequence a

14、number of queries K (1 = K = 100) is written, and in the next K lines there are queries one in each line. The query Which element is i-th by its value? is coded by the number i.OutputThe output should consist of K lines. In each line there should be an answer to the corresponding query. The answer t

15、o the query i is an element from the database, which is i-th by its value (in the order from the least up to the greatest element).Sample Input5712112371213325Sample Output1217123#include #include using namespace std; int num100010; int pos105;int main()int n;int i;int k;while(scanf(%d,&n)!=EOF)for(

16、i=1;i=n;i+) scanf(%d,&numi); scanf(%d,&k);for(i=1;i=k;i+) scanf(%d,&posi); sort(num+1,num+1+n); for(i=1;i=k;i+) printf(%dn,numposi);return 0;* 路由器连接Hub Connection plan DescriptionPartychen is working as system administrator and is planning to establish a new network in hiscompany. There will be N hu

17、bs in the company, they can be connected to each other using cables.Since each worker of the company must have access to the whole network, each hub must be accessible by cables from any other hub (with possibly some intermediate hubs). Since cables of different types are available and shorter ones

18、are cheaper, it is necessary to make such a plan of hub connection, that the cost is minimal. partychen will provide you all necessary information about possible hub connections. You are to help partychen to find the way to connect hubs so that all above conditions are satisfied.InputThe first line

19、of the input contains two integer numbers: N - the number of hubs in the network (2 = N = 1000) and M - the number of possible hub connections (1 = M = 15000). All hubs are numbered from 1 to N. The following M lines contain information about possible connections - the numbers of two hubs, which can

20、 be connected and the cable cost required to connect them. cost is a positive integer number that does not exceed 106. There will always be at least one way to connect all hubs.OutputOutput the minimize cost of your hub connection plan.Sample Input4 61 2 12 3 13 4 24 3 15 4 16 4 1Sample Output7#incl

21、ude#includeusing namespace std;struct Edgeint a,b;int cost;E15010;int Tree1010;int findRoot(int x)if(Treex=-1)return x;elseint tmp=findRoot(Treex); Treex=tmp;return tmp;bool Cmp(Edge a,Edge b) return a.costb.cost; int main()int n;int m;int i;while(scanf(%d,&n)!=EOF) scanf(%d,&m);for(i=1;i=m;i+)scanf

22、(%d%d%d,&Ei.a,&Ei.b,&Ei.cost);sort(E+1,E+1+m,Cmp);/ 排序for(i=1;i=n;i+)Treei=-1;int ans=0;for(i=1;i=m;i+)int a=findRoot(Ei.a); int b=findRoot(Ei.b); if(a!=b)Treea=b;ans+=Ei.cost;printf(%dn,ans); return 0;* 编译原理Principles of CompilerDescriptionAfter learnt the Principles of Compiler,partychen thought t

23、hat he can solve a simple expressionproblem.So he give you strings of less than 100 characters which strictly adhere to the followinggrammar (given in EBNF):A:= ( B)|x.B:=AC.C:=+A.Can you solve them too?InputThe first line of input gives the number of cases, N(1 ? N ? 100). N test cases follow.The n

24、ext N lines will each contain a string as described above.OutputFor each test case,if the expression is adapt to the EBNF above output “ Good” ,else output “ Bad” .Sample Input3(x)(x+(x+x)()(x)Sample OutputGoodGoodBad#include #include #include #include #include #include #include #include #include #i

25、nclude #include using namespace std; char ex110;int index;bool A();bool B();bool C();bool A()if(exindex=x)index+;while(exindex= ) index+;return true;if(exindex=()index+;while(exindex= ) index+;if(B()&exindex=)index+;while(exindex= ) index+;return true;return false;bool B()return A()&C(); bool C()whi

26、le(exindex=+)index+;while(exindex= ) index+;/return A();if (!A()return false;return true;int main()int N;scanf(%d,&N);getchar();while(N-)gets(ex);index=0;printf(%sn,A()&exindex=0?Good:Bad);return 0;* 分开连接Separate ConnectionsDescriptionPartychen are analyzing a communications network with at most 18

27、nodes. Character in a matrixi,j (i,j both 0-based,as matrixij) denotes whether nodes i and jcan communicate (Y for yes, Nfor no). Assuming a node cannot communicate with two nodes at once, return the maximumnumber of nodes that can communicate simultaneously. If node i is communicating with node jth

28、en node j is communicating with node i.InputThe first line of input gives the number of cases, N(1 ? N ? 100). N test cases follow. In each test case,the first line is the number of nodes M(1 ? M ? 18),then there are a grid by M*M describled the matrix.OutputFor each test case , output the maximum n

29、umber of nodes that can communicate simultaneouslySample Input25NYYYYYNNNNYNNNNYNNNNYNNNN5NYYYYYNNNNYNNNYYNNNYYNYYNSample Output24HintThe first test case:All communications must occur with node 0. Since node 0 can only communicate with 1 node ata time, the output value is 2. The second test case:In

30、this setup, we can let node 0 communicate with node 1, and node 3 communicate with node 4.#include #include #include #include #include #include #include #include #include #include #include using namespace std;#define MAXN 250#define MAXE MAXN*MAXN*2 #define SET(a,b) memset(a,b,sizeof(a) deque Q;bool

31、 gMAXNMAXN,inqueMAXN,inblossomMAXN;int matchMAXN,preMAXN,baseMAXN;int findancestor(int u,int v) bool inpathMAXN= false;while(1)u=baseu;inpathu=true;if(matchu=-1)break;u=prematchu;while(1)v=basev;if(inpathv)return v;v=prematchv;void reset(int u,int anc) while(u!=anc)int v=matchu;inblossombaseu=1;inbl

32、ossombasev=1;v=prev;if(basev!=anc)prev=matchu;u=v;void contract(int u,int v,int n) int anc=findancestor(u,v);SET(inblossom,0);reset(u,anc);reset(v,anc);if(baseu!=anc)preu=v;if(basev!=anc)prev=u;for(int i=1; i=n; i+)if(inblossombasei)basei=anc;if(!inquei)Q.push_back(i);inquei=1;bool dfs(int S,int n)f

33、or(int i=0; i=n; i+)prei=-1,inquei=0,basei=i;Q.clear();Q.push_back(S);inqueS=1;while(!Q.empty()int u=Q.front();Q.pop_front();for(int v=1; v=n; v+)if(guv&basev!=baseu&matchu!=v)if(v=S|(matchv!=-1&prematchv!=-1)contract(u,v,n);else if(prev=-1)prev=u;if(matchv!=-1)Q.push_back(matchv),inquematchv=1; els

34、eu=v;while(u!=-1)v=preu;int w=matchv;matchu=v;matchv=u;u=w;return true;return false;int solve(int n)SET(match,-1);int ans=0;for(int i=1; i=n; i+)if(matchi=-1&dfs(i,n)ans+;return ans;int main()int ans;int n,m;char tmp30;scanf(%d,&n);while(n-)ans=0;memset(g,0,sizeof(g);scanf(%d,&m);for(int i=1;i=m;i+)

35、scanf(%s,tmp+1);for(int j=1;j=m;j+)if(tmpj=Y)gij=gji=1;ans=solve(m);printf(%dn,ans*2);return 0;2010 机试ECNU勺含义Welcome to 2009 ACM selective trialDescriptionWelcome to 2009 ACM selective trial. ACM is a long way to go, and its not just a match. So what you need to do for now is do your best! And as me

36、mbers of ACM lab, we are going to teach you something important. Firstly you should be proud that you are a member of ECNU, because E represents Excellent, C represents Cheer, N represents Nice, U represents Ultimate. Second you should remember Impossible is nothing, because Impossible represents Im

37、 possible. Third for today you should keep ACM, because for you ACM represents Accept More. Do you remember them clearly?Now we will give you a string either E ,C, N,U,Impossible orACM, you need to tell me what does it means?InputThe first line of input gives the number of cases, N(1 ? N ? 10). N te

38、st cases follow.Each test consists of a string which will be one of E ,C, N,U,Impossible orACM.OutputTell me what does it means.Sample Input3ImpossibleACMSample OutputExcellentIm possibleAccept More#include#includechar str20;int main()int N;scanf(%d,&N);while(N-)scanf(%s,str);if(strcmp(str,E)=0) pri

39、ntf(Excellentn); elseif(strcmp(str,C)=0) printf(Cheern);else if(strcmp(str,N)=0) printf(Nicen);else if(strcmp(str,U)=0) printf(Ultimaten); elseif(strcmp(str,Impossible)=0)printf(Im possiblen); else if(strcmp(str,ACM)=0)printf(Accept Moren); return 0;空瓶换啤酒Soda SurplerDescriptionTim is an absolutely o

40、bsessive soda drinker,he simply cannot get enough. Most annoyingly though, he almost never has any money, so his only obvious legal way to obtain more soda is to take the money he gets when he recycles empty soda bottles to buy new ones. In addition to the empty bottles resulting from his own consum

41、ption he sometimes find empty bottles in the street. One day he was extra thirsty, so he actually drank sodas until he couldnt aford a new one.InputThree non-negative integers e,f, c, where e 1000 equals the number of empty soda bottles in Tims possession at the start of the day, f 1000 the number o

42、f empty soda bottles found during the day, and 1 c 2000 the number of empty bottles required to buy a new soda.OutputHow many sodas did Tim drink on his extra thirsty day?Sample Input9 0 35 5 2Sample Output4#include#includeint main()int e,f,c;int t;int sum;int full,empty;while(scanf(%d%d%d,&e,&f,&c)

43、!=EOF)sum=0;empty=e+f;/ 空瓶数量while(empty=c)/ 空瓶数量可换sum+=empty/c;/ 换的满瓶empty=empty/c+empty%c;/ 新的空瓶数量printf(%dn,sum);return 0;统计字符统计字符Description输入一行字符，分别统计其中英文字母、空格、数字和其他字符的个数。Input输入一个整数t,表示有几组数据 接下来有t行，每行字符不超过10000个Hint 可能有空格之类的字符Output对于每行字符输出其中1 英文字母( 大小写都算) 的个数2 数字的个数3 其他字符的个数Sample Input 2q2 e2

44、qweqrwwerr232424fwetetg=2342gdsg3.,/-=321Sample Output character:2number:2others:1character:21number:14others:9#include #include char str10010; int main()int t;int i;int cn,nn,on; scanf(%d,&t); getchar();/清除上一个换行符while(t-)gets(str);int l=strlen(str);cn=nn=on=0;for(i=0;i=0&stri=A&stri=a&stri=z)cn+;el

45、seon+;printf(character:%dn,cn); printf(number:%dn,nn);printf(others:%dn,on); return 0;2010 机试热身粽子买三送一，买五送二端午节快乐Description今天是端午节，ECNUfe定请大家吃粽子。恰好，今天超市为了迎合“端午节”，推出了 端午大酬宾”，即促销活动。严格的买三送一，买五送二。ECNU用现有的钱，买最多的粽子，但是他自己又不会算，所以希望你能帮帮他。Input每组测试数据有两输入第一行为一个数N(1=N=100),表示测试数据的组数 个整数，A,B (0=A=1000,0B10)表示ECNUt

46、 A元钱，每个粽子价格为B元钱 , 超市推出了买5 个送 2 个 , 和买 3 个送 1 个的活动。Output输出ECNUR多能买到的粽子数量。Sample Input210 322 3Sample Output49Hint:有两组测试数据:对于第一组测试数据: 有10 元钱, 粽子3 元一个, 可以买3 个, 但是买3 送1, 所以最后有4 个。对于第二组测试数据: 有22 元钱, 粽子3 元一个, 可以买7 个, 但是买5 送2, 所以最后有9 个。#include #include int main()int n;int a,b;int zn;int num;scanf(%d,&n);

47、while(n-)scanf(%d%d,&a,&b);/ 输入钱数和粽子单价zn=a/b;/ 买了 zn 个num=zn;if(zn/5!=0)num+=zn/5*2;zn=zn%5;if(zn/3!=0)num+=zn/3;printf(%dn,num);return 0;工程流水线问题工程DescriptionCastor在ECNU：厂工作。总厂有一条生产线，现在生产流水线上排队的零件总数为M当前 Castor 开始加工第一个零件。流水线上的零件总是按顺序加工的。例如零件i 必须是在零件i+1 之前加工.现在Castor只需要再加工K(K=M介零件就能休息了，Castor想知道他还要工作多

48、长时间才能休息 .Input第一行为一个整数T, 表示测数数据的组数. 对每组测试数据第一行有两个整数M,K(1=K=M=1000)然后一行有M个数字 第i个数字表示零件队列的第i个零件需要加工的时间为ti(1=ti=10000) Output每组数据输出一行, 每行只有一个整数表示Castor 还需要工作多长时间Sample Input23 25 2 33 11 2 3Sample Output71#include #include #include #include int main()int T;int M,K;int i;int t1005;int sum;scanf(%d,&T);w

49、hile(T-)sum=0;scanf(%d%d,&M,&K);for(i=0;iM;i+) scanf(%d,&ti);for(i=0;iK;i+)sum+=ti;printf(%dn,sum);return 0;2011 机试hello worldHello World!Description当开始学习程序语言，第一个程序肯定是在屏幕上输出一些字符，比如输 出” Hello World! ”。 遇到输出的句子过长时，输出的句子由于换行将被屏幕截断。现在给你一些文本，文本的文法如下:TEXT仪本）k SENTENCE | SENTENCE SPACE TEXT SENTENCE（）:= WORD SPACE SENTENCE | WORD END END符）:=.,?,!WOR欧词）k LETTER | LETTER W