NOIP2009普及組初賽(C語(yǔ)言)試題及答案

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

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

3、一倍。D)CPU最早是由Intel公司發(fā)明的。5、關(guān)于ASCII，下面哪個(gè)說(shuō)法是正確的：BASCII碼就是鍵盤上所有鍵的唯一編碼。一個(gè)ASCII碼使用一個(gè)字節(jié)的內(nèi)存空間就能夠存放。C)最新擴(kuò)展的ASCII編碼方案包含了漢字和其他歐洲語(yǔ)言的編碼。D)ASCII碼是英國(guó)人主持制定并推廣使用的。6、下列軟件中不是計(jì)算機(jī)操作系統(tǒng)的是：DWindowsB)LinuxC)OS/2D)WPS7、關(guān)于互聯(lián)網(wǎng)，下面的說(shuō)法哪一個(gè)是正確的：CA)新一代互聯(lián)網(wǎng)使用的IPv6標(biāo)準(zhǔn)是IPv5標(biāo)準(zhǔn)的升級(jí)與補(bǔ)充。B)互聯(lián)網(wǎng)的入網(wǎng)主機(jī)如果有了域名就不再需要IP地址。C)互聯(lián)網(wǎng)的基礎(chǔ)協(xié)議為TCP/IP協(xié)議。D)互聯(lián)網(wǎng)上所有可下載

4、的軟件及數(shù)據(jù)資源都是可以合法免費(fèi)使用的。8、關(guān)于HTML下面哪種說(shuō)法是正確的：BA)HTML實(shí)現(xiàn)了文本、圖形、聲音乃至視頻信息的統(tǒng)一編碼。HTML全稱為超文本標(biāo)記語(yǔ)言。C)網(wǎng)上廣泛使用的Flash動(dòng)畫(huà)都是由HTML編寫(xiě)的。D)HTML也是一種高級(jí)程序設(shè)計(jì)語(yǔ)言。9、關(guān)于程序設(shè)計(jì)語(yǔ)言，下面哪個(gè)說(shuō)法是正確的：C加了注釋的程序一般會(huì)比同樣的沒(méi)有加注釋的程序運(yùn)行速度慢。高級(jí)語(yǔ)言開(kāi)發(fā)的程序不能使用在低層次的硬件系統(tǒng)(如：自控機(jī)床)或低端手機(jī)上。高級(jí)語(yǔ)言相對(duì)于低級(jí)語(yǔ)言更容易實(shí)現(xiàn)跨平臺(tái)的移植。以上說(shuō)法都不對(duì)。10、已知大寫(xiě)字母A的ASCII編碼為65(10進(jìn)制)，則大寫(xiě)字母J的10進(jìn)制ASCII編碼為：DA)

5、71B)72C)73D)以上都不是11、十進(jìn)制小數(shù)125.125對(duì)應(yīng)的8進(jìn)制數(shù)是：CA)100.1B)175.175C)175.1D)100.17512、有六個(gè)元素FEDCBA從左至右依次順序進(jìn)棧，在進(jìn)棧過(guò)程中會(huì)有元素被彈出棧。問(wèn)下列哪一個(gè)不可能是合法的出棧序列？CA)EDCFABB)DECABFC)CDFEBAD)BCDAEF13、表達(dá)式a*(b+c)-d的后綴表達(dá)式是：BA)abcd*+-B)abc+*d-C)abc*+d-D)-+*abcd14、一個(gè)包含n個(gè)分支結(jié)點(diǎn)(非葉結(jié)點(diǎn))的非空二叉樹(shù)，它的葉結(jié)點(diǎn)數(shù)目最多為：DA)2n+1B)2n-1C)n-1D)n+115、快速排序最壞情況下的算法

