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

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

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

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

4、：1.數(shù)組面積的定義：(限定數(shù)組頭尾不為 0) 設(shè)有一個(gè)數(shù)組 C= (4,8 , 12,0,6),則C的面積的定義為：.求出二個(gè)整形數(shù)組錯(cuò)位相加的最大面積。也就是說(shuō)，Sc=#梯形面積之和(其中梯形的高約定為 處理)。又如D = ( 12,24,6 )時(shí)，其面積的定義為：12246Sc= (4+8)/ 2 + (8+12)/ 2 + 12 / 2 + 6 /1,三角形作為梯形的特殊情況2.數(shù)組錯(cuò)位相加的定義設(shè)有2個(gè)正整數(shù)的數(shù)組 a , b，長(zhǎng)度為n,當(dāng)n =5時(shí): a = ( 34,26,15,44,12 ) b = ( 23,46,4,0,18 ) 對(duì)a、b進(jìn)行錯(cuò)位相加，可能有下列情況：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可以看到：由于錯(cuò)位不同，相加的結(jié)果也不同。程序要求：找出一個(gè)錯(cuò)位相加的方案，使得輸出的數(shù)組面積為最大?！舅惴ㄌ嵋浚涸O(shè)a , b的長(zhǎng)度為10，用a , b : a

6、rray 1 . . 10 of integer表示,其結(jié)果用數(shù)組 c , d : array 1 . . 30 of in teger表示。錯(cuò)位相加的過(guò)程可以從開(kāi)始不重疊，然后逐步重疊，再到最后的不重疊。梯形面積的計(jì)算公式為：(上底+下底)*高/ 2，其中約定高為1,故可寫(xiě)為(上 底+下底)/ 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è)有一個(gè)表，記為L(zhǎng)=( a1 , a 2,，an),其中:L:表名； a 1 , a 2, ，a n為表中元素;當(dāng)a為09數(shù)字時(shí)，表示元素，為大寫(xiě)字母時(shí)表示是另一個(gè)表，但不能循環(huán)定義。 例如下列表的定義是合法的(約定L是第一個(gè)表的表名)。L =(1 ,3,K8,0, 4)K=(3,P,4,H7)P=(2,3)H=(4,0,5,3)程序要求:當(dāng)全部表給出之后，求出表中所有元素的最大元素，以及表中全部元素的和。【算法提要】 表用記錄類(lèi)型定義:設(shè)Im

9、ax為表中元素最大個(gè)數(shù)tabtype = recordlength : O.lmax;長(zhǎng)度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ì)一個(gè)字符入隊(duì)的過(guò)程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è)有一個(gè)實(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é)果不同， 和 比 多出一個(gè)文件目錄；(2) 本題9分列出的一個(gè)相應(yīng)問(wèn)題是：(能列出類(lèi)似的問(wèn)題均可)用五角錢(qián)換成5分、2分與1分的硬幣，有多少種換法(3) 本題8分這四對(duì)球匹配的情況為：ABCD4312(4)本題12分從存儲(chǔ)數(shù)據(jù)中求出從入口到出口經(jīng)過(guò)最少關(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