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

1、2009 机试 .2计算和的数位 .2大写改小写 .3素数对 .4求最大公约数和最小公倍数 .6排序后求位置处的数 .7*路由器连接 .8*编译原理 .10*分开连接 .132010 机试 .17ECNU 的含义 .17空瓶换啤酒 .18统计字符 .202010 机试热身 .21粽子买三送一，买五送二 .21工程流水线问题 .222011 机试 .24hello world.24Special judge.26查询成绩 .282011 机试热身 .30贪吃蛇 .30仰望星空 .34*编辑距离 .362012 机试 .38字母排序 .38幸运数 .39十六进制的加法 .42电话号码簿合并排序 .

2、42*五子棋 .43*正则表达式匹配 .452013 机试 .46斐波那契数列的素数个数 .46*将 a 字符变成 b 字符最少修改次数 .472013 机试热身 .49去重排序 .49蛇形图案 .51数学手稿 .542009 机试计算和的数位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 te

3、st cases follow.Each test case consists of two integers a and b which are separeted by a space in a line. (0int main()int n;int a,b;int sum;while(scanf(“%d“,scanf(“%d%d“,sum=a+b;while(sum)an+;sum/=10;printf(“%dn“,an+);return 0;大写改小写Capitalize Description Write a program which replace all the lower-c

4、ase letters of a given text with the corresponding captital letters. Input A text including lower-case letters, periods, and space.Output Output The converted text. Sample Input welcome to east china normal university. Sample Output WELCOME TO EAST CHINA NORMAL UNIVERSITY. #include#includechar str10

5、00;int main()int l;while(gets(str)l=strlen(str);int i;for(i=0;i=avoid init()int i;int j;prime0=prime1=false;/不是素数prime2=true;/是素数for(i=3;iint 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“,printf(“%d %dn

6、“,getgcd(a,b),a*b/(getgcd(a,b);return 0;排序后求位置处的数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

7、.It should be able to 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#includeusing namespace std;int

8、 num100010;int pos105;int main()int n;int i;int k;while(scanf(“%d“,i#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“,for(i=1;i=m;i+)scanf(“%d%d%d“,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 Compiler