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

全国青少年信息学奥林匹克联赛初赛练习卷(一)答案


全国青少年信息学奥林匹克联赛初赛练习卷(一)答案
2007. 7

一、单项选择题(15 题,每题 2 分,共 30 分) 1. 设全集 I = {a, b, c, d, e, f, g},集合 A = {a, b, c},B = {b, d, e},C = {e, f, g},那么集合(A-B)∪(~C∩B)为( A. {a, b, c, d} D

. {b, c, d, e} )。 C. {b, d, e}

B. {a, b, d, e} E. {d, f, g}

2. 设栈 S 和队列 Q 的初始状态为空,元素 e1,e2,e3,e4,e5,e6 依次通过栈 S,一个元素出栈 后即进入队列 Q,若出队的顺序为 e2,e4,e3,e6,e5,e1,则栈 S 的容量至少应该为( ) A) 2 B) 3 栈 e1 e1,e2 e1 e1,e3 e1,e3,e4 e1,e3 e1 e1,e5 e1,e5,e6 e1,e5 e1 e2 e2 e2 e2,e4 e2,e4,e3 e2,e4,e3 e2,e4,e3 e2,e4,e3,e6 e2,e4,e3,e6.e5 e2,e4,e3,e6,e5,e1 C) 4 D) 队列 5

3. 已知集合 E={2,3,5,1,6},请问E的所有子集个数是多少?( ) A) 25 B) 10 C) 32 D) 64 4. 由 3 个 a,5 个 b 和 2 个 c 构成的所有字符串中,包含子串“abc”的共有( )个。 A. 40320 B. 39600 C. 840 D. 780 E. 60

(8*7!)/(2!*4!) – (5+4+3+2+1)*4 = 780 亦即,考虑”abc”的摆放位置,共有 8 种,余下的 7 个字符的全排列有 7!种。但

1

是,在这 7!种全排列中,a 的重复摆放共有 2!种,b 的重复摆放有 4!种。此外,在余 下的 7 个字符中,仍有可能出现“abc”的排列,这与前面考虑的 8 种“abc”的摆放 是重复的,也要去掉。这时,根据头一个“abc”的摆放起点位置,后一个“abc”分 别有 5、4、3、2、1 种可能的摆放位置,而一旦第二个“abc”摆放好后,余下的一个
1 a 和三个 b 的摆放位置有 C4 种可能,因而得上式。

5. 假设一个十六位机的某存储单元存放着数 00001101101101001000, 如果用字母 A—V 来记 录 32 进制数,其表示的相应的 32 进制无符号整数是( A 1KP8 B 1MQ8 C DB48 )

D 1IAA

利用“五位转一位”的思想,再加上排除法即可。 6. 已知P是一双向链表中的一个结点,且P结点既非首元结点,也非尾元结点,Q是新生成的 结点,问将结点Q插入结点P后面的操作是( )。 ① P^.next=Q; ② Q^.next=P^.next; ③ P^.next^.prior=Q; ④ Q^.prior=P^.prior; ⑤ Q^.prior=P; A ①②⑤③ B ②⑤③① C ②⑤①③ D ②④①③ )。

7. 下面的自定义函数完成对一个单链表的查询操作,则方框中应填入( function find(head: pointer; x: integer):pointer; var p:pointer; begin p:=head; while ( find := p; end; A C (p^.data <> x) (p^.data <> x) OR (p <> nil) B (p <> nil) ) do p:=p^.next;

D (p <> nil) AND (p^.data <> x)

8. 已知一个递归函数: function x (n:integer):integer; begin A) 8 x(8)=x(6)+x(4)+1 =x(4)+x(2)+1 + x(2)+x(0)+1 + 1 =x(2)+x(0)+1 + 1 + 1 + 1 + 1 + 1 + 1 =1+1+1+1+1+1+1+1+1 =9 x(9)=x(7)+x(5)+1 =x(5)+x(3)+1 + x(3)+x(1)+1 + 1
2

