華東師范大學計算機機試真題

1、華東師范大學計算機機試真題華東師范大學計算機機試真題11/11華東師范大學計算機機試真題 TOC o ”12” h z u 2009機試計算和的數(shù)位Sum of digit Description Write a program which computes the digit number of sum of two integers a and b。 Input The first line of input gives the number of cases, N(1 N 100）. N test cases follow。Each test case consists of two i

2、ntegers a and b which are separeted by a space in a line。 （0=a，b=100000000）. Output For each test case, print the number of digits of a + b. Sample Input 35 71 991000 999 Sample Output 234 includeint main（）int n;int a，b;int sum;while(scanf（%d,n）！=EOF)while（n-)int an=0;scanf(”%dd，&a,&b);sum=a+b;while

3、(sum）an+；sum/=10;printf（”%dn,an+）；return 0；大寫改小寫Capitalize Description Write a program which replace all the lowercase letters of a given text with the corresponding captital letters. Input A text including lowercase letters， periods, and space.Output Output The converted text。 Sample Input welcome

4、to east china normal university。 Sample Output WELCOME TO EAST CHINA NORMAL UNIVERSITY。 #include#includestring.hchar str1000；int main（)int l；while（gets(str)）l=strlen（str);int i；for（i=0；i=a&stri=z）printf（”c”,stri32)；elseprintf（%c,stri)；printf（n)；return 0；素數(shù)對Primes Pair Description We arrange the numb

5、ers between 1 and N (1 = N includebool prime10005；void init（）int i;int j;prime0=prime1=false;/不是素數(shù)prime2=true；/是素數(shù)for（i=3；i=10005；i+=2)primei=true;/是素數(shù)primei+1=false;/不是素數(shù)除0和2之外的偶數(shù)都不是素數(shù)for(i=3;i=10005；i+=2)if(primei=true）/是素數(shù)j=i+i；while（j=10005)primej=false;/不是素數(shù)j+=i;int main（）int c；int n;init（)；/初始

6、化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(n2=1）/n為奇數(shù)if（primen/2+1=true）sum+=1;printf(dn”，sum);return 0；求最大公約數(shù)和最小公倍數(shù)GCD and LCM Description Write a program which computes the greatest common divisor （GCD） and the leas

7、t common multiple （LCM) of given a and b （0 a, b 44000）。 Input The first line of input gives the number of cases, N(1 N 100）。 N test cases follow.Each test case contains two interger a and b separated by a single space in a line。 Output For each test case, print GCD and LCM separated by a single spa

8、ce in a line. Sample Input 28 65000 3000 Sample Output 2 241000 15000 includestdio。hint getgcd(int a,int b）int gcd;int t1，t2;t1=a;t2=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(”%dd,a,b);printf（”d %dn”，getgcd(a，b),ab/(getg

9、cd(a,b）)）；return 0;排序后求位置處的數(shù)Sort it Description There is a database，partychen want you to sort the databases data in the order from the 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

10、 process quickly queries like this. Input The standard input of the problem consists of two parts. At first， a database is written， and then 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

11、 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 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 ith by its value？” is coded

12、by the number i。 Output The output should consist of K lines. In each line there should be an answer to the corresponding query。 The answer to 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 Input 5712112371213

13、325 Sample Output 1217123#includeincludealgorithmusing namespace std;int num100010;int pos105;int main（）int n;int i;int k；while(scanf(%d”，&n）！=EOF）for（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 Connec

14、tion plan Description Partychen is working as system administrator and is planning to establish a new network in his company. There will be N hubs 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 b

15、e accessible by cables from any other hub (with possibly some intermediate hubs)。 Since cables of different types are available and shorter ones 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 po

16、ssible hub connections。 You are to help partychen to find the way to connect hubs so that all above conditions are satisfied。 Input The first line 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

17、）. All hubs are numbered from 1 to N. The following M lines contain information about possible connections the numbers of two hubs， which can 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

18、 connect all hubs。 Output Output the minimize cost of your hub connection plan。 Sample Input 4 61 2 11 3 11 4 22 3 13 4 12 4 1 Sample Output 3#includestdio。hincludealgorithmusing namespace std;struct Edgeint a，b;int cost；E15010；int Tree1010；int findRoot（int x）if(Treex=1）return x；elseint tmp=findRoot

19、(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(ddd，&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！

20、=b）Treea=b;ans+=Ei。cost；printf（%dn,ans)；return 0；編譯原理Principles of Compiler Description After learnt the Principles of Compiler,partychen thought that he can solve a simple expression problem。So he give you strings of less than 100 characters which strictly adhere to the following grammar （given in

21、EBNF）： A:= （ B)x. B:=AC. C:=+A。Can you solve them too？ Input The first line of input gives the number of cases， N（1 N 100). N test cases follow。The next N lines will each contain a string as described above. Output For each test case,if the expression is adapt to the EBNF above output “Good”，else ou

22、tput “Bad”。 Sample Input 3(x)(x+（x+x）（）（x) Sample Output GoodGoodBad include cstdioinclude #include cmathinclude include include #include map#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=()

23、 index+; while（exindex= ) index+； if(B（）exindex=） index+; while（exindex= ) index+； return true; return false;bool B（) return A（）&C（）;bool C（) while（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）； retu