江苏青少年信息学奥林匹克联赛复习题.docx

一、 选择（每题1分，多选无分，共20分）
1、在八进制中，数773244556除以4的余数是（       ）
A  2             B  4          C  6         D  0
2、一个无符号二进制整数的第五位是1（从右边开始），则这个数的十进制值最小是（  ）
A  25            B  24         C  105        D  104
3、在计算机内部，一切信息存取、处理和传递的形式是（     ）
A  ASCII码      B  BCD码     C  二进制    D  十六进制
4、微型计算机的主机一般包括（    ）
A  CPU、内存  B  CPU、外存储器  C  主板、CPU  D  存储器、寄存器
5、用计算机进行图形制作时，正在绘制的图形是存放在（   ）中
A  CPU          B  ROM       C  RAM      D  外存
6、在WINDOWS中，能够打开对话框的菜单项中一般含有（    ）符号标志
A  …            B √           C  •         D ▲
7、在WORD中，将一段文字移到整个文档最后，正确的操作步骤的顺序是（   ）
  （1）打开编辑菜单，选择粘贴命令   （2）选择要移动的一段文字使其反黑
  （3）打开编辑菜单，单击复制命令   （3）把光标移到文档的最后
A （1）（2）（3）（4）             B （3）（2）（4）（1）
C （2）（3）（4）（1）             D （3）（1）（2）（4）
8、第三代计算机的主要制造材料是（    ）
A  ROM      B 中小规模集成电路   C  大规模集成电路   D  ROM与RAM
9、一个无符号二进制整数的右边加上二个0，形成的新数是原数的（   ）倍
A  2             B  4           C  10        D 16
10、中的“cn”代表了（     ）
A  国家（中国）  B  省市        C  用户      D  服务器
11、64K存储器含（    ）个字节
A  64000         B  65536       C  64536     D  32768
12、计算机病毒一般寄生在（    ）中
A  中央处理器    B  存储器      C  输入设备    D  输出设备
13、启动WINDOWS后，不是桌面上常见的图标是（     ）
A  我的电脑      B  回收站      C  控制面板    D  我的文档
14、在WINDOWS中，使用鼠标打开某个对象快捷菜单的操作方法是（    ）
A  单击对象      B  双击对象    C  右击对象    D  拖动对象
15、在WINDOWS中，可以由用户设置的文件属性为（     ）
A  存档、系统和隐藏       B  只读、系统和隐藏
C  只读、存档和隐藏       D  系统、只读和存档
16、下列选项中，不属于程序流程控制结构的是（    ）
A  循环          B  逻辑表达式    C  双分支     D  分支嵌套
17、用A表示某个人的总成绩，用B表示这个人的语文成绩，用C表示这个人的数学成绩。那么，用来表达总分不低于170分，同时数学成绩不低于90分，或者语文成绩不低于86分的逻辑表达式是（     ）
A    A>=170  AND  B>=86 OR  C>=90
B    总分超过170，并且语文超过86或数学超过90
C  A>=170  AND  (B>=86 OR  C>=90)
D （A>=170  AND  B>=86）OR  C>=90
18、已知一个数字方阵，共M排（0—M-1），每排N个（0—N-1）。现要求将这个数字方阵存放到一个长条形盒中（盒中长度不限），且盒中原来从头已经放有K个数字。如果按排取数存放，则数字方阵中第I排第J个数字，应该放在盒中的（   ）位置
A  I*N+J    B  K+I*N+J+1   C  K+J*M+I+1   D  J*M+I
19、有9个盒子，每个盒子中存放另一个盒子的号码。从1号盒子开始能够走遍所有盒子、直到结束（盒子中的号码为1）。那么3号盒和6号盒中的号码分别是（    ）
A  6，7     B  7，6         C  8，9         D  9，8
20、 有两个N位整数，将他们分别颠倒后表示成（……（（a0*10）+a1）*10+……）*10+an-1和（……（（b0*10）+b1）*10+……） *10+bn-1。他们按原数相加后得到的和，颠倒后表示为（……（（c0*10）+c1）*10+……）*10+cn-1,那么cn-1是（    ）
A  ai+bi+pi除以10的余数           B  ai-1+bi-1+pi-1除以10的余数
C  ai-1+bi-1+pi-2除以10的余数        D  ai-1+bi-1+pi除以10的余数
二、问题求解（6+6+8=20分）
   1、墙壁涂色：有一面三角形墙壁已被分割成4个小三角形（如右图）。
