北京清北學(xué)堂 報名咨詢熱線： 400-699-3290 北京清北學(xué)堂 報名咨詢熱線： 400-699-3290 更多競賽真題免費下載 見北京清北學(xué)堂官方網(wǎng)站 學(xué)習(xí)資源：自主招生 學(xué)科競賽 高考等資源 NOIP2010（ Pascal 提高組） 一、單 項 選擇 題 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.PQ （ PQ ） （ PQ ） D.PQ （ PQ ） (PQ) 4.Linux 下可執(zhí)行文件的默認擴展名是 ( )。 A. exe B. com C. dll D.以上都不是 5.如果在某個進制下等式 7*7=41 成立，那么在該進制下等式 12*12=（ ）也成立。 A. 100 B. 144 C. 164 D. 196 6.提出 “ 存儲程序 ” 的計算機工作原理的是（ ）。 A. 克勞德 香農(nóng) B.戈登 摩爾 C.查爾斯 巴比奇 D.馮 諾依曼 7.前綴表達式 “+ 3 * 2 + 5 12 ” 的值是（ ）。 A. 23 B. 25 C. 37 D. 65 8.主存儲器的存取速度比中央處理器 (CPU)的工作速度慢的多，從而使得后者的效率受到影響。而根據(jù)局部性原理， CPU 所訪問的存儲單元通常都趨于一個較小的連續(xù)區(qū)域中。于是，為了提高系統(tǒng)整體的執(zhí)行效率，在 CPU中引入了 ( )。 A.寄存器 B.高速緩存 C.閃存 D.外存 9.完全二叉樹的順序存儲方案，是指將完全二叉樹的結(jié)點從上到下、從左到右依次存放到一個順序結(jié)構(gòu)的數(shù)組中。假定根結(jié)點存放在數(shù)組的 1 號位置上，則第 k號結(jié)點的父結(jié)點如果存在的話，應(yīng)當(dāng)存放在數(shù)組中的（ ）號位置。 A. 2k B. 2k+1 C. k/2下取整 D. (k+1)/2 10.以下競賽活動中歷史最悠久的是（ ）。 A. NOIP B.NOI C. IOI D. APIO 二、不定 項 選擇 題 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ī)模無關(guān)的排序算法。以下屬于原地排序的有 ( )。 A.冒泡排序 B.插入排序 C.基數(shù)排序 D.選擇排序 4. 在整數(shù)的補碼表示法中，以下說法正確的是（ ）。 A只有負整數(shù)的編碼最高位為 1 B在編碼的位數(shù)確定后，所能表示的最小整數(shù)和最大整數(shù)的絕對值相同 C整數(shù) 0 只有一個唯一的編碼 D兩個用補碼表示的數(shù)相加時， 若 在最高位產(chǎn)生進位，則表示運算溢出 5. 一顆二叉樹的前序遍歷序列是 ABCDEFG，后序遍歷序列是 CBFEGDA，則根結(jié)點的左子樹的結(jié)點個數(shù)可能是（ ）。 A 0 B. 2 C. 4 D. 6 6. 在下列 HTML 語句中，可以正確產(chǎn)生一個指向 NOI 官方網(wǎng)站的超鏈接的是（ ）。 北京清北學(xué)堂 報名咨詢熱線： 400-699-3290 北京清北學(xué)堂 報名咨詢熱線： 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)于拓撲排序，下列說法正確的是 ( )。 A所有連通的有向圖都可以實現(xiàn)拓撲排序 B對同一個圖而言，拓撲排序的結(jié)構(gòu)是唯一的 C拓撲排序中入度為 0 的結(jié)點總會排在入度大于 0 的結(jié)點的前面 D拓撲排序結(jié)果序列中的第一個結(jié)點一定是入度大于 0 的點 8. 一個平面的法線是指與該平面垂直的直線。過點 (1,1,1)、（ 0,3,0） 、 (2,0,0)的平面的法線是（ ）。 A過點（ 1， 1， 1）、（ 2， 3， 3）的直線 B過點（ 1， 1， 1）、（ 3， 2， 1）的直線 C過點（ 0， 3， 0）、（ -3， 1， 1）的直線 D過點（ 2， 0， 0）、（ 5， 2， 1）的直線 9.雙向鏈表中有兩個指針域 llink和 rlink，分別指向該結(jié)點的前驅(qū)及后繼。設(shè) p 指向鏈表中的一個結(jié)點，他的左右結(jié)點均為非空。現(xiàn)要求刪除結(jié)點 p，則下列語句序列中正確的是 ( )。 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惠普實驗室研究員 Vinay Deolalikar 自稱證明了 PNP B英特爾公司收購計算機安全軟件公司邁克菲 (McAfee) C蘋果公司發(fā)布 iPhone 4 手機 D微軟公司發(fā)布 Windows 7 操作系統(tǒng) 三、問題求解 1 LZW 編碼是一種自適應(yīng)詞典編碼。在編碼的過程中，開始時只有一部基礎(chǔ)構(gòu)造元素的編碼詞典，如果在編碼的過程中遇到一個新的詞條，則該詞條及一個新的編碼會被追加到詞典中，并用于后繼信息的編碼。 舉例說明，考慮一個待編碼的信息串 ： “xyx yy yy xyx” 。初始詞典只有 3 個條目，第一個為 x,編碼為1；第二個為 y，編碼為 2；第三個為空格，編碼為 3；于是串 “xyx” 的編碼為 1-2-1（其中 -為編碼分隔符），加上后面的一個空格就是 1-2-1-3。但由于有了一個空格，我們就知道前面的 “xyx” 是一個單詞，而由于該單詞沒有在詞典中，我們就可以自適應(yīng)的把這個詞條添加到詞典里，編碼為 4，然后按照新的詞典對后繼信息進行編碼，以此類推。于是，最后得到編碼： 1-2-1-3-2-2-3-5-3-4。 我們可以看到，信息被壓縮了。壓縮好的信 息傳遞到接受方，接收方也只要根據(jù)基礎(chǔ)詞典就可以完成對該序列的完全恢復(fù)。解碼過程是編碼過程的逆操作。現(xiàn)在已知初始詞典的 3 個條目如上述，接收端收到的編碼信息為 2-2-1-2-3-1-1-3-4-3-1-2-1-3-5-3-6，則解碼后的信息串是 ”_” 。 2.無向圖 G有 7 個頂點，若不存在由奇數(shù)條邊構(gòu)成的簡單回路，則它至多有 _條邊。 3.記 T 為一隊列，初始時為空，現(xiàn)有 n個總和不超過 32 的正整數(shù)依次入列。如果無論這些數(shù)具體為何值，都能找到一種出隊的方式，使得存在某個時刻隊列 T 中 的數(shù)之和恰好為 9，那么 n的最小值是 _。 四、閱讀程序?qū)懡Y(jié)果 1. const size = 10； 北京清北學(xué)堂 報名咨詢熱線： 400-699-3290 北京清北學(xué)堂 報名咨詢熱線： 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.(過河問題 ) 在一個月黑風(fēng)高的夜晚 ,有一群人在河的右岸 ,想通過唯一的一根獨木橋走到河的左岸 .在伸手不見五指的黑夜里 ,過橋時必須借照燈光來照明 ,不幸的是 ,他們只有一盞燈 .另外 ,獨木橋上最多能承受兩個人同時經(jīng)過 ,否則將會坍塌 .每個人單獨過獨木橋都需要一定的時間 ,不同的人要的時間可能不同 .兩個人一起過獨木橋時 ,由于只有一盞燈 ,所以需要的時間是較慢的那個人單獨過橋所花費的時間 .現(xiàn)在輸入 N(2=N b then max := a else max := b； end； 北京清北學(xué)堂 報名咨詢熱線： 400-699-3290 北京清北學(xué)堂 報名咨詢熱線： 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. - 一、單項選擇題（共 10 題，每題 1.5 分，共計 15 分） 1 2 3 4 5 6 7 8 9 10 C A A D B D C B C B 二、不定項選擇題（共 10 題，每題 1.5 分，共計 15 分，多選或少選均不得分） 1 2 3 4 5 6 7 8 9 10 ACD AD ABD AC B B D D BCD ABC 三、問題求解（共