NOIP2009初賽普及組C++題目及答案

1、第十五屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽試題（2009）（普及組語言二小時(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ǔ)器（）的意思是當(dāng)程序運(yùn)行時(shí)，每次具體分配給程序的內(nèi)存位置是隨機(jī)而不確定的。B）1內(nèi)存通常是指1024*102

2、4字節(jié)大小的內(nèi)存。C）計(jì)算機(jī)內(nèi)存嚴(yán)格說來包括主存（）、高速緩存（）和寄存器（）三個(gè)部分。D）一般內(nèi)存中的數(shù)據(jù)即使在斷電的情況下也能保留2個(gè)小時(shí)以上。3、關(guān)于下面說法哪個(gè)是正確的：A）是計(jì)算機(jī)基本輸入輸出系統(tǒng)軟件的簡稱。B）里包含了鍵盤、鼠標(biāo)、聲卡、顯卡、打印機(jī)等常用輸入輸出設(shè)備的驅(qū)動(dòng)程序。C）一般由操作系統(tǒng)廠商來開發(fā)完成。D）能提供各種文件拷貝、復(fù)制、刪除以及目錄維護(hù)等文件管理功能。4、關(guān)于下面哪個(gè)說法是正確的：A）全稱為中央處理器（或中央處理單元）。B）可以直接運(yùn)行匯編語言。C）同樣主頻下，32位的比16位的運(yùn)行速度快一倍。D）最早是由公司發(fā)明的。5、關(guān)于，下面哪個(gè)說法是正確的：A）碼就是鍵

3、盤上所有鍵的唯一編碼。B）一個(gè)碼使用一個(gè)字節(jié)的內(nèi)存空間就能夠存放。C）最新擴(kuò)展的編碼方案包含了漢字和其他歐洲語言的編碼。D）碼是英國人主持制定并推廣使用的。6、下列軟件中不是計(jì)算機(jī)操作系統(tǒng)的是：A）B）C）2D）7、關(guān)于互聯(lián)網(wǎng)，下面的說法哪一個(gè)是正確的：A）新一代互聯(lián)網(wǎng)使用的6標(biāo)準(zhǔn)是5標(biāo)準(zhǔn)的升級(jí)與補(bǔ)充。B）互聯(lián)網(wǎng)的入網(wǎng)主機(jī)如果有了域名就不再需要地址。C）互聯(lián)網(wǎng)的基礎(chǔ)協(xié)儀為協(xié)儀。D）互聯(lián)網(wǎng)上所有可下載的軟件及數(shù)據(jù)資源都是可以臺(tái)法免費(fèi)使用的。8、關(guān)于下面哪種說法是正確的：A實(shí)現(xiàn)了文本、圖形、聲音乃至視頻信息的統(tǒng)一編碼。B）全稱為超文本標(biāo)記語言。C）網(wǎng)上廣泛使用的動(dòng)畫都是由編寫的。D）也是一種高級(jí)程

4、序設(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的編碼為65（10進(jìn)制），則大寫字母J的10進(jìn)制編碼為：71B)72C)73D)以上都不是11、十進(jìn)制小數(shù)125.125對(duì)應(yīng)的8進(jìn)制數(shù)是A)100.1B)175.175C)175.1D)100.17512、有六個(gè)元素從左至右依次順序進(jìn)棧，在進(jìn)棧過程中會(huì)有元素被彈出棧。問下列哪一個(gè)不可能是合法的出棧序列？A)B)C)D)

5、13、表達(dá)式a*()的后綴表達(dá)式是：A)*B)*C)*D)*14、一個(gè)包含n個(gè)分支結(jié)點(diǎn)(非葉結(jié)點(diǎn))的非空二叉樹，它的葉結(jié)點(diǎn)數(shù)目最多為：A)2n+1B)21C)1D)115、快速排序最壞情況下的算法時(shí)間復(fù)雜度為：A)O(2n)B)O(n)C)0(2n)D)O(n2)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)快速排序1