要求最多用三种颜色给墙壁涂色，使相邻小三角形的颜色不同。
   问：有多少种涂色方案？

   2、小明有X个玻璃杯，他想在每个杯子里放入若干个小球，并使各个杯子中的小球互不相同，但允许有一个空杯。
   问：小明至少要有多少小球，才可达到目的。
   3、对于任给的N，有数列：1，2，3，……，N-1，N，N-1，……，3，2，1。我们用t(n,i)表示该数列的第I项，用S（N，I）表示该数列的前I项之和。
   例如：T（4，6）是数列1，2，3，4，3，2，1的第6项，所以T（4，6）=2，而S（4，6）=1+2+3+4+3+2=15。
   请分别算出：T（10，15）、S（10，15），T（20，32）和S（20，32）
三、阅读程序，写出正确的程序运行结果（每题8分，共32分）
1、REM  XIAO-1
   n = 374
   s = 1 : j = 1 : i = 1
   do  while  s <= n
i = i + 1
j = j + 2
s = s + j
loop
i = i –1
print  i
end
2、REM  XIAO-2
   i = 1278 : j = 42
   i0 = i : j0 = j
   do  while  i <> j
if  i > j  then  i = i – j  else  j = j - i
   loop
   j =  i0 * j0 \ i
   print  i , j
   end
3、REM  XIAO-3
DIM A(20, 20)
N = 7: I = 1: J = N: K = 1: DI = 1: DJ = 1
DO WHILE K <= N * N
  A(I, J) = K: K = K + 1: I = I + DI: J = J + DJ
  IF I = N + 1 THEN
         I = N: J = J - 2: DI = -1: DJ = -1
  ELSEIF J = N + 1 THEN
         J = N: DI = -1: DJ = -1
  ELSEIF J = 0 THEN
         I = I + 2: J = 1: DI = 1: DJ = 1
  ELSEIF I = 0 THEN
         I = 1: DI = 1: DJ = 1
  END IF
LOOP
FOR J = 1 TO N
  PRINT A(N \ 2, J); "  ";
NEXT J
PRINT
END

4、  
REM  XIAO-4
DIM A(127)
FOR I = 1 TO 127
   C$ = CHR$(I)
   IF ("0" <= C$) AND (C$ <= "9") THEN
              A(I) = 1
      ELSEIF (("A" <= C$) AND (C$ <= "Z")) OR (("a" <= C$) AND (C$ <= "z")) THEN
              A(I) = 2
        ELSE
              A(I) = 0
   END IF
NEXT
INPUT S$
FOR I = 1 TO M
  J = ASC(MID$(S$, I, 1))
  IF A(J) > 0 THEN
      PRINT CHR$(J);
      A(J) = A(J) - 1
  END IF
NEXT
PRINT
END
输入： ？123+1234a+12abc-aaABB*ABC
输出：

四、根据题意，将程序补充完整：（共28分）
1、上楼梯
[问题描述]设有一个N级的楼梯（4<=N<=12）,编号从上到下依次为1至N。有一个人上楼时一步可走1级、或2级、或3级。
问：这个人从楼下走到第N级，共有多少种不同的走法？
例如：N=1时，仅有一种走法
N=2时，有1级+1级 或 2级    共2种走法
N=3时，有1级+1级+1级，或1级+2级，或2级+1级，或3级    共4种走法
[程序说明]  用递推方法求解。
[程序清单]  
REM  XIAO-5
INPUT  N
IF  N = 1  THEN  C = 1
  ELSEIF  N = 2  THEN  C = 2
  ELSEIF  N = 3  THEN              
ELSE
  A = 1 ：B = 2 ：C = 4
  FOR  I  =  4  TO  N
