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

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

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

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

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

5、數(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)nB)n1C)n1

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

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