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

全国青少年信息学奥林匹克联赛初赛练习卷（一）答案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)（CB）为（ ）。A. a, b, c, d B. a, b, d, e C. b, d, e D. b, c, d, e E. d, f, g2. 设栈S和队列Q的初始状态为空，元素e1,e2,e3,e4,e5,e6依次通过栈S，一个元素出栈后即进入队列Q，若出队的顺序为e2,e4,e3,e6,e5,e1，则栈S的容量至少应该为（）) 2 ) 3 ) 4 ) 5栈队列e1e1,e2e1e2e1,e3e2e1,e3,e4e2e1,e3e2,e4e1e2,e4,e3e1,e5e2,e4,e3e1,e5,e6e2,e4,e3e1,e5e2,e4,e3,e6e1e2,e4,e3,e6.e5e2,e4,e3,e6,e5,e13. 已知集合E=2，请问的所有子集个数是多少？（）) 25 ) 10) 32) 644. 由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!种。但是，在这7!种全排列中，a的重复摆放共有2!种，b的重复摆放有4!种。此外，在余下的7个字符中，仍有可能出现“abc”的排列，这与前面考虑的8种“abc”的摆放是重复的，也要去掉。这时，根据头一个“abc”的摆放起点位置，后一个“abc”分别有5、4、3、2、1种可能的摆放位置，而一旦第二个“abc”摆放好后，余下的一个a和三个b的摆放位置有种可能，因而得上式。5. 假设一个十六位机的某存储单元存放着数00001101101101001000，如果用字母AV来记录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 ( ) do p:=p.next; find := p;end;A (p.data x) B (p nil) C (p.data x) OR (p nil) D (p nil) AND (p.data x)8. 已知一个递归函数：function x (n：integer)：integer；begin if (n=3) then x：= 1 else x:=x(n-2)+x(n-4)+1; end；则y = x (x (8) )；将调用( )次函数x。A) 8 B) 9 C) 16 D) 18x(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 =9x(9)=x(7)+x(5)+1 =x(5)+x(3)+1 + x(3)+x(1)+1 + 1 =x(3)+x(1)+1 + 1 + 1 + 1 + 1 + 1 + 1 =1+1+1+1+1+1+1+1+1 =99. 下列程序段中执行后其运行结果是_ 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) 510. 下列程序段中执行后其运行结果是_program lian_2： function ack(m，n：integer)：integer； begin if m=0 then ack：=n+1else if n=0 then ack:=ack(m-1，1) else ack:=ack(m-1，ack(m，n-1) end； BEGIN WRITELN(ACK(3，3)； READLN； END.program ex1_2 ; var a: integer ; procedure sum( var x:integer) ; begin x:=x+100 writeln(x=,x); end; begin a:=500; sum(a); writeln(a=,a); end. A) 3 B) 7 C ) 56 D) 6111. 如下两个程序的运行结果是： program ex1_1 ; var a: integer ; procedure sum ( x:integer) ; begin x:=x+100 writeln(x=,x); end; begin 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 （2）x=600 a=600 C （1）x=600 a=500 （2）x=600 a=600D （1）x=500 a=500 （2）x=600 a=60012. 已知A=(27E)H，B=(135)D，则A-B的结果是 ( )。 A） (674)O B） (1AD)H C） (523)D D）(111110111)B13. 下面哪一句话是错误的？（ ）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，4725，28，32，53，74，43，86，4725，28，32，43，74，53，86，4725，28，32，43，47，53，86，7425，28，32，43，47，53，74，86也可以编出一个排序算法，即假设已有了最终的顺序，通过考察每个数据与其最终位置的差异，来进行交换调整。15. 有3个课外小组：物理组，化学组和生物组。今有张、王、李、赵、陈、5名同学，已知张、王为物理组成员，张、李、赵为化学组成员，李、赵、陈为生物组成员。如果要在3个小组分别选出3位组长，一位同学最多只能担任一个小组的组长，共有多少种选择方案？（ ）A）11 B）12 C）13 D）14张王物理组化学组生物组李、赵陈若不考虑约束条件，共有：2人（物理组）*3人（化学组）*3人（化学组）=18（种）考虑到约束条件，还要去掉：n 张被选为物理组及化学组的组长，这时生物组有3种选法；n 李、赵中的某一人兼了化学组和生物组的组长，这种情况下物理组有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:=puntil 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:array1.3,1.10 of integer ; i,n ,L, k, j:integer; begin read(n);for i := 1 to 10 do beginread( b1, I);b2, I: = 1; b3, I: = 0 ; end; for i: = n - 1 downto 1 do begin L:= 0; k:= 0 ;FOR j: = i + 1 TO n do begin if (b1, i = b1, j) and (L 0 then begin b2, i: = L+1 ; b3, i: = k ;end; end; j: = 1 ; for i: = 2 to n do if b2, i b2, j then j: = i ; writeln (b2, j) ;while j 0 do begin write( b1, j, ); j: = b3, j; end; end.当程序运行后，输入：10 23 18 21 45 61 104 71 83 91 87 输出： 7 18 21 45 61 71 83 91本题是计算什么的问题：本题求最长不下降子序列3、 program lianxi_1； var a: array1.10 of integer ； s, n, m： longint ; flag：set of byte；procedure try(dep：integer)；val i: integer；beginfor i:=1 to n doif not（i in flag ） thenbegin flag：=flag +i； adep：=i； if dep=m then inc(s) else 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 5输出结果：120 （即）分析：Try(1)i=1Flagsa1a2a3a4a5101Try(2)i=21,212Try(3)I=31,2,3123Try(4)(在第四位上变化)I=41,2,3,4123411,2,3I=51,2,3,5123521,2,3Try(3)(递归上升)(在第三位上变化)I=31,2,3-3=1,2I=41,2,41245Try(4)I=31,2,4,3124331,2,4I=51,2,4,5124541,2,4Try(3)(递归上升)I=41,2,41245I=51,2,4,51255Try(4) 注意这一求排列的递归程序与求组合值程序的不同4、 program lianxi_3 ;const a:array1.14 of longint=( 94,32,40,90,99,80,46,21,69,28,64,73,85,54);var i,j,k,m,left, right , temp: longint;beginm:=8 ; left :=1 ; right :=14 ;while left=right do begink:=am ; I:=left ; j:= right ;repeat while kai do i:=I+1 ; if Ij ; if jm then right:= j ;end;writeln(am);End. 输出结果：69 利用快速排序思想，确定最终am上的数据是哪一个，但本程序不能实现对整个数组的完整排序。5、 program lianxi_4; type arr=array0.31 of longint; var a:arr; n,i,j,k:longint; begin readln(n,k); fillchar(a,sizeof(a),0); an:=1; a0:=1; a数组中存放了二进制数各位的位权 for i:=n-1 downto 1 do ai:=ai+1*2; i:=0; j:=1; while k1 do begin while (iai) do begin dec(k,ai); 从k中不断地减去2i inc(i) end; of inner while loopj记录着打印了几个数字，且除了第一个数字外，后面的都要先打印空格 if j1 then write( ); inc(j); write(i); ai:=1 end; of outer while loop if i=0 then writeln(0); end.输入数据：8 35输出结果：1 2 3 8nkija0a1a2a3a4a5a6a7a8a9a108350111286432168421035-1=3412打印i，即打印1134-1=332打印一个空格3打印211133-1=323打印空格4打印3111132-1=31431-16=15515-8=767-4=373-2=18打印空格5打印81111168421三、完善程序1 简单的背包问题。设有一个背包，可以放入的重量为S。现有n件物品，重量分别为w1,w2,，wn,均为正整数，从n 件物品中挑选若干件，使得放入背包的重量之和正好为s。程序如下：program lianxi_5 ; const m=10 ; var w : array1.m of integer ; x,y :integer ; f : boolean ; function sng( x:integer ) : integer ; begin sng:=0 ; if x0 then sng:=1 ; if x1 then 线索，从n1可以看出是倒序扣减的 if _(2) beibao(s-wn,n-1) then begin writeln( data:,n:5, weight: , wn:5) ; 线索 (3)_beibao:=true_ ; end else beibao:=_(4)beibao(s, n-1)_ ; backtracking else beibao:=false ; end; -1 : if n1 then beibao:= (5) beibao(s,n-1) else beibao:=false; 线索 end ; end of case end; begin main program write( input data : ); repeat readln(y) ; y为物品的数量 until y=m; write(total weight = ) ;readln( x) ; x为背包的总容量 for i:=1 to y do read(wi); 读入每一物品的重量wi f:=_(1)_beibo(x, y)_; 执行正向beibao(x, 1)行不行？ if not(f) then writeln(not find); end.2 建立一个若干个学生姓名的循环链接表，并输出，完成以下任务：（1）建立按字典顺序排列的顺序链表，并输出。（2）输入一个学生姓名，若该学生姓名在链表中，则删除该结点，若不在链接表中，则插入该学生姓名，并使其仍然有序。program lianxi_6; type pointer = stu; stu= record da:string8 ; link: pointer; end;var head,p,q : pointer ; st1:string8; len,x: integer ;procedure print( head1: pointer);var p: pointer;beginp := head1.link ;while （1） p head1 dobeginwrite(p.da :5);p := p.link;end;writeln;end;procedure inser1( head1: pointer; st2: string);var p,q,r : pointer;beginnew(r);r.da:=st2 ; r.link:=nil ; p := head1.link ; q := head1;while ( 2 ) (p.dast2) and ( 3 )（phead1) dobeginq:=p; p:=p.link ;end;r.link:=q.link ; q.link:=r;q := q.link;end; of procedure inser1procedure dele( head1: pointer; st2: string);var p,q :pointer;beginp:=head1.link ; q:=head1 ;while ( 4 )(p.dast2) and ( 5 )(phead1) do 原来答案为p.linkhead，begin 该答案在处理到链表尾时会有问题q:=p; p:=p.link;end;if (p.link = p) or (p = head1) then 原为p.link=head1，现随着的改动而改动，begin 但这样一来，与or左边的条件就是一回事了writeln(not found );inser1( head1,st2);endelsebegin（6） q.link:=p.link ; dispose(p); p:=q.link;end;end;begin main programnew(head);head.da:=#; head.link:= head; #的ASCII码是35，小于数字字母的ASCII码p := head; 设置了这一特殊表头结点后，处理起来方便了许多，不用判断一般readln(st1); 意义下的表空等情况了，各种插入的代码也可以统一编写了while st1# dobegininser1(head,st1);readln(st1);end;print(head);repeatwrite(please input 1-3 );readln(x);case x of1: 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 i:=1; j:=1 ;while (i=L1) and (jL2 then pos1:=il2 else pos1:=0 ; end; beginreadln(x1); readln(x2); writeln(x1) ; writeln(x2);len1:= length(x1)