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

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

2、的。B) 1MB內(nèi)存通常是指1024*1024字節(jié)大小的內(nèi)存。C) 計算機(jī)內(nèi)存嚴(yán)格說來包括主存（memory）、高速緩存（cache）和寄存器（register）三個部分。D) 一般內(nèi)存中的數(shù)據(jù)即使在斷電的情況下也能保留2個小時以上。3、關(guān)于BIOS下面說法哪個是正確的：A) BIOS是計算機(jī)基本輸入輸出系統(tǒng)軟件的簡稱。B) BIOS里包含了鍵盤、鼠標(biāo)、聲卡、顯卡、打印機(jī)等常用輸入輸出設(shè)備的驅(qū)動程序。C) BIOS一般由操作系統(tǒng)廠商來開發(fā)完成。D) BIOS能提供各種文件拷貝、復(fù)制、刪除以及目錄維護(hù)等文件管理功能。4、關(guān)于CPU下面哪個說法是正確的：A) CPU全稱為中央處理器（或中央處理單元

3、）。B) CPU可以直接運(yùn)行匯編語言。C) 同樣主頻下，32位的CPU比16位的CPU運(yùn)行速度快一倍。D) CPU最早是由Intel公司發(fā)明的。5、關(guān)于ASCII，下面哪個說法是正確的：A) ASCII碼就是鍵盤上所有鍵的唯一編碼。B) 一個ASCII碼使用一個字節(jié)的內(nèi)存空間就能夠存放。C) 最新擴(kuò)展的ASCII編碼方案包含了漢字和其他歐洲語言的編碼。D) ASCII碼是英國人主持制定并推廣使用的。6、下列軟件中不是計算機(jī)操作系統(tǒng)的是： A) Windows B) Linux C) OS/2 D) WPS7、關(guān)于互聯(lián)網(wǎng)，下面的說法哪一個是正確的：A) 新一代互聯(lián)網(wǎng)使用的IPv6標(biāo)準(zhǔn)是IPv5標(biāo)

4、準(zhǔn)的升級與補(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)上所有可下載的軟件及數(shù)據(jù)資源都是可以合法免費(fèi)使用的。8、關(guān)于HTML下面哪種說法是正確的：A） HTML實(shí)現(xiàn)了文本、圖形、聲音乃至視頻信息的統(tǒng)一編碼。B） HTML全稱為超文本標(biāo)記語言。C） 網(wǎng)上廣泛使用的 Flash動畫都是由HTML編寫的。D） HTML也是一種高級程序設(shè)計語言。9、關(guān)于程序設(shè)計語言，下面哪個說法是正確的：A) 加了注釋的程序一般會比同樣的沒有加注釋的程序運(yùn)行速度慢。B) 高級語言開發(fā)的程序不能使用在低層次的硬件系統(tǒng)如：自控機(jī)床或低端手機(jī)上。C) 高級

5、語言相對于低級語言更容易實(shí)現(xiàn)跨平臺的移植。D) 以上說法都不對。10、已知大寫字母A的ASCII編碼為65（10進(jìn)制），則大寫字母J的10進(jìn)制ASCII編碼為：A) 71 B) 72 C) 73 D) 以上都不是11、十進(jìn)制小數(shù)125.125對應(yīng)的8進(jìn)制數(shù)是A) 100.1 B) 175.175 C) 175.1 D) 100.17512、有六個元素FEDCBA 從左至右依次順序進(jìn)棧，在進(jìn)棧過程中會有元素被彈出棧。問下列哪一個不可能是合法的出棧序列？ A) EDCFAB B) DECABF C) CDFEBA D) BCDAEF13、 表達(dá)式a*(b+c)-d的后綴表達(dá)式是：A) abcd*+

6、- B) abc+*d- C) abc*+d- D) -+*abcd14、一個包含n個分支結(jié)點(diǎn)（非葉結(jié)點(diǎn)）的非空二叉樹，它的葉結(jié)點(diǎn)數(shù)目最多為：A) 2n + 1 B) 2n-1 C) n-1 D) n+1 15、快速排序最壞情況下的算法時間復(fù)雜度為： A) O(log2n) B) O(n) C) O(nlog2n) D) O(n2)16. 有一個由4000個整數(shù)構(gòu)成的順序表，假定表中的元素已經(jīng)按升序排列，采用二分查找定位一個元素。則最多需要幾次比較就能確定是否存在所查找的元素： A) 11次 B) 12次 C) 13次 D) 14次17、排序算法是穩(wěn)定的意思是關(guān)鍵碼相同的記錄排序前后相對位置不

7、發(fā)生改變，下列哪種排序算法是不穩(wěn)定的：A) 冒泡排序 B) 插入排序 C) 歸并排序 D) 快速排序18、已知n個頂點(diǎn)的有向圖，若該圖是強(qiáng)連通的（從所有頂點(diǎn)都存在路徑到達(dá)其他頂點(diǎn)），則該圖中最少有多少條有向邊？A) n B) n+1 C) n-1 D) n*(n-1)19、全國信息學(xué)奧林匹克的官方網(wǎng)站為參與信息學(xué)競賽的老師同學(xué)們提供相關(guān)的信息和資源，請問全國信息學(xué)奧林匹克官方網(wǎng)站的網(wǎng)址是：A) B) /C) D) 20、在參加NOI系列競賽過程中，下面哪一種行為是 不 被嚴(yán)格禁止的：A) 攜帶書寫工具，手表和不具有通訊功能的電子詞典進(jìn)入賽場。B) 在聯(lián)機(jī)測試中

