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

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

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

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

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

5、數(shù)排序 d。選擇排序4. 在整數(shù)的補(bǔ)碼表示法中，以下說法正確的是（）。noip2010 初賽提高組pascal 2a只有負(fù)整數(shù)的編碼最高位為1 b在編碼的位數(shù)確定后, 所能表示的最小整數(shù)和最大整數(shù)的絕對(duì)值相同c整數(shù) 0 只有一個(gè)唯一的編碼d兩個(gè)用補(bǔ)碼表示的數(shù)相加時(shí)，若在最高位產(chǎn)生進(jìn)位，則表示運(yùn)算溢出5. 一顆二叉樹的前序遍歷序列是abcdefg, 后序遍歷序列是cbfegda，則根結(jié)點(diǎn)的左子樹的結(jié)點(diǎn)個(gè)數(shù)可能是（）. a 0 b. 2 c. 4 d 。 6 6。 在下列 html語句中，可以正確產(chǎn)生一個(gè)指向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。 關(guān)于拓?fù)渑判?下列說法正確的是( ）。a所有連通的有向圖都可以實(shí)現(xiàn)拓?fù)渑判騜對(duì)同一個(gè)圖而言, 拓?fù)渑判虻慕Y(jié)構(gòu)是唯一的c拓?fù)渑判蛑腥攵葹? 的結(jié)點(diǎn)總會(huì)排在入度大于0 的結(jié)點(diǎn)的前面d拓?fù)渑判蚪Y(jié)果序列中的第一個(gè)結(jié)點(diǎn)一定是入度大于0 的點(diǎn)8。 一個(gè)平面的法線是指與該平面垂直的直線。過點(diǎn)（1,1 ，1）、 (0 ，3,0 ）、（ 2,0,0 ）的平面的法線是（）。a過點(diǎn)（ 1， 1，1）、（ 2,3,3 ）的直線b

7、 過點(diǎn)（ 1，1,1 ）、 (3,2,1）的直線c過點(diǎn)（ 0,3,0) 、（ -3,1 ，1) 的直線d過點(diǎn) (2 ， 0，0）、（ 5,2,1 ）的直線9。雙向鏈表中有兩個(gè)指針域llink和 rlink， 分別指向該結(jié)點(diǎn)的前驅(qū)及后繼。設(shè) p 指向鏈表中的一個(gè)結(jié)點(diǎn),他的左右結(jié)點(diǎn)均為非空. 現(xiàn)要求刪除結(jié)點(diǎ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惠普實(shí)驗(yàn)室研究員vinay deolalikar 自稱證明了pnpb英特爾公司收購計(jì)算機(jī)安全軟件公司邁克菲（mcafee) c蘋果公司發(fā)布iphone 4 手機(jī)d微軟公司發(fā)布windows 7 操作系統(tǒng)三、問題求解1lzw編碼是一種自適應(yīng)詞典編碼。在編碼的過程中，開始時(shí)只有一部基礎(chǔ)構(gòu)造元素的編碼詞典，如

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

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

11、、閱讀程序?qū)懡Y(jié)果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. （過河問題）在一個(gè)月黑風(fēng)高的夜晚，有一群人在河的右岸, 想通過唯一的

18、一根獨(dú)木橋走到河的左岸。在伸手不見五指的黑夜里，過橋時(shí)必須借照燈光來照明，不幸的是, 他們只有一盞燈。另外, 獨(dú)木橋上最多能承受兩個(gè)人同時(shí)經(jīng)過，否則將會(huì)坍塌。每個(gè)人單獨(dú)過獨(dú)木橋都需要一定的時(shí)間,不同noip2010 初賽提高組pascal 5的人要的時(shí)間可能不同. 兩個(gè)人一起過獨(dú)木橋時(shí)，由于只有一盞燈, 所以需要的時(shí)間是較慢的那個(gè)人單獨(dú)過橋所花費(fèi)的時(shí)間. 現(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. 第十六屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽答案一、單項(xiàng)選擇題( 共 10 題，每題1.5 分, 共計(jì) 15 分）1 2 3 4 5 6 7 8 9 10 c a