Tài liệu đề thi học sinh giỏi môn tin lớp 11

Së gi¸o dôc - ®µo t¹o qu¶ng b×nh SBD: §Ò chÝnh thøc Kú thi chän häcSinh Giái líp 11 N¨m häc 2005-2006 M«n: Tin häc - chuyªn Thêi gian lµm bµi: 180 phót. §Ò ra: Sö dông ng«n ng÷ lËp tr×nh Turbo Pascal ®Ó lËp tr×nh gi¶i c¸c bµi to¸n sau: C©u 1. (3,0 ®iÓm) Gi¶i m· chuçi nhÞ ph©n - NHIPHAN.PAS Mäi th«ng tin ®Òu ®îc m· ho¸ díi d¹ng mét chuçi sè nhÞ ph©n. §Ó n©ng cao ®é tin cËy khi truyÒn tin, mçi bÝt ®îc biÓu diÔn lÆp l¹i 3 lÇn. VÝ dô, c¸c bÝt tin ‘011’ ®îc biÓu diÔn thµnh ‘000111111’ ®Ó thùc hiÖn truyÒn. Do nhiÔu cña m«i trêng nªn khi vÒ ®Õn ®Ých, c¸c bÝt tin cã thÓ bÞ sai lÖch. V× vËy, khi nhËn ®îc th«ng tin cø mçi ®o¹n 3 bÝt ®îc gi¶i m· thµnh mét bÝt. BÝt nµy cã gi¸ trÞ 0 nÕu trong nhãm 3 bÝt xuÊt hiÖn Ýt nhÊt 2 bÝt 0, bÝt nµy cã gi¸ trÞ 1 nÕu trong nhãm 3 bÝt xuÊt hiÖn Ýt nhÊt 2 bÝt 1. VÝ dô, nÕu c¸c bÝt tin nhËn ®îc lµ ‘000110010011’, sau khi ®· gi¶i m· ta thu ®îc ‘0101’. Yªu cÇu: Cho chuçi nhÞ ph©n biÓu diÔn th«ng tin nhËn ®îc, h·y gi¶i m· chuçi nhÞ ph©n ®ã. D÷ liÖu vµo: Cho trong file Nhiphan.inp cã cÊu tróc nh sau: - Dßng 1: Ghi chuçi nhÞ ph©n cÇn gi¶i m·, lµ mét d·y c¸c sè 0, 1 ghi liÒn nhau. D÷ liÖu ra: Ghi trong file Nhiphan.out theo cÊu tróc nh sau: - Dßng 1. Ghi chuçi nhÞ ph©n ®· ®îc gi¶i m·, lµ mét d·y c¸c sè 0, 1 ghi liÒn nhau. VÝ dô: Nhiphan.inp Nhiphan.out 001111010110111000 010110 C©u 2: (3,5 ®iÓm) D·y con - DAYCON.PAS Cho hai d·y sè thùc a 1, a2, ... ,an (1) vµ b1, b2, ... ,bm (2). D·y (1) ®îc gäi lµ d·y con cña d·y (2) nÕu bá ®i k phÇn tö trong d·y (2) th× ta ®îc d·y (1). VÝ dô: D·y 1, 3, 5 lµ mét d·y con cña d·y 0,1, 2, 1, 4, 3, 5, 7. Yªu cÇu: Víi hai d·y sè cho tríc, h·y x¸c ®Þnh xem d·y (1) cã ph¶i lµ d·y con cña d·y (2) hay kh«ng. D÷ liÖu vµo: Cho trong file DAYCON.INP cã cÊu tróc nh sau: - Dßng 1: Ghi sè N lµ sè lîng phÇn tö cña d·y (1) (1<=N<=1000). - Dßng 2: Ghi N sè a1 a2 ... an, c¸c sè ghi c¸ch nhau mét dÊu c¸ch. - Dßng 3: Ghi sè M lµ sè lîng phÇn tö cña d·y (2) (1<=M<=1000). - Dßng 4: Ghi M sè b1 b2 ... bm, c¸c sè ghi c¸ch nhau mét dÊu c¸ch. D÷ liÖu ra: Ghi ra file DAYCON.OUT theo cÊu tróc nh sau: - Dßng 1: Ghi ký tù ‘Y’ nÕu d·y (1) lµ d·y con cña d·y (2), ngîc l¹i ghi ‘N’ VÝ dô: DAYCON.INP 3 1 3 5 8 0 1 2 1 4 3 5 7 DAYCON.OUT Y C©u 3: (3,5 ®iÓm) S¾p xÕp x©u – STR.PAS Cho mét x©u mÉu S gåm N ký tù ®îc lÊy tõ tËp c¸c ký tù ‘A’...‘Z’. Víi mét cÆp sè nguyªn (i,j) (1<=i,j<=N), ta t¹o ra mét x©u thø cÊp S’ b»ng c¸ch ®æi chç ký tù thø i víi ký tù thø j cña x©u mÉu S. Víi M cÆp sè (i,j) ta sÏ thu ®îc M x©u thø cÊp. Yªu cÇu: S¾p xÕp c¸c x©u thø cÊp t¨ng dÇn theo thø tù tõ ®iÓn. D÷ liÖu vµo: Cho trong file STR.INP cã cÊu tróc nh sau: - Dßng 1: Ghi gi¸ trÞ N, lµ sè ký tù cña x©u S (1<=N<=500) - Dßng 2: Ghi x©u mÉu S. - Dßng 3: Ghi gi¸ trÞ M, lµ sè lîng c¸c cÆp sè (i, j) (1<=M<=500) - M dßng tiÕp theo: Mçi dßng ghi mét cÆp sè i, j lÇn lît lµ chØ sè cña ký tù thø i vµ chØ sè cña ký tù thø j cÇn ®æi chç cña x©u S. Hai sè ghi c¸ch nhau mét dÊu c¸ch. D÷ liÖu ra: Ghi ra file STR.OUT theo cÊu tróc nh sau: - M dßng: Mçi dßng ghi mét x©u thø cÊp, c¸c dßng ®îc s¾p t¨ng dÇn theo thø tù tõ ®iÓn. VÝ dô: STR.INP 5 ABCDA 3 2 4 1 5 3 3 STR.OUT ABCDA ABCDA ADCBA HÕt Híng dÉn chÊm thi chän häc sinh giái líp 11 - chuyªn n¨m häc 2005-2006 I/ Ph¬ng ph¸p chung - Gi¸m kh¶o t¹o c¸c bé d÷ liÖu vµo, tÝnh to¸n kÕt qu¶. Thùc hiÖn ch¬ng tr×nh cña häc sinh vµ so s¸nh kÕt qu¶. - Gi¸m kh¶o cã thÓ sö dông ch¬ng tr×nh mÉu ®Ó tÝnh kÕt qu¶ cña d÷ liÖu vµo: NHIPHAN.PAS DAYCON.PAS STR.PAS - Ch¬ng tr×nh häc sinh ch¹y ®óng mçi bé test, gi¸m kh¶o cho 0.5 ®iÓm. Nh vËy, nÕu c©u hái cã 3 ®iÓm th× gi¸m kh¶o ph¶i t¹o ®îc 6 bé test. - NÕu ch¬ng tr×nh ch¹y sai test nµo th× gi¸m kh¶o cho 0 ®iÓm ®èi víi test ®ã. - Gi¸m kh¶o cã thÓ sö dông c¸c test gîi ý díi ®©y nÕu cÇn thiÕt. II/ Ch¬ng tr×nh mÉu C©u 1. (3,0 ®iÓm) Gi¶i m· chuçi nhÞ ph©n - NHIPHAN.PAS const var fi='nhiphan.inp'; fo='nhiphan.out'; st,s1:string; procedure docdl; var f:text; begin assign(f,fi); reset(f); readln(f,st); close(f); end; function mahoa(kt1,kt2,kt3:char):char; var t:byte; begin t:=0; if kt1='1' then t:=t+1; if kt2='1' then t:=t+1; if kt3='1' then t:=t+1; if t>=2 then mahoa:='1' else mahoa:='0'; end; procedure xuli; var ll,l,i:integer; begin ll:=length(st); l:=1; s1:=''; while lb[j]) do j:=j+1; tim:=j; end; procedure xl; var i,j:word; kt:char; begin j:=1; kt:='Y'; for i:=1 to n do begin if (tim(a[i],j)>m) then kt:='N'; end; assign(f,fo);rewrite(f); writeln(f,kt); close(f); end; begin doc; xl; readln; end. C©u 3: (3,5 ®iÓm) S¾p xÕp x©u – STR.PAS {$r+} program sap_xau; const fi='str.inp'; fo='str.out'; type mmcc=array[1..500] of char; mmci=array[1..500] of integer; var d,s,b,c,tg1:mmcc; l,r:mmci; n,m:integer; f:text; procedure nhap; var i,j:integer; begin assign(f,fi); reset(f); readln(f,n); for i:=1 to n do read(f,s[i]); readln(f); readln(f,m); for i:=1 to m do readln(f,l[i],r[i]); close(f); end; procedure doicho(var x,y:char); var tg:char; begin tg:=x; x:=y; y:=tg; end; procedure xl; var i,j,k,tg:integer; begin for i:=1 to m-1 do begin b:=s; doicho(b[l[i]],b[r[i]]); for j:=i+1 to m do begin c:=s; doicho(c[l[j]],c[r[j]]); for k:=1 to n do begin if b[k]>c[k] then begin tg:=l[i];l[i]:=l[j];l[j]:=tg; tg:=r[i];r[i]:=r[j];r[j]:=tg; tg1:=b;b:=c;c:=tg1; break; end; if b[k] - Xem thêm -