NOIP提高組初賽及答案(Pascal)

1、第十八屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽（提高組pascal語言試題）競賽時間：2012年10月13日14:3016:30選手注意：l 試題紙共有10頁，答題紙共有2頁，滿分100分。請在答題紙上作答，寫在試題紙上一律無效。l 不得使用任何電子設(shè)備（如計算器、手機、電子詞典等）或查閱任何書籍資料一、單項選擇題（共10題，每題1.5分，共計15分；每題有且僅有一個正確選項） 1目前計算機芯片（集成電路）制造的主要原料是（ ），它是一種可以在沙子中提煉出的物質(zhì)。a硅 b銅 c鍺 d鋁 2（ ）是主要用于顯示網(wǎng)頁服務(wù)器或者文件系統(tǒng)的html文件的內(nèi)容，并讓用戶與這些文件交互的一種軟件。a資源管理器

2、b瀏覽器 c電子郵件 d編譯器3目前個人電腦的（ ）市場占有率最靠前的廠商包括intel、amd等公司。a顯示器 bcpu c內(nèi)存 d鼠標4無論是tcp/ip模型還是osi模型，都可以視為網(wǎng)絡(luò)的分層模型，每個網(wǎng)絡(luò)協(xié)議都會被歸入某一層中。如果用現(xiàn)實生活中的例子來比喻這些“層”，以下最恰當?shù)氖牵?）。 a 中國公司的經(jīng)理與波蘭公司的經(jīng)理交互商業(yè)文件b 軍隊發(fā)布命令c 國際會議中，每個人都與他國地位對等的人直接進行會談d 體育比賽中，每一級比賽的優(yōu)勝者晉級上一級比賽 5如里不在快速排序中引入隨機化，有可能導(dǎo)致的后果是（ ）。a數(shù)組訪問越界 b陷入死循環(huán)c排序結(jié)果錯誤 d排序時間退化為平方級61946

3、年誕生于美國賓夕法尼亞大學(xué)的eniac屬于（ ）計算機。 a電子管 b晶體管 c集成電路 d超大規(guī)模集成電路 7在程序運行過程中，如果遞歸調(diào)用的層數(shù)過多，會因為（ ）引發(fā)錯誤。a系統(tǒng)分配的?？臻g溢出 b系統(tǒng)分配的堆空間溢出 c系統(tǒng)分配的隊列空間溢出 d系統(tǒng)分配的鏈表空間溢出8地址總線的位數(shù)決定了cpu可直接尋址的內(nèi)存空間大小，例如地址總線為16位，其最大的可尋址空間為64kb。如果地址總線是32位，則理論上最大可尋址的內(nèi)存空間為（ ）。 a128kb b1mb c1gb d4gb9以下不屬于3g（第三代移動通信技術(shù)）標準的是（ ）。agsmbtd-scdmaccdma2000dwcdma10仿

4、生學(xué)的問世開辟了獨特的科學(xué)技術(shù)發(fā)展道路。人們研究生物體的結(jié)構(gòu)、功能和工作原理，并將這些原理移植于新興的工程技術(shù)中。以下關(guān)于仿生學(xué)的敘述，錯誤的是（ ）a由研究蝙蝠，發(fā)明雷達 b由研究蜘蛛網(wǎng)，發(fā)明因特網(wǎng) c由研究海豚，發(fā)明聲納 d由研究電魚，發(fā)明伏特電池二、不定項選擇題（共10題，每題1.5分，共計15分；每題有一個或多個正確選項，多選或少選均不得分）1如果對于所有規(guī)模為n的輸入，一個算法均恰好進行（ ）次運算，我們可以說該算法的時間復(fù)雜度為 。a b c d 2 從頂點 出發(fā)，對有向圖（ ）進行廣度優(yōu)先搜索（bfs）時，一種可能的遍歷順序是 。3如果一個棧初始時為空，且當前棧中的元素從棧頂?shù)綏?/p>

