(NOI)2010第十六屆全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽初賽試題

北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 更多競(jìng)賽真題免費(fèi)下載 見北京清北學(xué)堂官方網(wǎng)站 學(xué)習(xí)資源：自主招生 學(xué)科競(jìng)賽 高考等資源 NOIP2010（ Pascal 提高組） 一、單 項(xiàng) 選擇 題 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.PQ （ PQ ） （ PQ ） D.PQ （ PQ ） (PQ) 4.Linux 下可執(zhí)行文件的默認(rèn)擴(kuò)展名是 ( )。 A. exe B. com C. dll D.以上都不是 5.如果在某個(gè)進(jìn)制下等式 7*7=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 + 5 12 ” 的值是（ ）。 A. 23 B. 25 C. 37 D. 65 8.主存儲(chǔ)器的存取速度比中央處理器 (CPU)的工作速度慢的多，從而使得后者的效率受到影響。而根據(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.以下競(jìng)賽活動(dòng)中歷史最悠久的是（ ）。 A. NOIP B.NOI C. IOI D. APIO 二、不定 項(xiàng) 選擇 題 1.元素 R1、 R2、 R3、 R4、 R5 入棧的順序?yàn)?R1、 R2、 R3、 R4、 R5。如果第 1個(gè)出棧的是 R3，那么第 5個(gè)出棧的可能是 ( )。 A.R1 B.R2 C.R4 D.R5 2. Pascal語(yǔ)言， C 語(yǔ)言和 C+語(yǔ)言都屬于 ( )。 A.高級(jí)語(yǔ)言 B.自然語(yǔ)言 C.解釋性語(yǔ)言 D.編譯 性語(yǔ)言 3. 原地排序是指在排序過程中 (除了存儲(chǔ)待排序元素以外的 )輔助空間的大小與數(shù)據(jù)規(guī)模無(wú)關(guān)的排序算法。以下屬于原地排序的有 ( )。 A.冒泡排序 B.插入排序 C.基數(shù)排序 D.選擇排序 4. 在整數(shù)的補(bǔ)碼表示法中，以下說法正確的是（ ）。 A只有負(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 語(yǔ)句中，可以正確產(chǎn)生一個(gè)指向 NOI 官方網(wǎng)站的超鏈接的是（ ）。 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 A 歡迎訪問 NOI 網(wǎng)站 B 歡迎訪問 NOI網(wǎng)站 C h t t p : / / w w w . n o i . c n D 歡迎訪問 NOI 網(wǎng)站 7. 關(guān)于拓?fù)渑判颍铝姓f法正確的是 ( )。 A所有連通的有向圖都可以實(shí)現(xiàn)拓?fù)渑判?B對(duì)同一個(gè)圖而言，拓?fù)渑判虻慕Y(jié)構(gòu)是唯一的 C拓?fù)渑判蛑腥攵葹?0 的結(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過點(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)均為非空?，F(xiàn)要求刪除結(jié)點(diǎn) p，則下列語(yǔ)句序列中正確的是 ( )。 A p-rlink-llink=p-rlink； p-llink-rlink=p-llink； delete p； B p-llink-rlink=p-rlink； p-rlink-llink = p-llink； delete p； C p-rlink-llink = p-llink； p-rlink-llink -rlink = p-rlink； delete p； D p-llink-rlink = p-rlink； p-llink-rlink-link = p-llink； delete p； 10. 今年 (2010 年 )發(fā)生的事件有（ ）。 A惠普實(shí)驗(yàn)室研究員 Vinay Deolalikar 自稱證明了 PNP B英特爾公司收購(gòu)計(jì)算機(jī)安全軟件公司邁克菲 (McAfee) C蘋果公司發(fā)布 iPhone 4 手機(jī) D微軟公司發(fā)布 Windows 7 操作系統(tǒng) 三、問題求解 1 LZW 編碼是一種自適應(yīng)詞典編碼。在編碼的過程中，開始時(shí)只有一部基礎(chǔ)構(gòu)造元素的編碼詞典，如果在編碼的過程中遇到一個(gè)新的詞條，則該詞條及一個(gè)新的編碼會(huì)被追加到詞典中，并用于后繼信息的編碼。 舉例說明，考慮一個(gè)待編碼的信息串 ： “xyx yy yy xyx” 。初始詞典只有 3 個(gè)條目，第一個(gè)為 x,編碼為1；第二個(gè)為 y，編碼為 2；第三個(gè)為空格，編碼為 3；于是串 “xyx” 的編碼為 1-2-1（其中 -為編碼分隔符），加上后面的一個(gè)空格就是 1-2-1-3。但由于有了一個(gè)空格，我們就知道前面的 “xyx” 是一個(gè)單詞，而由于該單詞沒有在詞典中，我們就可以自適應(yīng)的把這個(gè)詞條添加到詞典里，編碼為 4，然后按照新的詞典對(duì)后繼信息進(jìn)行編碼，以此類推。于是，最后得到編碼： 1-2-1-3-2-2-3-5-3-4。 我們可以看到，信息被壓縮了。壓縮好的信 息傳遞到接受方，接收方也只要根據(jù)基礎(chǔ)詞典就可以完成對(duì)該序列的完全恢復(fù)。解碼過程是編碼過程的逆操作?，F(xiàn)在已知初始詞典的 3 個(gè)條目如上述，接收端收到的編碼信息為 2-2-1-2-3-1-1-3-4-3-1-2-1-3-5-3-6，則解碼后的信息串是 ”_” 。 2.無(wú)向圖 G有 7 個(gè)頂點(diǎn)，若不存在由奇數(shù)條邊構(gòu)成的簡(jiǎn)單回路，則它至多有 _條邊。 3.記 T 為一隊(duì)列，初始時(shí)為空，現(xiàn)有 n個(gè)總和不超過 32 的正整數(shù)依次入列。如果無(wú)論這些數(shù)具體為何值，都能找到一種出隊(duì)的方式，使得存在某個(gè)時(shí)刻隊(duì)列 T 中 的數(shù)之和恰好為 9，那么 n的最小值是 _。 四、閱讀程序?qū)懡Y(jié)果 1. const size = 10； 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 var i, j, cnt, n, m : integer； data : array1.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 (datai dataj) or (dataj = datai) and (j i) then inc(cnt)； if cnt = m then writeln(datai)； 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 = bj then begin write(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 then begin r := n； exit； end； for i :=1 to num do if r(n-i) 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(rleft, ri)； end； end； begin readln(n, m)； fillchar(map, sizeof(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)高的夜晚 ,有一群人在河的右岸 ,想通過唯一的一根獨(dú)木橋走到河的左岸 .在伸手不見五指的黑夜里 ,過橋時(shí)必須借照燈光來照明 ,不幸的是 ,他們只有一盞燈 .另外 ,獨(dú)木橋上最多能承受兩個(gè)人同時(shí)經(jīng)過 ,否則將會(huì)坍塌 .每個(gè)人單獨(dú)過獨(dú)木橋都需要一定的時(shí)間 ,不同的人要的時(shí)間可能不同 .兩個(gè)人一起過獨(dú)木橋時(shí) ,由于只有一盞燈 ,所以需要的時(shí)間是較慢的那個(gè)人單獨(dú)過橋所花費(fèi)的時(shí)間 .現(xiàn)在輸入 N(2=N b then max := a else max := b； end； 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 function go(stage : boolean) : integer； var i, j, num, tmp, ans : integer； begin if (stage = RIGHT_TO_LEFT) then begin num := 0； ans :=0； for i := 1 to n do if posi = Rignt then begin inc(num)； if timei ans then ans := timei； end； if _ then begin go := ans； exit； end； ans := INFINITY； for i := 1 to n 1 do if posi = RIGHT then for j := i+1 to n do if posj = RIGHT then begin posi := 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 := RIGHT； tmp := _； if tmp ans then ans := tmp； _； end； go := ans； end else go := 0； end； begin readln(n)； for i := 1 to n do begin read(timei)； posi := RIGHT； end； writeln(go(RIGHT_TO_LEFT)； end. - 一、單項(xiàng)選擇題（共 10 題，每題 1.5 分，共計(jì) 15 分） 1 2 3 4 5 6 7 8 9 10 C A A D B D C B C B 二、不定項(xiàng)選擇題（共 10 題，每題 1.5 分，共計(jì) 15 分，多選或少選均不得分） 1 2 3 4 5 6 7 8 9 10 ACD AD ABD AC B B D D BCD ABC 三、問題求解（共