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

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

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

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

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

6、rray 1 . . 10 of integer表示,其結果用數組 c , d : array 1 . . 30 of in teger表示。錯位相加的過程可以從開始不重疊，然后逐步重疊，再到最后的不重疊。梯形面積的計算公式為：(上底+下底)*高/ 2，其中約定高為1,故可寫為(上 底+下底)/ 2。程序：const n = 10;function sea : real; 計算數組 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.表的操作：設有一個表，記為L=( a1 , a 2,，an),其中:L:表名； a 1 , a 2, ，a n為表中元素;當a為09數字時，表示元素，為大寫字母時表示是另一個表，但不能循環(huán)定義。 例如下列表的定義是合法的(約定L是第一個表的表名)。L =(1 ,3,K8,0, 4)K=(3,P,4,H7)P=(2,3)H=(4,0,5,3)程序要求:當全部表給出之后，求出表中所有元素的最大元素，以及表中全部元素的和?！舅惴ㄌ嵋?表用記錄類型定義:設Im

9、ax為表中元素最大個數tabtype = recordlength : O.lmax;長度eleme nt : array 1.lmax of char; 表體en d;再定義隊列：qtype = recordbase : array 0.lmax of char; front , rear : 0.lmax;en d;表中最大元素及元素為此，設計一個字符入隊的過程in queue，出隊函數outquere ，求和均采用遞歸計算。程序：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) )設有一個實數，以字符串形式存放于數組x 中，用 x :array 1. . n of char 表示。其中 x 1 若為 - ，表示負數；若為 + ， ? ? ? ?則表示正數。若為數字，也認為是正數。例如 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)賽初賽(高中組)試題參考答案 、基礎題(33分)(1) 本題4分顯示結果不同， 和 比 多出一個文件目錄；(2) 本題9分列出的一個相應問題是：(能列出類似的問題均可)用五角錢換成5分、2分與1分的硬幣，有多少種換法(3) 本題8分這四對球匹配的情況為：ABCD4312(4)本題12分從存儲數據中求出從入口到出口經過最少關卡路徑的算法及輸出結果:算法：輸出結果1:=1;(17)WHILE NOI工 17 DOl:=l+1;(16)ENDWHILE;fREPEAT(19)WRITE ( ( ,NOI,);fWRITE (f);(18)I:=PREI;fUNTIL I=0;、根據題目要求，補充完善以下偽代碼程序(共67分)(1) 共10分(每空2分) CJ1=0 AND