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

1、第1頁共65頁第十五屆全國青少年信息學奧林匹克聯(lián)賽初賽試題（普及組普及組Pal語言語言二小時完成二小時完成）●●全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效●●一一單項選擇題單項選擇題（共（共20題，每題題，每題1.5分，共計分，共計30分。每題有且僅有一個正確答案。分。每題有且僅有一個正確答案。）1、關(guān)于圖靈機下面的說法哪個是正確的：A)圖靈機是世界上最早的電子計算機。B)由

2、于大量使用磁帶操作，圖靈機運行速度很慢。C)圖靈機是英國人圖靈發(fā)明的，在二戰(zhàn)中為破譯德軍的密碼發(fā)揮了重要作用。D)圖靈機只是一個理論上的計算模型。2、關(guān)于計算機內(nèi)存下面的說法哪個是正確的：A)隨機存儲器（RAM）的意思是當程序運行時，每次具體分配給程序的內(nèi)存位置是隨機而不確定的。B)1MB內(nèi)存通常是指10241024字節(jié)大小的內(nèi)存。C)計算機內(nèi)存嚴格說來包括主存（memy）、高速緩存（cache）和寄存器（register）三個部分。D

3、)一般內(nèi)存中的數(shù)據(jù)即使在斷電的情況下也能保留2個小時以上。3、關(guān)于BIOS下面說法哪個是正確的：A)BIOS是計算機基本輸入輸出系統(tǒng)軟件的簡稱。B)BIOS里包含了鍵盤、鼠標、聲卡、顯卡、打印機等常用輸入輸出設備的驅(qū)動程序。C)BIOS一般由操作系統(tǒng)廠商來開發(fā)完成。D)BIOS能供提各種文件拷貝、復制、刪除以及目錄維護等文件管理功能。4、關(guān)于CPU下面哪個說法是正確的：A)CPU全稱為中央處理器（或中央處理單元）。B)CPU可以直接運行

4、匯編語言。C)同樣主頻下，32位的CPU比16位的CPU運行速度快一倍。D)CPU最早是由Intel公司發(fā)明的。5、關(guān)于II，下面哪個說法是正確的：A)II碼就是鍵盤上所有鍵的唯一編碼。B)一個II碼使用一個字節(jié)的內(nèi)存空間就能夠存放。C)最新擴展的II編碼方案包含了漢字和其他歐洲語言的編碼。第3頁共65頁15、快速排序最壞情況下的算法復雜度為：A)O(log2n)B)O(n)C)O(nlog2n)D)O(n2)16.有一個由4000個整

5、數(shù)構(gòu)成的順序表，假定表中的元素已經(jīng)按升序排列，采用二分查找定位一個元素。則最多需要幾次比較就能確定是否存在所查找的元素：A)11次B)12次C)13次D)14次17、排序算法是穩(wěn)定的意思是關(guān)鍵碼相同的記錄排序前后相對位置不發(fā)生改變，下列哪種排序算法是不穩(wěn)定的：A)冒泡排序B)插入排序C)歸并排序D)快速排序18、已知n個頂點的有向圖，若該圖是強連通的（從所有頂點都存在路徑到達其他頂點），則該圖中最少有多少條有向邊？A)nB)n1C)n1

6、D)n(n1)19、全國信息學奧林匹克的官方網(wǎng)站為參與信息學競賽的老師同學們提供相關(guān)的信息和資源，請問全國信息學奧林匹克官方網(wǎng)站的網(wǎng)址是：A)B):www.noi.gC)D)20、在參加NOI系列競賽過程中，下面哪一種行為是不被嚴格禁止的：A)攜帶書寫工具，手表和不具有通訊功能的電子詞典進入賽場。B)在聯(lián)機測試中通過手工計算出可能的答案并在程序里直接輸出答案來獲取分數(shù)。C)通過互聯(lián)網(wǎng)搜索取得解題思路。D)在提交的程序中啟動多個進程以提高

7、程序的執(zhí)行效率。二問題求解（共二問題求解（共2題，每空題，每空5分，共計分，共計10分）分）1小陳現(xiàn)有2個任務A，B要完成，每個任務分別有若干步驟如下：A=a1a2a3，B=b1b2b3b4b5。在任何時候，小陳只能專心做某個任務的一個步驟。但是如果愿意，他可以在做完手中任務的當前步驟后，切換至另一個任務，從上次此任務第一個未做的步驟繼續(xù)。每個任務的步驟順序不能打亂，例如……a2b2a3b3……是合法的，而……a2b3a3b2……是不合