廣東省高一信息技術(shù)歷年NOIP初賽試題12

1、廣東省汕頭市金山中學(xué)高一信息技術(shù) 歷年NOIP初賽試題12分區(qū)聯(lián)賽初賽試題（高中組） 競賽用時(shí)： 2 小時(shí)一、基礎(chǔ)題執(zhí)行 C DIR 命令后，屏幕上顯示如下畫面：FORMATCOM12145SYSCOM4878PUCBAT126XCOPYEXE112164 File（s） 123456 bytes free接著又順序執(zhí)行了如下幾條 DOS命令： C DIR DF.TXT C TYPE DF.TXT C DIR試問：執(zhí)行命令和在屏幕上顯示的結(jié)果是否與相同？ 列舉一個問題，使問題的解能對應(yīng)相應(yīng)的算法 例如對算法 X:=10;Y;=5;READ（M,N）;S:=X*M-Y*N;可列舉出如下的問題：學(xué)

2、生答題，答對一題可得 10分，答錯一題則要扣去 5 分，輸入答對的題數(shù)（ M） 與答錯的題數(shù)（N）,求最后得分（S）是多少？ 現(xiàn)有以下算法： K:=0;FOR I:=0 TO 10 DO K:=K +（50-I*5） DIV 2 + 1; 請列出一個相應(yīng)的問題。.有標(biāo)號為 A、B、C D和1、2、3、4的8個球，每兩個球裝一盒，分裝 4盒。標(biāo)號 為字母的球與標(biāo)號為數(shù)字的球有著某種一一對應(yīng)的關(guān)系（稱為匹配）并已知如下條件： 匹配的兩個球不能在一個盒子內(nèi)； 2 號匹配的球與 1 號球在一個盒子里； A 號和 2 號球在一個盒子里； B匹配的球和 C號球在一個盒子里； 3號匹配的球與 A號匹配的球在

3、一個盒子里； 4號是A或B號球的匹配球； D號與1號或2號球匹配； 請寫出這四對球匹配的情況。.從入口（ 1）到出口（ 17）的可行路線圖中，數(shù)字標(biāo)號表示關(guān)卡：(18 )(19 )15 )(16)(17) 一(12)*(1)(2)(3)(7)(4)甲)-I(8)13 )(14 ):9 )(10 )(11)12187312419851316614159170111222345681011111112現(xiàn)將上面的路線圖，按記錄結(jié)構(gòu)存儲如下:1234567891011121314151617NOPRE請?jiān)O(shè)計(jì)一種能從存儲數(shù)據(jù)中求出入口到出口經(jīng)過最少關(guān)卡路徑的算法。二、根據(jù)題目要求，補(bǔ)充完善以下偽代碼程序

4、：1.數(shù)組面積的定義：(限定數(shù)組頭尾不為 0) 設(shè)有一個數(shù)組 C= (4,8 , 12,0,6),則C的面積的定義為：.求出二個整形數(shù)組錯位相加的最大面積。也就是說，Sc=#梯形面積之和(其中梯形的高約定為 處理)。又如D = ( 12,24,6 )時(shí)，其面積的定義為：12246Sc= (4+8)/ 2 + (8+12)/ 2 + 12 / 2 + 6 /1,三角形作為梯形的特殊情況2.數(shù)組錯位相加的定義設(shè)有2個正整數(shù)的數(shù)組 a , b，長度為n,當(dāng)n =5時(shí): a = ( 34,26,15,44,12 ) b = ( 23,46,4,0,18 ) 對a、b進(jìn)行錯位相加，可能有下列情況：34

5、26 15 44 12+)23 46 4 0 1834 26 15 44 12 23 46 4 0 18 或：34 26 15 44 12+)23 46 4 0 1834 26 15 44 35 46 4 0 18 或：34 26 15 44 12+)23 46 4 0 1834 26 15 67 58 4 0 18或：最后有：34 26 15 44 12+)23 46 4 0 1823 46 4 0 1834 26 15 44 12可以看到：由于錯位不同，相加的結(jié)果也不同。程序要求：找出一個錯位相加的方案，使得輸出的數(shù)組面積為最大?！舅惴ㄌ嵋浚涸O(shè)a , b的長度為10，用a , b : a

6、rray 1 . . 10 of integer表示,其結(jié)果用數(shù)組 c , d : array 1 . . 30 of in teger表示。錯位相加的過程可以從開始不重疊，然后逐步重疊，再到最后的不重疊。梯形面積的計(jì)算公式為：(上底+下底)*高/ 2，其中約定高為1,故可寫為(上 底+下底)/ 2。程序：const n = 10;function sea : real; 計(jì)算數(shù)組 C面積beginj1:=1;while do j1:=j1+1;if j1 = 3*n then sea:=0else begi nj2:=3* n;while do j2:=j2-1; if j1 = j2 th