if (n<=3) then B) 9

x:= 1

else x:=x(n-2)+x(n-4)+1; end; C) 16 D) 18

则 y = x (x (8) );将调用(

)次函数 x。

=x(3)+x(1)+1 + 1 + 1 + 1 + 1 + 1 + 1 =1+1+1+1+1+1+1+1+1 =9 9. 下列程序段中执行后其运行结果是______________ program lian_1; var y:integer; function fac (x:integer):integer ; var t,s :integer ; begin if x<=0 then fac:=0 else fac:=x+fac(x-1); end; begin y:=fac(5); writeln(y); end. A) 10 B) 15 C) 12 D) 5

10. 下列程序段中执行后其运行结果是______________ program lian_2: function ack(m,n:integer):integer; begin if m=0 then ack:=n+1 else if n=0 then ack:=ack(m-1,1) else ack:=ack(m-1,ack(m,n-1)) end; BEGIN A) 3 WRITELN(ACK(3,3)); READLN; END. B) 7 C ) 56 D) 61 program ex1_2 ; var a: integer ; procedure sum( var x:integer) ; begin x:=x+100 writeln(‘x=’,x); end; begin a:=500; sum(a);
3

11. 如下两个程序的运行结果是: program ex1_1 ; sum ( x:integer) ; var a: integer ; procedure begin x:=x+100 writeln(‘x=’,x); end; begin

writeln(‘a=’,a); end.

a:=500; sum(a); writeln(‘a=’,a); end. A (1)x=600 a= 500 (2)x=500 a=500 B (1)x=600 a=600 C (1)x=600 a=500 (2)x=600 a=600 (2)x=600 a=600

D (1)x=500 a=500 (2)x=600 a=600 12. 已知 A=(27E)H,B=(135)D,则 A-B 的结果是 ( A) (674)O B) (1AD)H ) C) (523)D )。 D)(111110111)B

13. 下面哪一句话是错误的?(

A)由一个指针指向的变量可以用 write 语句输出; B)由一个指针指向的变量可以出现在一个赋值语句的左边或右边; C)由一个指针指向的变量的名字与这个指针名无关; D)对一个指针变量的赋值会影响这个指针所指向的变量的值。 14. 将数组{32,74,25,53,28,43,86,47}中的元素按从小到大的顺序排列,每次可以 交换任意两个元素,最少需要交换___次。 A)5 B)6 C)7 D)8 根据每个数字与其最终位置的差异,可以发现,至少要做出以下交换: {25,74,32,53,28,43,86,47} {25,28,32,53,74,43,86,47} {25,28,32,43,74,53,86,47} {25,28,32,43,47,53,86,74} {25,28,32,43,47,53,74,86} 也可以编出一个排序算法,即假设已有了最终的顺序,通过考察每个数据与其最终位 置的差异,来进行交换调整。 15. 有 3 个课外小组:物理组,化学组和生物组。今有张、王、李、赵、陈、5 名同学,已 知张、王为物理组成员,张、李、赵为化学组成员,李、赵、陈为生物组成员。如果要 在 3 个小组分别选出 3 位组长, 一位同学最多只能担任一个小组的组长, 共有多少种选 择方案?( A)11 物理组 王 张 ) B)12 化学组 李、赵 陈 C)13 D)14 生物组

若不考虑约束条件,共有:2 人(物理组)*3 人(化学组)*3 人(化学组)=18(种)
4

考虑到约束条件,还要去掉: ? 张被选为物理组及化学组的组长,这时生物组有 3 种选法; ? 李、赵中的某一人兼了化学组和生物组的组长,这种情况下物理组有 2 人可 选,共 4 种情况 因此,18 – 3 – 4 = 11(种) 二、阅读程序 1、 program exp_2; type pointer=^node; node = record data: integer; next: pointer; end; var m, n, s: integer; p, q, head: pointer; begin read(n,m); new(head);q:=head;head^.data:=1; for s:=2 to n do begin new(p);p^.data:=s; q^.next:=p; q:=p; end; q^.next:=head; s:=1;q:=head; repeat p:=q^.next;s:=s+1; if s mod m=0 then begin q^.next:=p^.next; write(p^.data:3); p^.next:=nil; dispose(p) ; end else q:=p until q^.next=q; writeln(‘the number is:’, q^.data ) end. 输入:15 4

