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

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

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

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

4、生學(xué)的問(wèn)世開(kāi)辟了獨(dú)特的科學(xué)技術(shù)發(fā)展道路。人們研究生物體的結(jié)構(gòu)、功能和工作原理，并將這些原理移植于新興的工程技術(shù)中。以下關(guān)于仿生學(xué)的敘述，錯(cuò)誤的是（ ）a由研究蝙蝠，發(fā)明雷達(dá) b由研究蜘蛛網(wǎng)，發(fā)明因特網(wǎng) c由研究海豚，發(fā)明聲納 d由研究電魚(yú)，發(fā)明伏特電池二、不定項(xiàng)選擇題（共10題，每題1.5分，共計(jì)15分；每題有一個(gè)或多個(gè)正確選項(xiàng)，多選或少選均不得分）1如果對(duì)于所有規(guī)模為n的輸入，一個(gè)算法均恰好進(jìn)行（ ）次運(yùn)算，我們可以說(shuō)該算法的時(shí)間復(fù)雜度為 。a b c d 2 從頂點(diǎn) 出發(fā)，對(duì)有向圖（ ）進(jìn)行廣度優(yōu)先搜索（bfs）時(shí)，一種可能的遍歷順序是 。3如果一個(gè)棧初始時(shí)為空，且當(dāng)前棧中的元素從棧頂?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在計(jì)算機(jī)顯示器所使用的rgb顏色模型中，（ ）屬于三原色之一。a黃色 b藍(lán)色 c10 d155一棵二叉樹(shù)一共有19個(gè)節(jié)點(diǎn)，其葉子節(jié)點(diǎn)可能有（ ）個(gè)。 a1 b9 c紫色 d綠色6已知帶權(quán)有向圖g上的所有權(quán)值均為正整數(shù)，記頂點(diǎn)u到頂點(diǎn)v的最短路徑的權(quán)值為 。若 是圖g上的頂點(diǎn)，且它們之間兩兩都存路徑可達(dá)，則以下說(shuō)法正確的有（ ）。a 到的最短路徑可能包含一個(gè)環(huán)b c d如果是 到 的一條最短路徑，那么是 到的一條最短路徑

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

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

8、兩兩互不相鄰的節(jié)點(diǎn)構(gòu)成的集合。例如，圖1有5個(gè)不同的獨(dú)立集（1個(gè)雙點(diǎn)集合，3個(gè)單點(diǎn)集合、1個(gè)空集），圖2有14個(gè)不同的獨(dú)立集。那么圖3有 個(gè)不同的獨(dú)立集。三、閱讀程序?qū)懡Y(jié)果。（共4題，每題8分，共計(jì)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分，共計(jì)28分） 1（排列數(shù)）輸入兩個(gè)正整數(shù) ，在 中任取個(gè)數(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è)計(jì)了一種新的數(shù)據(jù)結(jié)構(gòu)“新殼?！?。首先，它和傳統(tǒng)的棧一樣支持壓入、彈出操作。此外，其棧頂?shù)那癱個(gè)元素是它的殼，支持翻轉(zhuǎn)操作。其中，c2是一個(gè)固定的正整數(shù)，表示殼的厚度。小z還希望，每次操作，無(wú)論是壓入、彈出還是翻轉(zhuǎn)，都僅用與c無(wú)關(guān)的常數(shù)時(shí)間完成。聰明的你能幫助她編程實(shí)現(xiàn)“新殼?！眴?程序期望的實(shí)現(xiàn)效果如以

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

16、53錯(cuò)誤信息1 4由于棧中元素不足c個(gè)，無(wú)法翻轉(zhuǎn)，故操作失敗，輸出錯(cuò)誤信息241彈出棧頂元素421空彈出棧頂元素12錯(cuò)誤信息空由于棧中元素不足c個(gè)，無(wú)法翻轉(zhuǎn)，故操作失敗，輸出錯(cuò)誤信息0空退出表2：輸入輸出樣例const nsize = 100000;csize = 1000;var n,c,r,tail,head:longint;s: array1.nsize of longint;/數(shù)組s模擬一個(gè)棧，n為棧的元素個(gè)數(shù)q:array1.csize of longint;/數(shù)組q模擬一個(gè)循環(huán)隊(duì)列，tail為隊(duì)尾的下標(biāo)，head為隊(duì)頭的下標(biāo)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