6、時(shí)間復(fù)雜度為：DA)O(log2n)B)O(n)C)O(nlog2n)D)O(n2)有一個(gè)由4000個(gè)整數(shù)構(gòu)成的順序表，假定表中的元素已經(jīng)按升序排列，采用二分查找定位一個(gè)元素。則最多需要幾次比較就能確定是否存在所查找的元素：BA)11次B)12次C)13次D)14次17、排序算法是穩(wěn)定的意思是關(guān)鍵碼相同的記錄排序前后相對(duì)位置不發(fā)生改變，下列哪種排序算法是不穩(wěn)定的：DA)冒泡排序B)插入排序C)歸并排序D)快速排序18、已知n個(gè)頂點(diǎn)的有向圖，若該圖是強(qiáng)連通的(從所有頂點(diǎn)都存在路徑到達(dá)其他頂點(diǎn))則該圖中最少有多少條有向邊？AA)nB)n+1C)n-1D)n*(n-1)19、全國(guó)信息學(xué)奧林匹克的官方

7、網(wǎng)站為參與信息學(xué)競(jìng)賽的老師同學(xué)們提供相關(guān)的信息和資源，請(qǐng)問(wèn)全國(guó)信息學(xué)奧林匹克官方網(wǎng)站的網(wǎng)址是：CA) HYPERLINK / /B) HYPERLINK / /C) HYPERLINK / /D) HYPERLINK / /20、在參加NOI系列競(jìng)賽過(guò)程中，下面哪一種行為是不被嚴(yán)格禁止的：B攜帶書(shū)寫(xiě)工具，手表和不具有通訊功能的電子詞典進(jìn)入賽場(chǎng)。在聯(lián)機(jī)測(cè)試中通過(guò)手工計(jì)算出可能的答案并在程序里直接輸出答案來(lái)獲取分?jǐn)?shù)。通過(guò)互聯(lián)網(wǎng)搜索取得解題思路。在提交的程序中啟動(dòng)多個(gè)進(jìn)程以提高程序的執(zhí)行效率。二問(wèn)題求解(共2題，每空5分，共計(jì)10分).小陳現(xiàn)有2個(gè)任務(wù)A，B要完成，每個(gè)任務(wù)分別有若干步驟如下：A=a

8、1-a24a3，B=b1-b24b34b44b5。在任何時(shí)候，小陳只能專心做某個(gè)任務(wù)的一個(gè)步驟。但是如果愿意，他可以在做完手中任務(wù)的當(dāng)前步驟后，切換至另一個(gè)任務(wù)，從上次此任務(wù)第一個(gè)未做的步驟繼續(xù)。每個(gè)任務(wù)的步驟順序不能打亂，例如a2-b2-a3-b3是合法的，而.a24b34a34b2.是不合法的。小陳從B任務(wù)的bl步驟開(kāi)始做，當(dāng)恰做完某個(gè)任務(wù)的某個(gè)步驟后，就停工回家吃飯了。當(dāng)他回來(lái)時(shí)，只記得自己已經(jīng)完成了整個(gè)任務(wù)A，其他的都忘了。試計(jì)算小陳飯前已做的可能的任務(wù)步驟序列共有70種。2有如下的一段程序：a=1;b=a;d=-a;e=a+d;c=2*d;f=b+e-d;g=a*f+c;現(xiàn)在要把這段

9、程序分配到若干臺(tái)(數(shù)量充足)用電纜連接的PC上做并行執(zhí)行。每臺(tái)PC執(zhí)行其中的某幾個(gè)語(yǔ)句，并可隨時(shí)通過(guò)電纜與其他PC通訊，交換一些中間結(jié)果。假設(shè)每臺(tái)PC每單位時(shí)間可以執(zhí)行一個(gè)語(yǔ)句，且通訊花費(fèi)的時(shí)間不計(jì)。則這段程序最快可以在5單位時(shí)間內(nèi)執(zhí)行完畢。注意：任意中間結(jié)果只有在某臺(tái)PC上已經(jīng)得到，才可以被其他PC引用。例如若語(yǔ)句4和6被分別分配到兩臺(tái)PC上執(zhí)行，則因?yàn)檎Z(yǔ)句6需要引用語(yǔ)句4的計(jì)算結(jié)果，語(yǔ)句6必須在語(yǔ)句4之后執(zhí)行。三閱讀程序?qū)懡Y(jié)果(共4題，每題8分，共計(jì)32分)#includeinta,b;intwork(inta,intb)if(a%b)returnwork(b,a%b);returnb;i