输出:4 8 12 1 6 11 2 9 15 10 5 3 7 14 the number is :13 {循环报数问题} 2、 program exp_4; var b:array[1..3,1..10] of integer ; i,n ,L, k, j:integer;

5

begin read(n); for i := 1 to 10 do begin read( b[1, I]); b[2, I]: = 1; b[3, I]: = 0 ; end; for i: = n - 1 downto 1 do begin L:= 0; k:= 0 ; FOR j: = i + 1 TO n do begin if (b[1, i] <= b[1, j]) and (L < b[2, j]) then begin L:= b[2, j]; k:= j ; end; end; if L > 0 then begin b[2, i]: = L+1 ; b[3, i]: = k ; end; end; j: = 1 ; for i: = 2 to n do if b[2, i] > b[2, j] then j: = i ; writeln (b[2, j]) ; while j<> 0 do begin write( b[1, j],‘ ’); j: = b[3, j]; end; end. 当程序运行后,输入:10 23 18 21 45 61 104 71 83 91 87 输出: 7 18 21 45 61 71 83 91 本题是计算什么的问题:本题求最长不下降子序列 3、 program var lianxi_1;

a: array[1..10] of integer ; s, n, m: longint ; flag:set of byte;

procedure try(dep:integer); val i: integer;
6

begin for i:=1 to n do if begin flag:=flag +[i]; a[dep]:=i; if else dep=m then inc(s) not(i in flag ) then

try (dep+1);