8、通過手工計算出可能的答案并在程序里直接輸出答案來獲取分?jǐn)?shù)。C) 通過互聯(lián)網(wǎng)搜索取得解題思路。D) 在提交的程序中啟動多個進(jìn)程以提高程序的執(zhí)行效率。二問題求解（共2題，每空5分，共計10分）1小陳現(xiàn)有2個任務(wù)A，B要完成，每個任務(wù)分別有若干步驟如下：A=a1->a2->a3，B=b1->b2->b3->b4->b5。在任何時候，小陳只能專心做某個任務(wù)的一個步驟。但是如果愿意，他可以在做完手中任務(wù)的當(dāng)前步驟后，切換至另一個任務(wù)，從上次此任務(wù)第一個未做的步驟繼續(xù)。每個任務(wù)的步驟順序不能打亂，例如a2->b2->a3->b3是合法的，而a2->

9、;b3->a3->b2是不合法的。小陳從B任務(wù)的b1步驟開始做，當(dāng)恰做完某個任務(wù)的某個步驟后，就停工回家吃飯了。當(dāng)他回來時，只記得自己已經(jīng)完成了整個任務(wù)A，其他的都忘了。試計算小陳飯前已做的可能的任務(wù)步驟序列共有 種。2有如下的一段程序：1.a=1;2.b=a;3.d=-a;4.e=a+d;5.c=2*d;6.f=b+e-d;7.g=a*f+c;現(xiàn)在要把這段程序分配到若干臺（數(shù)量充足）用電纜連接的PC上做并行執(zhí)行。每臺PC執(zhí)行其中的某幾個語句，并可隨時通過電纜與其他PC通訊，交換一些中間結(jié)果。假設(shè)每臺PC每單位時間可以執(zhí)行一個語句，且通訊花費(fèi)的時間不計。則這段程序最快可以在 單位時

10、間內(nèi)執(zhí)行完畢。注意：任意中間結(jié)果只有在某臺PC上已經(jīng)得到，才可以被其他PC引用。例如若語句4和6被分別分配到兩臺PC上執(zhí)行，則因?yàn)檎Z句6需要引用語句4的計算結(jié)果，語句6必須在語句4之后執(zhí)行。三閱讀程序?qū)懡Y(jié)果（共4題，每題8分，共計32分）1#include <iostream>using namespace std;int a,b;int work(int a,int b)if (a%b)return work(b,a%b);return b;int main()cin >> a >> b;cout << work(a,b) << e

11、ndl;return 0;輸入：20 12輸出：_2#include <iostream>using namespace std;int main()int a3,b3;int i,j,tmp;for (i=0;i<3;i+)cin >> bi;for (i=0;i<3;i+)ai=0;for (j=0;j<=i;j+)ai+=bj;bai%3+=aj;tmp=1;for (i=0;i<3;i+)ai%=10;bi%=10;tmp*=ai+bi;cout << tmp << endl;return 0;輸入：2 3 5輸出

12、：_3#include <iostream>using namespace std;const int c=2009;int main()int n,p,s,i,j,t;cin >> 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;cout << s << endl;return 0;輸入：11 2輸出： 4#include <iostream>using namespace std;const int maxn=50;void

13、getnext(char str)int l=strlen(str),i,j,k,temp;k=l-2;while(k>=0&&strk>strk+1) k-;i=k+1;while(i<l&&stri>strk) i+;temp=strk;strk=stri-1;stri-1=temp;for(i=l-1;i>k;i-)for(j=k+1;j<i;j+)if(strj>strj+1)temp=strj;strj=strj+1;strj+1=temp;return ;int main()char amaxn;int n;

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

15、7 8時，輸出16和7。#include <iostream>using namespace std;int a101;int n,i,ans,len,tmp,beg;int main()cin >> n;for (i=1;i<=n;i+)cin >> ai;tmp=0;ans=0;len=0;beg= ;for (i=1;i<=n;i+)if (tmp+ai>ans)ans=tmp+ai;len=i-beg;else if ( &&i-beg>len)len=i-beg;if (tmp+ai )beg= ;tmp=0

16、;else ;cout << ans << " " << len << endl;return 0;2. (國王放置) 在n*m的棋盤上放置k個國王，要求k個國王互相不攻擊，有多少種不同的放置方法。假設(shè)國王放置在第(x,y)格，國王的攻擊的區(qū)域是:(x-1,y-1), (x-1,y),(x-1,y+1),(x,y-1),(x,y+1),(x+1,y-1),(x+1,y),(x+1,y+1)。讀入三個數(shù)n,m,k，輸出答案。題目利用回溯法求解。棋盤行標(biāo)號為0n-1，列標(biāo)號為0m-1。#include <iostream&g

17、t;using namespace std;int n,m,k,ans;int hash55;void work(int x,int y,int tot)int i,j;if (tot=k)ans+;return;dowhile (hashxy)y+;if (y=m)x+;y= ;if (x=n)return;for (i=x-1;i<=x+1;i+)if (i>=0&&i<n)for (j=y-1;j<=y+1;j+)if (j>=0&&j<m) ; ;for (i=x-1;i<=x+1;i+)if (i>=0&

18、amp;&i<n)for (j=y-1;j<=y+1;j+)if (j>=0&&j<m) ;y+;if (y=m)x+;y=0;if (x=n)return;while (1);int main()cin >> n >> m >> k;ans=0;memset(hash,0,sizeof(hash); ;cout << ans << endl;return 0;參考答案一 選擇題DBAAB DCBCD CCBDD BDACB二 問題解答1. 702. 5三 閱讀程序1. 42. 4163. 7824.  NPOI 四完善程序1.（1）0（2）tmp+ai=ans 或者 ai+tmp=ans 或者ans=ai+tmp等（3）<0（4）i（5）tmp+=ai 或者 tmp=tmp+ai 2.（1）0（2）hashij+ 或者 hashij= hashij+1 或者 +hashij（3）wor