当前位置:首页 >> 学科竞赛 >>

NOIP赛前强化练习套题及解


信息学奥赛校队集训

分卷强化练习

西安高级中学信息教研室 陆裕元编

信息学奥赛强化练习卷一
西安高中信息技术教研室制 1.请用等号或不等号联接表示下列不同进位制数值的大小。 例如: (3)10 <(4)4 =(100)2 < ( A )16 其中圆括号外右下角的下标,表示圆括号内数的进位制。

(98.375)10 (142.3) 8 (58.5) 16 (1011000.0101)2 解: (142.3) 8 =(98.375)10 (58.5) 16 =(88.3125)10 (1011000.0101)2 =(56.3125)10 所以: (98.375)10 = (142.3) 8 > (58.5) 16 > (1011000.0101)2 2.一个汉字的机内码目前通常用二个字节来表示:第一个字节是区位码的区号加(160)10; 第二个字节是区位码的位码加(160)10 。 已知:汉字“却”的区位码是 4020,试写出机内码两个字节的二进制的代码:

答:两个字节二进制代码为:11001000(160+40=20010),10110100(160+20=18010) 3. 已知 ASCII 码表中的大写字母后有 6 个其它字符,接着便是小写字母。现已知:A 字母的 ASCII 码为(41)16{ 表示 16 进制数 41 },试写出如下字母用十进制表示的 ASCII 码: G → ( )10 B → ( )10 T → ( )10 答:G → (71)10 B → (66 )10 T → (84 )10 4.小张用十六进制、八进制和十进制写了如下一个等式: 52 - 19 = 33 式中三个数是各不相同进位制的数,试问 52、19、33,分别为_________. (A)八进制,十进制,十六进制 (C)八进制,十六进制,十进制 答: (B) 根据题意分析,算式计算结果为 33,这个 33 不可能是十进制,否则 52、19 也必 须是十进制,这与题意不符;计算结果也不可能是 16 进制,若是,则 52 必须是 8 进制数减去十进制 19,其结果不可能是 16 进制 33,所以,选结果(B) ,其运算: (52)10 – (19)16 = (33) 8 ? 52- (16+9) = (3*8+3) 5.如果用一个字节来表示整数,最高位用作符号位,其它位表示数值。例如: 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 表示+1 表示-1 ↑ 符号位表示正 ↑ 符号位表示负 试问这样表示法的整数 A 的范围应该是_____________________。 (B)十进制,十六进制,八进制 (D)十进制,八进制,十六进制

(A) -127 ≤ A ≤ 127 (C) –128 ≤ A < 128 答: (A)

(B) -128 ≤ A ≤ 128 (D) -128 < A ≤ 128

6.下列 IF 语句中,ENDIF 表示相应 IF 的结束: y=0 if x<0 then Y=5 else if x<10 then y=10 if x<100 then y=100 endif else y=200 endif endif 试指出: 当 X=80 时,运行的结果是______; 当 X=5 时,运行结果为_________。 (A) Y=9 (B) Y=5 (C) Y=10 答: .当 x=80 时,运行的结果为 当 x=5 时,运行的结果为 E D 。 。 (D) Y=100 (E)Y=200

7.设栈 S 的初始状态为空,现有 5 个元素组成的序列{1,2,3,4,5},对该序列在 S 栈上 依次进行如下操作(从序列中的 1 开始,出栈后不再进栈) :进栈、进栈、进栈,出栈、进 栈、出栈、进栈。试问出栈的元素序列是______________。 (A){ 5,4,3,2,1} (B){2,1} (C){ 2,3} 答: (D) (D){3,4}

8.阅读下列程序段,写出程序段运行后变量 X 的值。 X1:=3 ; X2:=8 ; FOR I:=1 TO 5 DO BEGIN 循环结构,应用数据轮换方式,求 X:=(X1+X2)*2 ; 两个数和的 2 倍。 X1:=X2 ;X2:=X ; END; WRITELN( ‘X=’ ,X) ; 答:X=1224 X=2(3+8), 2(8+22), 2(22+60), 2(60+164), 2(164+448)= 1224 9.阅读下列程序段,写出程序运行后数组元素 A1,A2,?,A11 中的值。 A[1]:=1;

A[2]:=1 ; K:=1 ; REPEAT A[K+2]:=1 ; FOR I:=K DOWNTO 2 DO A[I]:=A[I] +A[I-1 ] ; K:=K+1 ; UNTIL K>=11 ; 答: A1 1 A2 10 A3 45 A4 120 A5 210 A6 252 A7 210 A8 120 A9 45 A10 10 A11 1

分析:先注意内循环功能:重复求从当前数组元素开始,求其本身原值与前一元素值之和; 外循环重复内循环的操作 10 次(K=11 时退出) ,列表跟踪变量变化可看出规律与结果: K A1 A2 A3 A4 A5 A6 A7 A8 A9 A10 A11 1 1 1 1 2 1 2 1 1 3 1 3 3 1 1 4 1 4 6 4 1 1 。。。。 。。。 10 1 10 45 120 210 252 210 120 45 10 1 10. 从入口(1)到出口(17)的可行路线图中,数字标号表示关卡:

现将上面的路线图,按记录结构存储如下: 1 2 3 4 5 6 7 8 9 10 No PRE 1 0 2 1 18 1 7 1 3 2 12 2 4 2 19 3 8 4 5 5

11

12 13 14 6 10

15 16 17 9 11

18

13 16 6 8

14 15 11 11

17 ? 12 ?

请设计一种能从存储数据中求出从入口到出口经过最少关卡路径的算法。 答:按广度搜索的方法生成了上述队列,(可以画出广度搜索结点发展的树型结构来看) 算法: 输出结果: I:=1; (17)

WHILE NO[I] I:=I+1;

<>17 DO

REPEAT WRITE(?(?,NO[I],?)?); WRITE(?↑?); I:=PRE[I]; UNTIL I=0;

↑ (16) ↑ (19) ↑ (18) ↑ (1)

11. 列举一个问题,使问题的解能对应相应的算法。 例如对算法: X:=10; Y:=5; READ(M,N) ; S:=X*M-Y*N; 可列举出如下的问题: 学生答题,答对一题可得 10 分,答错一题则要扣去 5 分,输入答对的题数(M) 与答错的题数(N) ,求最后得分(S)是多少? 现有以下算法: K:=0 ; FOR I:=0 TO 10 DO K:=K+(50-I*5)DIV 2+1

请列出一个相应的问题。 答:用五角钱换成 5 分、2 分与 1 分的硬币,有多少种换法。 I 代表 5 分币个数,K 累加 5 角钱对换成 5 分、2 分、1 分的对换方法总数 12. 有标号为 A、B、C、D 和 1、2、3、4 的 8 个球,每两个球装一盒,分装 4 盒。标号 为字母的球与标号为数字的球有着某种一一对应的关系 (称为匹配) 并已知如下条件: , ① 匹配的两个球不能在一个盒子内。 ② 2 号匹配的球与 1 号球在一个盒子里。 ③ A 号和 2 号球在一个盒子里。 ④ B 匹配的球和 C 号球在一个盒子里。 ⑤ 3 号匹配的球与 A 号匹配的球在一个盒子里。 ⑥ 4 号是 A 或 B 号球的匹配球。 ⑦ D 号与 1 号或 2 号球匹配。 请写出这四对球匹配的情况。 答:ABCD 4 3 12 由(3)可知 A 只能配 134 若 A 配 1 ,则(2) (5)矛盾;若 A 配 3,则(5)矛盾,所以 A 只能配 4 B 只能配 123 ,若 B 配 2,则(3) (4)矛盾,若 B 配 1,则 C 可配 2 或 3,但由(7) 知,此种情况下 D 只能配 2,则 C 就只能配 3,即 A4B1C3D2,按此配对, (5)将出现 (4) 矛盾,可见,B 不能配 1,所以,B 只能配 3 由(7)知 D 配 1 或 2,若 D 配 1,则 C 配 2,导致(2) (4)矛盾,所以 D 只能配 2, 则 C 配 1.