flag:=flag-[i]; end; end; begin writeln ('please input M and N: ’); readln(m,n); flag:=[];s=0; try(1); writeln(s); end. 输入数据: please input M and N:4 输出结果:120 (即 P ) 分析: Try(1) i=1 Flag [1] Try(2) i=2 [1,2] Try(3) I=3 [1,2,3] Try(4)(在 第四位上 变化)
7
4 5

5

s 0

a[1] 1

a[2]

a[3]

a[4]

a[5]

1

2

1

2

3

I=4 [1,2,3,4] 1 [1,2,3] I=5 [1,2,3,5] 2 [1,2,3] Try(3)(递 归上 升)(在第 三位上变 化) I=4 [1,2,4] Try(4) I=3 [1,2,4,3] 3 [1,2,4] I=5 [1,2,4,5] 4 [1,2,4] Try(3)(递 归上升) I=5 Try(4) [1,2,4,5] …… 1 2 5 5 I=4 [1,2,4] 1 2 4 5 1 2 4 5 1 2 4 3 1 2 4 5 I=3 [1,2,3]-[3]=[1,2] 1 2 3 5 1 2 3 4

{注意这一求排列的递归程序与求组合值程序的不同}

4、 program

lianxi_3 ;

const a:array[1..14] of longint=( 94,32,40,90,99,80,46,21,69,28,64,73,85,54); var begin m:=8 ; left :=1 ; right :=14 ; while left<=right do
8

i,j,k,m,left, right , temp: longint;

begin k:=a[m] ; I:=left ; repeat while while k<a[j] k>a[i] then do do j:=j-1 ; i:=I+1 ; j:= right ;

if I<= j begin

temp:=a[I] ; a[I]:=a[j]; a[j]:= temp ; i:=i+1; j:=j-1 ; end; until i>j ; if if end; writeln(a[m]); End. 输出结果:69 {利用快速排序思想,确定最终 a[m]上的数据是哪一个,但本程序不能实现对整个数 组的完整排序。} j<m i>m then left:=i ; then right:= j ;

5、 program

lianxi_4;

type arr=array[0..31] of longint; var a:arr; n,i,j,k:longint; begin readln(n,k); fillchar(a,sizeof(a),0); a[n]:=1; a[0]:=1; for i:=n-1 downto 1 do a[i]:=a[i+1]*2; i:=0; j:=1; while k>1 do begin while (i<=n) and (k>a[i]) do { a[]数组中存放了二进制数各位的位权 }

9

begin dec(k,a[i]); inc(i) end; {of inner while loop} {j 记录着打印了几个数字,且除了第一个 数字外,后面的都要先打印空格} { 从 k 中不断地减去 2 }
i

if j<>1 then write(' '); inc(j); write(i); a[i]:=1 end; {of outer while loop} if i=0 then writeln(0); end. 输入数据:8 35

输出结果:1 2 3 8 n 8 k 35 35-1=34 i 0 1 2 打印 i,即打印 1 1 34-1=33 打印一个空格 3 打印 2 1 33-1=32 打印空格 4 打印 3 1 32-1=31 31-16=15 15-8=7 7-4=3 3-2=1 4 5 6 7 8
10

j 1

a[0] 1

a[1] 128

a[2] 64

a[3] 32

a[4] 16

a[5] 8

a[6] 4

a[7] 2

a[8] 1

a[9] 0

a[10]

2

1

1

3

1

1

1

打印空格 5 打印 8 1 1 1 1 16 8 4 2 1

三、完善程序 1. 简单的背包问题。设有一个背包,可以放入的重量为 S。现有 n 件物品,重量分别为 w1,w2,……,wn,均为正整数,从 n 件物品中挑选若干件,使得放入背包的重量之和正 好为 s。 程序如下: program lianxi_5 ; m=10 ; of integer ; const

var w : array[1..m] function begin sng:=0 ; if if end; Function var begin x>0 x<0

x,y :integer ; f : boolean ; sng( x:integer ) : integer ;

then then

sng:=1 ; sng:=-1 ;

beibao( s, n : integer ) : boolean ; k : integer ;

k:=sng(s-w[n]); {线索,可以用来判断参数 s、n 的含义} case k of 0: begin writeln( ‘ data:’,n:5, ’weight:’ , w[n]:5)) ; beibao:= true end; 1: begin if if n>1 then {线索,从 n>1 可以看出是倒序扣减的} _(2) beibao(s-w[n],n-1) then begin writeln( ‘ data:’,n:5, ’weight:’ , w[n]:5)) ; {线索} (3)_beibao:=true_ end else else beibao:=_(4)beibao(s, n-1)_ ; {backtracking} beibao:=false ;
11

; {根据题目的要求“正好为 s” ,必须达到“0”后,} {函数的值才为 true}

;

end; -1 : if n>1 then beibao:= (5) beibao(s,n-1) else beibao:=false; {线索} end ; {end of case} end; begin {main program} write(‘ input data : ’); repeat readln(y) ; until y<=m; write(‘total weight = ‘) ;readln( x) ; for i:=1 to y do read(w[i]); f:=_(1)_beibo(x, y)_; if not(f) then writeln(‘not find‘); end. 2. 建立一个若干个学生姓名的循环链接表,并输出,完成以下任务: (1)建立按字典顺序排列的顺序链表,并输出。 (2)输入一个学生姓名,若该学生姓名在链表中,则删除该结点,若不在链接表中,则插 入该学生姓名,并使其仍然有序。 program lianxi_6; {x 为背包的总容量} {读入每一物品的重量 wi} {执行正向 beibao(x, 1)行不行?} {y 为物品的数量}

type pointer = ^stu; stu= record da:string[8] ; link: pointer; end; var head,p,q : pointer ; st1:string[8]; len,x: integer ; procedure print( head1: pointer);

var p: pointer; begin p := head1^.link ; while (1) p <> head1 do begin write(p^.da :5); p := p^.link;

