全國青少年信息學奧林匹克聯(lián)賽初賽試題2009-

1、第十五屆全國青少年信息學奧林匹克聯(lián)賽初賽試題（ 普及組Pascal語言二小時完成）全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效一單項選擇題（共 20 題，每題1.5分，共計30 分。每題有且僅有一個正確答案。）1、 關于圖靈機下面的說法哪個是正確的：A) 圖靈機是世界上最早的電子計算機。B) 由于大量使用磁帶操作，圖靈機運行速度很慢。C) 圖靈機是英國人圖靈發(fā)明的，在二戰(zhàn)中為破譯德軍的密碼發(fā)揮了重要作用。D) 圖靈機只是一個理論上的計算模型。2、關于計算機內(nèi)存下面的說法哪個是正確的：A) 隨機存儲器（ RAM ）的意思是當程序運行時，每次具體分配給程序的內(nèi)存位置是隨機而不確定的。B)

2、1MB 內(nèi)存通常是指 1024*1024 字節(jié)大小的內(nèi)存。C) 計算機內(nèi)存嚴格說來包括主存（ memory ）、高速緩存（ cache）和寄存器（ register）三個部分。D)一般內(nèi)存中的數(shù)據(jù)即使在斷電的情況下也能保留2 個小時以上。3、關于 BIOS 下面說法哪個是正確的：A) BIOS 是計算機基本輸入輸出系統(tǒng)軟件的簡稱。B) BIOS 里包含了鍵盤、 鼠標、 聲卡、顯卡、打印機等常用輸入輸出設備的驅動程序。C) BIOS 一般由操作系統(tǒng)廠商來開發(fā)完成。D) BIOS 能供提各種文件拷貝、復制、刪除以及目錄維護等文件管理功能。4、關于 CPU 下面哪個說法是正確的：A) CPU 全稱為

3、中央處理器（或中央處理單元） 。B) CPU 可以直接運行匯編語言。C) 同樣主頻下， 32 位的 CPU 比 16 位的 CPU 運行速度快一倍。D) CPU 最早是由 Intel 公司發(fā)明的。5、關于 ASCII ，下面哪個說法是正確的：A) ASCII 碼就是鍵盤上所有鍵的唯一編碼。B) 一個 ASCII 碼使用一個字節(jié)的內(nèi)存空間就能夠存放。C) 最新擴展的 ASCII 編碼方案包含了漢字和其他歐洲語言的編碼。D) ASCII 碼是英國人主持制定并推廣使用的。6、下列軟件中不是計算機操作系統(tǒng)的是：A) WindowsB) LinuxC) OS/2D) WPS7、關于互聯(lián)網(wǎng)，下面的說法哪一

4、個是正確的：A) 新一代互聯(lián)網(wǎng)使用的 IPv6 標準是 IPv5 標準的升級與補充。C) 互聯(lián)網(wǎng)的基礎協(xié)議為 TCP/IP 協(xié)議。D) 互聯(lián)網(wǎng)上所有可下載的軟件及數(shù)據(jù)資源都是可以合法免費使用的。8、關于 HTML 下面哪種說法是正確的：A ） HTML 實現(xiàn)了文本、圖形、聲音乃至視頻信息的統(tǒng)一編碼。B） HTML 全稱為超文本標記語言。C） 網(wǎng)上廣泛使用的Flash 動畫都是由HTML 編寫的。D） HTML 也是一種高級程序設計語言。9、關于程序設計語言，下面哪個說法是正確的：A) 加了注釋的程序一般會比同樣的沒有加注釋的程序運行速度慢。B) 高級語言開發(fā)的程序不能使用在低層次的硬件系統(tǒng)（如

5、：自控機床）或低端手機上。C) 高級語言相對于低級語言更容易實現(xiàn)跨平臺的移植。D) 以上說法都不對。10、已知大寫字母A)71A 的 ASCII 編碼為 65（十進制），則大寫字母B) 72C) 73D) 以上都不是J的十進制ASCII編碼為：11、十進制小數(shù) 125.125對應的八進制數(shù)是A) 100.1B) 175.175C) 175.1D) 100.17512、有六個元素 FEDCBA 從左至右依次順序進棧，在進棧過程中會有元素被彈出棧。問下列哪一個 不可能 是合法的出棧序列？A)EDCFABB) DECABFC) CDFEBAD) BCDAEF13、 表達式 a*(b+c) - d 的

