(NOI)2009第十五屆全國青少年信息學奧林匹克聯賽初賽試題

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