10、ntmain()scanf(%d%d,&a,&b);printf(%dn,work(a,b);return0;輸入：2012輸出：4#includeintmain()inta3,b3;inti,j,tmp;for(i=0;i3;i+)scanf(%d,&bi);for(i=0;i3;i+)ai=0;for(j=0;j=i;j+)ai+=bj;bai%3+=aj;tmp=1;for(i=0;i3;i+)ai%=10;bi%=10;tmp*=ai+bi;printf(%dn,tmp);return0;輸入：235輸出：416#includeconstintc=2009;intmain()intn,

11、p,s,i,j,t;scanf(%d%d,&n,&p);s=0;t=1;for(i=1;i=n;i+)t=t*p%c;for(j=1;j=i;j+)s=(s+t)%c;printf(%dn,s);return0;輸入：112輸出：782#include#include#definemaxn50voidgetnext(charstr)intl=strlen(str),i,j,k,temp;k=l-2;while(k=0&strkstrk+1)k-;i=k+1;while(istrk)i+;temp=strk;strk=stri-1;stri-1=temp;for(i=l-1;ik;i-)for(

12、j=k+1;jstrj+1)temp=strj;strj=strj+1;strj+1=temp;return;intmain()charamaxn;intn;scanf(%s%d,a,&n);while(n0)getnext(a);n-;printf(%sn,a);return0;輸入：NOIP3輸出：NPOI四完善程序(前8空，每空3分，后2空，每空2分，共28分)1(最大連續(xù)子段和)給出一個(gè)數(shù)列(元素個(gè)數(shù)不多于100)，數(shù)列元素均為負(fù)整數(shù)、正整數(shù)、0。請(qǐng)找出數(shù)列中的一個(gè)連續(xù)子數(shù)列，使得這個(gè)子數(shù)列中包含的所有元素之和最大，在和最大的前提下還要求該子數(shù)列包含的元素個(gè)數(shù)最多，并輸出這個(gè)最大和以及

13、該連續(xù)子數(shù)列中元素的個(gè)數(shù)。例如數(shù)列為4，-5，3，2，4時(shí)，輸出9和3；數(shù)列為123-5078時(shí)，輸出16和7。#includeinta101;intn,i,ans,len,tmp,beg;intmain()scanf(%d,&n);for(i=1;i=n;i+)scanf(%d,&ai);tmp=0;ans=0;len=0;beg=;for(i=1;ians)ans=tmp+ai;len=i-beg;elseif(&i-beglen)len=i-beg;TOC o 1-5 h zif(tmp+ai)beg=;tmp=0;else;printf(%d%dn,ans,len);return0;:

14、0:tmp+ai=ans:0:i:tmp=tmp+ai2.(國(guó)王放置)在n*m的棋盤上放置k個(gè)國(guó)王，要求k個(gè)國(guó)王互相不攻擊，有多少種不同的放置方法。假設(shè)國(guó)王放置在第(x,y)格，國(guó)王的攻擊的區(qū)域是：(x-1,y-1),僅-1,y),(x-1,y+1),(x,y-1),(x,y+1),(x+1,y-1),(x+1,y),(x+1,y+1)。讀入三個(gè)數(shù)n,m,k，輸出答案。題目利用回溯法求解。棋盤行標(biāo)號(hào)為0n-1,列標(biāo)號(hào)為0m-1。#include#includeintn,m,k,ans;inthash55;voidwork(intx,inty,inttot)inti,j;if(tot=k)ans+;return;dowhile(hashxy)y+;if(y=m)x+;y=if(x=n)return;for(i=x-l;i=0&in)for(j=y-l;j=0&jm)；fo