初赛试题信息学命题

1、信息学竞赛初赛模拟试题（十六）（初中组 PASCAL 语言，两小时完成）请将正确在答卷上填写，在本试题卷上作答无效一、 选择题：（选出每题正确的一个代码，填在横线上，每题 1.5 分，共 30 分）1、执行下列二进制算术加运算 11001001（ ）。D. 10100010A. 11101111B. 11110000C. 000000012、假设 a1，a2，a3 是变量，且值均为 True，则下列表达式中值为 False 的是A. NOT a1 AND NOT a2C. (NOT a1 OR a2)AND (a2 OR a3)B. a1 OR a2 AND a3D. False OR a1

2、AND a2 OR NOT a33、若一个问题的求解既可以用递归算法，也可以用递推算法，则往往用算法。A.先递归后递推 B. 先递推后递归 C.递归D.递推4、表达式 8 MOD (2*(5-3*(4*(5 DIV 2)DIV 10)的值是A. 0B. 1C. 2D. 35、贪婪法是一种的算法。 A.不求最优，只求满意C.求取全部可行解B.只求最优D.求取全部最优解6、称一种语言为低级程序语言是由于它。A.离机器特性近 C.编程难度低B.离自然语言近 D.通用性强7、排序方法中，从未排序序列中依次取出元素与已排序序列(初始时为空)中的元素作比较，将其放入已排序序列的正确位置上的方法，称为.A.

3、 归并排序B. 二分法排序C. 冒泡排序D.排序8、若进栈序列为 3,5,7,9,进栈过程中可以出栈，则不可能是一个出栈序列。A. 7,5,3,9B. 9,7,5,3C.7,5,9,3D. 9,5,7,39、中缀表达式(a-b)*(cd)的后缀表达式是.A. abcd*-B. ab-cdC. ab-*cdD. a-bcd *10、字符A、B、C 依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成多少个不同的字符串？A. 5B. 4C. 6D. 111、一个字长的二进制位数是A.8B.16C.32D.随计算机系统而不同的12、当a=1,b=3,c=5,d=4 时，执行下面一段程序后，

4、x 的值为if(ab)thenif(cd)then x=1 elseif(ac)thenif(b1）则 fun(4)的值是A.25B.30C.33D. 2817、在完全二叉树中，若一个结点是叶结点，则它没A.C.B. 右子结点结点结点和右子结点D.结点、右子结点和兄弟结点在数组 A1.101中,对 1k101,若 Ak是叶子结点,则18、一棵含有 101 个结点的完全二叉树k 的最小值是。A. 51B.50C. 49D.48时要占个字节，设 I 从 0 变化到，J 从变化到 1，19、已知数组 A 中，每个元素 AI,J在分配内存时是从地址SB 开始连续按行分配的试问：A4,8的起始地址为A.

5、 SB+141B. SB+180C. SB+142D. SB+18120、下面关于图的的叙述中正确的是。A.B.C.用相邻矩阵法用相邻矩阵法用邻接表法图，占用的图，占用的图，占用的图，占用的空间大小只与图中结点个数有关，而与边数无关。空间大小只与图中边数有关，而与结点个数无关。空间大小只与图中结点个数有关，而与边数无关。空间大小只与图中边数有关，而与结点个数无关。D. 用邻接表法二、问题解答：(4+6=10 分)1、 将一支铅笔、一枝原子笔和一个橡皮擦分别放入A、B、C 三位的笔盒中，每个笔盒只能放一种文具，且三个笔盒内放的文具都不相同。下列三句叙述中只有一句为真，其余二句为假。试问哪一句为真

6、？A 的笔盒中放的是铅笔。B 的笔盒中没有铅笔。C 的笔盒中没有橡皮擦。2、喜欢收集布偶，她将红、蓝、黄色的趴趴熊、kitty 猫、狗布偶各 1 只（共 9 只）排成三行三列的方阵，然后请北北来猜。提示说：红色的动物都在第一列。黄色的动物都不在第三列。kitty 猫只能在四个角或正中间。趴趴熊只能在第一行最上面二个位置或在第三行最下面一个位置。第二行最下面一个位置放的是颜色的布偶。三、看程序写结果：(8+10+12=30 分)1.var x,y:eger;function(x,y:eger):eger;var r:eger; beginrepeatr:=x mod y; x:=y;y:=r;

7、until r=0;:=x;end;beginx:=80;y:=98;wrin(x*y div(x,y);end.输出：2. const n=12; var i,j:eger; list:array0.n ofbegineger;for i:=1 to n do read(listi); for i:=2 to n dobeginlist0:=listi; j:=i-1;while list0listj do beginlistj+1:=listj; dec(j);end; listj+1:=list0;end;for i:=1 to n do wriend.isti:5);输入：67 98

8、7823 2332 2323 64 90 -34 121 -98 22 67输出：3. var i,j,k,n:eger;a:array1.100,1.100 of beginreadln(n); k:=1;i:=1;j:=1;ai,j:=1;while kn doeger;beginif (i=1) and (j mod 2=1) then inc(j) else if (j=1) and (i mod 2=0) then inc(i)else if (i+j) mod 2=0 then begin dec(i);inc(j);end else if (i+j) mod 2=1 then b

9、egin inc(i);dec(j);end;inc(k);ai,j:=k;end;wrin(i,/,j);end.输入：1999输出：四、程序填空：(12+18=30 分)1、一个数如果正好等于其因子之和，就称其为“完数”。例如 6 的因子是 1，2，3，并且 6=1+2+3，所以 6 是一个“完数”。下面的程序可以输出 2n 之间的所有完数之和。其中n 为 21000 之间的任意整数。请将程序填写完全。PROGRAM bs1；VAR a，n，s:eger；FUNCTION func(n:eger)：；VAR s，k: BEGINs:=0；eger；FOR k:=1 TO DOIF n MO

10、D k=0 THENs:= ；IF THENfunc:=TrueELSEEND；func:=FalseBEGINs:=0；Readln(n)； FOR a:=2 TO n DOIF func THEN Wrin(s)END.s:=s+a；2.本程序的功能是将中缀表示的算术表达式转换成后缀表示。如中缀表达式(A-(B*C+D)*E)/(F+G)的后缀表示为ABC*D+E*-FG+/为了方便，假定变量名为单个英语字母，运算符只有/（均为双目运算符，左结合），并假定所提供的算术表达式非空且语法是正确的。另外，中缀表示形式中无空格符，但整个算术表达式以空格符结束。各数组意义如下：POLISH其后缀表示

11、;s是一个后进先出栈。函数 PRIOR(CHAR)返回符号 CHAR 的优先级，各符号的优先级如下表示：CHAR* /+ -()PRIOR(CHAR) 4321label 10; var input:string;polish,s:array1.100 of char;k,p,i:eger;function prior(ch:char) :begineger;if (ch=*) or (ch=/) then prior:=4;if (ch=+) or (ch=-) then prior:=3; if ch=( then prior:=2;if ch=) then prior:=1; end;procedure a; begin;end; procedure b; begin ;end;begininput:=(A-(B*C+D)*E)/(F+G); k:=0;p:=0;i:=1;while i=length(input) do beginif (inputi=+) or (inputi=-) or (inputi=*) or (inputi=/) then beginwhile p0 dobeginif end;a;then b e