6、后綴表達式是：A)abcd*+ -B) abc+*d -C) abc*+d -D) - +*abcd14、一個包含n 個分支結點（非葉結點）的非空二叉樹，它的葉結點數(shù)目最多為：A) 2n + 1B) 2n - 1C) n- 1D) n+115、快速排序最壞情況下的算法復雜度為：A) O(log 2 n)B) O(n)C) O(nlog 2n)D)O(n 2)16. 有一個由 4000 個整數(shù)構成的順序表， 假定表中的元素已經(jīng)按升序排列，定位一個元素。則最多需要幾次比較就能確定是否存在所查找的元素：采用二分查找A) 11次B) 12次C) 13次D)14 次17、排序算法是穩(wěn)定的意思是關鍵碼相同

7、的記錄排序前后相對位置不發(fā)生改變，下列哪種排序算法是不穩(wěn)定的：A)冒泡排序B) 插入排序C) 歸并排序D)快速排序18、已知 n 個頂點的有向圖，若該圖是強連通的（從所有頂點都存在路徑到達其他頂點）則該圖中最少有多少條有向邊？，A) nB) n+1C) n - 1D)n*(n - 1)19、全國信息學奧林匹克的官方網(wǎng)站為參與信息學競賽的老師同學們提供相關的信息和資源，請問全國信息學奧林匹克官方網(wǎng)站的網(wǎng)址是：20、在參加NOI 系列競賽過程中，下面哪一種行為是不 被嚴格禁止的：A) 攜帶書寫工具，手表和不具有通訊功能的電子詞典進入賽場。B) 在聯(lián)機測試中通過手工計算出可能的答案并在程序里直接輸出

8、答案來獲取分數(shù)。C) 通過互聯(lián)網(wǎng)搜索取得解題思路。D) 在提交的程序中啟動多個進程以提高程序的執(zhí)行效率。二問題求解（共2 題，每空5 分，共計10 分）1小陳現(xiàn)有2 個任務 A ， B 要完成，每個任務分別有若干步驟如下：A=a1->a2->a3 ，B=b1->b2->b3->b4->b5 。在任何時候，小陳只能專心做某個任務的一個步驟。但是如果愿意，他可以在做完手中任務的當前步驟后，切換至另一個任務，從上次此任務第一個未做的步驟繼續(xù)。每個任務的步驟順序不能打亂，例如,a2->b2->a3->b3 , 是合法的，而,a2->b3-&g

9、t;a3->b2 , 是不合法的。小陳從 B 任務的 b1 步驟開始做， 當恰做完某個任務的某個步驟后，就停工回家吃飯了。當他回來時，只記得自己已經(jīng)完成了整個任務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;現(xiàn)在要把這段程序分配到若干臺（數(shù)量充足）用電纜連接的PC 上做并行執(zhí)行。每臺PC執(zhí)行其中的某幾個語句，并可隨時通過電纜與其他PC 通訊，交換一些中間結果。假設每臺 PC 每單位時間可以執(zhí)行一個語句，且通訊花費

10、的時間不計。則這段程序最快可以在單位時間內(nèi)執(zhí)行完畢。注意：任意中間結果只有在某臺PC 上已經(jīng)得到，才可以被其他PC引用。例如若語句4 和 6 被分別分配到兩臺 PC 上執(zhí)行，則因為語句 6 需要引用語句4 的計算結果，語句6 必須在語句 4 之后執(zhí)行。三閱讀程序寫結果（共4 題，每題 8 分，共計32 分）1vara, b: integer;function work(a, b: integer): integer;beginif a mod b <> 0 thenwork := work(b, a mod b)elsework := b;end;beginread(a, b);w

11、riteln(work(a, b);end.輸入： 20 12輸出： _2vara, b: array0.2 of integer;i, j, tmp: integer;beginfor i := 0 to 2 doread(bi);for i := 0 to 2 dobeginai := 0;for j := 0 to i dobegininc(ai, bj);inc(bai mod 3, aj);end;end;tmp := 1;for i := 0 to 2 dobeginai := ai mod 10;bi := bi mod 10;tmp := tmp * (ai + bi);end;writeln(