5、底依次為a，b，c（如右圖所示），另有元素d已經(jīng)出棧，則可能的入棧順序是（ ）。aa, b, c, d bb, a, c, d ca, c, b, d dd, a, b, c4在計算機顯示器所使用的rgb顏色模型中，（ ）屬于三原色之一。a黃色 b藍色 c10 d155一棵二叉樹一共有19個節(jié)點，其葉子節(jié)點可能有（ ）個。 a1 b9 c紫色 d綠色6已知帶權(quán)有向圖g上的所有權(quán)值均為正整數(shù)，記頂點u到頂點v的最短路徑的權(quán)值為 。若 是圖g上的頂點，且它們之間兩兩都存路徑可達，則以下說法正確的有（ ）。a 到的最短路徑可能包含一個環(huán)b c d如果是 到 的一條最短路徑，那么是 到的一條最短路徑

6、7邏輯異或（）是一種二元運算，其真值表如下所示。abfalsefalsefalsefalsetruetruetruefalsetruetruetrueflase以下關(guān)于邏輯異或的性質(zhì)，正確的有（ ）。a交換律： b結(jié)合律：c關(guān)于邏輯與的分配律：d關(guān)于邏輯或的分配律：8十進制下的無限循環(huán)小數(shù)（不包括循環(huán)節(jié)內(nèi)的數(shù)字均為0成均為9的平凡情況），在二進制下有可能是（ ）。a無限循環(huán)小數(shù)(不包括循環(huán)節(jié)內(nèi)的數(shù)字均為0或均為9的平凡情）b無限不循環(huán)小數(shù)c有限小數(shù)d整數(shù)9（ ）是目前互聯(lián)網(wǎng)上常用的e-mail服務(wù)協(xié)議。ahttp bftp cpop3 dsmtp10以下關(guān)于計算復(fù)雜度的說法中，正確的有（ ）。

7、a如果一個問題不存在多項式時間的算法，那它一定是np類問題b如果一個問題不存在多項式時間的算法，那它一定不是p類問題c如果一個問題不存在多項式空間的算法，那它一定是np類問題d如果一個問題不存在多項式空間的算法，那它一定不是p類問題三、問題求解（共2題，每題5分，共計10分） 1 本題中，我們約定布爾表達式只能包含p，q，r三個布爾變量，以及“與”（）、“或”（）、“非”（）三種布爾運算。如果無論p，q，r如何取值，兩個布爾表達式的值總是相同，則稱它們等價。例如(pq)r和p(qr)等價，pp和qq也等價；而pq和pq不等價。那么兩兩不等價的布爾表達式最多有 個。2 對于一棵二叉樹，獨立集是指

8、兩兩互不相鄰的節(jié)點構(gòu)成的集合。例如，圖1有5個不同的獨立集（1個雙點集合，3個單點集合、1個空集），圖2有14個不同的獨立集。那么圖3有 個不同的獨立集。三、閱讀程序?qū)懡Y(jié)果。（共4題，每題8分，共計32分） 1 var n,i,temp,sum:integer;a :array1.100 of integer;beginreadln(n);for i:=1 to n doread(ai);for i:=1 to n-1 doif aiai+1 thenbegintemp := ai;ai := ai+1;ai+1 := temp;end;for i:=n downto 2 doif ai1)

9、and (datah=datah-1) domerge;end;writeln(ans);end.（1）輸入：8輸出：_ （4分）（2）輸入：2012輸出：_ （4分）4 varleft, right, father:array1.20 of integer;sl, s2, s3:string;n,ana:integer;procedure check(x:integer);begin if leftx0 then check(leftx); s3 := s3 + slx; if rightx0 then check(rightx);end;procedure calc(x,dep:integ

10、er);begin ans:= ans + dep*(ord(slx)-ord(a)+1); if leftx 0 then calc(leftx,dep+l); if rightx 0 then calc(rightx),dep+l);end;procedure dfs(x,th :integer);beginif th = n+1 thenbegin s3 :=; check(1); if s2=s3 then beginans := 0;calc(1,1);writeln(ans);end;exit;end;if (leftx=0) and (rightx=0) thenbegin le