D =   （1）          
A = B
    （2）        
    （3）      
  NEXT
ENDIF
PRINT  C
END
2、取数组合
[问题描述] 从1，2，……，N这N个自然数中任取R个数进行组合（4<=N<=8,1<=R<N）,
然后列出全部组合。
例如：当N=5，R=3时，列出的全部组合如下：
1  2  3       1  2  4        1  2  5        1  3  4        1  3  5
1  4  5       2  3  4        2  3  5        2  3  5        3  4  5
[程序说明] 对任给出的N和R，则：
第一个组合为：1，2，……，R
然后变化第R位；
第二个组合为：1，2，……，R+1
继续变第R位，可以变到N；然后再变化第R-1，R-2位，……直至第1位的变化。
用数组B（0，20）记录组合，S记录组合总数
[程序清单]
REM  XIAO-6
DIM  B（20）
INPUT  N，R
（1）            
FOR  I = 0  TO  R
   B（I）= I
NEXT
DO  WHILE    （2）              
   S=S+1
FOR  I =  1  TO  R
    PRINT  B（I）；“  ”；
NEXT  
PRINT
J = R
DO  WHILE     （3）    
    J = J – 1
LOOP
B（J）= B（J）+ 1
FOR  I  =  J+1  TO  R
    B（I）= B（I-1）+1
NEXT
LOOP
PRINT  S
END
3、数列求和
[问题描述]
求SN=A+AA+AAA+……+AA…A(N个A)，其中A是一位数字（1<=A<=9,1<=N<=6）。
例如：当A=2：N=5时，S5=2+22+222+2222+22222=24690
[程序清单]
REM  XIAO-7
INPUT  A,N
COUNT = 1
SN = 0
TN = 0
DO  WHILE     （1）          
TN = TN + A
SN =  （2）          
A =     （3）      
COUNT = COUNT + 1
LOOP
PRINT  SN
END

答案：
一. 选择一个正确答案代码（A/B/C/D）,填入每题选择项内 (每题1分,多选无分, 共20 分)

题号
  1
  2
  ３
  4
  5
  6
  7
  8
  9
 10
选择
A
B
C
A
C
A
 C
B
B
A
题号
 11
  12
  13
  14
  15
  16
  17
  18
  19
 20
选择
B
B
C
C
C
B
C
B
D
C

二．问题解答 （ 6+6+8=共20 分）
1. 答：有24 种涂色方案。
2. 答：小明至少有X×(X-1)/2个小球，才可达到目的。
3. 答：当i<=n时t(n,i)=i, s(n,i)=i*(i+1)/2；
         当i >n时 t(n,i)=2*n-i, s(n,i)=((n*(n+1)+(3*n-i-1)*(i-n))/2
         所以:  t(10,15)=5                    s(10,15)=(10*11+14*5)/2=90  
                t(20,32)=8                    s(20,32)=(20*21+27*12)/2=372       

三. 阅读程序，并写出程序的正确运行结果：（每题8 分，共32分）
  1）程序的运行结果是:   19
2) 程序的运行结果是:   6     8946 
3) 程序的运行结果是:  35   33   24   19   13    8    6
4)     输入:  123+1234a+12abc-aaABB*ABC   程序的运行结果是:  1234aabcABBAC

四.根据题意, 将程序补充完整(共28分)
题一（2+3+2+2  共9分）
①                                   c = 4                  ②      a + b + c　  　
③            b = c  　              ④      c = d   　　　

题二（ 2+3+4 共9分）
①                            s = 0      
②                            b(0) = 0    　   
③                            b(j) = n - r + j  

