NOIP2009第十五屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽試題普及組d

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

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

3、公司發(fā)明的。5、關(guān)于ASCII,下面哪個說法是正確的:A)ASCII碼就是鍵盤上所有鍵的唯一編碼。一個ASCII碼使用一個字節(jié)的內(nèi)存空間就能夠存放。最新擴展的ASCII編碼方案包含了漢字和其他歐洲語言的編碼。ASCII碼是英國人主持制定并推廣使用的。6、下列軟件中不是計算機操作系統(tǒng)的是:WindowsB)LinuxC)OS/2D)WPS7、關(guān)于互聯(lián)網(wǎng)，下面的說法哪一個是正確的：A）新一代互聯(lián)網(wǎng)使用的IPv6標準是IPv5標準的升級與補充。B）互聯(lián)網(wǎng)的入網(wǎng)主機如果有了域名就不再需要IP地址。C）互聯(lián)網(wǎng)的基礎(chǔ)協(xié)議為TCP/IP協(xié)議。D）互聯(lián)網(wǎng)上所有可下載的軟件及數(shù)據(jù)資源都是可以合法免費使用的。8、

4、關(guān)于HTML下面哪種說法是正確的：A）HTML實現(xiàn)了文本、圖形、聲音乃至視頻信息的統(tǒng)一編碼。B）HTML全稱為超文本標記語言。網(wǎng)上廣泛使用的Flash動畫都是由HTML編寫的。D）HTML也是一種高級程序設(shè)計語言。9、關(guān)于程序設(shè)計語言，下面哪個說法是正確的：A）加了注釋的程序一般會比同樣的沒有加注釋的程序運行速度慢。B）高級語言開發(fā)的程序不能使用在低層次的硬件系統(tǒng)（如：自控機床）或低端手機上。C）高級語言相對于低級語言更容易實現(xiàn)跨平臺的移植。D）以上說法都不對。10、已知大寫字母A的ASCII編碼為65（10進制），則大寫字母J的10進制ASCII編碼為:A)71B)72C)73D)以上都不是

5、11、十進制小數(shù)125.125對應(yīng)的8進制數(shù)是A)100.1B)175.175C)175.1D)100.17512、有六個元素FEDCBA從左至右依次順序進棧，在進棧過程中會有元素被彈出棧。問下列哪一個不可能是合法的出棧序列？A）EDCFABB）DECABFC）CDFEBAD）BCDAEFNOIP2009初賽普及組C語言 NOIP2009初賽普及組C語言 13、表達式a*(b+c)d的后綴表達式是：A)abcd*+abc*+dB)abc+*dC)D)+*abcd14、一個包含n個分支結(jié)點(非葉結(jié)點)的非空二叉樹，它的葉結(jié)點數(shù)目最多為：A)2n+1B)2n1C)n1D)n+115、快速排序最壞情

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

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

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

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

10、)scanf(%d%d,&a,&b);printf(%dn,work(a,b);return0;輸入：2012輸出：2#includeintmain()inta3,b3;inti,j,tmp;for(i=0;i3;i+)scanf(%d,&bi);for(i=0;i3;i+)ai=0;ai+=bj;bai%3+=aj;tmp=1;for(i=0;i3;i+)for(j=0;j=i;j+)ai%=10;bi%=10;prtimnpt*f=(a%id+nb,itm;p);printf(%dn,tmp);return0;輸入：235輸出：3#includeconstintc=2009;NOIP200

11、9初賽普及組C語言 intmain()for(i=1;i=n;i+)intn,p,s,i,j,t;scanf(%d%d,&n,&p)s=0;t=1;t=t*p%c;for(j=1;j=i;j+)s=(s+t)%c;printf(%dn,s);return0;輸入：112輸出：4#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

12、;for(i=l-1;ik;i-)for(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輸出：空，完每善空程2序分，（共前288空分，）每空3分，后21（最大連續(xù)子段和）給出一個數(shù)列（元素個數(shù)不多于100），數(shù)列元素均為負整數(shù)、正整數(shù)、0。請找出數(shù)列中的一個連續(xù)子數(shù)列，使得這個子數(shù)列中包含的所有元素之和最大，在和最大的前提下還要求該子數(shù)列包含的元

13、素個數(shù)最多，并輸出這個最大和以及該連續(xù)子數(shù)列中元素的個數(shù)。例如數(shù)列為4，-5，3，2，4時，輸出9和3；數(shù)列為123-5078時，輸出16和7。#includeinta101;intn,i,ans,len,tmp,beg;intmain()scanf(%d,&n);for(i=1;ians)ans=tmp+ai;len=i-beg;elseif(&i-beglen)len=i-beg;if(tmp+ai)beg=;tmp=0;else;printf(%d%dn,ans,len);return0;個國王翻個國王互相不攻置在放多少少是F，y)格，國王的攻:擊.的屈域(x-1,y),(x-1,y+1),(x,y-1),(x,y+盤行標輸刪號回0m-1。#includeVstdio.h#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