11、ftx) := th; fatherth := x; dfs(th, th+1); fatherth := 0; leftx := 0;end;if rightx = 0 thenbegin rightx := th; fatherth := x; dfs(th, th+1); fatherth := 0; rightx := 0;end;if (fatherx 0) then dfs(fatherx,th);end;beginreadln(s1);readln(s2);n := length(s1);fillchar(left,sizeof(left),0);fillchar(right,s

12、izeof(right),0);fillcahr(father,sizeof(father),0);dfs(1,2);end.輸入：abcdefbcaedf輸出：_ 五、完善程序（第1題第2空3分，其余每空2.5分，共計28分） 1（排列數(shù)）輸入兩個正整數(shù) ，在 中任取個數(shù)，按字典序從小到大輸出所有這樣的排列。例如輸入：3 2輸出：1 21 32 12 33 13 2constsize=20;varused:array 1.size of boolean;data:array 1.size of integer;n,m,i,j,k:integer;flag:boolean;beginreadl

13、n(n,m);fillchar(used,sizeof(used)，false);for i:=1 to m dobegin datai := i; usedi:= true;end;flag := true;while flag dobeginfor i:=1 to m-1 do write(datai, );writeln(datam);flag := ;for i := m downto 1 dobegin ;for j := datai+1 to n do if usedj = false thenbegin usedj := true; datai := ;flag := true;

14、break;end;if flag thenbeginfor k:= i+l to m dofor j:= 1 to do if usedj=false thenbegindatak := j;usedj := true;break;end; ;end;end;end;end.2(新殼棧)小z設(shè)計了一種新的數(shù)據(jù)結(jié)構(gòu)“新殼?！薄Ｊ紫?，它和傳統(tǒng)的棧一樣支持壓入、彈出操作。此外，其棧頂?shù)那癱個元素是它的殼，支持翻轉(zhuǎn)操作。其中，c2是一個固定的正整數(shù)，表示殼的厚度。小z還希望，每次操作，無論是壓入、彈出還是翻轉(zhuǎn)，都僅用與c無關(guān)的常數(shù)時間完成。聰明的你能幫助她編程實現(xiàn)“新殼?！眴?程序期望的實現(xiàn)效果如以

15、下兩表所示。其中，輸入的第一行是正整數(shù)c，之后每行輸入都是一條指令。另外，如遇彈出操作時棧為空，或翻轉(zhuǎn)操作時棧中元素不足c個，應(yīng)當輸出相應(yīng)的錯誤信息。指令涵義1空格e在棧頂壓入元素e2彈出（并輸出）棧頂元素3翻轉(zhuǎn)棧頂?shù)那癱個元素0退出表1：指令的涵義輸入輸出棧中的元素（左為棧底，右為棧頂）說明3輸入正整數(shù)c1 11壓入元素11 21 2壓入元素21 31 2 3壓入元素31 41 2 3 4壓入元素431 4 3 2翻轉(zhuǎn)棧頂?shù)那癱個元素1 51 4 3 2 5壓入元素531 4 5 2 3翻轉(zhuǎn)棧頂?shù)那癱個元素231 4 5 2彈出棧頂元素3221 4 5彈出棧頂元素 2251 4彈出棧頂元素

16、53錯誤信息1 4由于棧中元素不足c個，無法翻轉(zhuǎn)，故操作失敗，輸出錯誤信息241彈出棧頂元素421空彈出棧頂元素12錯誤信息空由于棧中元素不足c個，無法翻轉(zhuǎn)，故操作失敗，輸出錯誤信息0空退出表2：輸入輸出樣例const nsize = 100000;csize = 1000;var n,c,r,tail,head:longint;s: array1.nsize of longint;/數(shù)組s模擬一個棧，n為棧的元素個數(shù)q:array1.csize of longint;/數(shù)組q模擬一個循環(huán)隊列，tail為隊尾的下標，head為隊頭的下標direction,empty :boolean;func

17、tion previous(k :longint) :longint;beginif direction thenprevious := (k+c-2) mod c) + 1;else previous := (k mod c) + 1;end;function next(k:longint):longint;beginif direction then else next := (k+c-2) mod c)+1;end;procedure push;varelement:longint;beginread(element);if next(head) = tail thenbegininc(

18、n); ;tail := next(tail);end;if empty thenempty := falseelsehead := next(head); := element;end;procedure pop;beginif empty thenbeginwriteln(error: the stack is empty!);exit;end:writeln( );if tail = head then empty := trueelsebegin head := previous(head);if n 0 thenbegin tail := previous(tail); := sn;dec(n);end;end;end;procedure reverse;var temp:longint;beginif = tail