(NOI)2006第十二屆全國青少年信息學奧林匹克聯(lián)賽初賽試題

北京清北學堂 報名咨詢熱線： 400-699-3290 北京清北學堂 報名咨詢熱線： 400-699-3290 更多競賽真題免費下載 見北京清北學堂官方網(wǎng)站 學習資源：自主招生 學科競賽 高考等資源 第十二屆全國青少年信息學奧林匹克聯(lián)賽初賽試題 （提高組 Pascal 語言 二小時完成 ） 全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效 一、 單項選擇題 （共 10 題，每題 1.5 分，共計 15 分。每題有且僅有一個正確答案 .）。 1. 在以下各項中。（）不是 CPU 的組成部分。 A. 控制器 B. 運算器 C. 寄存器 D. ALU E. RAM 2. BIOS （基本輸入輸出系統(tǒng)）是一組固化在計算機內(nèi)（）上一個 ROM 芯片上的程序。 A. 控制器 B. CPU C. 主板 D. 內(nèi) 存條 E. 硬盤 3. 在下面各世界頂級的獎項中，為計算機科學與技術領域作出杰出貢獻的科學家設立的獎項是（）。 A. 沃爾夫獎 B. 諾貝爾獎 C. 菲爾茲獎 D. 圖靈獎 E. 南丁格爾獎 4 在編程時（使用任一種高級語言，不一定是 Pascal ），如果需要從磁盤文件中輸入一個很大的二維 數(shù)組（例如 1000*1000 的 double 型數(shù)組），按行讀（即外層循環(huán)是關于行的）與按列讀（即外層循 環(huán)是關于列的）相比，在輸入效率上（）。 A. 沒有區(qū)別 B. 有一些區(qū)別，但機器處理速度很快，可忽略不計 C. 按行讀的方式要高一些 D. 按列讀的方式要高一些 E. 取決于數(shù)組的存儲方式。 5 在 Pascal 語言中，表達式 (21 xor 2)的值是（） A. 441 B. 42 C.23 D.24 E.25 6 在 Pascal 語言中，判斷 a 不等于 0 且 b 不等于 0 的正確的條件表達式是（） A. not a=0 or not b=0 B. not(a=0)and(b=0) C. not(a=0 and b=0) D. (a0)or(b0) E. (a0)and (b0) 7 某個車 站呈狹長形，寬度只能容下一臺車，并且只有一個出入口。已知某時刻該車站狀態(tài)為空，從 這一時刻開始的出入記錄為： “進，出，進，進，進，出，出，進，進，進，出 ,出 ”。假設車輛入站的 順序為 1 ， 2 ， 3 ， ，則車輛出站的順序為（）。 A. 1, 2, 3, 4, 5 B. 1, 2, 4, 5, 7 C. 1, 4, 3, 7, 6 D. 1, 4, 3, 7, 2 E. 1, 4, 3, 7, 5 8 高度為 n 的均衡的二叉樹是指：如果去掉葉結點及相應的樹枝，它應該是高度為 n-1 的滿二叉樹。 1在 這里，樹高等于葉結點的最大深度，根結點的深度為 0 ，如果某個均衡的二叉樹共有2381 個結點， 則該樹的樹高為（）。 北京清北學堂 報名咨詢熱線： 400-699-3290 北京清北學堂 報名咨詢熱線： 400-699-3290 A. 10 B. 11 C. 12 D. 13 E. 2 10 1 9. 與十進制數(shù) 1770.625 對應的八進制數(shù)是（）。 A. 3352.5 B. 3350.5 C. 3352.1161 D. 3350.1151 E. 前 4 個答案都不對 10 將 5 個數(shù)的序列排序，不論原先的順序如何，最少都可以通過（）次比較，完成從小到大的排序。 A. 6 B. 7 C. 8 D. 9 E. 10 二、 不定項選擇題 （共 10 題，每題 1.5 分，共計 15 分。每題正確答案的個數(shù)大于或等于 1 。多選 或少選均不得分）。 11. 設 A=B=D=true ， C=E=false ，以下邏輯運算表達式值為真的有（）。 A. ( A B) (C D) E B. (A B) C) D E) C. A (B C D E) D. (A (B C) D E 12. (2010)16 + (32)8 的結果是（）。 A. (8234)10 B. (202A)16 C. (100000000110)2 D. (2042)16 13. 設棧 S 的初始狀態(tài)為空，元素 a, b, c, d, e 依次入棧，以下出棧序列不可能出現(xiàn)的有（）。 A. a, b, c, e, d B. b, c, a, e, d C. a, e, c, b, d D. d, c, e, b, a 14. 已知 6 個結點的二叉樹的先根遍歷是 1 2 3 4 5 6 （數(shù)字為結點的編號，以下同），后根遍歷是 3 2 5 6 4 1 ，則該二叉樹的可能的中根遍歷是（） A. 3 2 1 4 6 5 B. 3 2 1 5 4 6 C. 2 3 1 5 4 6 D. 2 3 1 4 6 5 15. 在下列各數(shù)據(jù)庫系統(tǒng)軟件中，以關系型數(shù)據(jù)庫為主體結構的是（）。 A. ACCESS B. SQL Server C. Oracle D. Foxpro 16.在下列各軟件中，屬于 NOIP 競賽（復賽）推薦使用的語言環(huán)境有（）。 A. gcc/g+ B. Turbo Pascal C. Turbo C D. free pascal 217. 以下斷電之后將不能保存數(shù)據(jù)的有（）。 A. 硬盤 B. ROM C. 顯存 D. RAM 18. 在下列關于計算機語言的說法中，正確的有（）。 A. Pascal 和 C 都是編譯執(zhí)行的高級語言 B. 高級語言程序比匯編語言程序更容易從一種計算機移植到另一種計算機上 C. C+是歷史上的第一個支持面向對象的計算機語言 D. 高級語言比匯編語言更高級，是因為它的程序的運行效率更高 19. 在下列關于計算機算法的說法中，正確的有（）。 A. 一個正確的算法至少要有一個輸入 B. 算法的改進，在很大程度上推動了計算機科學與技術的進步 C. 判斷一個算法的好壞，主要依據(jù)它在某臺 計算機上具體實現(xiàn)時的運行時間 D. 目前仍然存在許多涉及到國計民生的重大課題，還沒有找到能夠在計算機上實施的有效算法 20. 在下列關于青少年信息學競賽的說法中，你贊成的是（）（本題不回答為 0 分，答題一北京清北學堂 報名咨詢熱線： 400-699-3290 北京清北學堂 報名咨詢熱線： 400-699-3290 律滿分）。 A. 舉行信息學競賽的目的，是為了帶動廣大青少年學科學、愛科學，為造就一大批優(yōu)秀的計算機科學 與技術人才奠定良好的基礎 B. 如果競賽優(yōu)勝者不能直接保送上大學，我今后就不再參與這項活動了 C. 準備競賽無非要靠題海戰(zhàn)術，為了取得好成績，就得拼時間、拼體力 D. 為了取得好成績，不光要看智力因素， 還要看非智力因素。優(yōu)秀選手應該有堅韌不拔的意志，有 嚴謹求實的作風，既要努力奮進，又要勝不驕敗不餒 三問題求解（共 2 題，每題 5 分，共計 10 分） 1 將 2006 個人分成若干不相交的子集，每個子集至少有 3 個人，并且： （ 1 ）在每個子集中，沒有人認識該子集的所有人。 （ 2 ）同一子集的任何 3 個人中，至少有 2 個人互不認識。 （ 3 ）對同一子集中任何 2 個不相識的人，在該子集中恰好只有 1 個人認識這兩個人。 則滿足上述條件的子集最多能有 _個？ 2 將邊長為 n 的正三角形 每邊 n 等分，過每個分點分別做另外兩邊的平行線，得到若干個正三角形， 我們稱為小三角形。正三角形的一條通路是一條連續(xù)的折線，起點是最上面的一個小三角形，終點是最 下面一行位于中間的小三角形。在通路中，只允許由一個小三角形走到另一個與其有公共邊的且位于同 一行或下一行的小三角形，并且每個小三角形不能經(jīng)過兩次或兩次以上（圖中是 n=5 時一條通路的例 子）。設 n=10 ，則該正三角形的不同的通路的總數(shù)為 _。 3四閱讀程序寫結果（共 4 題，每題 8 分，共計 32 分） 1. Program ex401； var u,v:array0.3 of integer； i,x,y:integer； begin x:=10； y:=10； for i:=0 to 3 do read(ui)； v0:=(u0+u1+u2+u3) div 7； v1:=u0 div (u1-u2) div u3)； v2:=u0*u1 div u2*u3； v3:=v0*v1； x:=(v0+v1+2)-u(v3+3) mod 4； if (x10) then y:=y+(v2*100-v3) div (uu0 mod 3*5) else y:=y+20+(v2*100-v3) div (uv0 mod 3*5)； writeln (x,y)； end. *注：本例中，給定的輸入數(shù)據(jù)可以避免分母為 0 或下標越界。 ) 北京清北學堂 報名咨詢熱線： 400-699-3290 北京清北學堂 報名咨詢熱線： 400-699-3290 輸入： 9 3 9 4 輸出： _ 2.Program ex402； const m:array0.4 of integer=(2,3,5,7,13)； var i,j:integer； t: longint； begin 4for i:=0 to 4 do begin t:=1； for j:=1 to mi-1 do t:=t*2； t:=(t*2-1)*t； write (t, )； end； writeln； end. 輸出 :_ 3. Program ex403； Const NN=7； Type Arr1=array0.30 of char； var s:arr1； k,p:integer； function fun1(s:arr1； a:char；n:integer):integer； var j:integer； begin j:=n； while (a0) do dec(j)； fun1:=j； end； Function fun2(s:arr1； a:char； n:integer):integer； var j:integer； begin j:=1； while (asj)and(j0) then begin n2:=n mod 10； write(n2:2)； if(m1) then digit(n div 10,m div 10)； n2:=n mod 10； write(n2:2)； end； end； begin writeln(Input a number:)； readln(x)； x2:=1； while(x2x) do x2:=x2*10； x2:=x2 div 10； digit(x,x2)； writeln； end. 輸入： 9734526 輸出： _ 五完善程序 (前 5 空，每空 2 分，后 6 空，每空 3 分，共 28 分 ) 1 （選排列）下面程序的功能是利用遞歸方法生成從 1 到 n(n10)的 n 個數(shù)中取 k(1=k=n)個數(shù)的 全部可能的排列（不一定按升序輸出）。例如，當 n=3 ， k=2 時，應該輸出（每行輸出 5 個排列）： 12 13 21 23 32 31 程序： 6Program ex501； Var i,n,k:integer； a:array1.10 of integer； count:longint； Procedure perm2(j:integer)； var i,p,t:integer； begin if then begin 北京清北學堂 報名咨詢熱線： 400-699-3290 北京清北學堂 報名咨詢熱線： 400-699-3290 for i:=k to n do begin inc(count)； t:=ak； ak:=ai； ai:=t； for do write(ap:1)； write( )； t:=ak；ak:=ai；ai:=t； if (count mod 5=0) then writeln； end； exit； end； for i:=j to n do begin t:=aj；aj:=ai；ai:=t； ； t:=aj； ； end end； begin writeln(Entry n,k (k4-2-1-5-3 。遺傳算法的核心是通過兩個個體的交叉操作，產(chǎn)生兩 個新的個體。下面的程序給出了最簡單的一種交叉算法。具體過程如下： (1)選定中間一段作為互換段，該段的起止下標為 t1 ， t2 ，隨機生成 t1 ， t2 后，互換兩段。 (2)互換后，在每個新的排列中可能有重復數(shù)字，因而不能作為新個體的編碼，一般再做兩步處理： (2.1) 將兩個互換段中，共同的數(shù)字標記為 0 ，表示已處理完。 (2.2) 將兩個互換段中其余數(shù)字標記為 1 ，按順序將互換段外重復的數(shù)字進行替換。 例如： n=12 ，兩個個體分別 是： a1: 1 3 5 4 * 2 6 7 9 * 10 12 8 11 a2: 3 2 1 12 * 6 7 10 11 * 8 5 4 9 t1=5 ， t2=8 。上述每一行中，兩個星號間的部分為互換段。假定數(shù)組的下標從 1 開始，互換后有： 北京清北學堂 報名咨詢熱線： 400-699-3290 北京清北學堂 報名咨詢熱線： 400-699-3290 a1: 1 3 5 4 * 6 7 10 11 * 10 12 8 11 a2: 3 2 1 12 * 2 6 7 9 * 8 5 4 9 然后，將數(shù)字 6,7 對應的項標記為 0 ，星號內(nèi)數(shù)字 2,9,10,11 對應的項標記為 1 ，并且按順序對 應關系為 : 102 ， 119 。于是，將 a19=10 替換為 a19=2 ，將 a22=2 替換為a22=10 ， 類似再做第 2 組替換。這樣處理后，就得到了兩個新個體： a1: 1 3 5 4 6 7 10 11 2 12 8 9 a2: 3 10 1 12 2 6 7 9 8 5 4 11 （ 3 ）輸出兩個新個體的編碼。 程序： program ex502； type arr1=array1.20 of integer； var a1,a2,kz1,kz2:arr1； n,k,t1,t2:integer； function rand1(k:integer):integer； var t:integer； begin t:=0； while (tk) do t:=random(k+1)-2； rand1:=t； end； procedure read1(var a:arr1；m:integer)； 讀入數(shù)組元素 a1至 am， a0=0 ，略。 procedure wrt1(var a:arr1；m:integer)； 輸出數(shù)組元素 a1至 am，略。 8procedure cross(var a1,a2:arr1；t1, t2,n:integer)； var i,j,t,kj:integer； begin for i:=t1 to t2 do begin t:=a1i； ； end； for i:=1 t