(NOI)2002第八屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽試題

北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 更多競賽真題免費(fèi)下載 見北京清北學(xué)堂官方網(wǎng)站 學(xué)習(xí)資源：自主招生 學(xué)科競賽 高考等資源 第八屆全國青少年信息學(xué)奧林匹克聯(lián)賽 初賽試題 （提高組 PASCAL 語言 二小時(shí)完成） 審定：全國青少年信息學(xué)奧林匹克競賽科學(xué)委員會(huì) 主管：中國科協(xié)、教育部 主辦：中國計(jì)算機(jī)學(xué)會(huì) 承辦：江蘇省科協(xié)青少年科技中心 全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效 一 選擇一個(gè)正確答案代碼（ A/B/C/D），填入每題的括號內(nèi)（每題 1.5 分，多選無分，共 30 分） 1 微型計(jì)算機(jī)的問世是由于（ ）的出現(xiàn)。 A）中小規(guī)模集成電路 B）晶體管電路 C）（超）大規(guī)模集成電路 D）電子管電路 2 中央處 理器（ CPU）能訪問的最大存儲(chǔ)器容量取決于（ ）。 A）地址總線 B）數(shù)據(jù)總線 C）控制總線 D）實(shí)際內(nèi)存容量 3 十進(jìn)制書 11/128 可用二進(jìn)制數(shù)碼序列表示為：（ ）。 A） 1011/1000000 B） 1011/100000000 C） 0.001011 D） 0.0001011 4 算式（ 2047） 10 （ 3FF） 16 （ 2000） 8 的結(jié)果是（ ）。 A）（ 2048） 10 B）（ 2049） 10 C）（ 3746） 8 D）（ 1AF7） 16 5 已知 x =（ 0.1011010） 2 ，則 x / 2 補(bǔ) =（ ） 2 。 A） 0.1011101 B） 11110110 C） 0.0101101 D） 0.100110 6 IPv4 地址是由（ ）位二進(jìn)制數(shù)碼表示的。 A） 16 B） 32 C） 24 D） 8 7 計(jì)算機(jī)病毒傳染的必要條件是：（ ）。 A）在內(nèi)存中運(yùn)行病毒程序 B）對磁盤進(jìn)行讀寫操作 C）在內(nèi)存中運(yùn)行含有病毒的可執(zhí)行的程序 D）復(fù)制文件 8 在磁盤上建立子目錄有許多優(yōu)點(diǎn)，下列描述中不屬于建立 子目錄優(yōu)點(diǎn)的是（ ）。 A）便于文件管理 B）解決根目錄中目錄項(xiàng)個(gè)數(shù)有限問題 C）加快文件查找速度 D）節(jié)省磁盤使用空間 9 在使用 E-mail 前，需要對 Outlook 進(jìn)行設(shè)置，其中 ISP 接收電子郵件的服務(wù)器稱為（ ）服務(wù)器。 A） POP3 B） SMTP C） DNS D） FTP 10 多媒體計(jì)算機(jī)是指（ ）計(jì)算機(jī)。 A）專供家庭使用的 B）裝有 CD-ROM 的 C）連接在網(wǎng)絡(luò)上的高級 D）具有處理文字、圖形、聲音、影像等信息的 11 微型計(jì)算機(jī)中，（ ） 的存取速度最快。 A）高速緩存 B）外存儲(chǔ)器 C）寄存器 D）內(nèi)存儲(chǔ)器 12 資源管理器的目錄前圖標(biāo)中增加“ +”號，這個(gè)符號的意思是（ ）。 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 A）該目錄下的子目錄已經(jīng)展開 B）該目錄下還有子目錄未展開 C）該目錄下沒有子目錄 D）該目錄為空目錄 13 在 WORD 文檔編輯中實(shí)現(xiàn)圖文混合排版時(shí)，關(guān)于文本框的下列敘述正確的是（ ）。 A）文本框中的圖形沒有辦法和文檔中輸入文字疊加在一起，只能在文檔的不同位置 B）文本框中的圖形不可以襯于文檔中輸入的文字的下方 C）通過文本框，可以實(shí)現(xiàn)圖形 和文檔中輸入的文字的疊加，也可以實(shí)現(xiàn)文字環(huán)繞 D）將圖形放入文本框后，文檔中輸入的文字不能環(huán)繞圖形 14 一個(gè)向量第一個(gè)元素的存儲(chǔ)地址是 100，每個(gè)元素的長度是 2，則地 5 個(gè)元素的地址是（ ）。 A） 110 B） 108 C） 100 D） 109 15 已知 A = 35H， A / 05H / A / 30H 的結(jié)果是：（ ）。 A） 30H B） 05H C） 35H D） 53H 16 設(shè)有一個(gè)含有 13 個(gè)元素的 Hash 表（ 0 12）， Hash 函數(shù)是： H（ key） = key % 13，其中 %是 求余數(shù)運(yùn)算。用線性探查法解決沖突，則對于序列（ 2、 8、 31、 20、 19、 18、 53、27）， 18 應(yīng)放在第（ ）號格中。 A） 5 B） 9 C） 4 D） 0 17 按照二叉數(shù)的定義，具有 3 個(gè)結(jié)點(diǎn)的二叉樹有（ ）種。 A） 3 B） 4 C） 5 D） 6 18 在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的（ ）倍。 A） 1/2 B） 1 C） 2 D） 4 19 要使 1 8 號格字的訪問順序?yàn)椋?8、 2、 6、 5、 7、 3、 1、 4，則下圖中的空格中應(yīng)填入（ ）。 1 2 3 4 5 6 7 8 4 6 1 -1 7 3 2 A） 6 B） 0 C） 5 D） 3 20 設(shè)棧 S 和隊(duì)列 Q 的初始狀態(tài)為空，元素 e 1 ， e 2 ， e 3 ， e 4 ， e 5 ， e 6 依次通過棧 S，一個(gè)元素出棧后即進(jìn)入隊(duì)列 Q，若出隊(duì)的順序?yàn)?e 2 ， e 4 ， e 3 ， e 6 ， e 5 ， e 1 ，則棧S 的容量至少應(yīng)該為（ ）。 A） 2 B） 3 C） 4 D） 5 二問題求解：（ 6 + 8 = 14 分） 1 在書架上放有編號為 1 ， 2 ， n 的 n 本書。現(xiàn)將 n 本書全部取下 然后再放回去，當(dāng)放回去時(shí)要求每本書都不能放在原來的位置上。例如： n = 3 時(shí)： 原來位置為： 1 2 3 放回去時(shí)只能為： 3 1 2 或 2 3 1 這兩種 問題：求當(dāng) n = 5 時(shí)滿足以上條件的放法共有多少種？（不用列出每種放法） 2 設(shè)有一棵 k 叉樹，其中只有度為 0 和 k 兩種結(jié)點(diǎn)，設(shè) n 0 ， n k ，分別表示度為 0 和度為 k 的結(jié)點(diǎn)個(gè)數(shù)，試求出 n 0 和 n k 之間的關(guān)系（ n 0 = 數(shù)學(xué)表達(dá)式，數(shù)學(xué)表達(dá)式僅含 n k 、k 和數(shù)字）。 三閱讀程序，寫出正確的程序運(yùn)行結(jié)果：（ 8 + 9 + 9 = 26 分） 1 program Gxp1； var i , n , jr , jw , jb : integer ； ch1 : char ； ch : array1.20 of char ； begin 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 readln(n)； for i:=1 to n do read(chi)； jr:=1； jw:=n； jb:=n； while (jr=jw) do begin if (chjw=R) then begin ch1:=chjr； chjr:=chjw； chjw:=ch1； jr:=jr+1； end else if chjw=W then jw:=jw-1； else begin ch1:=chjw； chjw:=chjb； chjb:=ch1； jw:=jw-1； jb:=jb-1； end end； for i:=1 to n do write(ch1)； writeln； end. 輸入： 10 RBRBWWRBBR 輸出： 2 program Gxp2； var i , j , s ,sp1 : integer ； p : boolean ； a : array1.10 of integer ； begin sp1:=1； a1:=2； j:=2； while sp110 do begin j:=j+1； p:=true； for i:=2 to j-1 do if (j mod i=0) then p:=false； if p then begin sp1:=sp1+1； asp1:=j； end； end； j:=2； p:=true； while p do begin s:=1； for i:=1 to j do s:=s*ai； s:=s+1； for i:=2 to s-1 do if s mod i=0 then p:=false； 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 j:=j+1； end； writeln(s)； writeln； end. 輸出： 3 Program Gxp2 Var d1 , d2 , X , Min : real ； begin Min:=10000； X:=3； while X15 do begin d1:=sqrt(9+(X-3)*(X-3)； d2:=sqrt(36+(15-X)*(15-X)； if(d1+d2)Min then Min:=d1+d2； X:=x+0.001； end； writeln(Min:10:2)； end. 輸出： 四完善程序：（ 15 + 15 = 30 分） 1 問題描述： 工廠在每天的生產(chǎn)中，需要一定數(shù)量的零件，同時(shí)也可以知道每天生產(chǎn)一個(gè)零件的生產(chǎn)單價(jià)。在 N 天的生產(chǎn)中，當(dāng)天生產(chǎn)的零件可以滿足當(dāng)天的需要，若當(dāng)天用不完，可以放到下一天去使用，但要收取每個(gè)零件的保管費(fèi)，不同的天收取的費(fèi)用也不相同。 問題求解： 求得一個(gè) N 天的生產(chǎn)計(jì)劃（即 N 天中每天應(yīng)生產(chǎn)零件個(gè)數(shù)），使總的費(fèi)用最少。 輸入： N（天數(shù) N=29） 每天的需求量（ N 個(gè)整數(shù)） 每天生產(chǎn)零件的單價(jià)（ N 個(gè)整數(shù)） 每天保管零件的單價(jià)（ N 個(gè)整數(shù)） 輸出： 每天的生產(chǎn)零件個(gè)數(shù)（ N 個(gè)整數(shù)） 例如：當(dāng) N=3 時(shí)，其需要量與費(fèi)用如下： 第一天 第二天 第三天 需 要 量 25 15 30 生產(chǎn)單價(jià) 20 30 32 保管單價(jià) 5 10 0 生產(chǎn)計(jì)劃的安排可以有許多方案，如下面的三種： 第一天 第二天 第三天 總的費(fèi)用 25 15 30 25*20+15*30+30*32=1910 40 0 30 40*20+15*5+30*32=1835 70 0 0 70*20+45*5+30*10=1925 程序說明： bn：存放每天的需求量 cn：每天生產(chǎn)零件的單價(jià) dn：每天保管零件的單價(jià) 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 en：生產(chǎn)計(jì)劃 程序： program exp5； var i,j,n,yu,j0,j1,s : integer ； b,c,d,e : array0.30 of integer ； begin readln(n)； for i:=1 to n do readln(bi,ci,di)； for i:=1 to n do ei:=0； _:=10000； cn+2=0； bn+1:=0 j0:=1； while (j0=n) do begin yu:=cj0； j1:=j0； s:=bj0； while _ do begin _ j1:=j1+1； s:=s+bj1； end； _ j0:=j1+1； end； for i:=1 to n do _ readln； end. 二問題描述： 有 n 種基本物質(zhì)（ n 10），分別記為 P1， P2， Pn，用 n 種基本物質(zhì)構(gòu)造物質(zhì)，這些物品使用在 k 個(gè)不同地區(qū)（ k 20），每個(gè)地區(qū)對物品提出自己的要求，這些要求用一個(gè) n 位的數(shù)表示： a1a2 a n，其中： ai = 1 表示所需物質(zhì)中必須有第 i 種基本物質(zhì) = -1 表示所需物質(zhì)中必須不能有第 i 種基本物質(zhì) = 0 無所謂 問題求解： 當(dāng) k 個(gè)不同要求給出之后，給出一種方案，指出哪些物質(zhì)被使用，哪些物質(zhì)不被使用。 程序說明： 數(shù)組 b1,b2bn 表示某種物質(zhì) a1.k,1.n 記錄 k 個(gè)地區(qū)對物品的要求，其中： ai,j=1 表示第 i 個(gè)地區(qū)對第 j 種物品是需要的 ai,j=0 表示第 i 個(gè)地區(qū)對第 j 種物品是無所謂的 ai,j= -1 表示第 i 個(gè)地區(qū)對第 j 種物品是不需要的 程序： program gxp2； var i,j,k,n : integer ； p : boolean ； b : array0.20 of 0.1 ； a : array1.20,1.10 of integer ； begin 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 readln(n,k)； for i:=1 to k do begin for j:=1 to n do read(ai,j)； readln； end； for i:=0 to n d