2009年南海区青少年信息学奥林匹克竞赛初赛试题(初中组,A4).doc

2009年南海区青少年信息学奥林匹克竞赛初赛试题（初中组，两小时完成）请将正确答案在答卷上填写，在本试题卷上答题无效一、单项选择题：（共20小题，每题1.5分，共计30分）1在以下各项中，不属于面向对象编程语言的是（ ）。AFree pascal BC+ CVisual Basic DDelphi2计算机中可以采用16*16、32*32等数字化点阵字模，字模中的每一个点在存储器中用个二进制位(bit)存储。那么，两个16*16点阵的汉字在计算机中需要（ ）字节的存储空间。A24 B32 C48 D643现有两条平行直线，直线L1和L2上分别各有m和n个指定点（如下图所示），如果不包含直线L1上两个点之间组成的线段数和直线L2上两个点之间组成的线段数，则这些点共可组成的线段数为（ ）。A.(m-1)(n-1) B.m(n-1) C.(m-1)n D.mn4算术表达式a+b*（c+d/e）转为后缀表达式后为（ ） 。Aab+cde/* Babcde/+*+ Cabcde/*+ Dabcde*/+5（3731）8-（5B）16=（ ）10A1918 B1977 C1937 D19816若A=B=true，C=D=false ，则下面逻辑表达式中值为真的是（ ）。A（ABC）D B（AC）（BD）C（BCD）DA DA（D C）C7对一组数据（84，47，25，15，21）进行排序，排列过程的状态变化如下：（1）84 47 25 15 21 （2）47 25 15 21 84 （3）25 15 21 47 84 （4）15 21 25 47 84 由此推出所采用的排序方法是（ ）排序。 A选择 B冒泡 C快速 D插入8若串S=software,其互异的非平凡子串（非空且不同于S本身）的数目是（ ）。A37 B36 C35 D89二分查找的基本前提条件是（ ）。A、数据不能多于32767个 B、 数值不能大于32767C、数据是有序的 D、用顺序查找没法查找的数据10假设以行序为主序存储二维数组A=array1.100，1.100，设每个数据元素占2个存储单元，基地址为10，则A5，5的起始地址是（ ）。 A. 808 B. 818 C. 1010 D. 102011把10个苹果分成三堆，每堆至少1个，应有（ ）种分法。 A8 B9 C10 D1112将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度（ ）。A4 B5 C6 D713栈的输入序列为a, b，c，d，下面的四个序列中，不可能是它的输出序列的是（ ）。 Ad，c，a，b Bb, c，d，a C c, d，b, a Da，c，b，d14关于pascal的过程中参数的描述，下列哪个是正确的？（ ）A.任何过程在执行时都要有参数传递进去B.值参数是一个常量，而变量参数是一个变量C.值参数的值在过程体中不能改变D.在调用过程时，实际参数的类型必须与形参表中对应变量的类型赋值相容15有3个箱子，如果两箱两箱地称它们的重量，分别是83千克、85千克和86千克，那么其中最轻的箱子重多少千克？（ ）A24 B37 C41 D8316对于二维数组var a,b array1.n,1.n of integer，将数组a中的数据按位置顺时针旋转90度后赋值给数组b，则下面表达式正确的是（ ）。Abj,n-i+1:=ai,j Bbi,j:=ai,j Cbi,n-j+1:=ai,j Dbn-i+1,n-j+1:=ai,j17在PASCAL程序中，表达式(205 xor 100 and 300)的值是（ ）。A40 B233 C22 D27818在PASCAL中，下列属于动态数据类型的是（ ）。A布尔型 B记录类型 C指针类型 D集合类型19下列程序段的时间复杂度为（ ）。for i:=1 to n do begin S:=s*i; for j:=1 to n do ai,j:=j+s; end;AO(nlog2n) B O(n2) CO(n) D O(1) 20目前GPS技术广泛应用于日常生活中，它是指（ ）。A无线网络通信系统 B全球卫星定位系统 C点对点通信系统 D图像辅助系统二、问题求解：（共两题，每小题5分，共10分）1一条直线可以将平面分成2个部分，二条不同的直线最多可以将平面分成4个部分，那么m条不同直线最多可以将平面分成几个部分？试写出平面划分数f(m)与m的关系式。23名司机和6名乘客分别上三辆不同型号的汽车，每车1名司机及2名乘客，则上车方法共有多少种？三、读程序写结果：（共4题，每小题8分，共计32分）1Program p1;var a,b,c,i,sum:integer; x,y,z:array1.3of integer;begin read(a,b,c) ; for i:=1 to 3 do begin xi:=a; a:=a+c; yi:=a+b; zi:=xi+yi; end; if a20 then sum:=(x1+y2+z3)div c else sum:= (x1+y2+z3)div a; writeln(sum);end.输入：10 40 72. Program p2;var a,b,c:integer; procedure loop(o,p,q:integer); begin if qxi then m:=i; xm:=xm+m; m:=1; for i:=a to b-1 do for j:=i+1 to b do if xixj then m:=0; until m0; write(xa); end.输入： 2 54.program p4;const n=3;var b:array1.31 of char; e:array1.63 of byte; h,i,k:integer;procedure tree(t:integer);begin if et=0 then exit else begin write(bt:2);et:=0; t:=2*t;tree(t); t:=t+1;tree(t); end;end;beginfillchar(e,sizeof(e),0);k:=1;for i:=1 to n do k:=k*2;k:=k-1;for i:=1 to k do ei:=1;for i:=1 to 26 do bi:=chr(64+i);for i:=1 to 5 do b26+i:=chr(48+i);h:=1 ;tree(h);writeln;end.四、完善程序：（共2题，每小题前1空2分，后4空每空3分，共计28分）1.【问题描述】给定一个正整数X,按一定规律构成一个递增的序列，例如，当x=4时，这个序列是：1，4，5，16，17，20，21，（该序列实际上就是：40，41，40+41，42，40+42，41+42，40+41+42，）请你求出这个序列的第N项的值（用10进制数表示），3X15，10N1000。例如，对于X=4，N=50，正确答案应该是1284。【算法分析】分析公式的规律可知将n转成二进制数，再按X的幂展开求和即可。【程序】program p2_1; var k,ans:longint; n,x,r:integer; begin readln(x,n); ans:=0;_; while n0 do begin r:=_; n:=_; ans:=ans+r*k; ; end; if ans=0 then else writeln(ans);end.2.【问题描述】一个m*n矩形阵列由数字0或1组成，数字1代表细胞。细胞的定义为沿细胞数字1上下左右还是细胞数字1则为同一细胞，如下面4*10的阵列中有4个细胞：0111100011101111010010111001110000000011 给出m与n（1m,n50）以及阵列，求细胞的数量。【算法分析】将阵列转换成boolean数组bz，0为FALSE。从阵列左上角开始搜索第一个细胞，将细胞的位置入队h，并沿其四个方向上的细胞位置入队，入队后的位置bz数组置为FALSE；将h队的队头出队，取队里下一个细胞位置，沿其四个方向上的细胞位置入队，入队后的位置bz数组置为FALSE；当h队空，则此时找出了一个细胞。【程序】program p2_2;const dx:array1.4 of -1.1=(-1,0,1,0); dy:array1.4 of -1.1=(0,1,0,-1);var s:string; bz:array1.50,1.50 of boolean; m,n,i,j,num:integer; h:array1.3000,1.2 of byte; procedure doing(p,q:integer); var i,t,w,x,y:integer; begin ; bzp,q:=false; t:=1; w:=1; h1,1:=p; h1,2:=q; repeat for i:=1 to 4 do begin x:=ht,1+dxi; y:=ht,2+dyi; if then begin inc(w); hw,1:=x; hw,2:=y; ; end; end; inc(t); until ; end;begin fillchar(b