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

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

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

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

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

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

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、兩兩互不相鄰的節點構成的集合。例如，圖1有5個不同的獨立集（1個雙點集合，3個單點集合、1個空集），圖2有14個不同的獨立集。那么圖3有 個不同的獨立集。三、閱讀程序寫結果。（共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 ai>ai+1 thenbegintemp := ai;ai := ai+1;ai+1 := temp;end;for i:=n downto 2 doif a

9、i<ai-1 thenbegintemp := ai;ai := ai-1;ai-1 := temp;end;sum := 0;for i:=2 to n-1 doinc(sum,ai);writeln(sum div (n-2);end.輸入：840 70 50 70 20 40 10 30輸出：_ 2var n,i,ans:integer;function gcd(a,b :integer) : integer;beginif a mod b=0 then gcd :=0;else gcd := gcd(b,a mod b);end;beginreadln(n);ans := 0;f

10、or i:=1 to n doif gcd(n,i)=ithen ans := ans + 1;writeln(ans);end.輸入：120輸出：_ 3 var data : array1.20 of integer;n,i,h,ans: integer;procedure merge;begindatah-1 := datah-1 + datah;dec(h);inc(ans);end;beginreadln(n);h := 1;datah := 1;ans := 0;for i:=2 to n dobegininc(h);datah := 1;while (h>1) and (da

11、tah=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 leftx>0 then check(leftx); s3 := s3 + slx; if rightx>0 then check(rightx);end;procedure calc(x,dep:inte

12、ger);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

13、) and (rightx=0) thenbegin leftx) := 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(lef

14、t,sizeof(left),0);fillchar(right,sizeof(right),0);fillcahr(father,sizeof(father),0);dfs(1,2);end.輸入：abcdefbcaedf輸出：_ 五、完善程序（第1題第2空3分，其余每空2.5分，共計28分） 1（排列數）輸入兩個正整數 ，在 中任取個數，按字典序從小到大輸出所有這樣的排列。例如輸入：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

15、,k:integer;flag:boolean;beginreadln(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 then

16、begin usedj := true; datai := ;flag := true;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設計了一種新的數據結構“新殼棧”。首先，它和傳統的棧一樣支持壓入、彈出操作。此外，其棧頂的前c個元素是它的殼，支持翻轉操作。其中，c>2是一個固定的正整數，表示殼的厚度。小z還希望，每次操作，無論是壓入、彈出還是

17、翻轉，都僅用與c無關的常數時間完成。聰明的你能幫助她編程實現“新殼棧”嗎?程序期望的實現效果如以下兩表所示。其中，輸入的第一行是正整數c，之后每行輸入都是一條指令。另外，如遇彈出操作時棧為空，或翻轉操作時棧中元素不足c個，應當輸出相應的錯誤信息。指令涵義1空格e在棧頂壓入元素e2彈出（并輸出）棧頂元素3翻轉棧頂的前c個元素0退出表1：指令的涵義輸入輸出棧中的元素（左為棧底，右為棧頂）說明3輸入正整數c1 11壓入元素11 21 2壓入元素21 31 2 3壓入元素31 41 2 3 4壓入元素431 4 3 2翻轉棧頂的前c個元素1 51 4 3 2 5壓入元素531 4 5 2 3翻轉棧頂的

18、前c個元素231 4 5 2彈出棧頂元素3221 4 5彈出棧頂元素 2251 4彈出棧頂元素 53錯誤信息1 4由于棧中元素不足c個，無法翻轉，故操作失敗，輸出錯誤信息241彈出棧頂元素421空彈出棧頂元素12錯誤信息空由于棧中元素不足c個，無法翻轉，故操作失敗，輸出錯誤信息0空退出表2：輸入輸出樣例const nsize = 100000;csize = 1000;var n,c,r,tail,head:longint;s: array1.nsize of longint;/數組s模擬一個棧，n為棧的元素個數q:array1.csize of longint;/數組q模擬一個循環隊列，ta

19、il為隊尾的下標，head為隊頭的下標direction,empty :boolean;function 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(n); ;tail := next(tail);end;if empty thenempty