13. 已知如下 N*(N+1)/2 个数据,按行的顺序存入数组 A[1],A[2],??中: a11 a21 a22 a31 a32 a33 ?? an1 an2 an3 ?? ann 其中:第一个下标表示行 第二个下标表示列。 若:aij(i≥j,j,i=1,2,??n)存贮在 A[k]中,试问: (1)k 和 i,j 之间的关系如何表示? (2)给定 k 值(k≤n*(n+1)/2)后,写出能决定相应的 i,j 值的算法程序段。 答: (1)K=I*(I-1)/2+J (前 I-1 行共有 1+2+3+4+……+(I-1)=I*(I-1)/2 个元素) (2)程序段可以如下: READ(K); FOR I:=1 TO K DO FOR J:=1 TO I DO IF K=(TRUNC(I*(I-1)/2+J) THEN WRITE (K,?----?,I, J); 14. 有红、黄、黑、白四色球各一个,放置在一个内存编号为 1、2、3、4 四个格子的盒中, 每个格子放置一只球,它们的顺序不知。甲、乙、丙三人猜测放置顺序如下: 甲:黑编号 1,黄编号 2; 乙:黑编号 2,白编号 3; 丙:红编号 2,白编号 4 。 结果证明甲乙丙三人各猜中了一半。写出四色球在盒子中放置情况及推理过程。 答: 如果甲后半部分对,即:黄 2、白 3、红 2,黄红矛盾,所以只能是黑 1 白 3 红 2 15.已知:ACK(M,N)函数的计算公式如下: N+1 ACK(M,N)= ACK(M-1,1) ACK(M-1,ACK(M,N-1) 请计算:ACK(1,2)与 ACK(2,2)的值。 答: ACK(1, 2)=4 ACK(0,ACK(1,1) )=4 ACK(0,ACK(1,0) )=3 ACK(0,1)=2 所以 ACK(1,2)=4 ACK(2,2)=7

M=0 N=0 M≠0 且 N≠0

16.已知:A1,A2,??,A81 共有 81 个数,其中只有一个数比其它数大,要用最少的比 较运算次数,把这个值大的数找出来(假设两个数比较一次能决定出大于、小于或等于这三 种情况)请将以下算法补充完整: 第一步: S1 = A1 + A2 + ?? + A27 S2 = A28 + A29 +??+ A54 第一次比较(S1,S2) : S1 > S2 取 K=0 S1 < S2 取 K=27 S1 = S2 取 K=54 第二步: S1 = AK+1 + AK+2 + ?? + AK+9 S2 = AK+10 + AK+11 +??+ AK+18 第二次比较(S1,S2) : S1 > S2 取 K= S1 < S2 取 K= S1 = S2 取 K= 第三步: S1 = AK+1 + AK+2 + AK+3 S2 = AK+4 + AK+5 + AK+6 第三次比较(S1,S2) : S1 > S2 取 K= S1 < S2 取 K= S1 = S2 取 K= 第四步: S1 = AK+1 S2 = AK+2 第四次比较(S1,S2) : S1 > S2 为最大数 S1 < S2 为最大数, S1 = S2 为最大数。 答:第二次比较(S1,S2) : S1>S2 S1<S2 S1=S2 取 K=K+0 取 K=K+9 取 K=K+18

第三次比较(S1,S2) : S1>S2 S1<S2 S1=S2 取 K=K+0 取 K=K+3 取 K=K+6

第四次比较(S1,S2) : S1>S2 S1<S2 S1=S2 AK+1 AK+2 AK+3 为最大数 为最大数 为最大数

17. 下面是一个利用完全二叉树特性,用顺序表来存储的一棵二叉树,结点数据为字符型

(结点层次号从小到大,同一层从左到右顺序存储,#表示空结点,@表示存储数据结束) 。 现要求画出对应该存储结构的二叉树示意图。 分) (7 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 A B 答: C # # D E # # # # # G F A C E F @

18. 设数组 A[10..100,20..100] 以行优先的方式顺序存储,每个元素 B 占 4 个字节,且已知 A[10,20]的地址为 1000,则 A[50,90] D 的地址是 。 G 答:地址是 14240 数组大小 A[10..100,20..100]共占有 91 行,每行有 81 个下标 变量共计 7371 个单元; A[10,20]的起始地址为 1000,A[10,100]的起始地址是: 1000+(100-20)*4=1000+320 每行的起始地址计算公式:1000+(X-10)*324+(100-20)*4; 任意一行一列的起始地址计算公式:1000+(X-10)*324+(J-20)*4 所以:A[50,90]的起始地址是:1000+40*324+70*4=14240

19. 下面是一个求:1/1+1/2+2/3+3/5+5/8+8/13+13/21+21/32…前 20 项的和的程序段,试将 程序补充完整: S:=0 ;A:=1 ; B:=1 ; FOR K:=1 TO 10 DO BEGIN S:=____① ;A:= _ ②____; S:= __ _③ ; B:= _ ④ ; END; WRITELN(S) ; 答:① S+A/B ② A+B ③ S+B/A ④ A+B 20. 为了便于处理表达式,常常将普通表达式(称为中缀表示)转换为前缀{运算符在前, 如 X/Y 写为/XY} 和后缀 { 运算符在后,如 X/Y 写为 XY/}的表达形式。 在这样的表示中可以不用括号即可确定求值的顺序,如: (P+Q)*(R-S)→*+PQ-RS 或 → PQ + RS -* ① 试将下面的表达式改写成前缀与后缀的表示形式: <A> A+B*C/D <B> A-C*D+B∧E ② 试将下面的前缀表示还原成中缀的表示形式,同时写出后缀表示: +△A *B△C {前缀式中△表示一元运算符取负号,如△A 表示(-A)} 答: ①<a>前缀形式为:+A/*BCD;后缀形式为:ABC*D/+ <b>前缀形式为:+-A*CD∧BE;后缀形式为:ACD*-BE∧+ ② 中缀形式为(-A)+B*(-C) ;后缀形式为:A△BC△*+

本题也是二叉树的遍历(前序、中序、后序)的一种应用 (1) 将中缀表达式按中序遍历法画出表达式树,对此树按前序遍历和后序遍历将分别 得到前缀表达式:+A*B/CD = +A/*BCD;和后缀表达式:ABCD/*+ = ABC*D/+ (2)先按前序遍历画出表达式树,然后按照中序及后序遍历写出相应的中缀表达式及后 缀表达式。 + A B C * / D A - C - - + ^ × - B D E - A B + * - C

21. 一个将角编了号的正三角形可以绕着外心 O(中心)逆时针旋转 1200,如下图所示: 1 3


0 3

2

a



0 2

1

图一 图二 如果将这一旋转用字母 a 来表示,看作运算对象,同时用 aa 或 a2 表示旋转 1200 后再旋转 1200 ,也就是说将连续运动看作乘法运算,那么三角形状态(可简 称为元素)即可与运动表达式关联起来,请回答: ① 如果将图一的原始三角形连续旋转 1200N 次,简单地表示为 an (N 为任意自 然数) ,试求 an 的值(指三角形旋转后的结果状态) ; -1 ② 如果将下面的旋转看作是 a 的逆元素,记为 a ,则有 a-1 = a2 试求:a-n 3 1


0 2

1 答: ①a =
n

aa 图三



0 3

2

a ,当 n MOD 3=1 时; a2,当 n MOD 3=2 时; a3,当 n MOD 3=0 时;

②a =

-n

a2,当 n MOD 3=1 时; a ,当 n MOD 3=2 时; a3,当 n MOD 3=0 时;

信息学奥赛强化练习卷二
西安高中信息技术教研室制 1.下列无符号数中,最小的数是( ) A. (11011001)2 B. (75)10 答:C C. (37)8 D. (2A)16

2.某台计算机的内存容量为 640K,这里的 640K 容量是指( A.640 个 B.640*1000 个 C.640 * 1024 个 答:C

)字节 D.640*1024*1024 个

3.有 8 个小球, 其中 7 个重量相同, 仅有一个较重, 要求在天平上称两次, 找出重的小球来. 解决这个问题的算法,用自然语言描述为: 答:解决这个问题的算法, 用自然语言描述为: ①任取 6 个球,在天平上每边放 3 个; ②若相等,则余下的 2 个中必有 1 个,此时在天平每边放 1 个,再称一次即可。 ③若不相等,则从较重的一边的 3 个球中任取 2 个称量: 若相等,则剩下的 1 个即为所求; 若不相等,则重的一边为所求。 4.有一堆游戏棒,第一个参加游戏的人取走了一半多一根,第二个游戏者再将剩下的取走 一半多一根,以此类推,以后的游戏者均取走前一次剩下的一半多一根,到第 10 个人来取 时,发现只剩下一根了。 问:游戏开始前这堆游戏棒共有多少根?写出最简洁的算法程序段,来描述是如何求 解的。 答:程序段如下: S:=1 FOR I:=9 DOWNTO 1 DO S:=(S+1)*2; WRITE ( ‘S=’ ,S) ; 5.在微机中,通用寄存器的位数是 。 A.8 位 B.16 位 C.计算机字长 D.32 位 答:C 6.不同的计算机,其指令系统也不同,这主要取决于 。 A.所用的操作系统 B.系统的总体结构 C.所用的 CPU D.所用的程序设计语言 答:C 7.公安部门破译了某一段密电码与其译文,现列如下(□:表示一个空格) ; 密电码: NC□WLH□6.0□□XLN 译 文: MX□DOS□6.0□□COM 现已知此密电码及译文所使用的均为 26 个英文大写字母 (其他字符不变) 请根据此对 。 应规律,写出某一个密电码字母(X$)与其译文字母(K$)之间的 ASCII 码的关系表达 式: 。

并根据以上规律,将以下译文,还原成密电码: 译 文:WINDOWS□98 密电码: 答:根据此对应规律,某一个密电码字母(X$)与其译文字母(K$)之间的 ASCII 码 的关系表达式为:ASC(K$)或 ASC(X$)=155-ASC(K $) (Z(90)+A(65)=155) 根据以上对应规律,以下译文,还原成密电码为: 译 文:WINDOWS□98 密电码:DRMWLDH□98 8.已知 N 个自然数(1,2,?,N)的各位数字的总个数是 1980,求 N= {例如:有自然数 1,2,3?,9,10,即数字总个数为 11 时,n=10} 答:666 (696) 分析:1 位数时:数字个数 9 个 2 位数时:数字个数 20*9=180 个 3 位数时:100?199 共 3*100=300 个,100?699 共 6*3*100=1800 。 9.我们将正方形沿着中心逆时针旋转 90°的运动用符号 a 来表示: 1 4 4 3 a 2 3 2 1 如果将连续两次旋转 90°的运动看作是 a 和 a 的乘法运算,记为:aa 或 a2,如下所示: 1 2 4 a2 3 4 1 (1)请对下图画出 an 运动的结果,这里 n 取自然数,an 表示连续进行 n 次旋转 90°的 运动。 1 4 an 2 3 (2)如果将如下的旋转运动看作 a 的逆元素,记为 1/a; 4 3 a3 1 2 2 那么便有:1/a=a3 问题:an 的逆元素 1/an 的值是什么(n 取自然数)? 答: ① an 运动的结果图示为: 1 2 4 4 3 3 4 2 1 n mod 4=2 3 1 4 3 2

2 3

1 4 n mod 4=3

3 1 2 n mod 4=0 n mod 4=1 ② an 的逆元素 1/ an 的值是:

当 n MOD 4=0 时,1/ an 的值是:a4 当 n MOD 4=1 时,1/ an 的值是:a3 当 n MOD 4=2 时,1/ an 的值是:a2 当 n MOD 4=3 时,1/ an 的值是:a 10.已知一个数列 1,1,2,3,5,?,可用符号表示为 a1=1,a2=1,a3=2,?,试写出 an-2,an-1,an 之间的关系。 答:an = an-1+ an-2 (N>=3) 11.任给自然数 N,K(1≤K≤9) ,按如下计算步骤(算法)求序列 XjXj-1?X0 步骤: ① j=0 ② 如果 N>=K 则转第 3 步,否则转第 7 步 ③ Xj=N MOD K {DIV 表示整数除法,结果取整数;MOD 表示整除去余数} ④ N=N DIV K ⑤ j=j+1 ⑥ 回第二步 ⑦ Xj=N ⑧ 结束 试求当:N=1998,K=3 时,XjXj-1?X0 之值。 答:当 n=1998,k=3 时,xjxj-1...x0 之值为 2202000 根据题目内容和程序的算法, 可以知道这是一个典型的将十进制数转化成任意进制数 的程序(1≤K≤9) 是被转换的十进制数,K 是需要转换的进制数;转换方法:重复将被 ,n 除数除以 K(进制) ,求余数将余数存入 Xj 中,并计算新的被除数,直到被除数为零;反 向输出余数得到转换后的数。 12.已知数组 A 的下标 I 可以从 1 变化到 100,如果假设 A(100)的下一个元素是 A(1)。当 任给定下标 I(1≤I≤100)后,试写出取下一个数组元素值赋给变量 X 的程序段。 答:程序段如下: IF I<100 THEN X:=A[I+1] ELSE X:=A[1] 13.某班有 50 名学生,每位学生发一张调查卡,上写 a,b,c 三本书的书名,将读过的书 打?,结果统计数字如下: 只读 a 者 8 人;只读 b 者 4 人;只读 c 者 3 人;全部读过的 有 2 人;读过 a,b 两本书的有 4 人;读过 a,c 两本书的有 2 人;读过 b,c 两本书的有 3 人。 请问: (1)读过 a 的人数是 (2)一本书也没有读过的人数是 答: (1)读过 a 的人数是:=A+AB+AC-ABC=8+4+2-2=12 人 , (2)一本书也没有读过 的人数是 :50-(A+B+C+AB+BC+AC-2ABC)=50-20=30 人 本题是推理题,可用集合概念推理得到结果。 AB=4 B=4 ABC=2 BC=3 C=3 A=8 AC=2

14.分别用邻接矩阵和邻接表表示出下面的无向图: 答:邻接矩阵如下: 0 1 0 0 0 0 0 1 0 1 1 0 0 0 0 1 0 1 0 0 0 0 1 1 0 1 1 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 1 1 0 邻接表如下: V1:---2 V2:---1---3---4 V3:---2---4 V4:---2---3---5---6---7 V5:---4---7 V6:---4---7 V7:---4---5---6

15.给出一棵二叉树的中序遍历:DBGEACHFI 与后序遍历:DGEBHIFCA 画出此二叉树。 答: A B D G E H C F I

16. 将 Ln 定义为求在一个平面中用 n 条直线所能确定的最大区域数目。例如:当 n=1 时, L1=2,进一步考虑,用 n 条折成角的直线(角度任意) ,放在平面上,能确定的最大区域数目 Zn 是多少?例如:当 n=1 时,Z1=2(如下图所示) 当给出 n 后,请写出以下的表达式: 1 Ln = ______________ 2 Zn = _______________ 答分析: (1)通过几何知识知道,N 条直线两两相交,所构成的区域数目最大: 4 1 2 N=1, L1=2 N=2, L2=4 N=3, L3=7 N=4, L4=11 N=5, L5=16 …… F(1)=2; F(2)=F(1)+2; F(3)=F(2)+3; F(4)=F(3)+4; F(5)=F(4)+5; 3 1 7 6 5 2 4 3

由此推出 F(n)=F(n-1)+n F(n)=n+(n-1)+(n-2)+…+2+1+1=n*(n+1)/2+1

1 2 1 7 用 N 条折线所能确定的最大区域数目是:

6 5 2 4 3

N=1, Z1=2 F(1)=0+2; N=2, Z2=7 F(1)=1*(2*2-1)+4; N=3, Z3=16 F(3)=2*(2*3-1)+6 …… 由此推得:N=K 时,F(k)=(k-1)*(2*k-1)+2*k 确定的最大区域数目为:Zn=(n-1)*(2n-1)+2n 17.设循环队列中数组的下标范围是 1–n,其头尾指针分别为 f 和 r,则其元素个数为( ) . A.r- f B.r- f +1 C. f ) MOD n+1 (rD. f + n) MOD n (r答:D 3 4 2 5 循环队列中,头指针和尾指针指向同一个单元, 元素个数为(r-f+n) mod n f 1 6 队列的头指针是指向第一个元素的前一个单元,队尾指 9 7 循环队列一般特征: 8 r f= r 时,可能是队空或队满,编程时, 实际队空:f=r 时,置 r=f=0,所以 r =0 时队空; 实际队满: (r mod n = f mod n) and (f<>0) 补充: (1 判定一个队列 Q(最多元素为 N)为空的条件是: front = rear (2 判定一个队列 Q(最多元素为 N)为队满的条件是:rear – front = N (3 判定一个循环队列 Q(最多元素为 N)为空的条件是:front = rear (4 判定一个循环队列 Q(最多元素为 N)为队满的条件是:front = (rear + 1)mod N (5 循环队列用数组 A[ 0 . . N-1 ] 存入元素值, 已知其头尾指针分别是 front 和 rear , 则当前队列中的元素个数为:( rear – front + m ) mod N 18.阅读程序,写出程序的正确运行结果: program exp1 (imput,output); VAR i, s, max: integer; a :array [1..10] of integer; begin for i:=1 to 10 do read (a[i]); max:=a[1] ;s:=a[1]; for i:=2 to 10 do begin if s<0 then s:=0; s:= s+a[i]; if s>max then max:=s end; writeln(?max=?, MAX) end.
输入:8 9 -1 24 6 5 -11 15 -28 9

输出:max= 答:51

信息学奥赛强化练习卷三
西安高中信息技术教研室制

阅读程序写执行结果题型答题方法指导
阅读程序写执行结果这种题型较易失分,因为一旦最终结果不正确,将一分不得,这种 题型主要考察学生: (1 程序设计语言的掌握情况; (2 数学运算能力; (3 细心、耐心的心理品质。 解决这类问题的关键在于能够分析程序的结构以及程序段的功能。 完成这类题的一般方法和步骤是: (1 从头至尾通读程序,大致把握程序的算法; (2 通过给程序分段,理清程序的结构和层次,达到读懂程序的目的; (3 阅读程序中特别注意跟踪主要变量的值的变化,可以用列表法,了解变量变化的规 律和程序的运行结果。所谓列表法,就是将各变量名作为表头,在程序的执行过程中,将各 变量值的变化记录在相应变量下方。 (4 阅读程序时,应特别注意过程、函数所完成的子任务以及和主要程序之间的参数传 递关系。 A)在阅读程序中,比较好的方法是先阅读主程序,看其需要调用的过程或函数是 什么,最后要求输出变量是什么?(注意输出语句) B)阅读程序中,将较长的程序分成几个程序段(特别注意循环结构、判断结构) , 阅读理解各程序段的功能以及各程序段之间的关联; C)切记在阅读程序时,一定不能浮躁,要有足够的耐心,因为有些程序读起来是 比较繁琐的。 1.阅读程序,并给出结果 PROGRAM EXP1(INPUT,OUTPUT); VAR I,J,K,S,T:INTEGER; A:ARRAY[1..16] OF INTEGER; BEGIN FOR I:=1 TO 16 DO A[I]:=I; FOR I:=1 TO 3 DO BEGIN J:=1; S:=1; FOR K:=1 TO I-1 DO S:=S*2; WHILE J<16 DO BEGIN FOR K:=1 TO S DO BEGIN A[J+K-1]:=A[J+K-1]+A[J+K-1+S]; A[J+K-1+S]:=A[J+K-1]-A[J+K-1+S]; A[J+K-1]:=A[J+K-1]-A[J+K-1+S]; END; J:=J+S*2;

END; END FOR I:=1 TO 16 DO BEGIN WRITE (A[I]:3); IF I MOD 8 =0 THEN WRITELN; END; END. 输出结果是: 答:程序的运行结果是: 8 7 6 5 4 3 2 1 16 15 14 13 12 11 10 9 I S A1 A2 A3 A4 A5 A6 A7 A8 A9 A10 A11 A12 A13 A14 A15 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 1 2 1 4 3 6 5 8 7 10 9 12 11 14 13 16 2 2 4 3 2 1 8 7 6 5 12 11 10 9 16 15 14 3 4 8 7 6 5 4 3 2 1 16 15 14 13 12 11 10 分析可知:I 循环 3 次,每次循环主要是交换两个数组元素的值,两元素之间相隔列数 为 S,跟踪一下变量 I,J,S,K 的变化,就会发现这个规律,所以最后的结果就是 I=3, S=4 时 A 数组按规律交换后的值。 2.阅读程序,并给出结果 PROGRAM TTO_004; VAR I, J, J1, J2, P, Q :INTEGER; P1 :BOOLEAN; B,C :ARRAY[1..100] OF INTEGER; BEGIN READLN(Q, P); J:=1; P1:=TRUE; B[J]:=Q; J1:=0; WHILE (Q>0) AND P1 DO BEGIN J1:=J1+1; C[J1]:=Q*10 DIV P; Q:=Q*10-C[J1]*P; IF Q>0 THEN BEGIN J2:=1; WHILE (B[J2]<>Q) AND (J2<=J) DO J2:=J2+1; IF B[J2]=Q THEN BEGIN P1:=FALSE; WRITE(?0.?); FOR I:=1 TO J2-1 DO WRITE(C[I]:1); WRITE(?{?); FOR I:=J2 TO J1 DO WRITE(C[I]:1); WRITELN(?}?) END ELSE BEGIN J:=J+1;B[J]:=Q END END END; IF Q=0 THEN BEGIN WRITE(?0.?);

A16 16 15 13 9

FOR I:=1 TO J1 DO WRITE(C[I]:1); END; READLN END. 输入 (1) 1 (2) 2
答:①

WRITELN

8 7

输出: 输出:

0.125 ② 0.{285714}

分析:分析程序可以看出:该程序实际是求两个整数相除所得的商。 (1 在读程序时,同学们应该把握住程序的重点语句,也就是能表达出程序的主要目的 的主要语句,在该程序中,主要语句是: J1:=J1+1; C[J1]:=Q*10 DIV P; Q:=Q*10-C[J1]*P; 该段程序是一个典型的逐位求商的语句,是 Q 被 P 除,商放在 C[ J1 ]中。根据问题中 给的数据可以知道,本题得到的结果是一个纯小数的数据。 对于纯小数的处理有两种情况: A) Q 被 P 能除尽; B) Q 被 P 不能除尽。 (2 WHILE Q>0 AND P1 DO 重复做,将每次产生的余数 Q 值存在数组 B 中,判断下 标变量 B[ J2]是否与 Q 相等,若相等,则是无限循环小数,按循环小数处理;否则将余数扩 大 10 倍,再进行除法运算。 IF B[J2]=Q THEN BEGIN P1:=FALSE; 循环小数处理 WRITE(?0.?); FOR I:=1 TO J2-1 DO WRITE(C[I]:1); WRITE(?{?); FOR I:=J2 TO J1 DO WRITE(C[I]:1); WRITELN(?}?) END 否则继续做除法 ELSE BEGIN J:=J+1;B[J]:=Q END (3 当 Q=0,表示 Q 被 P 除尽,则输出小数点后的所有余数 IF Q=0 THEN BEGIN WRITE(?0.?); FOR I:=1 TO J1 DO WRITE(C[I]:1); WRITELN END; 理解上述程序功能后,根据输入数据的情况,输出结果用手工除法即可得知。所以阅 读程序要注意分析程序的功能。 3. 阅读程序,写出该程序正确的运行结果: (1)program xp1 var x,y,z:integer; function gcd(a,b:integer):integer; begin if a=b then gcd:=a else if a>b then gcd:=gcd(a-b,b) else gcd:=gcd(a,b-a)

end; begin readln(x,y,z);x:=gcd(x,y);x:=gcd(x,z); writeln(x); end. 输入:6 2 4 程序输出结果为: 答:程序的运行结果是:2 分析可知:该程序功能是求三个整数的最大公约数。 4. 阅读程序,写出执行结果 program xp2; var i,j: integer; begin writeln; {?□?表示一个空格} writeln(?*?:40); writeln(?* * *?:41); for I:=1 to 4 do begin write(?□?:38-I); write(?* *?); for j:=1 to 2*I-1 do write(?□?); writeln(?* *?) end; end. 程序输出结果为: 答:输出结果为一个人字图形 * *** ** ** ** ** ** ** ** ** 二重循环打印图形的程序,一般外循环控制行的变化,内循环控制列的变化。 5. 阅读程序,写出执行结果: program exXp3; var i,j:integer; a:array[1..14] of integer; procedure sw(i1,j1:integer); var k1:integer; begin for k1=1 to (j1-i1+1) div 2 do begin a[i1+k1-1]:=a[i1+k1-1]+a[j1-k1+1];

a[j1-k1+1]:=a[i1+k1-1]-a[j1-k1+1]; a[i1+k1-1]:=a[i1+k1-1]-a[j1-k1+1]; end; end; begin j:=211; for I:=1 to 14 do begin a[I]:=i;j:=j-i; end; sw(1,4); sw(5,10); sw(11,14);sw(1,14); for I:=1 to 14 do begin if j mod I=1 then write(a[i]:3); j:=j-a[i]; end; writeln; end. 程序输出结果为: 答:程序的运行结果是:12 5 10 分析: (1 本题的程序结果非常清晰,易于阅读,读者只要把握过程的功能、主程序如何与 过程衔接,就可以很快知道问题的解; (2 过程的主要作用是利用数学的和差计算,交换两个下标变量的值(参考本卷第 1 题) ;交换单元是首尾两个存储单元 (3 主程序的作用是给 a 数组赋值, 分段调用过程交换两个下标对应的数组元素的值, 跟踪变量的变化情况观察数组变化情况; (4 J 初值=211,经过 J=J-1,J=106; (5 将 J 除以 I 余数为 1 的下标变量输出。 (对应 a[2] a[5] a[10]) 6. program exp3(input,output);
VAR I,J,S:INTEGER; B :ARRAY[0..5] OF INTEGER; BEGIN S:=1; FOR I:=1 TO 5 DO B[I]:=I J:=1; WHILE J>0 DO BEGIN J:=5; WHILE (J>0) AND (B[J]=10+J-5) DO J:=J-1; IF J>0 THEN BEGIN S:=S+1; B[J]:=B[J]+1; FOR I:=J+1 TO 5 DO B[I]:=B[J]+I-J END;

END; WRITELN('S=',S); END.

答:S=252 分析:本程序输出十分简单,就是一个 S 值,其初值为 1. 该程序的难点在于循环语 句的嵌套,为此,必须明确其循环范围,才能顺利阅读并跟踪程序。 初始状态 S=1,S[0]=0,B[1]=1,b[2]=2,?b[5]=5,j=1。进入循环(外循环)J=5, 内循环条件不满足 b[5]<>10;所以 S=2,b[5]=6;这样到 s=6 时,b[5]=10,内循环条件才 满 足 ( J>0 and b[5]=10 ) 这 时 J=4,S=7,b[4]=5,b[5]=6 ; 由 此 可 知 , 只 有 当 , b[5]=10,b[4]=9,b[3]=8,b[2]=7,b[1]=6 时程序才结束。B[1]~b[5]的任何元素增加 1 都引 起 S 加 1,这样,只要统计 b[1]~b[5]达到结束程序的终值共增值的次数即可获得输出的 S 值(注意:b[j]增值后,b[j+1]~ b[5]初值将进行重赋值) 。下表列出了运行程序过程中数 组 b 和 S 的变化。 初值 循环中的变化 1 2 3 5 6 7 1 2 3 5 10 11 1 2 6 ? 9 10 52 1 6 8 ? 9 10 125 1 2 3 6 7 12 1 2 7 8 9 53 1 7 8 9 10 126 2 3 4 5 6 127 ? ? 1 2 3 6 10 15 1 2 3 7 8 16 1 2 7 9 10 55 1 2 3 7 10 18 1 2 8 9 10 56 3 7 8 9 10 231 4 5 6 7 8 232 ? ? 1 2 3 8 9 19 1 2 3 8 10 20 1 3 4 5 6 57 1 2 3 9 10 21 1 3 8 9 10 91 4 7 8 9 10 246 1 2 3 5 6 22 1 4 5 6 7 92 5 6 7 8 9 247 ? ? ? 1 2 4 9 10 36 1 4 8 9 10 111 5 7 8 9 10 251 1 2 5 6 7 37 1 5 6 7 8 112 6 7 8 9 10 252 ? ? 1 2 5 9 10 46 1 5 8 9 10 121 B[1]1 1 B[2]2 2 B[3]3 3 B[4]4 4 B[5]5 10 S=1 B[1] B[2] B[3] B[4] B[5] S=46 B[1] B[2] B[3] B[4] B[5] 6 1 2 6 7 8 47 1 6 7 8 9

S=121 122

信息学奥赛强化练习卷四
西安高中信息技术教研室制
1〃阅读程序,写出程序运行结果 Program exp2 (input,output);

Const n=5; Var i,j,k : integer; a : array[1..2*n, 1..2*n] of integer; Begin K:=1; For I:=1 to 2*n-1 do If i<=n then if odd(i) then for j:= I downto 1 do begin a [I-j+1,j]:=k; else for j: =1 to begin i do k:=k+1; end downto I-n+1 do k:=k+1; end a[i-j+1,j]:=k; k:=k+1;end

else if odd(i) then for j:=n begin a[I-j+1,j]:=k; else for j:=I-n+1 to n do begin a[I-j+1,j]:=k; for I:=1 to n begin for j:=1 to n do writeln end; end. 答:输出结果为: 1 2 6 3 5 4 9 10 12 18 21 23 11 19 20 24 25 do

k:=k+1; end;

write(a[I,j]:3);

8 13

7 14 17 15 16 22

分析:该程序已知 10*10(N=5)的二维数组,程序最后输出数组左上角 5*5 的 部分;显然程序中主要完成的处理是向数组左上角元素中填写数值,填写的数值为 K,K 的 初值为 1,填写一次增加 1,可见该程序要将 1、2、3…逐次填入要输出的部分,整个填写 过程由一个循环语句 FOR I:=1 TO 2*N-1 DO 来完成;2N-1 正好是 N*N 二维数组(矩阵) 的对角线条数,可见填数过程是按对角线方向填写的。 从整个程序的大体情况来看,分为两个循环,第一个循环为(I=1 TO 2N-1) ,主要

完成将 K 值不断地赋给数组 A, 第二个循环为最后一段双重循环输出 A 数组的左上角矩阵。 程序在大循环(I=1 TO 2N-1)范围内又包含了两小块,第一块为 I<=N 时,奇数行、偶数行 分别赋值,第二块为 I>N 时,奇数行偶数行分别赋值。 从程序看,程序先将 2N-1 条对角线分为 1-N(1~5)和 N+1~2N-1(6~9)两组; 对每一组 都分奇偶两种情况,第一组对 I 为奇数号对角线而言,列坐标 J 由大到小(从 I 降到 1) ,行 坐标由小变大(从 1 变到 I) ,可见对角线填数方向为右上到左下,同样可以发现对 I 为偶数 号对角线而言,程序中行坐标由大变小(从 I 变到 1) ,列坐标由小变大(由 1 变到 I) ,对 角线填数方向为由右下到左上。 对第二组对角线而言, 所不同的仅是行列坐标的变化范围不 同(I 为奇数时,列坐标从 N 变到 I,行坐标由 I-N+1 变到 N;I 为偶数时列坐标由 I-N+1 变 到 N,行坐标由 N 变到 I-N+1) 。 对 I=1 2 3 4 5 6 7 8 9 该程序主要考测同学们的对下标变化规律的理解。 2. 阅读程序,写执行结果 Program uup3 (input,output); Const N=10; Var S,I : integer; Function CO(I1:integer) : integer; VAR J1,S1 : integer; Begin S1:=N; For J1:= (N-1) downto S1:= S1*J1 CO:=S1 End; Begin S:=N+1; For I:= 2 to N do S:=S + CO(I); Writeln(?S=?,S); End. 答:S=1024 (11+45+120+210+252+210+120+45+10+1) 该题主要考测同学们对函数过程的理解。 主程序十分简单表达了一个求和过程 (n=10) s=11+co(2)+co(3)+co(4)+…+co(10), 最 : 后输出 S;函数 CO(I)是由函数过程定义的,它的计算方法是: (N-I1+1) do div (N-J1+1); N=5, 2N-1=9 的各条对角线填数的方向如图示:

CO(I)=(n(n-1)……(n-I+1))/(2*3*……I) = (10*9*……(10-I+1))/(2*3*….i) co(2)=(10*9)/2=45 co(3) =((10*9)/2)* 8/3=(45*8)/3=120 co(4) =(((10*9)/2)* 8/3)*7/4= ( 120*7)/4=210 co(5) =((((10*9)/2)* 8/3)*7/4)*6/5= ( 210*6)/5=252 co(6) =(252*5)/6 =210 co(7) =(210*4)/7 =120 co(8) =(120*3)/8 =45 co(9) =(45*2)/9 =10 co(10)=(10*1)/10=1 3. 阅读程序写出执行结果 Program exp4(input,output); Const N=3; VAR I, J,S,X :integer; P G Begin For I := 0 to 100 do G[I]:=0; P[0]:=0; P[n+1]:=100; For I:= 1 to n do read (P[I]); readln; For I:= 0 to n do For J:= I+1 to N+1 do G[abs(P[J]-P[I])]:=G[abs(P[J]-P[I])]+1; S:=0; For I:=0 to 100 do Write(I :4); S:=S+1; End; Writeln; writeln(?S=?,S); Writeln(?input data:?); readln(X); Writeln(G[x]) End. 输入:10 20 65 input data: 10 输出: 答:10 20 34 45 55 65 80 90 100 S=9 输入:input data:10 If G[I]>0 then begin :array[0..n+1] of integer; :array[0..100] of integer;

输出:2 从程序的输出部分可以看到输出的内容为数组 g[0..100]中大于 0 的元素的下标及大于 0 的元素的总个数 S,然后根据输入下标 x, 再输出数组中的元素 g[x]的值。 程序的主体部分是根据 p 数的初值 (其中 p[1]~p[3]为输入数据: p[0]=0, p[1]=10, p[2]=20, p[3]=65, p[4]=100 来计算数组元素 g[0] ~ g[100]的值 (它们的初始值为 0) 其计算规律为 , (循 环控制变量 I 从 0 变到 3) : I=0 J=1 J=2 J=3 J=4 g[10]=1 g[20]=1 g[65]=1 g[100]=1 I=1 J=2 J=3 J=4 G[10]=2 g[55]=1 g[90]=1 I=2 J=3 J=4 G[45]=1 g[80]=1 I=3 J=4 G[35]=1 这样输出结果为:10 20 34 45 55 65 80 90 100 S=9 Input data: 10 2 {2 是 G[10]的值}
4〃 阅读程序,写出执行结果 Program EXP4 (input,output); const n=4; type se=array[1..n*2] of char; var i,j,i1,j1,k,s,t,s1,l,swap :integer; temp :char; a :se; begin for i:=1 to n*2 do read(a[i]); readln; s:=0; t:=0; for i:=1 to n*2 do

if a[i]='1' then s:=s+1 else if a[i]='0' then t:=t+1; if (s<>n) or (t<>n) then writeln('error') else begin s1:=0; for i:=1 to 2*n-1 do if a[i]<>a[i+1] then s1:=s1+1; writeln('jamp=',s1); swap:=0; for i:=1 to 2*n-1 do for j:=i+1 to 2*n do if a[i]<>a[j] then begin temp:=a[i];a[i]:=a[j] ;a[j]:=temp; s:=0; for l:=1 to 2*n-1 do if a[l]<>a[l+1] then s:=s+1;

if s>swap then begin swap:=s; i1:=i; j1:=j end; temp:=a[i]; a[i]:=a[j]; a[j]:=temp end; if swap>0 then end END. 输入:10101100 输出: 答:输入:10101100 输出:jamp=5 maxswap=2 i=6 j=7 该程序的输出分两步,先输出 jamp=, 然后可能输出 maxswap= i= j= (在 swap>0 的条件下才有输出, swap<=0 时, 第二步没有输出。Swap 变量的初值为 0,在第一步输出结 束后给出)。 这样就可以比较明显地来分段阅读程序了。 数组元素 a[1] ~ a[8] 中读入的初始数据为: a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] 1 0 1 0 1 1 0 0 从程序比较容易看出,第一段(第一步输出前的部分)s 中记录了 a[1] ~ a[8] 中 1 的 个数,t 中统计了 0 的个数(对输入数据而言 S=4, t=4); 如果输入 0,1 的个数不等,作出错 处理。 接着程序对相邻字符进行了逐个比较;由变量 S1 记录了相邻字符不相等的个数,对 输入的数据而言,a[1]<>a[2], a[2]<>a[3], a[3]<>a[4], a[4]<>a[5], a[5]<>a[6], a[6]<>a[7], 共 5 组,所以第一步输出为:jamp=5 第二段程序将对数组中的字符逐个与后面所有字符进行比较,不等时交换内容;交换 后立即统计相邻字符不相等的个数, 记录在 S 中; 当交换后, 相邻字符不相等的个数变大时, 立即将其保存,swap 中保存个数,i1,j1 记录交换字符的位置。然后再将数组内容复原。 可见最后输出的结果为:交换两个字符位置引起相邻字符不等的个数的最大值,以及 这次交换位置的两个数组元素下标值。这样,就可不必模拟程序运行,直接将程序运行结果 一眼看出来: a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] 1 0 1 0 1 1 0 0 相邻不相等个数 5,交换 A[6] 和 A[7]的内容得: 1 0 1 0 1 0 1 0 相邻字符不相等个数为 7,这时相邻字符不相等个数已达到了最大值,比原来增加 2, 所以第二步输出结果为:MAXSWAP=2 I=6 J=7 如果按程序一步一步模拟执行出结果,将会很麻烦,而且容易出错,可见阅读程序的 关键是要读明白程序表达的算法。 5.阅读以下程序,写出程序的运行结果: program ppex; CONST N=23 VAR I,J,TEMP,V:INTEGER; A :ARRAY[1..N] OF CHAR; B :ARRAY[0..9]OF INTEGER; writeln('maxswap=',swap-s1,' i=',i1,' j=',j1)

BEGIN FOR I:=1 TO N DO READ (A[I]) ; FOR I:=0 TO 9 DO B[I]:=0; FOR I:=1 TO N DO BEGIN VAL(A[I],V,J) ; B[V]:=B[V]+1; END; FOR I:=1 TO 9 DO FOR J:=0 TO 9-I DO IF B[J]>B[J+1] THEN BEGIN TEMP:=B[J]; B[J]:=B[J+1]; B[J+1]:=TEMP; END; J:=0; WHILE B[J]=0 DO J:=J+1; FOR I:=J TO 9 TO WRITE(B[I]:3) ; END. 程序输入:22334455664567655555445 答:程序运行结果为:1 2 2 4 5 9 提示:过程 VAL(A(I) , V , J)是将 A(I)字符串转化为数值型数据存入 V 变量中,如果 A(I)中有错,在 J 中会返回检测到出错的第一个字符的位置,未出错时返回 J=0。 主程序中,第一个循环将 23 个数字字符输入到 A(I)中,第 2 个循环将 B[0]~B[9]清零, 第 3 个循环统计 A 数组中相同数字字符的个数,并存入对应这个字符的 B 数组中。所以可 以看出:B[2]=2 B[3]=2 B[4]=5 B[5]=9 B[6]=4 B[7]=1, 其它 B[]=0 第 4 个双重循环实现对 B 数组 B[0]~B[9]的排序(升序) 程序最后一段则输出 B[]不为 0 的那一段。

信息学奥赛强化练习卷五
西安高中信息技术教研室制

完善程序题型答题方法指导:
(1) (2) (3) 根据[问题描述],明确理解程序要做的工作(功能); 分析[算法说明],理解程序所用的算法思想; 通读程序,列出所用变量,初步分析各变量(尤其是一些重要的变量,如输入输出 的变量、数组等)的作用,尽可能将程序划分为若干段(块),然后推敲每一段的 详细算法,并考虑填空。 (4) 熟记一些常用算法的子程序,如:穷举法、分离一个整数的各位、任意数制间的转 换、求素数、排序、链表、队列、栈的操作、树的遍历(深度优先和广度优先)、 动态规划核心算法、矩阵的转置、对分法查找、高精度+-*/算法的核心思想等。

以下各题请根据题意,补充完善程序: 1.[问题描述] 求出二个自然数的最小公倍数。 例如:24,27 的最小公倍数为 216; 12,36 的最小公倍数为 36。 [算法说明] 首先读入二个自然数 X,Y,然后求其最大公因子存于变量 GCD 中,最后 按下列公式计算求得最小公倍数 gcm: gcm=(x*y)/gcd: [程序] program expl(input,output); var x,y,gcd,gcm,x0,y0:integer; Begin readln(x,y); x0:=x; y0:=y; while ① do if x>y then x:= ② else y:= ③ ; ④ ; gcm:=x0*y0 div gcd; writeln(gcm) End. 答: ① x<>y ② x-y ③ y-x ④ GCD:=X 分析:由问题描述可知,该程序主要是求两自然数的最小公倍数,而算法说明中已说 明,程序中要先求最大公约数,然后代公式求最小公倍数。通读程序可知,程序倒数第 3 句就是求最小公倍数,此前的关键是求 X Y 的最大公约数。求最大公约数的一般方法是: 当 X=Y 时,X 就是最大公约数,X<>Y 时采用减法计算,不断缩小大数,直至两者相等。 据此分析,可得出上述填空的结果。 2.[问题描述] 在进行正整数的除法运算时,可以通过减法来实现。 例如:X÷Y=Q...R(Q:商,R:余数)可以通过下列的方法实现

Q=0 ;R=X; WHILE Y<=R DO BEGIN R=R-Y;Q=Q+1 END 结果:商在 Q 中,余数在 R 中。 [算法说明] 但是上面的算法有一个缺点,就是当 X 比较大,Y 比较小时,则运算的次 数非常多,速度太慢。为提高速度,下面给出改进的算法: 先找一个非常接近 x 的数 w,且满足: w=y*2k,Y*2k-1≤x<w 然后通过减法与移位的运算,以较少的运算次数完成除法。 [程序] program exp3(input,output); var x,y,w,r,q:integer; Begin readln(x,y); r:=x; ① ; while w<= r do ② ; q:=0; while ③ do begin w:=w div 2; ④ ; If r >= w then begin q:= ⑤ : ⑥ ; end; end; writeln(q,?...?,r) End. 答: ① W:=Y ② W:=W+W ③ W>Y ④ Q:=Q+Q ⑤ Q+1 ⑥ R:=R-W 分析:由算法说明可知,该说法中求商的思想是:被除数减去一倍的除数,商就 增 1,直到新的被除数(余数)小于除数为止。程序中改进的思想是:每次被除数不是减一 倍的除数,而是减一个接近于被除数的数 W,确定 W 值,采用在 Y 的基础上不断试加的方 法。由此可知:① W:=Y ② W:=W+W 当 W 超过 R(X)时跳出循环;第 5 6 两个 空可参考算法说明得出: Q+1 ⑥ R: ⑤ =R-W ③处的循环让 W 成倍递减, 每递减一次, 商翻倍,如果 W 还比余数大,则执行⑤⑥处理,并继续递减,直到 W 小于除数为止,所以 ③ W>Y ④ Q:=Q+Q 3.[问题描述] 求出 1 至 N(10<N<10000)之间不能被 2,3,5,7 除尽的整数个数。 [算法说明] 定义一个数组 A[10..10000] OF INTEGER;其中 A(I)存放 I,然后进行筛 选:将凡是能被 2,3,5,7 除尽的数,全部变成为 0,最后统计出剩下的不为 0 的数,即 为所求。 [程序] PROGRAM EX1(INPUT,OUTPUT) ;

VAR N,I,S:=INTEGER; A :ARRAY[10..10000] OF INTEGER; BEGIN WRITE(?INPUT N=?); READ(N); FOR I:=1 TO N DO ① FOR I:=1 TO N DO IF ② OR ③ OR ④ OR ⑤ THEN A(I):=0; ⑥ FOR I:=1 TO N DO IF ⑦ THEN S:=S+1 WRITE( ‘S=’ ,S) END. 答: (1)A[I]:=I, (2) (A[I] MOD 2=0) (3) (A[I] MOD 3=0) (4) (A[I] MOD 5=0) (5) (A[I] MOD 7=0) (6)S;=0; (7)A[I]<>0 本题比较直观,根据算法说明,即可得出以上填空。 4.[问题描述] 设有 2 个字符串 A$,B$,现将这 2 个字符串合并为 1 个字符串,合并的方 法为: 设 A$=‘a1 a2 ??an', 其中 a1, a2,?? an 为 A$中的字符,n 为 A$的长度; B$=‘b1 b2 ??bm',其中 b1,b2,?? bm 为 B$中的字符,m 为 B$的长度。 当 n>m 时,合并之后成为: ' a1 b1 a2 b2 ?? am bm am+1 ??an' 当 n≤m 时 ,合并之后成为: 'b1 a1 b2 a2 ?? bn an bn+1 ?? bm' [算法说明] 定义一个足够长的字符数组 C$(长度不超过 200),然后求出 A$、B$字 符串的长度,最后根据长度的大小进行合并。 [程序] PROGRAM exp2(INPUT,OUTPUT); VAR I,Ja,Jb,Jc:INTEGER; CH :CHAR; A,B :ARRAY[1..100] OF CHAR; C :ARRAY[1..200] OF CHAR; BEGIN Ja:=0;WRITE(?INPUT A$=?);READ(CH); WHILE CH<>?$? DO BEGIN ① A[Ja]:=CH; READ(CH); END; READLN; Jb:=0;WRITE(?INPUT B$=?); READ(CH); WHILE CH<>?$? DO BEGIN

Jb:=Jb+1; B[Jb]:=CH; READ(CH); END; Jc:=0 ; IF Ja>Jb THEN BEGIN FOR I: ② BEGIN ③ C[Jc]:=B[I]; Jc:=Jc+1; C[Jc]:=A[I]; END;

DO ;

FOR I:=1 TO ④ DO BEGIN Jc:=Jc+1;C[Jc]:=A[I]; END; END ELSE BEGIN FOR I:=1 TO JA DO BEGIN JC:=JC+1;C[JC]:=B[I]; JC:=JC+1;C[JC]:=A[I] END; FOR I:= ⑤ DO BEGIN Jc:=Jc+1;C[Jc]:=A[I] END END; FOR I:=1 TO Jc DO WRITE(C[I],’; ’) WRITELN END. 答: (1)Ja:=Ja+1; (2)1 TO Jb (3)Jc:=Jc+1; (4)Jb+1 TO Ja (5)Ja+1 TO Jb 分析:Ja、Jb、Jc 分别是 A$、B$、C$的字符个数,从程序分段来看,显然,前两 段大循环分别读入 A$和 B$字符串,参考 B$读入的程序段,可以看出(1)Ja:=Ja+1; (2) 空这一段程序是 Ja>Jb 时,先将 Jb 长度的字符拼接起来,然后将 A$剩余的部分再接上去, 所以(2)1 TO Jb (3)Jc:=Jc+1 (4)Jb+1 TO Ja; (5)空所在段则是 Jb>Ja 时, 先拼 Ja 长度字符,再将 B$剩余部分接上去,参考(4)可知(5)Ja+1 TO Jb 5.[问题描述] 读入 N 个不相同且不为 0 的数(1≤N≤100) ,不用排序,求出其中第 R 个 大的数(1≤R≤N) 即有 R-1 个数比它大,其余的数都比它小。 , 例如:输入 3,14,22,15,17,6 其中第 3 个大的数为 15。

[算法说明] 以数组 A[1. .20]记录读入的 N 个数,并以 0 为结束(0 本身不是 N 个数 中的) 。然后从第一个数开始,将它与其余的数进行比较并记录出比它大的数的个数(存于 变量 Y 中) ,若 Y=R-1 时,得到所求结果,否则对下一个数进行同样的处理。 [程序] program exp2(input,output); var r,i,j,k,x,y:integer; a :array[1..20] of integer; p :boolean; Begin j:=0; readln(x); while ① do begin ② ; a[j]:=x; ③ ; end; readln(r); p:=true; i:=1; while p do begin ④ ; y:=0; for k:=1 to j do if x<a[k] then ⑤ ; if ⑥ then begin writeln(x); p:=false end else i:=i+1 end End. 答: ① x<>0 ② J:=J+1 ③ READLN(X) ; ④ X:=A[I]; ⑤ Y:=Y+1 ⑥ Y=R-1 参考问题说明和算法说明,再将程序根据循环分成几大段,可以看出: (2) (3) 空所在循环是读入 A[J]数组, 所以① x<>0 ② J: =J+1 ③ READLN (X) 第 2 个 while ; 循环是从第 1 个数开始求出每个数比自已大的数的个数,即找出第 R 大的数,其中⑥空显 然是找到答案的情况,所以⑥ Y=R-1 (4)是取出第 I 个数, (5)空则是发现有一个比 自己大的数就 Y:=Y+1。 6.[问题描述] 设有五个城市 A,B,C,D,E 排成一排,相邻城市之间有若干条通路,每 一条通路上有一个运行时间,如下图:

4 6 5 A 7 B 6 2 C 6 4 3 D E

该图中: A,B 之间有 4 条通路(K=4) ,通行时间分别为 4,6,5,7; B,C 之间有 2 条通路,(K=2)通行时间分别为 6,2,...... 试找出从 A 到 E 的最小通行时间。 [数据结构]: (1)用 N 表示城市个数-1。 (2)用数组 A[1..n,0..k]表示城市之间的通路条数和通行时间,如上图:N=4 A(1,0)=4,A(1,1)=4,A(1,2)=6,A(1,3)=5,A(1,4)=7, A(2,0)=2,A(2,1)=6,A(2,2)=2 A(3,0)=3,A(3,1)=6,A(3,2)=4,A(3,3)=3 A(4,0)=4,?? [程序]: PROGRAM exp-5: VAR s,i,j,n,T:integer A: array[1..20,0..10]of integer; Begin readln(n); {n 为共有 n+1 个城市} for I:=1 to n do begin readln(a[i,0]); for j:=1 to ① do readln(a[i,j]); end; s:=0; for I:=1 to n do begin t:= ② ; for j:= ③ do if a[i,j]<t then t:=a[i,j]; s:= ④ ; end; writeln(s) End. 答: ① a[i,0] ② a[i,1] ③ 2 to a[i,0] ④ s+t 留作同学们自行分析

信息学奥赛强化练习卷六
西安高中信息技术教研室制 以下各题请分析问题,完善程序: 1. [题 目] 找出小于 33 的 6 个正整数,用这些整数进行加法运算,使得包括原来的整数在内能组 成尽可能多的不同整数。 例如:用 2,3,5 这三个数能可组成下面的数 2, 3, 5 2 + 3 = 5, 但 5 已经存在 2 + 5 = 7, 3 + 5 = 8, 2 + 3 + 5 = 10 所以用 2,3,5 能组成 6 个不同的数。 [程序要求]:输出所选的这 6 个数,以及能组成不同整数的个数。 [算法提要]:选择的这 6 个数,用来组成数时应该尽可能不重复,引入数组 A 保存找 出的这 6 个整数。 程序:begin A[1] := 1; t := 0; For i := 2 to 6 do begin _____①____; for j := 1 to i - 1 do s := ______②_______; a[i] := _______③_______; END; FOR i:=1 TO 6 DO begin T := ______④______ WRITE(a[i], ' '); END; Writeln('能组成不同整数的个数:', t) End. 答: ① s:=0; ② s:=s+a[j]; ③ a[i]:=s+1 ④ t:=t+a[i]; 或 t:=t*2+1 分析:掌握程序中变量 S 的意义是求解本题的关键。根据算法说明中提到的 “选择的 这 6 个数,用来组成数时应尽可能不重复” 这一策略,同时,这 6 个数要小于 33 的限制条 件,我们不妨假设前 I-1 个数 a1,a2,a3,a4…ai-1 已找到,对第 I 个数 ai, 确定其值的原则为: (1)ai 要尽可能小且满足 a1<a2<a3<a4<…<ai-1<ai ; (2)由 ai 参与加法的结果应大于 a1+a2+…a i-1 , 这样保证与前 I-1 个数所组成的整数不重复。显然 ai=a1+a2+…ai-1+1。因此, S 的意义为前 I-1 个数之和,填空②为 S+a[ j ], 填空①置 S 初值为 0,填空③为 S+1。 我们还可以换一种方法来思考:所选 6 个数 1=a1<a2<a3<a4<a5<a6<33, 这 6 个数在组 成数时, 每一个数都有参与加法或不参与加法两种可能, 很自然想到, 6 个数在组成数时, 这

可用一个 6 位二进制数表示 b6b5b4b3b2b1, 其中 bi=0 表示 ai 不参与加法运算,bi=1 表示 ai 参与加法运算。6 位二进制数的每一种情况就表示组成的一个数,且各不相同。000001 表示 只有 a[1]=1 时的值,当有 a[1]=1 和 a[2]时,能组成的数为 000001,000010,000011,这 3 个不同的数, 所以 a[2]取 2, 即二进制 000010,。。 。。依次可得 a[3]=4, 即二进制 000100, a[4]=8, a[5]=16, a[6]=32。 能组成不同整数的个数 t=a[1]+a[2]+a[3]+a[4]+a[5]+a[6], 所以④处应填 t+a[I ],得到累 加和。 2. [题 目] 求出所有满足下列条件的二位数: 将此二位数的个位数字与十位数字进行交换, 可得到 一个新的数,要求新数与原数之和小于 100。 程序要求:每行输出 6 个满足条件的数。 [算法提要] 分解每一个二位数,然后重新组成一个新数,当满足条件时,用计数器来统 计个数。 程序: K := 0; FOR i := ______①____ TO 99 DO X := _____②_____; Y := _____③_____; J := x * 10 + y; IF ____④_____ THEN K := k + 1; Write(I : 4); ______⑤_____ THEN WRITELN; ENDIF ENDFOR; 答: ① ② ③ ④ ⑤ 10 x:=i mod 10; y:=i div 10; If (i+j)<100 if k mod 6=0

3.[题 目] 设有 N 个不同整数的数列:例如 N=4 时,有 4 个不同整数的数列为 17,4,16,5。数 列中的第 1 个数 17,比它后面的三个数都大,则称数 17 的逆数为 3。数列中的第 2 个数 4 比它后面的数都小,则称数 4 的逆数为 0。同时记数列中全部逆数的和称为数列的逆数。上 例中,数列 17,4,16,5 的逆数:为 3+0+1+0=4。 [程序要求] 当给出 N 个不同整数的数列后,求出此数列的逆数。 [算法描述] 为求得上面问题的解,设置数组 A : ARRAY[1..N] OF INTEGER 和逆数计 数器 5,然后用一个二重循环求出数列的逆数。 [程 序] CONST N=10;

VAR I,J,S:INTEGER; A:ARRAY[1..N] OF INTEGER; BEGIN S:=0; FOR I:=1 TO N DO READ(A[I]); FOR I:=1 TO ① DO FOR J:= ② TO N DO IF A[I]>A[J] THEN ③ WRITELN('S=',S) END. 答: ① N-1 ② I+1

;

③ S:=S +1;

4.[题 目] 装球:设有 n 个盒子(n 足够大,可装入任何数量的球) ,分别编号 1,2,??。同时 有 k 个小球(k>0) ,今将 k 个小球装入到盒子中去。 装入规则如下: (1)第一个盒子不能为空。 (2)装入必须严格按递增顺序进行。 例如,当 k=8,n=6 时,装入方法有 1,2,5 或 1,3,4 (3)在满足上面的两个条件下,要求有球的盒子尽可能多。 (4)装完后,相邻盒子中球个数差的绝对值之和最小(未装的盒子不计) 。 如上例中: 装入法 1,2,5,则差的绝对值之和为 2-1+5-2=4 装入法 1,3,4,则差的绝对值之和为 3-1+4-3=3 [程序要求] 给出 k(k 表示小球的个数)之后,求出满足上述四个条件的装入方法。 [算法描述] 设计一个数组 A 用数组元素代表盒子,然后依次装入小球。 [程序清单] CONST N=20; VAR I,J,K,L:INTEGER; A:ARRAY[1..N] OF INTEGER; BEGIN READLN (K) ; ① ; J:=1; WHILE ② DO BEGIN A[J]:=J; ③ ; J:=J+1 END; L:=J-1; WHILE K>0 DO BEGIN ④ ; K:=K-1; L:=L-1; END;

FOR I:=1 TO ⑤ DO WRITE(A[I]:4) END. 答:① for I:=1 to n do A[I]:=0; ② K>A[J-I] ③ K:=K-J ④ A[L]:=A[L]+1 ⑤ J-1 分析:由本题条件(1) ,第一个盒子至少放一个小球,即 A[I]>=1;根据条件(2)盒 子中放到小球数必须严格按递增的顺序,因此 A[1]<A[2]<?<A[n-1]<A[n]。为达到放球的盒 子尽可能多,也就是 n 尽可能大的目的,在小球数 K 确定的情况下,对每个盒子放球时要 尽可能节约,显然 A[1]=1, A[2]=2?A[n]=n 是最节约的放法,具体实现时,先根据盒子的编 号,从 1 号盒子放 1 个球,2 号盒子放 2 个球,?,n 号盒子放 n 个球,n 的确定可根据余 下的球数小于 n+1 为止。也就是第 n+1 个盒子就不够放了。因此,填空②③处的作用应该 是余下的球数不够放下一个盒子,所以③处是计算余下的球数,应该填 K:=K-J, 而②处为 循环控制条件 k>=J。 上述这种放球的思路可以仔细阅读程序得到启发: 语句 a[ j]:= j 告诉我 们程序先利用第 j 号盒子放 j 个球的方法,满足题目给出的前三个条件。 用上述方法放球后,如果余下的球数为 0,放球过程结束,如果还有球多出来,把这些 余下的球再分配到各个装球的盒中,考虑到条件(4) :装完后,相邻的盒中球的个数差的绝 对值之和为最小,如何分配,这是程序要处理的第二个问题。由于 a1<a2<?<an,相邻盒中 球个数差的绝对值之和:s=(a2-a1)+(a3-a2)+?+(an-2-an-1) = a2-a1+a3-a2+?+an-2-an-1+an-an-1=an-a1 显然 s 与第 1 个盒子、 n 个盒子的球数有关, 第 增加第 1 个盒子的球数, 可以使 s 更小, 但第 1 个盒子加 1 个,后面的盒子至少都要加 1 个,而多出来的球数<=n ,所以只能从编号 大的加起,逐个往编号小的盒子中加 1 个球,直到加完为止(最多 n 个盒子) 。程序中④处 应填 a[1]:=a[1]+1。变量 j 的最后值为装球盒子数加 1,所以输出部分 I 的终值应为装球的 盒子数:j-1 2.[题 目] 4 色问题。 设有下列形状的图形: (N=8) ,其编号为 1,2,??,N。

图形之间的相邻关系用下面的邻接矩阵表示: 1 1 2 3 4 5 0 1 0 0 0 2 1 0 1 0 0 3 0 1 0 1 0 4 0 0 1 0 1 5 0 0 0 1 0 6 0 1 1 1 1 7 1 1 0 0 0 8 1 0 0 0 0

6 7 8

0 1 1

1 1 0

1 0 0

1 0 0

1 0 0

0 1 0

1 0 1

0 1 0

其中:1——相邻,0——不相邻。 [程序要求] 将上面图形的每一个部分涂上红(1) ,黄(2) ,蓝(3) ,绿(4)四种颜 色之一,要求相邻的部分有不同颜色。 输入方式:邻接矩阵。 输出方式:区域、颜色。 ???? [算法描述] 用数组 R:ARRAY[1..N,1..N] OF 0..1 表示相邻关系,S:ARRAY[1..N] OF INTEGER 表示颜色。 采用回溯的方法,首先给第一个图形涂上红色(1) ,然后在下面的图形中依次涂上其他 颜色,当有矛盾时回溯解决。 [程 序] PROGRAM EXP2(INPUT,OUTPUT); CONST N=8; VAR I,J,K:INTEGER; R:ARRAY[1..N,1..N] OF 0..1; S:ARRAY[1..N] OF INTEGER; BEGIN FOR I:=1 TO N DO BEGIN FOR J:=1 TO N DO READ(R[I,J]); READLN END; ① ;I:=2; J:=1; WHILE I<=N DO BEGIN WHILE (J<=4) AND (I<=N) DO BEGIN K:=1; WHILE ② DO K:=K+1; IF K<I THEN ③ ELSE BEGIN ④ ; I:=I+1; J:=1 END END; IF J>4 THEN BEGIN I:=I-1; ⑤ END; END; FOR I:=1 TO N DO WRITELN(I,'?',S[I]) END.

答:① S[1]:=1 ; ② (K<I) AND (S[K]*R[I,J])<>J ③ J:=J+1; ④ S[I]:=J; ⑤ J:=S[I]+1 分析:涂色算法:深度优先搜索 读入邻接矩阵; 对第一号区域涂色; while I<n do {还有区域尚未涂色} while (J<=4) and (I<=n) do {选择颜色} begin if k<I and (检查相邻区域,如不是当前要涂色区域) then 试探下一区:k+1?K if 当前色不能涂 then 试探下一种颜色:y+1?y else 本区域涂色,准备试探下一区域 if 试探不成功 then {回溯} I-1?I {返回上一个点区域} 修正 y 颜色值; end; 3.[题 目] 多项式加法运算:一个仅含有 x 的多项式可以用下列的方式表示: (系数,指数)(系数,指数) , ,?, (0,0) 。 其中(0,0)作为结束标志。 例如:P(x)=4x6-3x3+2x2-1 可表示为:(4,6),(-3,3),(2,2),(-1,0),(0,0) Q(x)=x4-x+1 可表示为:(1,4),(-1,1),(1,0),(0,0) 当用上面的方式给出 2 个多项式之后, 编制程序对这两个多项式进行加法运算, 结果也 用上面的方式给出。 例如:上面的 P(x)和 Q(x)相加的结果为: 4x6+x4-3x3+2x2-x 表示结果为:(4,6),(1,4),(-3,3),(2,2),(-1,1),(0,0) [算法描述] 多项式可用数组 P 表示;分别以 p1 表示 P,p2 表示 Q,p3 表示结果。 处理的过程为将 P 复制到 p3,然后逐项检查 Q,当发现有相同的方次时,进行系数相 加;当发现没有相同方次时,插入到 p3 中去。 [程 序] PROGRAM EXP3(INPUT,OUTPUT) VAR X,Y,I,I1,J,J1,J2:INTEGER; P1,P2,P3 :ARRAY[1..20,1..2] OF INTEGER BEGIN J1:=0; WRITE('INPUT P(X)='); READ(X,Y); WHILE X<>0 DO BEGIN J1:=J1+1; P1[J1,1]:=X; P1[J1,2]:=Y; READ(X,Y) END; J1:=J1+1; P1[J1,1]:=0; P1[J1,2]:=0;

WRITE('INPUT Q(X)='); READ(X,Y); J2:=0; WHILE X<>0 DO BEGIN J2:=J2+1; P2[J2,1]:=X; P2[J2,2]:=Y; READ(X,Y) END; J2:=J2+1; P2[J2,1]:=0; P2[J2,2]:=0; FOR I:=1 TO J1 DO BEGIN P3[I,1]:=P1[I,1]; P3[I,2]:=P1[I,2] END; I:=1; WHILE ① DO BEGIN IF ② THEN BEGIN FOR J:=J1 DOWN TO 1 DO BEGIN P3[J+1,1]:=P3[J,1]; P3[J+1,2]:=P3[J,2] END; P3[I,1]:=P2[I,1]; P3[I,2]:=P2[I,2]; J1:=J1+1 END ELSE BEGIN I1:=1; WHILE P2[I,2]<P3[I1,2] DO ③ ; IF P2[I,2]=P3[I1,2] THEN P3[I1,1]:= ④ ELSE BEGIN FOR J:=J1 DOWNTO I1 DO BEGIN P3[J+1,1]:=P3[J,1]; P3[J+1,2]:=P3[J,2] END; P3[I1,1]:=P2[I,1]; P3[I1,2]:=P2[I,2]; ⑤ END; END; I:=I+1 END; FOR J:=1 TO J1-2 DO WRITE ('(',P3[J,1],',',P3[J,2],'),'); WRITELN('(',P3[J+1,1],',',P3[J+1,2],')'); END. 答:① P2[I,1]<>0 ② P2[I,1]> P3[1,2] ③ I1:=I1+1; ④ P3[I1,1]+ P2[I,1] ⑤ J1:=J1+1 ; 分析:

程序实现的是线性表的归并算法。多项式相加的规则是指数相同,系数相加。多项式 p 和 q 利用了将系数不为 0 的项用一对数字表示某一项的方式,分别存在一个二维数组中,p 和 q 相加的结果用另一个二维数组存放。根据算法说明,归并运算实际上在表示多项式 q 的数组 p2 和表示相加结果的数组 p3 之间进行,p3 的初始值为表示多项式 p 的数组 p1,其 初始长度为 p1 的长度。以后在归并过程中,p3 的长度将会变大,因此,仔细阅读程序可发 现,表示 p3 长度的变量 j1 是一个关键的量。程序的主要部分是如何实现将 p2 的每一分量 加入到数组 p3 中去。 程序利用循环扫描数组 p2 的方法,其扫描指针为变量 I ,因此(1)处为循环控制条 件,由题意可知,应为 p2[I ,1]<>0;下面的循环体用嵌套的 if then else 结构分别处理 p2 数组的当前分量 p2[I]是插入到 p3 还是与 p3 中某一分量合并(指数相同时) 。从 if 条件(2) 成立时处理的程序段 for j:=j1 downto 1 do ?可知,是将 p3 各项依次向后移一位置,p2[I] 插入 p3 的第 1 个位置,可知, (2)应为 p2[I,2]>p3[I,2], 即 p2(i )的指数大于 p3 的最大指 数(注:数组表示多项式均利用降幂形式) 。当(2)处条件不成立时,p2(i)将与 p3 中各分 量一一比较,程序用语句 i1:=1; while p2[I,2] <p3[i1,2] do ③ 来实现,③处实现时表示 P3 分量位置指针 I1 往后移,直到 P2[I,2]<P3[I1,2]不成立, 所以空格③处应填 I1:=I1+1;然后比 较 P2 和 P3 当前分量的指数,若相同,则系数相加 P3[I1,1]:=P3[I1,1]+P2[I,1]。指数不同, 此时 P2[I,2]>P3[I1,2],就把 P2 的第 I 个分量插入到 P3 的 I1 位置。空格⑤处应处理 p3 的长 度增加,即 j1:=j1+1。 题目给出的程序中,忽略了一种情形,当 p2 与 p3 中两个同类项相加,系数之和为 0 时,是否要保存在 p3 中,程序没有进行处理,因此,p3 中会出现系数为 0 的项,同学们可 试试改动程序,使之更符合题目要求。

信息学奥赛强化练习卷七
西安高中信息技术教研室制
1 填空完善程序

[问题描述]:表的操作:设有一个表,记为 L=(a1, a2, …, an) ,其中: L:表名 a1, a2, …, an 为表中的元素 当 ai 为 0~9 数字时,表示元素,ai 为大写字母时, 表示是另一个表,但不能循环 定义。 例如下列表的定义是合法的。 (约定 L 是第一个表的表名) L=(1,3,K,8,0,4) K=(3,P,4,H,7) P=(2,3) H=(4,0,5,3) 要求: 当全部表给出之后, 求出表中所有元素的最大元素, 以及表中全部元素的和。 [算法说明]:表用记录类型定义: 长度(LENGTH) 表体(是元素为字符类型的数组 ELEMENT) 队列用数组 BASE 表示; 队列指针用整型变量 FRONT 与 REAR。 为此,设计一个字符入队的过程 inqueue,出队函数 outqueue,表中最大元素及元素求 和均采用递归计算。 [程序]: PROCEDURE INQUEUE(Q,C); //过程需要二个参数,Q 记录类型,C 字符类型// Q.REAR := _________①__________; //入队时,尾指针先后移一位// Q.BASE[Q.REAR] := C; //新元素存入队尾指针所指的位置// END; //过程结束// FUNCTION OUTQUEUE(Q) //函数需要一个参数,Q 记录类型// Q.FRONT := _________②__________; //出队时,头指针先后移一位// OUTQUEUE := Q.BASE[Q.FRONT] //头指针指示的元素出队// END; //函数结束// FUNCTION MAXNUMBER(C) //函数求一个表的最大值,需要一个参数,C 字符类型// Max := CHR(0); //最大值初始化// FOR i:=1 to T[C].LENGTH DO CH := T[C].ELEMENT[i]; IF _______③________ THEN M := MAXNUMBER(CH) //递归求子表最大值// ELSE M := CH ENDIF; IF MAX < M THEN //比较是否比原有的 MAX 大//

MAX := M ENDIF; ENDFOR; ___________④____________ END; //函数结束//

//函数出口语句//

FUNCTION TOTAL(C) //函数需要一个参数,C:字符类型// K := 0; FOR i:= 1 TO T[C].LENGTH DO CH := T[C].ELELMENT[i]; IF _________⑤__________ THEN M := TOTAL(CH); //递归求子表的和// ELSE M := ORD(CH)-ORD('0'); //取出元素值// ENDIF K := K + M //累加和// ENDFOR; TOTAL := K; END; //函数结束// //主程序// MAX := 36; FOR TABNO := 'A' TO 'Z' DO T[TABNO].LENGTH := 0; //每个表的初始长度清零// ENDFOR; Q.FRONT := 0; Q.REAR := 0; INQUEUE(Q,'L'); //字母 L 入队// WHILE (Q.FRONT <>Q .REAR ) DO TABNO := OUTQUEUE(Q); //头指针指向的字母出队,以便输入该子表// WRITE(TABNO, '='); READLN(S); //输入子表(字符串)// i := 1; WHILE S[i] <> '(' DO //寻找左括号// i := i+ 1; ENDWHILE; WHILE S[i] <> ')' DO //未到右括号说明子表未处理完,继续// IF (S[i]>='a') AND (S[i]<='z') THEN S[i]:=CHR(ORD(S[i])+ORD('A')-ORD('a')); //子表中的字母转为大写// IF (S[i]>='A') AND (S[i]<='Z') THEN INC(T[TABNO].LENGTH); //子表中有一个元素表长就增 1// T[TABNO].ELEMENT[T[TABNO].LENGTH] := S[i]; INQUEUE(Q, S[i]); //遇到子表中有字母时,将该字母入队// ENDIF; ELSE

IF (S[i]>='0') ANDN (S[i]<='9') THEN INC(T[TABNO].LENGTH); T[TABNO].ELEMENT[T[TABNO].LENGTH] := S[i] ENDIF; INC(i) ENDIF; ENDWHILE; ENDWHILE; WRITE('The max number in table L is:', maxnumber('L')); WRITE('Total is:', total('L')) END. //主程序结束//

分析:
本题考核同学们对广义表遍历操作的掌握以及队列、递归等知识。题目采用递归定义广 义表,约定表名为大写字母且 L 为第一个表的表名,用记录类型 tabtype 表示表,数组 element 表示表体。因此,仔细阅读主程序可发现,每一个表用一字符串 S 读入,且把 S 中 所有的字母、数字看成为表的元素,其中小写字母化为大写。先读入表 L,将其元素存入数 组元素 t[L]中,对 L 中出现的字母,依次进入队列 q;若 q 不空,队列元素出队,读入以该 元素为名的子表,若再出现字母,再入队,??直到队列 q 为空为止。下面是表输入过程: (1 置队列为空队 F r (2 ?L? 进队 L F r (3 ?L?表读入 S=?(13K804)?,?K?入队 L K F r 得表 t[L]=?13K804? (4 ?K? 出队,读入 S=? ( 3P4H7)?, ?P?和?H?入队 L K F 得表 t[K]=?3P4H7? (5 ?P? 出队,读入 S=?(2 3)? L K P F 得表 t[P]=?2 3? (6 置队空,队列?H?出队,读入 S=?(4053)? L K P H Fr 得表 t[H]=?4053? 此时,f= r 队空,大循环(输入表)结束 由上述分析可知,入队过程①应为 q. rear+1,出队过程②处应为 q. front+1, 求表中最 大元素及求所有元素的和的过程相似,均采用递归的思想,所以③⑤应为(CH>=?A?) AND(CH<=?Z?), ④空很明显, 是函数出口语句, 必须为函数名赋值即 MAXNUMBER:=MAX H r P H r

2 根据题意,将以下程序填写完善 [问题描述] 求一棵树的深度与宽度。 [算法说明] 树可用数组 tree:array[1..n,1..5]of integer; 其中:tree[I,1]表示结点号;tree[I,2]——tree[I,5]所属结点 如上图可表示为: 1 2 3 4 0 2 5 6 7 0 (1) 3 8 0 0 0 4 9 10 0 0 (2) (3) (4) 5 0 0 0 0 (5) (7) (8) (9) (10) (6) 6 0 0 0 0 7 11 12 0 0 (11) (12) 8 0 0 0 0 (13) 9 0 0 0 0 10 0 0 0 0 11 0 0 0 0 12 13 0 0 0 13 0 0 0 0 在求解的过程中,用到数组 G:ARRAY[1..N,1..7]OF INTEGER; 其中:G[I,1]表示父结点,G[I,2]表示层次, G[I,3]表示本结点号,G[I,4]——G[I,7]表示子女结点; 同时,设 2 个指针 SP1(取数指针) ,SP2(存数指针) [程序]: program exGp3; const n=13; var i,j,k,sp1,sp2,n1,n2,jmax,p:integer; tree:array[1..n,1..5]of integer; g :array[1..n,1..7]of integer; begin for i:=1 to n do //二重循环将树存入 tree[I,j]数组中 begin tree[i,1]:=i; for j:=2 to 5 do read (tree[i,j]);readln; end; // sp1:=1;sp2:=1;g[1,1]:=0;g[1,2]:=1;g[1,3]:=1; //初始化并处理根结点 for i:=4 to 7 do g[1,i]:=tree[1,i-2]; // while__________①_________do //按层处理各结点 begin p:=g[sp1,2];n2:=g[sp1,3];_________②________;j:=4; while _________③_________do begin n1:=g[sp1,j];j:=j+1;__________④_________; g[sp2,1]:=n2;g[sp2,2]:=p;g[sp2,3]:=n1;

for i:=1 to 4 do g[sp2,i+3]:=tree[n1,i+1]; end; __________⑤_________; end; writeln('maxd=',g[sp2,2]); j:=1;k:=g[1,2];jmax:=0; for i:=2 to sp2 do if __________⑥__________then j:=j+1 else begin if j>jmax then jmax:=j; __________⑦________;k:=g[I,2]; end; if j>jmax then jmax:=j; writeln('max1=',jmax); end. 答:① sp1<=sp2 ② p:=p+1 ③ g[sp1,j]<>0 ④ sp2:=sp2+1; ⑤ sp1:=sp1+1 ⑥ k=g[i,2] ⑦ j:=1; 分析: ①?⑤所在程序段主要是由 tree[ ]数组生成 g[ ]数组,处理的顺序是按层处理各结点: 阅读程序可以初步看出,外循环指向父结点,而内循环指向子女结点。从程序看 sp1 指向父结点,sp2 指向子女结点,p:=g[sp1,2]取出父结点所在层号,该父结点的子女结点元 素将处在 p+1 层,所以 ②应为 p:=p+1,n2 是父结点号;所以③ g[sp1,j]<>0 表示非零元 素都要处理,n1 为要处理的非零元素结点号(子女结点) ; 由 g[sp2,1]:=n2,保存 sp2 所指结点的父结点层号,所以④ sp2:=sp2+1 由此可见控制循环(处理每个结点)的条件① sp1<=sp2 ⑤ sp1:=sp1+1 处理后 g[ ]数组的情况如下: I g[I,1] g[I,2] g[I,3] g[I,4] g[I,5] g[I,6] g[I,7] 1 0 1 1 2 3 4 0 2 1 2 2 5 6 7 0 3 1 2 3 8 0 0 0 4 1 2 4 9 10 0 0 5 2 3 5 0 0 0 0 6 2 3 6 0 0 0 0 7 2 3 7 11 12 0 0 8 3 3 8 0 0 0 0 9 4 3 9 0 0 0 0 10 4 3 10 0 0 0 0 11 7 4 11 0 0 0 0 12 7 4 12 13 0 0 0 13 12 5 13 0 0 0 0 输出的 g[sp2,2]之值即为最大层号,对该例而言层号为 5,即树的深度为 5; 最后一段计算树的宽度:程序段由 j 记录同一层的结点个数,因此⑥ k=g[i,2];当层 号发生变化时,jmax 便表示该层的最大宽度,因此,⑦ j:=1 是为下一层做准备工作。 3 填空完善程序:

[问题描述]: 背包问题, 假设带着一个能装 20 份容量的背包去批发甲、 乙、 丙三种贷物, 如果: (1)买甲贷物全部可得利 252 元,占背包 18 份容量; (2)买乙贷物全部可得利 240 元,占背包 15 份容量; (3)买丙贷物全部可得利 150 元,占背包 10 份容量; 显然,要获利最大,应该尽可能利用背包的 20 份容量,下面是几种采购方案: 方案 1 2 3 4 甲 全部 0 1/2 5/9 乙 2/15 全部 1/3 0 丙 0 1/2 6/10 全部 总容量 18+2+0=20 0+15+5=20 9+5+6=20 10+0+10=20 得利(元) 252+240+2/15=284 240+150*1/2=315 252/2+240/3+150*3/5=296 252*5/9+150=290

从上面列出的方案可以发现,并不是尽可能采购得利高的贷物总得利最大(实际上第 1 个方案最不好) 原因是不仅要看到某种贷物的得利大小, 。 还要考虑到背包容量的利用情况, 如果用一份背包容量装采购的贷物的得利数值作为性价比的话, 那么三种贷物采购时的性价 比为: 甲贷物: 252/18=14 元 乙贷物: 249/15=16 元 丙贷物: 150/10=15 元 显然,乙贷物的性价比最高,应优先考虑采购,若背包有剩余空间,其次才考虑丙贷物, 或前两种全采购了,还有空间,最后再考虑甲贷物。 问题: 如果给出一个容量为 m 的背包, 种贷物采购后的得利 pi 和它占背包容量的 Wi, n 如何采购,才能获利最大? [算法描述] 全部贷物用记录数组 hw[ ]保存, 记录包含四个域:bh、dl、zy、cg,分别表 示贷物编号、全部采购时得利、占背包容量、实际采购量: type hwtype =array[1..n] of record bh:integer; dl,zy,cg:real; end; 假设存入顺序表的数据已经按 Pi / Wi (性价比)从大到小排过序。按性价比从高 到低依次选择采购,直到背包装满为止。 [程序] program bbwt(input,output); {背包问题} const n=3; type hwtype=array[1..100] of record bh:integer; dl,zy,cg:real; end; var hw:hwtype; i,j,k:integer; m:real; procedure sort(var hw:hwtype;n:integer); {性价比排序} var i,j:integer; t:hwtype; begin for i:=1 to n-1 do

for j:=i+1 to n do if (hw[i].dl/hw[i].zy<hw[j].dl/hw[j].zy) then begin t[i]:=hw[i];hw[i]:=hw[j];hw[j]:=t[i]; end; for i:=1 to n do writeln('I=',hw[i].bh,' ','XJB=',hw[i].dl/hw[i].zy:6:2); end; procedure cgsf(var hw:hwtype;n:integer;m:real); {采购算法} var i:integer; s,mcu:real; begin mcu:=m; i:=1; while ① do begin ② ③ i:=i+1; end; if i<=n then ④ else writeln; s:=0; for i:=1 to n do begin writeln(hw[i].bh,' cg=',hw[i].cg:6:2); s:=s+(hw[i].dl/hw[i].zy)*hw[i].cg; end; writeln('total_dl=',s:6:2); end; begin {main} write('m=');readln(m); writeln('Input hw[ ].bh(dl,zy,cg)='); for i:=1 to n do readln(hw[i].bh,hw[i].dl,hw[i].zy); sort(hw,n); cgsf(hw,n,m); end. 答: (1)(hw[i].zy<mcu) and (i<=n) (2)hw[i].cg:=hw[i].zy; (3)mcu:=mcu-hw[i].zy; (4)hw[i].cg:=mcu 4 填空完善程序

[问题描述]:高精度计算问题,设计一个程序,使之能精确计算两个数据相乘的结果 [算法描述]: (1 用字符串的方式接收两个相乘的数据; (2 位数的确定:设被乘数为 a, 乘数为 b,它们的位数分别为 T1、T2,所以积的 位数最长是:T1+T2; (3 进位处理: 加法进位:a[I]=a[I]+b[I] 若 a[I]>10 则:a[i]=a[I]-10, a[I+1]=a[I+1]+1 乘法进位 y=a[I]*b[i] +c,c= y div 10, a[I]= y mod 10; [程序] program p12_11(input,output); const n=100; var a:array[1..n] of integer; b:array[1..n] of integer; c:array[1..2*n+1] of integer; i,j,kw,cj,jw,len1,len2:integer; str1,str2:string; begin write('str1=');readln(str1); write('str2=');readln(str2); len1:=length(str1); for i:=1 to len1 do ① ; len2:=length(str2); for i:=1 to len2 do ② ; for i:=1 to ③ do c[i]:=0; for i:=1 to len2 do for j:=1 to len1 do begin ④ ; c[kw]:= ⑤ ; c[kw+1]:= ⑥ ; c[kw]:= ⑦ ; end; i:=len1+len2+1; while ⑧ do i:=i-1; for j:=i downto 1 do write(c[j]); writeln; end. 答:① a[len1-i+1]:=ord(str1[i])-ord('0') ② b[len2-i+1]:=ord(str2[i])-ord('0') ③ len1+len2+1 ④ kw:=i+j-1 ⑤ c[kw]+a[i]*b[j] ⑥ c[kw+1]+(c[kw] div 10) ⑦ c[kw] mod 10 ⑧ c[i]=0 5 填空完善程序 [问题描述]:设有一个正整数的序列:b1,b2,b3?,bn,对于下标 I1<I2<I3<?< Ii,若有

bi1<=bi2<=bi3<=?<=bin 则称存在一个长度为 L 的不下降序列。 例如:下列数列 13 7 9 16 38 24 37 18 44 19 21 22 63 15 对于下标 i1=1,i2=4,i3=5,i4=9,i5=13, 且满足: 13< 16 < 38 < 44 < 63 则存在长度为 5 的不下降序列 但是,我们看到还存在其它的不下降序列,如: i1=2,i2=3,i3=4,i4=8,i5=10,i6=11,i7=12,i8=13 且满足: 7<9<16<18<19<21<22<63 则存在长度为 8 的不下降序列 问题: 当 b1,b2,?bn 给出之后,求出最长的不下降序列。 [算法描述]: 用 b[I,1]---表示第 I 项数值本身。 B[I,2]---表示从第 I 项到最后一项最长不下降序列的长度。 B[I,3]---链接字,表示最长不下降序列经过此项后,后面继续的项。当 B[I,3]=0 时表示链接结束。 初始状态的 B 数组如下: 1 13 1 0 2 7 1 0 3 9 1 0 4 16 1 0 5 38 1 0 6 24 1 0 7 37 1 0 8 18 1 0 9 44 1 0 10 19 1 0 11 21 1 0 12 22 1 0 13 63 1 0 14 15 1 0

上表中第一行表示 B 数组下标,即数据项的位置,第二行表示数据项本身的数值,第三 行为最大长度,初始时,均设为 1,即数据本身,第四行为链接字,0 表示无链接。 接下来,就是采用动态规划思想从后向前的求解过程: (1 首先从倒数第 2 项开始计算,因为 63>15,不存在不下降序列,所以,长度为 1, 链接字为 0 (2 再看倒数第 3 项 22,在它后面有两项,找出比它大的,最长的作为链接,这样对 应 22 的长度就改为 2,链接字改为 13 (3 再看数项 21,在它后面有三项,分别比较,找出比它大,最长的作为链接,这样 对应数据项 21 的长度改为 3,链接字改为 12 以此类推,直到第一项,最后计算后的 B 数组如下: 最终状态的 B 数组如下: 1 13 7 4 2 7 8 3 3 9 7 4 4 16 6 8 5 38 3 9 6 24 4 7 7 37 3 9 8 18 5 10 9 44 2 13 10 19 4 11 11 21 3 12 12 22 2 13 13 63 1 0 14 15 1 0

(4 输出结果: 首先在 B[I,2]中找出最大者(本题 B[2,2]=8),输出最大长度,并 K=2,记录最大长 度的位置,沿后继指针输出子序列 [程序] program dtgh_bigup(input,output); {求最长的不下降序列} uses wincrt; const n=10; {N 表示原始序列的长度} var i,j,k,len,l:integer; {B[i,1]---表示 I 号数据本身的值} b:array[1..n,1..3] of integer; {B[i,2]---表示 I 号数据后面存在的不下降序

列的最大长度} begin {B[i,3]---链接字,表示 I 号数据后面的链接者序号} writeln('Input N number...'); for i:=1 to n do begin read(b[i,1]); {输入 N 个数据的序列} b[i,2]:=1; {初始时,以每个结点开始的最长不下降序列长度均设为 1} b[i,3]:=0; {初始时,每个结点的后继链接序号均设为 0,表示无链接} end; for i:= ① downto 1 do {从倒数第 2 项开始计算各结点的最大长度和链接字} begin k:=0;len:=0; for j:= ② to n do if ③ then {找出 I 号后面比 I 号结点数大,且长度最大的结点号 K} begin ④ ; ⑤ ; end; if len>0 then {如果长度>0 则长度增 1 作为该 I 号结点的最大长度} begin ⑥ ; ⑦ ; {K 作为该 I 号结点的链接字} end; end; L:=1; for j:=2 to n do {找出 B[I,2]中最大者作为最大长度} if b[ j,2]>b[L,2] then L:= j; writeln('max=', ⑧ ); while ⑨ do begin write(b[L,1]:4); {沿链接字输出最长不下降序列} ⑩ ; end; writeln; end. 答:① n-1 ② i+1 ③ (b[j,1]>b[i,1]) and (b[j,2]>len) ④ k:=j ⑤ len:=b[j,2] ⑥ b[i,2]:=len+1 ⑦ b[i,3]:=k ⑧ b[L , 2] ⑨ L<>0 ⑩ L:=b[L,3]

信息学奥赛强化练习卷八
西安高中信息技术教研室制 1 在一个图中,所有顶点的度数之和等于所有边数的_______倍 A 1/2 B. 1 C. 2 D. 4 (C) 2 在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的_____倍 A 1/2 B. 1 C. 2 D. 4 (B ) 3 一个有 n 个顶点的无向图最多有________条边 A n B. n(n-1) C. n(n-1)/2 D. 2n (C) 4 具有 6 个顶点的无向图至少应有_______条边,才能确保是一个连通图 A 5 B. 12 C 7 D 8 (A) 5 在一个具有 n 个顶点的无向图中,要连通全部顶点至少需要_______条边 A n B. n+1 C. n-1 D. n/2 (C) 6 已知一个图如图,若从顶点 a 出发,按深度优先搜索进行遍历,则可能得到的一种顶点 序列为________,按宽度优先搜索法进行遍历,则可能得到的一种顶点序列为_______ (1)A.a,b,e,c,d,f B. a,c,f,e,b,d C. a,e,b,c,f,d D. a,e,d,f,c,b (2)A. a,b,c,e,d,f B. a,b,c,e,f,d C. a,e,b,c,f,d D. a,c,f,d,e,b (1) D (2) B a b e f d c

7 采用邻接表存储的图的深度优先遍历算法类似于二叉树的__________ A.先序遍历 B。中序遍历 C。后序遍历 D。按层遍历 (A) 8 采用邻接表存储的图的宽度优先遍历算法类似于二叉树的_________ A.先序遍历 B。中序遍历 C。后序遍历 D。按层遍历 (D) 9 如图示,_______不是完合二叉树

10 二叉树的前序遍历序列中,任意一个结点均处在其子女结点的前面,这种说法____ A 正确 B 错误 (A) 11 设高度为 h 的二叉树上只有度为 0 和度为 2 的结点,则此类二叉树中所包含的结点数至 少为_______________

A.2h B. 2h-1 C. 2h+1 12 如图示二叉树的中序遍历序列是: A.abcdgef B. dfebagc C. dbaefcg D. defbagc 13

D. h+1

(B) b

a c g

(C)

d

14 15

16 17 18 19

20 21 22

某二叉树的前序遍历结点序列是: abdgcefh,中序遍历结点序列是: e dgbaechf,则后序遍历的结点序列是: f A:bdgcefha B:gdbecfha C:bdgaechf D:gdbehfca (D) 按照二叉树的定义,具有 3 个结点的二叉树有_______种 A:3 B:4 C:5 D:6 (C) 树的基本策略可分为先根遍历和后根遍历; 二叉树的基本遍历策略可分为先序遍历、 中 序遍历、后序遍历。这里我们把由树转化得到的二叉树叫做这棵树对应的二叉树,结论 ____是正确的。 a A:树的先根遍历序列与其对应的二叉树的先序遍历序列相同 B:树的后根遍历序列与其对应的二叉树的后序遍历序列相同 b d c C:树的先根遍历序列与其对应的二叉树的中序遍历序列相同 a D:以上都不对 (A) 深度为 5 的二叉树至多有______个结点 f g e A:16 B:32 C:31 D:10 (C) a a 任何一棵二叉树的叶结点在先序、后序、中序遍历序列中的相对次序__________ A:不发生改变 B:发生改变 C:不能确定 D:以上都不对 (A) 设 n, m 为一棵二叉树上两个结点,在中序遍历时,n 在 m 前的条件是_________ A:n 在 m 右方 B:n 是 m 的祖先 C:n 在 m 的左方 D:n 是 m 子孙 (C) 深度为 K 的完全二叉树至少有_______个结点,至多有______个结点,若按自上而下, 从左到中次序给结点编号(从 1 开始) ,则编号最小的叶结点的编号是_______ k k k-2 答:2 -1 2 –1 2 +1 在一棵二叉树中, 度为零的结点个数为 N0 , 度为 2 的结点个数为 N2, 则有 N0=______ 答: N2+1 结点最少的树为_________, 结点最少的二叉树为__________ 答:只有一个结点的树, 空的二叉树 以数据结{ 4, 5 ,6, 7,10,12,18}为结点权值所构造的哈夫曼树为_________________, 其带 权路径长度为_______________________ 答:长度为 165 62 a b c e a f d a 10 4 19 9 a 5 37 18 6 13 7 a 25 d a

g a

23 已知一棵树如右上图所示,其二叉树表示为:

(如上图)


相关文章:
NOIP赛前强化练习套题及解
NOIP赛前强化练习套题及解 隐藏>> 信息学奥赛校队集训 分卷强化练习 西安高级中学信息教研室 陆裕元编 信息学奥赛强化练习卷一西安高中信息技术教研室制 1.请用等...
赛前强化题
() A、佩戴的头冠 B、腰带 C、佩戴的玉佩 15、 《说文解字》中“变”的...NOIP赛前强化练习套题及... 暂无评价 53页 2下载券 大学生数学竞赛(数学类...
NOIP2015普及组初赛试题及答案(Pascal)
NOIP2015普及组初赛试题及答案(Pascal)_学科竞赛_初中教育_教育专区。第二十一届全国青少年信息学奥林匹克联赛初赛普及组 Pascal 语言试题 竞赛时间:2015 年 10 月...
NOIP2015普及组初赛试题及答案(Pascal)
NOIP2015普及组初赛试题及答案(Pascal)_学科竞赛_初中教育_教育专区。第二十一届全国青少年信息学奥林匹克联赛初赛普及组 Pascal 语言试题 竞赛时间:2015 年 10 月...
NOIP初赛练习之完成程序题
NOIP初赛练习之完成程序题_学科竞赛_高中教育_教育专区。NOI 初赛练习之四(完成程序题) [如何做完成程序题]: 每年的信息学奥林匹克分区初赛的最后一部分都是完成...
noip初赛选择题专题训练(4套)
noip 初赛选择题专题训练 姓名: 成绩: 姓名:朱望 成绩:第一套选择题: (本题共 20 小题,1—15 小题为单选题,每题 1 分;16—20 小题为多选 第一套选择...
noip2000初赛试题及答案
noip2000初赛试题及答案_IT/计算机_专业资料。noip2000初赛试题及答案没分了,大力兜售啊第六届全国青少年信息学(计算机)奥林匹克分区联赛试题( 普及组 PASCAL 语言 ...
NOIP初赛练习之二(解答题)
NOIP 初赛练习之二(解答题) 前言:如何做解答题 解答题一般是根据要求写出表达式或画出图等, 涉及的知识点主要有数学方面的基本知 识、数据结构方面的如树和图等...
NOIP初赛模拟试题及答案
NOIP初赛模拟试题及答案_计算机硬件及网络_IT/计算机_专业资料。信息学奥林匹克联赛...第一题3 每空2 第二题前1 每空2 每空5 28分 四、完善程序 (第一题3...
noip2001初赛试题及答案
noip2001初赛试题及答案_IT认证_资格考试/认证_教育专区。noip2001初赛试题及答案〓〓 第七届全国青少年信息学奥林匹克联赛(NOIP2001)初赛试题 〓〓 (普及组 PASCAL...
更多相关标签: