余姚市程序设计比赛初中组初赛试题 [2016年]

1. 用一个字节表示整数，则-1在计算机内部分别表示为（ ）

2. CPU访问内存的速度比访问下列哪个存储设备要慢( )。

3. 下列电子邮件地址，正确的是( )。

4. 以下二进制数的值与十进制数23.456 的值最接近的是（ ）。

5. 完全二叉树的结点个数为4 * N + 3，则它的叶结点个数为（ ）。

6. 对有序数组{5, 13, 19, 21, 37, 56, 64, 75, 88, 92, 100}进行二分查找，11个数每个数等概率出现的情况下查找成功的平均查找长度（平均比较次数）是（ ）。

7. 已知队列(13，2，11，34，41，77，5，7，18，26，15)，第一个进入队列的元素是13，则第五个出队列的元素是( )。

8. 在程序运行过程中，如果递归调用的层数过多，会因为（ ）引发错误。

9. 现在主要使用的IP v6地址是由( ) 位二进制数码表示的。

10. 除了冯诺依曼，在同时期还提出存储控制采用二进制的数学家是( )。

1. 某个国家的钱币面值有1, 2, 4, 8,16，32……等2^k（k>=0）面值，如果要用现金付清2016元的货物，那么交易过程中至少需要_____张钱币。
答案：6

2. 已知a, b, c, d, e, f, g七个人中，a会讲英语；b会讲英语和汉语；c会讲英语、意大利语和俄语；d会讲汉语和日语；e会讲意大利语和德语；f会讲俄语、日语和法语；g会讲德语和法语。能否将他们的座位安排在圆桌旁，使得每个人都能与他身边的人交谈？如果可以，请以“a b”开头写出你的安排方案:_________________。
答案：abdfgec

1.

var
n,i,x,s:longint;
a:array[0..51]of longint;
begin
readln(n);
for i:=1 to n do read(a[i]);
for i:=1 to n do
 begin
    read(x);
    if a[i]>x then s:=s+1;
  end;
writeln(s);
end.
输入：
5
1 3 5 7 9
2 4 6 8 10
输出：0

2.

var n,i,j,ans:longint;
    a,b,c:array[0..1000000] of longint;
begin
  readln(n);
  for i:=1 to n do read(a[i]);
  b[1]:=a[1];
  for i:=2 to n do b[i]:=b[i-1]+a[i];
  c[0]:=b[0];
  for i:=1 to n do
    if b[i]<c[i-1] then c[i]:=b[i]
      else c[i]:=c[i-1];
  for j:=1 to n do
    if b[j]-c[j-1]>ans then ans:=b[j]-c[j-1];
  writeln(ans);
end.
输入：
5
3 4 -2 8 -10

输出：13

3.

var 
	data : array[1..20] of integer;
	n,i,h,ans	: integer;
	
procedure merge;
begin
	data[h-1] := data[h-1] + data[h];
	dec(h);
	inc(ans);
end;

begin
	readln(n);
	h := 1;
	data[h] := 1;
	ans := 0;
	for i:=2 to n do
	begin
		inc(h);
		data[h] := 1;
		while (h>1) and (data[h]=data[h-1]) do
			merge;
	end;
	writeln(ans);
end.
（1）
输入：8
输出：______________ （5分）
（2）
输入：2016
输出：______________ （5分）

输出：7|2010

1. （最大质因子）小明有N(1<=N<=5000)个正整数（每个数都不超过20000），他想要从中找出一个含有最大质因子的数。例如10，含有2和5两个质因子；31，含有31这个质因子。
样例输入：
4
36
38
40
42
样例输出：
38 //38含有最大质因子19

var
  prime:array[1..20000]of boolean;
  a,i,j,n,max,maxnum:word;
procedure create;
var
  i,j:word;
begin
  fillchar(prime,sizeof(prime),true);
  prime[1]:=false;
  for i:=2 to 20000 do
    for j:=2 to trunc(sqrt(i))do
    if i mod j=0 then
    begin
             _prime[i]:=true_       ;
      break;
    end;
end;
 
begin
  create;
  readln(n);
  for i:=1 to n do
  begin
    readln(a);
    for j:=   __j:=a downto 2__        do
      if(a mod j=0)and(     __prime[j]__      )then break;
    if   _j>max__  then begin max:=j;maxnum:=a;end;
  end;
  write(  __maxnum__  );
  readln;
end.

2. (逆序对) 对于一个包含N个非负整数的数组A[1..n]，如果有i<j，且A[i]>A[j]，则称(A[i],A[j])为数组A中的一个逆序对。例如，数组（3，1，4，5，2）的逆序对有(3,1),(3,2),(4,2),(5,2)，共4个。 (n<=1,000,000)
求n个数中的逆序对个数。
【样例输入】
5
3 1 4 5 2
【样例输出】
4
算法提示：采用归并排序的方式，在归并排序的合并过程中统计逆序对数量。

var
  a,b:array[1..1000000]of longword;
  i,n:longword;
  ans:qword;
procedure Merge(l,mid,r:longword);
var
  x,y,i,loc:longword;
begin
  x:=l;y:=  _mid+1_  ;loc:=l;
  while(x<=mid)and(y<=r)do
  if a[x]<=a[y]then
  begin
      _b[loc]:=a[x]_   ;inc(loc);inc(x);
  end
  else
  begin
    ans:=ans+   _ans+mid-x+1_   ;
    b[loc]:=a[y];inc(loc);inc(y);
  end;
  for i:=x to mid do
  begin
    b[loc]:=a[i];inc(loc);
  end;
  for i:=y to r do
  begin
    b[loc]:=a[i];inc(loc);
  end;
  for i:=l to r do a[i]:=b[i];
end;
procedure MergeSort(l,r:longword);
var
  mid:longword;
begin
  if l=r then exit;
  mid:=(l+r)div 2;
  MergeSort(l,mid);
  MergeSort( _mid+1,r_ );
  Merge(l,mid,r);
end;
 
begin
  readln(n);
  for i:=1 to n do read(a[i]);
  MergeSort(1,n);
  write( _ans_  );
end.