(NOI)2009第十五屆全國青少年信息學(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í)完成 ） 全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效 一 單項(xiàng)選擇題 （ 共 20 題，每題 1.5 分，共計(jì) 30 分。每題有且 僅 有一個(gè)正確答案 。 ） 1、 關(guān)于圖靈機(jī)下面的說法哪個(gè) 是正確的： A) 圖靈機(jī) 是世界上最早的電子計(jì)算機(jī)。 B) 由于大量使用磁帶操作，圖靈機(jī)運(yùn)行速度很慢 。 C) 圖靈機(jī) 是英國人圖靈發(fā)明的，在二戰(zhàn)中為破譯德軍的密碼發(fā)揮了重要作用。 D) 圖靈機(jī)只是一個(gè)理論上的計(jì)算模型。 2、關(guān)于計(jì)算機(jī)內(nèi)存下面的說法哪 個(gè) 是正確的 ： A) 隨機(jī)存儲(chǔ)器（ RAM）的意思 是當(dāng)程序運(yùn)行時(shí)，每次具體分配給程序的內(nèi)存位置 是隨機(jī)而 不確定的。 B) 1MB 內(nèi)存通常是指 1024*1024 字節(jié) 大小的內(nèi)存 。 C) 計(jì)算機(jī) 內(nèi)存 嚴(yán)格說來包括主存（ memory）、高速緩存（ cache）和寄存器（ register）三個(gè)部分 。 D) 一般內(nèi)存中的數(shù)據(jù)即使在斷電的情況下也能保留 2 個(gè)小時(shí)以上。 3、關(guān)于 BIOS 下 面說法哪個(gè) 是正確的： A) BIOS 是計(jì)算機(jī)基本輸入輸出系統(tǒng)軟件的簡稱 。 B) BIOS 里包含了鍵盤、鼠標(biāo)、聲卡、顯卡、打印機(jī)等常用輸入輸出設(shè)備的驅(qū)動(dòng)程序 。 C) BIOS 一般由操作系統(tǒng)廠商來開發(fā)完 成 。 D) BIOS 能 供 提各種文件拷貝、復(fù)制、刪除以及目錄維護(hù)等文件管理功能 。 4、 關(guān)于 CPU 下面哪個(gè) 說法是正確的： A) CPU 全稱為中央處理器 （或中央處理單元） 。 B) CPU 可以直接運(yùn)行匯編語言 。 C) 同樣主頻下， 32 位的 CPU 比 16 位的 CPU 運(yùn)行速度快一倍。 D) CPU 最早 是由 Intel 公司發(fā)明的 。 5、 關(guān)于 ASCII，下面哪個(gè)說法是正確的 ： A) ASCII 碼就是鍵盤上所有鍵的唯一編碼。 B) 一個(gè) ASCII 碼 使用 一個(gè)字節(jié)的內(nèi)存空間就能夠存放。 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 C) 最新擴(kuò)展的 ASCII 編碼方案包含了漢字和其他歐洲語言的編碼 。 D) ASCII 碼是英國人主持 制定并推廣使用的。 6、下列軟件中不是計(jì)算機(jī)操作系統(tǒng)的是 ： A) Windows B) Linux C) OS/2 D) WPS 7、關(guān)于互聯(lián)網(wǎng)，下面的說法哪一個(gè) 是正確的： A) 新一代 互聯(lián)網(wǎng)使用的 IPv6 標(biāo)準(zhǔn)是 IPv5 標(biāo)準(zhǔn)的升級(jí)與補(bǔ)充 。 B) 互聯(lián)網(wǎng)的入網(wǎng)主機(jī)如果有了域名就不再需要 IP 地址。 C) 互聯(lián)網(wǎng)的基礎(chǔ)協(xié)議為 TCP/IP 協(xié)議 。 D) 互聯(lián)網(wǎng)上所有可下載的軟件及數(shù)據(jù)資源都是可以合法免費(fèi)使用的。 8、關(guān)于 HTML 下面哪種說法是正確的： A） HTML 實(shí)現(xiàn)了文本、圖形、聲音乃至視頻信息的統(tǒng)一編碼 。 B） HTML 全稱為超文本標(biāo)記語言。 C） 網(wǎng)上廣泛使用的 Flash 動(dòng)畫都是由 HTML 編寫的。 D） HTML 也是一種高級(jí)程序設(shè)計(jì)語言。 9、 關(guān)于 程序設(shè)計(jì) 語言，下面哪 個(gè) 說法是正確的： A) 加了注釋的程序一般會(huì)比同樣的沒有加注釋的程序運(yùn)行速度慢 。 B) 高級(jí)語言開發(fā)的程序不能使用在低層次的硬件系統(tǒng) （ 如：自控機(jī)床 ） 或低端手機(jī)上。 C) 高級(jí) 語言 相對(duì)于低級(jí)語言更容易實(shí)現(xiàn)跨平臺(tái)的移植。 D) 以上說法都不對(duì) 。 10、 已知大寫字母 A的 ASCII編碼為 65（ 十 進(jìn)制），則大寫字母 J的 十 進(jìn)制 ASCII編碼為： A) 71 B) 72 C) 73 D) 以上都不是 11、十進(jìn)制小數(shù) 125.125對(duì)應(yīng)的 八 進(jìn)制數(shù)是 A) 100.1 B) 175.175 C) 175.1 D) 100.175 12、 有六個(gè)元素 FEDCBA 從左至右 依次順序進(jìn)棧，在進(jìn)棧過程中會(huì)有元素被彈出棧。問下列哪一個(gè) 不可能 是合法的出棧序列？ A) EDCFAB B) DECABF C) CDFEBA D) BCDAEF 13、 表達(dá)式 a*(b+c)-d 的后綴表達(dá)式是： A) abcd*+- B) abc+*d- C) abc*+d- D) -+*abcd 14、一個(gè)包含 n 個(gè) 分支 結(jié)點(diǎn) （非葉 結(jié)點(diǎn) ）的非空二 叉樹，它的葉結(jié)點(diǎn)數(shù)目 最多 為： A) 2n + 1 B) 2n-1 C) n-1 D) n+1 15、 快速排序 最壞情況下的算法復(fù)雜度 為： A) O(log2n) B) O(n) C) O(nlog2n) D) O(n2) 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 16. 有 一個(gè)由 4000 個(gè)整數(shù)構(gòu)成的順序表，假定表中 的 元素已經(jīng)按升序排列，采用二分 查找定位一個(gè)元素。則最多需要幾次比較就能確定是否存在所查找的元素： A) 11 次 B) 12 次 C) 13 次 D) 14 次 17、排 序算法是穩(wěn)定的意思是關(guān)鍵碼相同的記錄排序前后相對(duì)位置不發(fā)生改變 ，下列哪種排序算法是不穩(wěn)定的： A) 冒泡排序 B) 插入排序 C) 歸并排序 D) 快速排序 18、 已知 n 個(gè)頂點(diǎn)的有向圖，若該圖是強(qiáng)連通的（從所有頂點(diǎn)都存在路徑到達(dá)其他頂點(diǎn)），則該圖中最少有多少條有向邊？ A) n B) n+1 C) n-1 D) n*(n-1) 19、 全國信息學(xué)奧林匹克的官方網(wǎng)站為參與信息學(xué)競賽的老師同學(xué)們提 供相關(guān)的信息和資源，請(qǐng)問全國信息學(xué)奧林匹克官方網(wǎng)站的網(wǎng)址是 ： A) / B) / C) / D) / 20、 在參加 NOI 系列競賽過程中，下面哪 一 種行為是 不 被嚴(yán)格禁止的： A) 攜帶書寫工具，手表和不具有通訊功能的電子詞典進(jìn)入賽場。 B) 在聯(lián)機(jī)測試中通過手工計(jì)算出可能的答案并在程序里直接輸出答案來獲取 分 數(shù) 。 C) 通過互聯(lián)網(wǎng)搜索取得解題思路。 D) 在提交的程序中 啟動(dòng)多個(gè)進(jìn)程以提高程序的執(zhí)行效率。 二 問題求解（ 共 2 題， 每空 5 分，共計(jì) 10 分 ） 1 小陳現(xiàn)有 2 個(gè)任務(wù) A， B 要完成，每個(gè)任務(wù)分別有若干步驟如下： A=a1-a2-a3，B=b1-b2-b3-b4-b5。在任何時(shí)候，小陳只能專心做某個(gè)任務(wù)的一個(gè)步驟。但是如果愿意，他可以在做完手中任務(wù)的當(dāng)前步驟后，切換至另一個(gè)任務(wù)，從上次此任務(wù)第一個(gè)未做的步驟繼續(xù)。每個(gè)任務(wù)的步驟順序不能打亂，例如 a2-b2-a3-b3是合法的，而a2-b3-a3-b2是不合法的。小陳從 B 任務(wù)的 b1 步驟 開始做，當(dāng)恰做完某個(gè)任務(wù)的某個(gè)步驟后，就停工回家吃飯了。當(dāng)他回來時(shí)，只記得自己已經(jīng)完成了整個(gè)任務(wù) A，其他的都忘了。 試計(jì)算小陳飯前已做的可能的任務(wù)步驟序列共有 種。 2有如下的一段程序： 1. a:=1； 2. b:=a； 3. d:=-a； 4. e:=a+d； 5. c:=2*d； 6. f:=b+e-d； 7. g:=a*f+c； 現(xiàn)在要把這段程序分配到若干臺(tái)（數(shù)量充足）用電纜連接的 PC 上做并行執(zhí)行。每臺(tái) PC 執(zhí)行其中的某幾個(gè)語句，并可隨時(shí)通過電纜與其他 PC 通訊，交換一些中間結(jié)果。假設(shè) 每臺(tái) PC北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 每單位時(shí)間可以執(zhí)行一個(gè)語句，且通訊花費(fèi)的時(shí)間不計(jì)。則這段程序最快可以在 單位時(shí)間內(nèi)執(zhí)行完畢。注意：任意中間結(jié)果只有在某臺(tái) PC 上已經(jīng)得到，才可以被其他 PC 引用。例如若語句 4 和 6 被分別分配到兩臺(tái) PC 上執(zhí)行， 則因?yàn)檎Z句 6 需要引用語句 4 的計(jì)算結(jié)果，語句 6 必須在語句 4 之后執(zhí)行 。 三 閱讀程序?qū)懡Y(jié)果（ 共 4 題，每題 8 分，共計(jì) 32 分 ） 1 var a, b: integer； function work(a, b: integer): integer； begin if a mod b 0 then work := work(b, a mod b) else work := b； end； begin read(a, b)； writeln(work(a, b)； end. 輸入： 20 12 輸出： _ 2 var a, b: array0.2 of integer； i, j, tmp: integer； begin for i := 0 to 2 do read(bi)； for i := 0 to 2 do begin ai := 0； for j := 0 to i do begin inc(ai, bj)； inc(bai mod 3, aj)； 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 end； end； tmp := 1； for i := 0 to 2 do begin ai := ai mod 10； bi := bi mod 10； tmp := tmp * (ai + bi)； end； writeln(tmp)； end. 輸入： 2 3 5 輸出： _ 3 const c = 2009； var n, p, s, i, j, t: integer； begin read(n, p)； s := 0； t := 1； for i := 1 to n do begin t := t * p mod c； for j := 1 to i do s := (s + t) mod c； end； writeln(s)； end. 輸入： 11 2 輸出： 4 var a: string； n: integer； procedure getnext(var str: string)； var l, i, j, k: integer； 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 temp: char； begin l := length(str)； k := l - 1； while (k=1) and (strkstrk+1) do dec(k)； i := k + 1； while (istrk) do inc(i)； temp := strk； strk := stri-1； stri-1 := temp； for i := l downto k + 1 do for j := k + 1 to i - 1 do if strj strj+1 then begin temp := strj； strj := strj+1； strj+1 := temp； end； end； begin read(a)； read(n)； while n 0 do begin getnext(a)； dec(n)； end； write(a)； end. 輸入： NOIP 3 輸出： 四 完善程序 (前 8 空，每空 3 分，后 2 空，每空 2 分，共 28 分 ) 1 （最大連續(xù)子段和） 給出一個(gè)數(shù)列（元素個(gè)數(shù)不多于 100），數(shù)列元素均為負(fù)整數(shù)、正整數(shù)、 0。請(qǐng)找出數(shù)列中的一個(gè)連續(xù)子數(shù)列，使得這個(gè)子數(shù)列中包含的所有元素之和最大，在和最大的前提下還要求該子數(shù)列包含的元素個(gè)數(shù)最多，并輸出這個(gè)最大和以及該連續(xù)子數(shù)列中元素的個(gè)數(shù)。例如數(shù)列 為 4， -5， 3， 2， 4 時(shí) ， 輸出 9和 3；數(shù)列為 1 2 3 -5 0 7 8時(shí)，輸出 16和 7。 var 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 a: array1.100 of integer； n, i, ans, len, tmp, beg: integer； begin read(n)； for i := 1 to n do read(ai)； tmp := 0； ans := 0； len := 0； beg := ； for i := 1 to n do begin if tmp + ai ans then begin ans := tmp + ai； len := i - beg； end else if ( ) and (i - beg len) then len := i - beg； if tmp + ai then begin beg := ； tmp := 0； end else ； end； writeln(ans, , len)； end. 2. (國王放置 ) 在 n*m 的棋盤上放置 k 個(gè)國王，要求 k 個(gè)國王互相不攻擊，有多少種不同的放置方法。假設(shè)國王放置在第 (x,y)格，國王的攻擊的區(qū)域是 :(x-1,y-1), (x-1,y),(x-1,y+1),(x,y-1),(x,y+1),(x+1,y-1),(x+1,y),(x+1,y+1)。讀入三個(gè)數(shù) n,m,k，輸出答案。題目利用回溯法求解。棋盤行標(biāo)號(hào)為 0n-1，列標(biāo)號(hào)為 0m-1。 var n, m, k, ans: integer； hash: array0.4, 0.4 of integ