6、8、已知n個(gè)頂點(diǎn)的有向圖，若該圖是強(qiáng)連通的(從所有頂點(diǎn)都存在路徑到達(dá)其他頂點(diǎn))，則該圖中最少有多少條有向邊？A)nB)1C)1D)n*(1)19、全國信息學(xué)奧林匹克的官方網(wǎng)站為參與信息學(xué)競賽的老師同學(xué)們提供相關(guān)的信息和資源，請問全國信息學(xué)奧林匹克官方網(wǎng)站的網(wǎng)址是：A)B)C)D)20、在參加系列競賽過程中，下面哪一種行為是不被嚴(yán)格禁止的：A) 攜帶書寫工具，手表和不具有通訊功能的電子詞典進(jìn)入賽場。B) 在聯(lián)機(jī)測試中通過手工計(jì)算出可能的答案并在程序里直接輸出答案來獲取分?jǐn)?shù)。C) 通過互聯(lián)網(wǎng)搜索取得解題思路。D）在提交的程序中啟動(dòng)多個(gè)進(jìn)程以提高程序的執(zhí)行效率。二. 問題求解（共2題，每空5分，共計(jì)

7、10分）小陳現(xiàn)有2個(gè)任務(wù)A,B要完成，每個(gè)任務(wù)分別有若干步驟如下:1->a2->a3,1->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ì)算小陳飯

8、前已做的可能的任務(wù)步驟序列共有種。1.2.3.4.5.6.7.1. 有如下的一段程序：1；2*d;；大.現(xiàn)在要把這段程序分配到若干臺(tái)(數(shù)量充足)用電纜連接的上做并行執(zhí)行。每臺(tái)執(zhí)行其中的某幾個(gè)語句，并可隨時(shí)通過電纜與其他通訊，交換一些中間結(jié)果。假設(shè)每臺(tái)每單位時(shí)間可以執(zhí)行一個(gè)語句，且通訊花費(fèi)的時(shí)間不計(jì)。則這段程序最快可以在單位時(shí)間內(nèi)執(zhí)行完畢。注意：任意中間結(jié)果只有在某臺(tái)上已經(jīng)得到，才可以被其他引用。例如若語句4和6被分別分配到兩臺(tái)上執(zhí)行，則因?yàn)檎Z句6需要引用語句4的計(jì)算結(jié)果，語句6必須在語句4之后執(zhí)行。三. 閱讀程序?qū)懡Y(jié)果(共4題，每題8分，共計(jì)32分)1.<>；(b)()()；b；(

9、)(>>a>>b;<<()<<；0;輸入：20122.<>；()(a33;；(0<3)>>bi;(0<3)(ai=0;(0<)(aij；bai%3j;1;(0<3)(ai10;bi10;*ii;<<<<0;3.<>；2009;()(；>>n>>p;01;(1<)(*;(1<)();<<s<<0;輸入：112輸出：4.<>50;()();2；(k>=0k>1);1；(i<i&g

10、t;k)；k;k1;l ;(1>)(1<)(j>1)(j；j1；;；()a；n；>>a>>n;（n>0）（a）；<<a<<0；輸入：3輸出：四. 完善程序（前8空，每空3分，后2空，每空2分，共28分）1.（最大連續(xù)子段和）給出一個(gè)數(shù)列（元素個(gè)數(shù)不多于100）,數(shù)列元素均為負(fù)整數(shù)、正整數(shù)、0。請找出數(shù)列中的一個(gè)連續(xù)子數(shù)列，使得這個(gè)子數(shù)列中包含的所有元素之和最大，在和最大的前提下還要求該子數(shù)列包含的元素個(gè)數(shù)最多，并輸出這個(gè)最大和以及該連續(xù)子數(shù)列中元素的個(gè)數(shù)。例如數(shù)列為4,-5,3,2,4時(shí)，輸出9和3;數(shù)列為123-5078

11、時(shí)，輸出16和7。<>J()(>>n;(1<)>>ai;0；0；0；(1<)(i>)(i；(>)；(i_)(0；<<<<<<<<0;2.(國王放置)在n*m的棋盤上放置k個(gè)國王，要求k個(gè)國王互相不攻擊，有多少種不同的放置方法。彳段設(shè)國王放置在第()格，國王的攻擊的區(qū)域是:(11),(11),(1),(1),(11),(1),(11)。讀入三個(gè)數(shù)，輸出答案。題目利用回溯法求解。棋盤行標(biāo)號(hào)為01,列標(biāo)號(hào)為01。<>；55;()(；()(；(J()(;();(1<1)(i>=0<n)(1<1)(j>=0<m)(1<1)(i>=0<n)(1<1)(j>=0<m)J0;();(1);()(>>n>>m>>k;0；(,0();<<<<0;參考答案一.選擇題