题三（ 3+4+3 共10分）
①         count <= n  
②          sn + tn  
①                             a * 10   　
2004年江苏省小学生信息学奥林匹克竞赛复赛试题
（1.5小时完成   共400分）
陶陶摘苹果（100分）
(apple.pas/c/cpp) 
【问题描述】 
陶陶家的院子里有一棵苹果树，每到秋天树上就会结出10个苹果。苹果成熟的时候，陶陶就会跑去摘苹果。陶陶有个30厘米高的板凳，当她不能直接用手摘到苹果的时候，就会踩到板凳上再试试。 
现在已知10个苹果到地面的高度，以及陶陶把手伸直的时候能够达到的最大高度，请帮陶陶算一下她能够摘到的苹果的数目。假设她碰到苹果，苹果就会掉下来。 
【输入文件】 
输入文件apple.in包括两行数据。第一行包含10个100到200之间（包括100和200）的整数（以厘米为单位）分别表示10个苹果到地面的高度，两个相邻的整数之间用一个空格隔开。第二行只包括一个100到120之间（包含100和120）的整数（以厘米为单位），表示陶陶把手伸直的时候能够达到的最大高度。 
【输出文件】 
输出文件apple.out包括一行，这一行只包含一个整数，表示陶陶能够摘到的苹果的数目。 
【样例输入】 
100 200 150 140 129 134 167 198 200 111 
110 
【样例输出】 
5

校门外的树（100分）
(tree.pas/c/cpp) 
【问题描述】 
某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0，1，2，……，L，都种有一棵树。 
由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。 
【输入文件】 
输入文件tree.in的第一行有两个整数L（1 <= L <= 10000）和 M（1 <= M <= 100），L代表马路的长度，M代表区域的数目，L和M之间用一个空格隔开。接下来的M行每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标。 
【输出文件】 
输出文件tree.out包括一行，这一行只包含一个整数，表示马路上剩余的树的数目。 
【样例输入】 
500 3 
150 300 
100 200 
470 471 
【样例输出】 
298 
【数据规模】 
对于20%的数据，区域之间没有重合的部分； 
对于其它的数据，区域之间有重合的情况。

采药（100分）
(medic.pas/c/cpp) 
【问题描述】 
辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。” 
如果你是辰辰，你能完成这个任务吗？ 
【输入文件】 
输入文件medic.in的第一行有两个整数T（1 <= T <= 1000）和M（1 <= M <= 100），用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。 
【输出文件】 
输出文件medic.out包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。 
【样例输入】 
70 3 
71 100 
69 1 
1 2 
【样例输出】 
3 
【数据规模】 
对于30%的数据，M <= 10； 
对于全部的数据，M <= 100。

循环（100分）
(circle.pas/c/cpp) 
【问题描述】 
乐乐是一个聪明而又勤奋好学的孩子。他总喜欢探求事物的规律。一天，他突然对数的正整数次幂产生了兴趣。 
众所周知，2的正整数次幂最后一位数总是不断的在重复2，4，8，6，2，4，8，6……我们说2的正整数次幂最后一位的循环长度是4（实际上4的倍数都可以说是循环长度，但我们只考虑最小的循环长度）。类似的，其余的数字的正整数次幂最后一位数也有类似的循环现象：  
循环
循环长度
2
 2、4、8、6
 4 
3
 3、9、7、1
 4
4
 4、6
 2
5
 5
 1
6
 6
 1 
7
 7、9、3、1
 4 
8
 8、4、2、6
 4
9
 9、1
 2
这时乐乐的问题就出来了：是不是只有最后一位才有这样的循环呢？对于一个整数n的正整数次幂来说，它的后k位是否会发生循环？如果循环的话，循环长度是多少呢？ 
注意： 
1．  如果n的某个正整数次幂的位数不足k，那么不足的高位看做是0。 
2．  如果循环长度是L，那么说明对于任意的正整数a，n的a次幂和a + L次幂的最后k位都相同。 
【输入文件】 
输入文件circle.in只有一行，包含两个整数n（1 <= n < 10100）和k（1 <= k <= 100），n和k之间用一个空格隔开，表示要求n的正整数次幂的最后k位的循环长度。 
【输出文件】 
输出文件circle.out包括一行，这一行只包含一个整数，表示循环长度。如果循环不存在，输出-1。 
【样例输入】 
32 2 
【样例输出】 
4 
【数据规模】 
对于30%的数据，k <= 4； 
对于全部的数据，k <= 100。