7、e n sea:=O else beg inj3:=c j1 + c j2 ; for j4:=j1+1 to j2-1 do j3 := j3 + cj4*2;sea:=j3 / 2enden d;begin 主程序for i:=1 to n do read (a i );for j:=1 to n do read (b j ); ；for i:=1 to 2*n+1 dobeginfor j:=1 to 3*n do；for j:=1 to n do c j+n := a j ;for j:=1 to n do；p:=sea;if p s the n beg ind:=c;s:=pen d

8、;en d;for i:=1 to 3*n do write (d i ,);write In;write In ( s= , s)en d.表的操作：設(shè)有一個表，記為L=( a1 , a 2,，an),其中:L:表名； a 1 , a 2, ，a n為表中元素;當(dāng)a為09數(shù)字時(shí)，表示元素，為大寫字母時(shí)表示是另一個表，但不能循環(huán)定義。 例如下列表的定義是合法的(約定L是第一個表的表名)。L =(1 ,3,K8,0, 4)K=(3,P,4,H7)P=(2,3)H=(4,0,5,3)程序要求:當(dāng)全部表給出之后，求出表中所有元素的最大元素，以及表中全部元素的和?！舅惴ㄌ嵋?表用記錄類型定義:設(shè)Im

9、ax為表中元素最大個數(shù)tabtype = recordlength : O.lmax;長度eleme nt : array 1.lmax of char; 表體en d;再定義隊(duì)列：qtype = recordbase : array 0.lmax of char; front , rear : 0.lmax;en d;表中最大元素及元素為此，設(shè)計(jì)一個字符入隊(duì)的過程in queue，出隊(duì)函數(shù)outquere ，求和均采用遞歸計(jì)算。程序：const lmax = 38 ;var t : array A . . Z of tabtype;s : stri ng lmax ;procedure in

10、q ueue ( var q : qtype; c : char ); beginq.rear :=；q.base q.rear := cen d;function outqueue ( var q : qtype ) : char; beginq.fro nt :=；outqueue := q.base q.front en d;function maxnu mber ( c : char ) : char;var max : char;beginmax := chr (0);for i:=1 to tc .len gth dobeginch := tc.eleme nti;if the n

11、 m := maxnu mber (ch) else m := ch;if maxm the n max:=mend;en d;function total ( c : char ) : in teger; var k , i : in teger;begink := 0;for i := 1 to tc.le ngth dobeginch := tc. lelment i ;-ord (0);if the n m := total (ch) else m := ord (ch) k := k + men d; total := ken d;beginmax : = 36;for tab no

12、 := A to Z do t tab no . le ngth := 0;q.front := 0; q.rear := 0;inqueue (q , L);while q. front q. rear dobegintab no := outqueue (q);write ( tab no , =);readl n (s);i := 1;while s i ( do i:=i+1;while s i ) dobeginif (s i =a ) and (s i = A ) and (s i =0) and (s i =9)then begininc ( t tabno . length )

13、; tabno . element t tabno . length := s i end;inc ( i )end;end;writeln ( the max number in table L is : , maxnumber ( L ) );writeln ( Total is : , total (end.L) )設(shè)有一個實(shí)數(shù)，以字符串形式存放于數(shù)組x 中，用 x :array 1. . n of char 表示。其中 x 1 若為 - ，表示負(fù)數(shù)；若為 + ， ? ? ? ?則表示正數(shù)。若為數(shù)字，也認(rèn)為是正數(shù)。例如 x = ( , 2 , 0 ?JJ 3 , . , 55,U, %

14、)則表示 203.5x = ( - , 1 , . = O) and ( x i 0 the n while a k =0 do beg inendend.分區(qū)聯(lián)賽初賽(高中組)試題參考答案 、基礎(chǔ)題(33分)(1) 本題4分顯示結(jié)果不同， 和 比 多出一個文件目錄；(2) 本題9分列出的一個相應(yīng)問題是：(能列出類似的問題均可)用五角錢換成5分、2分與1分的硬幣，有多少種換法(3) 本題8分這四對球匹配的情況為：ABCD4312(4)本題12分從存儲數(shù)據(jù)中求出從入口到出口經(jīng)過最少關(guān)卡路徑的算法及輸出結(jié)果:算法：輸出結(jié)果1:=1;(17)WHILE NOI工 17 DOl:=l+1;(16)ENDWHILE;fREPEAT(19)WRITE ( ( ,NOI,);fWRITE (f);(18)I:=PREI;fUNTIL I=0;、根據(jù)題目要求，補(bǔ)充完善以下偽代碼程序(共67分)(1) 共10分(每空2分) CJ1=0 AND