宁波市第31届中学生计算机程序设计初赛试题 [2016年]

1. 下面关于CPU的说法不正确的是：

2. 下面关于计算机程序语言的说法不正确的是：

3. 在TCP/IP网络体系结构中，与TCP协议在同一层的协议是：

4. 下列不是浏览器软件的是：

5. 第四代移动通信技术简称为4G，下列属于4G网络制式的是：

6. 下列关于HTTP协议的说法正确的是：

7. 下面不同进制的数中，最大的是：

8. 计算机采用标准ASCII码对字符进行编码，共128个，码值在存储时占用一个字节中的:

9. 某计算机中采用16X16 数字化点阵表示一个汉字，字模中的每一个点用一个一进制位存储，则存储1024个汉字所需的存储空间约为：

10. 下列关于图深度优先搜索和广度优先搜索说法不正确的是：

11. 有一栈容量足够大的空栈S,元素序列A、B、C、D、E、F依次进栈，其间允许进栈、出栈交替执行，但不允许连续四次执行进栈操作，则不可能的出找序列是：

12. 线性表(ai，a2，a3,…，an)若采用顺序存储结构，每个数据元素占4个存储单元，第一个数据元素al的存储地址为800(按十进制计算)，则数据元素a5的存储地址为:

13. 设A=False，B=True，C=False，D=True,则与逻辑表达式A∨B∧¬C值不同的是:

14. 己知一个线性表（36, 43, 25, 77, 45, 28, 33, 54)，假定采用散列函数h(key)=key%9 (%为求余运算）依次计算散列地址，并存储在散列表A[0..8]中。若采用线性探测方法解决冲突，则线性表中的元素“54”在散列表中的位置为：

15. 若算术表达式“c-a*(b+d)”釆用二叉树表示，则合理的树结构为:

16. 某一序列中A元素与B元素的数值相同，且A元素在B元素前面，现对该序列进行排序，要求排序后A元素仍然在B元素前面且平均排序速度较快，下列最合适的排序算法是：

17. 现有一棵2000个结点的完全二叉树，对树中的结点按层次依次编号(每层中从左向右编号)，其中根结点编号为1。编号为512的结点，其右孩子结点的编号为：

18. 在一个具有n个结点的有序单链表（线性链表）中删除关键字为key的结点，其时间 复杂度为：

19. 2015年 3月25日，美国计算机科学家迈克尔斯通布雷克（Michael Stonebraker）获得2014年度“图灵奖”，奖金金额100万美元。迈克尔.斯通布雷克最主要的贡献在（ ）。

20. 以下关于“图灵测试”的说法不正确的是：

1. 栈是一种后进先出的线性表，元素A、B、C按顺序进栈（栈容量足够大），则不同的出 栈顺序有_____种。
答案：5

2. 现有4 位小朋友围坐成一个圆圈，依次编号为A，B，C，D, 每位小朋友可以挑红、绿 蓝三种不同颜色气球中的一种拿在手上，但要求相邻小朋友手中气球的颜色互不相同 则小朋友们拿气球不同的方案有_______种。
答案：18

1.

var
a,  b,  c,  x,  y :  longint; 
begin
readln(a, b,  c);  
x  :=  a  div c; 
y  := b mod  c; 
if x  <  y  then 
begin
x  :=  x  -  y;  y  :=  x  +  y;  x  :=  y  -  x; 
end;
writeln(x, ' ', y);
end.
输入：25 38 13
输出：12 1

2.

type
pointer = ^longint;
var
a, b: longint;
procedure  myfun(a:  pointer;  b:  longint); 
var
c: longint; 
begin
c := a^; 
a^ := b; 
b:=c; 
a^:= b + 1; 
b :=a^ -1;
end;
begin
readln(a,  b); 
myfun(@a, b); 
writeln(a,' ', b);
end.
输入：2015 2016
输出：2016 2016

3.

var
n, sum, avg, cnt, i: longint; 
v:array[1..101] of longint; 
begin
readln(n); 
avg := 0; 
sum := 0;
for i := 1 to n do 
begin
read(v[i]); 
sum := sum + v[i]; 
end;
avg := sum div n;
cnt  := 0；
for  i  :=  1  to  n  do 
begin
v[i]  :=  v[i]  -  avg; 
if  v[i]  <>  0  then 
begin
inc(cnt);
v[i  +  1]:= v[i  +  1]  +  v[i]; 
end; 
end;
writeln(cnt);
end.
输入：
7
8 9 6 17 10 13 7
输出：4

4.

var
n:  longint;
function  f(n,  m:  longint):   longint; 
begin
if  (n  =  0)  or  (m =  0)  then 
f  :=  0
else  if  (n  =  1)  or  (m =  1)  then 
f  :=  1
else  if  n  <  m  then 
f  :=  f(n,  n) 
else  if  n  = m  then
f := f(n,  m-1)+1
else
f  :=  f (n,  m  -  1)  +  f (n  -  m,  m ) ;
end;
begin
readln(n); 
writeln (f (n,  n ) );
end.
输入：6
输出：11

1. (二维数组鞍点）给出一个N (N < l00)行M(M <100)列的二维数组，每个数组元素都是整数，编程寻找该二维数组中的鞍点。所谓二维数组的鞍点是指该位置上的元素值在其所在行上最大，在其所在列上最小。程序要求输出鞍点的位置和元素值。如果找不到，则输出“Not exist” 。例如下面输入第1行为二维数组的行数N 和列数M ，接下来N 行 M 列
表示二维数组，输出表示鞍点位置在数组的第1 行第4 列，元素值为4。同一行中相邻两个数字中间有一个空格，行末没有空格。
输入样例：
3 4
1 2 3 4
8 7 6 5
9 10 11 12
输出样例
1 4 4

ar
  n, m, i, j: longint;
  a: array[1..100, 1..100] of longint; 
  row_max: array[1..100] of longint;
  //row_max [i]存储二维数组第i行中最大元素的列号
function check(i, j: longint): boolean;
//函数check检査在第j 列中是否元素a [i][j]最小
var
  k: longint;
  flag: boolean; 
begin
  flag:= true; 
  for k:= 1 to n do
  if  a[i,j]>a[k,j]  then
    begin
     flag := false;
     break;
    end;
    check := flag;
end;

begin
  readln(n, m); 
  for i := 1 to n do 
    for j := 1 to m do 
      read(a [i][j]);
  for i := 1 to n do 
  begin
      row_max[i]:=a[i,1]  ;
    for j:=2 to n do
      if a[i][j] > a[i][row_max[i]] then
        a[i][row_max[i]]:= j ;
  if check ( i,row_max[i] ) =true then
  begin
    writeln(i,' ',row_max[i],' ', a[i,row_max[i]] );
     halt ;
  end;
  end;
  writeln('Not exist');
end.

2. (最大连续子序列和问题）给出包含n(n<100)个整数的序列a1,a2,a3,...an，其任意子序列可以表示为ai,ai+1,ai+2,...,aj，其中1 ≤ i ≤ j ≤ n。求所有连续子序列中元素之和的最大值。如果n 个整教都为负数，则输出0。例如序列-2, 11, -4, 13, -5, -2的连续子
序列11, -4 , 13 和最大，最大和为20。
输入样例：
6
-2 11 -4 13-5-2
输出样例：
20
算法分析：将给定的序列分成长度相等（或相差1个数）的左右两段，分别求出这两段的最大连续子序列和，则给定序列的最大连续子序列和有三种可能情况：
1 ) 与左半段的最大连续子序列和相同。
2 ) 与右半段的最大连续子序列和相同。
3 ) 包含两部分，一部分在左半段中（子序列包含左半段的最后一个元素），另一部分在右半段中（子序列包含右半段的第一个元素）。
前两种情形我们可以用递归方法求出， 第三种情形可以分别求出左右两部分的最大连续子序列和后再相加。原序列的最大连续子序列和即为这三种情形的最大值。

var
  n, i: longint; 
  a: array[1..100] of longint; 
function getmax(a, b, c: longint): longint;
begin
  if a > b then
     if a > c then getmax := a else getmax :=c 
  else
     if b > c then getmax := b else getmax :=c;
end;
function search(L, R: longint): longint;
var
  Leftmaxsum: longint;// Leftmaxsum存储左半端的最大连续子序列和
  Rightmaxsum: longint;// Rightmaxsum存储右半端的最大连续子序列和
  mid, i, sum1, sum2, maxsum1, maxsum2: longint; 
begin
  if L = R then
     if a[L] > 0 then
        exit(a[L])
  else
       exit(0)  ; 
  mid := (L + R) div 2;
  Leftmaxsum := search(L, mid);
  Rightmaxsum := search(mid+1,R) ;
  sum1 := 0; sum2 := 0;
  maxsum1 := 0; maxsum2 := 0;
  for i := mid downto L do
  begin
     sum1:=sum1+a[i] ;
    if sum1 > maxsum1 then
	   maxsum1 := sum1;
  end;
  for i := mid + 1 to R do
  begin
    sum2 := sum2 + a[i];
    if sum2 > maxsum2 then
       maxsum2 := sum2;
   end;
   search := getmax (Leftmaxsum, Rightmaxsum, maxsum1+maxsum2 );
end;
begin
readln(n);
for i := 1 to n do
read(a[i]);
writeln ( search(1,n) )；
end.