12

end; writeln; end;

procedure inser1( head1: pointer; st2: string); var begin new(r);r^.da:=st2 ; r^.link:=nil ; p := head1^.link ; q := head1; while ( 2 ) (p^.da<st2) begin q:=p; p:=p^.link ; end; r^.link:=q^.link ; q^.link:=r; q := q^.link; end; {of procedure inser1} and ( 3 )(p<>head1) do p,q,r : pointer;

procedure dele( head1: pointer; st2: string); var begin p:=head1^.link ; q:=head1 ; while ( 4 )(p^.da<>st2) and ( 5 )(p<>head1) do {原来答案为 p^.link<>head,} begin q:=p; p:=p^.link; end; if (p^.link = p) or (p = head1) then {原为 p^.link=head1,现随着的改动而改动,} begin writeln('not found '); inser1( head1,st2); end else begin (6) q^.link:=p^.link ; dispose(p); p:=q^.link; {但这样一来,与 or 左边的条件就是一回事了} {该答案在处理到链表尾时会有问题} p,q :pointer;

13

end; end;

begin

{main program}

new(head); head^.da:='#'; head^.link:= head; {‘#’的 ASCII 码是 35,小于数字字母的 ASCII 码} p := head; readln(st1); {设置了这一特殊表头结点后, 处理起来方便了许多, 不用判断一般} {意义下的表空等情况了,各种插入的代码也可以统一编写了}

while st1<>'#' do begin inser1(head,st1); readln(st1); end; print(head); repeat write('please input 1-3 '); readln(x); case x of 1: begin readln(st1);inser1(head,st1);print(head); end; 2: begin readln(st1);dele(head,st1);print(head);end; end; until x = 3; end. 3. 求子串位置:从键盘输入两个字符串 x1,x2,要求查找出 x2 在 x1 字符串中的位置(起 始位置) 。 算法说明: (1)用两个变量分别表示输入的字符串,并求出两个字符串的长度。 (2)利用 I, j 变量作为扫描两个字符串的指针 (3)扫描两个字符串,当其相等时,将指针指向下一个字符, 当 j 的值大于 len2,则输出 x2 在 x1 中的位置 (4)若子串位置不匹配,则使 I 的指针回溯,j 指针重新指向子串的第一个字符。 program exp_6 ; var x1,x2 :string; i, j, len1, len2, ps :integer ; function pos1( r1,r2 : string; L1,L2:integer) :integer ; var i, j : integer ; begin
14

i:=1; j:=1 ; while (i<=L1) and (j<=L2 ) do if r1[i] = r2[j] then begin

③ i:=i+1 ; ④ j:=j+1; ⑥ j:=1 ;end; else ⑧ pos1:=0

if

else begin j>L2 then

end ⑤ i:=i-j+2 ; ⑦ pos1:=i–l2

;

end; begin readln(x1); readln(x2); writeln(x1) ; writeln(x2); len1:= ① length(x1) ; len2:= ② length(x2) ; ps:=pos1(x1,x2,len1,len2); writeln(ps:5); end.
r 4、 求 Cn 的程序(此处 n = 10,r = 5,即求 1~10 这 10 个数中取 5 个数的组合数数目) :

program shuzu3; 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 or b[i]=b[i-1]+1 ; end; end;; writeln(‘s=’,s); end.

15

练习卷(一)答题纸
姓名: 一、选择题(15 题,每题 2 分,共 30 分) 题号 答案 题号 答案 1 A 11 C 2 B 12 D 3 C 13 D 4 D 14 A 5 B 15 A 6 B 7 D 8 D 9 B 10 D 分数:

二、读程序写结果(5 题,每题 7 分,共 35 分) 1、运行结果:4 8 12 1 6 11 2 9 15 10 5 3 7 14 the number is :13 2、运行结果: 7 18 21 45 61 71 83 91 本题是计算什么的问题:本题求最长不下降子序列。
4 3、运行结果:120 (即 P 5 )

4、运行结果:69 5、运行结果:1 2 3 8 四、完善程序(22 空,每空约 1.5 分,共约 35 分) 1、 (1)beibo(x, y) (3)beibao:=true (5)beibo(s,n-1) 2、 (1)p<>head1 (3) (p<>head1) (5)(p^.link<>head1) 3、 (1)length(x1) (3)i:=i+1 (5)i:=i-j+2 (7) pos1:=i–l2 4、 (1)j > 0 (3)b[i]:=b[j] + i – j (2)(p^.da<st2) (4)(p^.da<>st2) (6)q^.link:=p^.link (2)length(x2) (4)j:=j+1 (6)j:=1 (8)pos1:=0 (2)b[j]=10+j-5 (2)beibao(s-w[n],n-1) (4)beibao(s, n-1)

16


相关文章:
全国青少年信息学奥林匹克联赛初赛练习卷(十四)new答案
全国青少年信息学奥林匹克联赛初赛练习卷(十四)new答案_英语考试_外语学习_教育...8 【程序要求】 将上图中每一个部分涂上红(1) 、黄(2) 、蓝(3) 、绿...
全国青少年信息学奥林匹克联赛初赛练习卷(八)new答案
全国青少年信息学奥林匹克联赛初赛练习卷(八)new答案_学科竞赛_初中教育_教育专区...一个完整的计算机系统应包括___。 A.系统硬件和系统软件 B.硬件系统和软件系统...
全国青少年信息学奥林匹克联赛初赛练习卷(六)答案
全国青少年信息学奥林匹克联赛初赛练习卷()答案_学科竞赛_高中教育_教育专区。...因此会出现下面的 4 种情况(如 上图一(b)所示):(1)下靠,即回收区域和...
全国青少年信息学奥林匹克联赛初赛试题2009-2015
第十五届全国青少年信息学奥林匹克联赛初赛试题( 普及组 Pascal 语言 二小时完成 ) ●● 全部试题答案均要求写在答卷纸上,写在试卷纸上一律无效 ●● 一. 单项...
全国青少年信息学奥林匹克联赛初赛练习卷(一)答案
全国青少年信息学奥林匹克联赛初赛练习卷(一)答案_学科竞赛_高中教育_教育专区。全国青少年信息学奥林匹克联赛初赛练习卷(一)答案 2007. 7 一、单项选择题(15 题,...
全国青少年信息学奥林匹克联赛初赛练习卷(三)答案
全国青少年信息学奥林匹克联赛初赛练习卷()答案_IT认证_资格考试/认证_教育...至少需要多大存储容量才能存放一幅分辨率为 1024×800 的黑白图像 (不压缩) ( ...
全国青少年信息学奥林匹克联赛初赛练习卷(二)答案
全国青少年信息学奥林匹克联赛初赛练习卷()答案_其它课程_高中教育_教育专区。...5 D. 2 E. 6 (最后一个分支结点:n\2=11\2=5,故叶子有 6 个) 平面...
全国青少年信息学奥林匹克联赛初赛练习卷(九)new答案
全国青少年信息学奥林匹克联赛初赛练习卷(九)new答案_学科竞赛_高中教育_教育专区...在程序设计语言中,一个过程通常由四个要素组成:过程名、一组称为( 所组成的...
全国青少年信息学奥林匹克联赛初赛练习卷(七)答案
全国青少年信息学奥林匹克联赛初赛练习卷()答案_学科竞赛_高中教育_教育专区。...已知程序P 的算 法时间复杂度为O(n2),如果处理器A执行程序P时能在一小时内...
全国青少年信息学奥林匹克联赛初赛练习卷(十一)new答案
全国青少年信息学奥林匹克联赛初赛练习卷(十一)new答案_学科竞赛_高中教育_教育...每一层都调用它的下一层所提供的网络服务来完成自 己的需求。这 4 层分别为...
更多相关标签: