《全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽初賽試題》由會(huì)員分享，可在線(xiàn)閱讀，更多相關(guān)《全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽初賽試題（9頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

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è)是正確的： A) 圖靈機(jī)是世界上最早的電子計(jì)算機(jī)。 B) 由于大量使用磁帶操作，圖靈機(jī)運(yùn)行速度很慢。 C) 圖靈機(jī)是英國(guó)人圖靈發(fā)明的，在二戰(zhàn)中為破譯德軍的密碼發(fā)揮了重要作用。 D) 圖靈機(jī)只是一個(gè)理論上的計(jì)算模型。 2、關(guān)于計(jì)算機(jī)內(nèi)存下面的說(shuō)法哪個(gè)是

2、正確的： A) 隨機(jī)存儲(chǔ)器（RAM）的意思是當(dāng)程序運(yùn)行時(shí)，每次具體分配給程序的內(nèi)存位置是隨機(jī)而不確定的。 B) 1MB內(nèi)存通常是指1024*1024字節(jié)大小的內(nèi)存。 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è)是正確的： A) BIOS是計(jì)算機(jī)基本輸入輸出系統(tǒng)軟件的簡(jiǎn)稱(chēng)。 B) BIOS里包含了鍵盤(pán)、鼠標(biāo)、聲卡、顯卡、打印機(jī)等常用輸入輸出設(shè)備的驅(qū)動(dòng)程序。 C) BIOS一般由操作系統(tǒng)廠(chǎng)商來(lái)開(kāi)發(fā)完成。 D) BIOS

3、能提供各種文件拷貝、復(fù)制、刪除以及目錄維護(hù)等文件管理功能。 4、關(guān)于CPU下面哪個(gè)說(shuō)法是正確的： A) CPU全稱(chēng)為中央處理器（或中央處理單元）。 B) CPU可以直接運(yùn)行匯編語(yǔ)言。 C) 同樣主頻下，32位的CPU比16位的CPU運(yùn)行速度快一倍。 D) CPU最早是由Intel公司發(fā)明的。 5、關(guān)于A(yíng)SCII，下面哪個(gè)說(shuō)法是正確的： A) ASCII碼就是鍵盤(pán)上所有鍵的唯一編碼。 B) 一個(gè)ASCII碼使用一個(gè)字節(jié)的內(nèi)存空間就能夠存放。 C) 最新擴(kuò)展的ASCII編碼方案包含了漢字和其他歐洲語(yǔ)言的編碼。 D) ASCII碼是英國(guó)人主持制定并推廣使用的。 6、

4、下列軟件中不是計(jì)算機(jī)操作系統(tǒng)的是： A) Windows B) Linux C) OS/2 D) WPS 7、關(guān)于互聯(lián)網(wǎng)，下面的說(shuō)法哪一個(gè)是正確的： A) 新一代互聯(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é)議為T(mén)CP/IP協(xié)議。 D) 互聯(lián)網(wǎng)上所有可下載的軟件及數(shù)據(jù)資源都是可以合法免費(fèi)使用的。 8、關(guān)于HTML下面哪種說(shuō)法是正確的： A） HTML實(shí)現(xiàn)了文本、圖形、聲音乃至視頻信息的統(tǒng)一編碼。 B） HTML全稱(chēng)為超文本標(biāo)記語(yǔ)言。 C） 網(wǎng)上廣泛使用的 Fl

5、ash動(dòng)畫(huà)都是由HTML編寫(xiě)的。 D） HTML也是一種高級(jí)程序設(shè)計(jì)語(yǔ)言。 9、關(guān)于程序設(shè)計(jì)語(yǔ)言，下面哪個(gè)說(shuō)法是正確的： A) 加了注釋的程序一般會(huì)比同樣的沒(méi)有加注釋的程序運(yùn)行速度慢。 B) 高級(jí)語(yǔ)言開(kāi)發(fā)的程序不能使用在低層次的硬件系統(tǒng)如：自控機(jī)床或低端手機(jī)上。 C) 高級(jí)語(yǔ)言相對(duì)于低級(jí)語(yǔ)言更容易實(shí)現(xiàn)跨平臺(tái)的移植。 D) 以上說(shuō)法都不對(duì)。 10、已知大寫(xiě)字母A的ASCII編碼為65（10進(jìn)制），則大寫(xiě)字母J的10進(jìn)制ASCII編碼為： A) 71 B) 72 C) 73 D) 以上都不是 11、十進(jìn)制小數(shù)125.125對(duì)應(yīng)的8進(jìn)制數(shù)是 A)

6、100.1 B) 175.175 C) 175.1 D) 100.175 12、有六個(gè)元素FEDCBA 從左至右依次順序進(jìn)棧，在進(jìn)棧過(guò)程中會(huì)有元素被彈出棧。問(wèn)下列哪一個(gè)不可能是合法的出棧序列？ A) EDCFAB B) DECABF C) CDFEBA D) BCDAEF 13、 表達(dá)式a*(b+c)-d的后綴表達(dá)式是： A) abcd*+- B) abc+*d- C) abc*+d- D) -+*abcd 14、一個(gè)包含n個(gè)分支結(jié)點(diǎn)（非葉結(jié)點(diǎn)）的非空二叉樹(shù)，它的葉結(jié)點(diǎn)數(shù)目最多為： A) 2n + 1 B) 2n-1

7、 C) n-1 D) n+1 15、快速排序最壞情況下的算法時(shí)間復(fù)雜度為： A) O(log2n) B) O(n) C) O(nlog2n) 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) 插入排

8、序 C) 歸并排序 D) 快速排序 18、已知n個(gè)頂點(diǎn)的有向圖，若該圖是強(qiáng)連通的（從所有頂點(diǎn)都存在路徑到達(dá)其他頂點(diǎn)），則該圖中最少有多少條有向邊？ A) n B) n+1 C) n-1 D) n*(n-1) 19、全國(guó)信息學(xué)奧林匹克的官方網(wǎng)站為參與信息學(xué)競(jìng)賽的老師同學(xué)們提供相關(guān)的信息和資源，請(qǐng)問(wèn)全國(guó)信息學(xué)奧林匹克官方網(wǎng)站的網(wǎng)址是： A) B) http://www.noi.org/ C) D) 20、在參加NOI系列競(jìng)賽過(guò)程中，下面哪一種行為是 不 被嚴(yán)格禁止的： A) 攜帶書(shū)寫(xiě)工具，手表和不具有通訊功能

9、的電子詞典進(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)程以提高程序的執(zhí)行效率。 二．問(wèn)題求解（共2題，每空5分，共計(jì)10分） 1．小陳現(xiàn)有2個(gè)任務(wù)A，B要完成，每個(gè)任務(wù)分別有若干步驟如下：A=a1->a2->a3，B=b1->b2->b3->b4->b5。在任何時(shí)候，小陳只能專(zhuān)心做某個(gè)任務(wù)的一個(gè)步驟。但是如果愿意，他可以在做完手中任務(wù)的當(dāng)前步驟后，切換至另一個(gè)任務(wù)，從上次此任務(wù)第一個(gè)未做的步驟繼續(xù)。每個(gè)任務(wù)的步驟順序不能打亂，例如……a2->b2->a3->b3……

10、是合法的，而……a2->b3->a3->b2……是不合法的。小陳從B任務(wù)的b1步驟開(kāi)始做，當(dāng)恰做完某個(gè)任務(wù)的某個(gè)步驟后，就停工回家吃飯了。當(dāng)他回來(lái)時(shí)，只記得自己已經(jīng)完成了整個(gè)任務(wù)A，其他的都忘了。試計(jì)算小陳飯前已做的可能的任務(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)在要把這段程序分配到若干臺(tái)（數(shù)量充足）用電纜連接的PC上做并行執(zhí)行。每臺(tái)PC執(zhí)行其中的某幾個(gè)語(yǔ)句，并可隨時(shí)通過(guò)電纜與其他PC通訊，交換一些中間結(jié)果。假設(shè)

11、每臺(tái)PC每單位時(shí)間可以執(zhí)行一個(gè)語(yǔ)句，且通訊花費(fèi)的時(shí)間不計(jì)。則這段程序最快可以在 單位時(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分） 1． #include using namespace std; int a,b; int work(int a,int b){ if (a%b) return work(b,a%b); ret

12、urn b; } int main(){ cin >> a >> b; cout << work(a,b) << endl; return 0; } 輸入：20 12 輸出：_______ 2． #include using namespace std; int main() { int a[3],b[3]; int i,j,tmp; for (i=0;i<3;i++) cin >> b[i]; for (i=0;i<3;i++) { a[i]=0; for (j=0;j<=i;j++)

13、{ a[i]+=b[j]; b[a[i]%3]+=a[j]; } } tmp=1; for (i=0;i<3;i++) { a[i]%=10; b[i]%=10; tmp*=a[i]+b[i]; } cout << tmp << endl; return 0; } 輸入：2 3 5 輸出：_______ 3． #include using namespace std; const int c=2009; int main() { int n,p,s,i,j,t;

14、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 using namespace std; const int maxn=50; void getnext(char str[]) { int l=strlen(str),i,j,k,temp; k=l-

15、2; while(k>=0&&str[k]>str[k+1]) k--; i=k+1; while(istr[k]) i++; temp=str[k]; str[k]=str[i-1]; str[i-1]=temp; for(i=l-1;i>k;i--) for(j=k+1;jstr[j+1]) { temp=str[j]; str[j]=str[j+1]; str[j+1]=temp; } return ; } int main()

16、{ char a[maxn]; int n; cin >> a >> n; while(n>0) { getnext(a); n--; } cout << a << endl; return 0; } 輸入：NOIP 3 輸出： 四．完善程序 (前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ù)最多，并輸出這

17、個(gè)最大和以及該連續(xù)子數(shù)列中元素的個(gè)數(shù)。例如數(shù)列為4，-5，3，2，4時(shí)，輸出9和3；數(shù)列為1 2 3 -5 0 7 8時(shí)，輸出16和7。 #include using namespace std; int a[101]; int n,i,ans,len,tmp,beg; int main(){ cin >> n; for (i=1;i<=n;i++) cin >> a[i]; tmp=0; ans=0; len=0; beg= ① ; for (i=1;i<=n;i++){ if (tmp+a[i]

18、>ans){ ans=tmp+a[i]; len=i-beg; } else if ( ② &&i-beg>len) len=i-beg; if (tmp+a[i] ③ ){ beg= ④ ; tmp=0; } else ⑤ ; } cout << ans << " " << len << endl; return 0; } 2. (國(guó)王放置) 在n*m的棋盤(pán)上放置k個(gè)國(guó)王，要求k個(gè)國(guó)王互相不攻擊，有多少種不同的放置方

19、法。假設(shè)國(guó)王放置在第(x,y)格，國(guó)王的攻擊的區(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)。讀入三個(gè)數(shù)n,m,k，輸出答案。題目利用回溯法求解。棋盤(pán)行標(biāo)號(hào)為0~n-1，列標(biāo)號(hào)為0~m-1。 #include using namespace std; int n,m,k,ans; int hash[5][5]; void work(int x,int y,int tot){ int i,j; if (tot==k){ ans++;

20、 return; } do{ while (hash[x][y]){ y++; if (y==m){ x++; y= ① ; } if (x==n) return; } for (i=x-1;i<=x+1;i++) if (i>=0&&i=0&&j

21、+) if (i>=0&&i=0&&j> n >> m >> k; ans=0; memset(hash,0,sizeof(hash)); ⑤ ; cout << ans << endl; return 0; }