信息學奧賽初賽試題(第十六屆)

1、noip2010 初賽提高組pascal 1第十六屆全國青少年信息學奧林匹克聯(lián)賽初賽試題( 提高組 pascal語言二小時完成 ) 全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效一單項選擇題（共 10 題, 每題 1。5 分，共計15 分。每題有且僅有一個正確答案.) 1。與 16 進制數(shù) a1。 2 等值的 10 進制數(shù)是（ ) a.101.2 b。111。4 c.161。125 d.177。25 2。一個字節(jié)（byte ）由 ( ）個二進制組成。a。8 b。16 c。32 d.以上都有可能3。以下邏輯表達式的值恒為真的是（）。a.p（ pq ）( pq ）b。q ( pq)(pq)c

2、.pq （pq)（ pq ）d.pq （pq ）（ pq)4.linux下可執(zhí)行文件的默認擴展名是（ ) 。a. exe b。 com c。 dll d.以上都不是5. 如果在某個進制下等式77=41 成立 , 那么在該進制下等式12*12=( ）也成立。a. 100 b。 144 c. 164 d。 196 6. 提出“存儲程序的計算機工作原理的是（）。a。 克勞德 ?香農(nóng) b。戈登 ?摩爾c。查爾斯 ?巴比奇d。馮?諾依曼7. 前綴表達式“ + 3 * 2 + 512 ” 的值是 ( ) 。 a. 23 b。 25 c。 37 d。 65 8. 主存儲器的存取速度比中央處理器（cpu ）的

3、工作速度慢的多，從而使得后者的效率受到影響。而根據(jù)局部性原理，cpu所訪問的存儲單元通常都趨于一個較小的連續(xù)區(qū)域中。于是，為了提高系統(tǒng)整體的執(zhí)行效率，在cpu中引入了（ ) 。a.寄存器b。高速緩存c.閃存d 。外存9。完全二叉樹的順序存儲方案, 是指將完全二叉樹的結點從上到下、從左到右依次存放到一個順序結構的數(shù)組中。假定根結點存放在數(shù)組的1 號位置上，則第k 號結點的父結點如果存在的話, 應當存放在數(shù)組中的（ ) 號位置。a。 2k b。 2k+1 c。 k/2下取整d. (k+1 ）/2 10。以下競賽活動中歷史最悠久的是( ）。 a. noip b。noi c。 ioi d 。 apio

4、 二不定項選擇題(共 10 題，每題1。5 分，共計15 分。每題正確答案的個數(shù)不少于1.多選或少選均不得分） . 1. 元素 r1、r2、r3、r4、r5入棧的順序為r1、r2、r3、r4 、r5。如果第 1 個出棧的是r3，那么第 5 個出棧的可能是 ( ）.a.r1 b.r2 c。r4 d。r5 2. pascal語言， c語言和 c+ 語言都屬于 ( ) 。a。高級語言 b 。自然語言 c. 解釋性語言 d. 編譯性語言3。 原地排序是指在排序過程中（除了存儲待排序元素以外的）輔助空間的大小與數(shù)據(jù)規(guī)模無關的排序算法。 以下屬于原地排序的有（） .a. 冒泡排序b。 插入排序 c 。 基

5、數(shù)排序 d。選擇排序4. 在整數(shù)的補碼表示法中，以下說法正確的是（）。noip2010 初賽提高組pascal 2a只有負整數(shù)的編碼最高位為1 b在編碼的位數(shù)確定后, 所能表示的最小整數(shù)和最大整數(shù)的絕對值相同c整數(shù) 0 只有一個唯一的編碼d兩個用補碼表示的數(shù)相加時，若在最高位產(chǎn)生進位，則表示運算溢出5. 一顆二叉樹的前序遍歷序列是abcdefg, 后序遍歷序列是cbfegda，則根結點的左子樹的結點個數(shù)可能是（）. a 0 b. 2 c. 4 d 。 6 6。 在下列 html語句中，可以正確產(chǎn)生一個指向noi 官方網(wǎng)站的超鏈接的是( ）。a歡迎訪問noi 網(wǎng)站 /a b歡迎訪問noi 網(wǎng)站

6、/a c ah t t p ： / / w w w . n o i . c n da name”h t t p : / / w w w . n o i . c n”歡迎訪問noi 網(wǎng)站 7。 關于拓撲排序,下列說法正確的是( ）。a所有連通的有向圖都可以實現(xiàn)拓撲排序b對同一個圖而言, 拓撲排序的結構是唯一的c拓撲排序中入度為0 的結點總會排在入度大于0 的結點的前面d拓撲排序結果序列中的第一個結點一定是入度大于0 的點8。 一個平面的法線是指與該平面垂直的直線。過點（1,1 ，1）、 (0 ，3,0 ）、（ 2,0,0 ）的平面的法線是（）。a過點（ 1， 1，1）、（ 2,3,3 ）的直線b

7、 過點（ 1，1,1 ）、 (3,2,1）的直線c過點（ 0,3,0) 、（ -3,1 ，1) 的直線d過點 (2 ， 0，0）、（ 5,2,1 ）的直線9。雙向鏈表中有兩個指針域llink和 rlink， 分別指向該結點的前驅及后繼。設 p 指向鏈表中的一個結點,他的左右結點均為非空. 現(xiàn)要求刪除結點p, 則下列語句序列中正確的是( ). ap-rlink-llink=p rlink； p-llink rlink=p llink； delete p；bp- llink rlink=p-rlink; p-rlink llink = p-llink; delete p; cp-rlink lli

8、nk = p-llink； p- rlink llink -rlink = p-rlink； delete p；dpllinkrlink = p rlink； p llink-rlink link = p- llink； delete p；10。 今年 (2010 年) 發(fā)生的事件有（ ). a惠普實驗室研究員vinay deolalikar 自稱證明了pnpb英特爾公司收購計算機安全軟件公司邁克菲（mcafee) c蘋果公司發(fā)布iphone 4 手機d微軟公司發(fā)布windows 7 操作系統(tǒng)三、問題求解1lzw編碼是一種自適應詞典編碼。在編碼的過程中，開始時只有一部基礎構造元素的編碼詞典，如

9、果在編碼的過程中遇到一個新的詞條，則該詞條及一個新的編碼會被追加到詞典中，并用于后繼信息的編碼。舉例說明，考慮一個待編碼的信息串：“xyx yy yy xyx 。初始詞典只有3 個條目，第一個為x，編碼為 1；第二個為y，編碼為 2；第三個為空格，編碼為3；于是串“ xyx”的編碼為121( 其中 - 為編碼分隔符），加上后面的一個空格就是12-1 3。但由于有了一個空格，我們就知道前面的“xyx 是一個單詞，而由于該單詞沒有在詞典中，我們就可以自適應的把這個詞條添加到詞典里，編碼為4，然后按照新的詞典對后繼信息進行編碼，以此類推。于是，最后得到編碼：12 13-2-2 3534。noip20

10、10 初賽提高組pascal 3我們可以看到，信息被壓縮了。壓縮好的信息傳遞到接受方，接收方也只要根據(jù)基礎詞典就可以完成對該序列的完全恢復。解碼過程是編碼過程的逆操作. 現(xiàn)在已知初始詞典的3 個條目如上述, 接收端收到的編碼信息為22 123-1-1-3-43-1 2-1 3-5 36，則解碼后的信息串是”_ ”。2。無向圖g有 7 個頂點，若不存在由奇數(shù)條邊構成的簡單回路，則它至多有_條邊。3. 記 t 為一隊列，初始時為空，現(xiàn)有n 個總和不超過32 的正整數(shù)依次入列。如果無論這些數(shù)具體為何值，都能找到一種出隊的方式，使得存在某個時刻隊列t中的數(shù)之和恰好為9， 那么 n 的最小值是 _. 四

11、、閱讀程序寫結果1. const size = 10; var i ， j ， cnt, n， m ： integer; data ： array 1。.size of integer; begin readln(n, m）; for i := 1 to n do read （ datai); for i := 1 to n do begin cnt ： = 0; for j := 1 to n do if (data i data j ）or (dataj = datai ） and （j i） then inc(cnt）； if cnt = m then writeln（data i)；

12、end; end. 輸入5 2 96 -8 0 16 87 輸出： _ 2. const size = 100；var na ， nb ， i, j， k ： integer； a ， b ： array1。 .size of integer; begin readln(na）; for i ：= 1 to na do read （ai ） ; readln(nb）; for i := 1 to nb do read(bi）； i ：= 1 ； j := 1； while （i = na) and （j = nb ） do begin if ai = b j then begin write（

13、ai , ） ; inc(i）； end else begin write（bj， ）； inc （j ）； end ； end ； if i = na then for k := i to na do write(ak， ) ； if j = nb then for k := j to nb do write（bk, );end。輸入5 1 3 5 7 9 4 2 6 10 14 輸出： _ 3. const num = 5; var n: integer；function r（n : integer） ： integer; var i : integer; begin if n = num

14、 then begin r := n; exit； end ； for i ：=1 to num do if r（n-i ） 0 then begin noip2010 初賽提高組pascal 4 r:=i; exit； end ； r:= 1; end; begin readln（n）； writeln（r（ n) ）; end。輸入 16 輸出 :_ 4. const size=100 ；var n,m,x,y,i :integer; r: array1. size of integer; map : array1。 .size, 1.size of boolean ； found : b

15、oolean; function successful : boolean; var i ： integer；begin for i ：=1 to n do if not map r ir i mod n + 1 then begin successful ：= false; exit; end ； successful ：=true ；end; procedure swap(var a, b ： integer）; var t : integer；begin t := a; a ：= b; b := t；end；procedure perm（left, right ： integer） ;

16、var i ： integer；begin if found then exit; if left right then begin if successful then begin for i := 1 to n do writeln(ri， ）; found ：= true； end ； exit; end ； for i：= left to right do begin swap(rleft, ri ）; perm(left + 1， right); swap(r left, ri ） ; end ；end；begin readln（n, m ）； fillchar（map, sizeo

17、f(map)， false); for i ：= 1 to m do begin readln（x， y ）； mapxy ：= true; mapyx := true; end ； for i ：= 1 to n do ri := i; found ：= false; perm(1, n）； if not found then writeln（no soloution ) ；end. 輸入：9 12 1 2 2 3 3 4 4 5 5 6 6 1 1 7 2 7 3 8 4 8 5 9 6 9 輸出 :_ 五、完善程序1. （過河問題）在一個月黑風高的夜晚，有一群人在河的右岸, 想通過唯一的

18、一根獨木橋走到河的左岸。在伸手不見五指的黑夜里，過橋時必須借照燈光來照明，不幸的是, 他們只有一盞燈。另外, 獨木橋上最多能承受兩個人同時經(jīng)過，否則將會坍塌。每個人單獨過獨木橋都需要一定的時間,不同noip2010 初賽提高組pascal 5的人要的時間可能不同. 兩個人一起過獨木橋時，由于只有一盞燈, 所以需要的時間是較慢的那個人單獨過橋所花費的時間. 現(xiàn)在輸入n(2 ans then ans ：= timei; end; if _ then begin go ：= ans ； exit；end; ans := infinity；for i ：= 1 to n 1 do if posi =

19、right then for j := i+1 to n do if posj = right then begin pos i := left; posj ：= left； tmp := max(timei ，timej) + _; if tmp ans then ans ：= tmp; posi ：= right； posj ：= right; end; go := ans；end else if (stage = left_to_right) then begin ans := infinity； for i := 1 to n do if _ then begin posi := ri

20、ght； tmp ： = _; if tmp 1） and (heapi 1) and (heap i heap i div 2) do begin swap (i， i div 2)； i ： = i div 2；end; while i + i heap j then begin i: = j end else break; end；end; begin readln (n， m) ；for i ： = 1 to n do read （value i ） ；r ：= 0; for i ： = 1 to m do begin opt il := value i ; add （i) ; end; for i := m + 1 to n do begin opt i := remove （） add （i) ；end; noip2010 初賽提高組pascal 8 writeln （ heap 1 ) ；end. 第十六屆全國青少年信息學奧林匹克聯(lián)賽初賽答案一、單項選擇題( 共 10 題，每題1.5 分, 共計 15 分）1 2 3 4 5 6 7 8 9 10 c a