NOI新編初賽普及組C++題目及答案精編

第 十 四 屆 全 國 青 少 年 信 息 學(xué) 奧 林 匹 克 聯(lián) 賽 初 賽 試 題 2 0 0 8（普及組 C++語言二小時(shí)完成）● ●全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效 ●●一、單項(xiàng)選擇題（共 20題，每題 1.5分，共計(jì) 30分。每題有且僅有一個(gè)正確答案1．微型計(jì)算機(jī)中，控制器的基本功能是（）。A.控制機(jī)器各個(gè)部件協(xié)調(diào)工作 B.實(shí)現(xiàn)算術(shù)運(yùn)算和邏輯運(yùn)算C.獲取外部信息 D.存放程序和數(shù)據(jù)2.設(shè)A=true，B=false，C=true，D=false，以下邏輯運(yùn)算表達(dá)式值為真的是（）。A.(A∧B)∨(C∧D∨ A)B.(( A∧B)∨C)∧ D

.）。C.(B∨C∨D)∧D∧AD.A∧(D∨

C)∧B在下列關(guān)于圖靈獎(jiǎng)的說法中，不正確的是（）。A.圖靈獎(jiǎng)是美國計(jì)算機(jī)協(xié)會(huì)于 1966年設(shè)立的，專門獎(jiǎng)勵(lì)那些對計(jì)算機(jī)事業(yè)作出重要貢獻(xiàn)的個(gè)人圖靈獎(jiǎng)有“計(jì)算機(jī)界諾貝爾獎(jiǎng)”之稱迄今為止，還沒有華裔計(jì)算機(jī)科學(xué)家獲此殊榮圖靈獎(jiǎng)的名稱取自計(jì)算機(jī)科學(xué)的先驅(qū)、英國科學(xué)家阿蘭·圖靈4．計(jì)算機(jī)在工作過程中，若突然停電，（）中的信息不會(huì)丟失。5．完全二叉樹共有 2*N-1個(gè)結(jié)點(diǎn)，則它的葉節(jié)點(diǎn)數(shù)是（）。N-1在以下各項(xiàng)中，（）不是操作系統(tǒng)軟件。WindowsVistaD.Sybase7．設(shè)棧S的初始狀態(tài)為空，元素 a，b，c，d，e，fc，a，則棧S的容量至少應(yīng)該是（）。

依次入棧

S，出棧的序列為

b，d，f，e，

與十進(jìn)制數(shù)28.5625相等的四進(jìn)制數(shù)是（）。131.22 C設(shè)字符串S=”O(jiān)lympic”，S的非空子串的數(shù)目是（）。10．Web2.0是近年來互聯(lián)網(wǎng)的熱門概念之一，其核心思想是互動(dòng)與分享。下列網(wǎng)站中，（）是典型的Web2.0應(yīng)用。11．遞歸過程或函數(shù)調(diào)用時(shí)，處理參數(shù)和返回地址，通常使用一種稱為（）的數(shù)據(jù)結(jié)構(gòu)。A.隊(duì)列B.多維數(shù)組C.線性表D.棧12.(2008)10+(5B)16的結(jié)果是（）。A.(833)16B.(2089)10C.(4163)8D.(100001100011)2二叉樹T，已知其先根遍歷是1243576（數(shù)字為結(jié)點(diǎn)的編號，以下同），中根遍歷是2415736，則該二叉樹的后根遍歷是（）。14．將數(shù)組{8,23,4,16,77,-5,53,100} 中的元素按從大到小的順序排列，每次可以交換任意兩個(gè)元素，最少需要交換（）次。 15．對有序數(shù)組{5,13,19,21,37,56,64,75,88，92，100}進(jìn)行二分查找，成功查找元素19的查找長度（比較次數(shù)）是（）。 面向?qū)ο蟪绦蛟O(shè)計(jì)（Object-OrientedProgramming）是一種程序設(shè)計(jì)的方法論，它將對象作為程序的基本單元，將數(shù)據(jù)和程序封裝在對象中，以提高軟件的重用性、靈活性和擴(kuò)展性。下面關(guān)于面向?qū)ο蟪绦蛟O(shè)計(jì)的說法中，不正確的是（）。面向?qū)ο蟪绦蛟O(shè)計(jì)通常采用自頂向下設(shè)計(jì)方法進(jìn)行設(shè)計(jì)。面向?qū)ο蟪绦蛟O(shè)計(jì)方法具有繼承性（inheritance）、封裝性（encapsulation）、多態(tài)性（polymorphism）等幾大特點(diǎn)。C.支持面向?qū)ο筇匦缘恼Z言稱為面向?qū)ο蟮木幊陶Z言，目前較為流行的有 C++、JAVA、C#等。D.面向?qū)ο蟮某绦蛟O(shè)計(jì)的雛形來自于 Simula語言，后來在 SmallTalk 語言的完善和標(biāo)準(zhǔn)化的過程中得到更多的擴(kuò)展和對以前思想的重新注解。至今， SmallTalk 語言仍然被視為面向?qū)ο笳Z言的基礎(chǔ)。在32*32點(diǎn)陣的“字庫”中，漢字“北”與“京”的字模占用字節(jié)數(shù)之和是（）。 設(shè)T是一棵有n個(gè)頂點(diǎn)的樹，下列說法不正確的是（）。A.T有n條邊B.T是連通的C.T是無環(huán)的D.T有n-1條邊下列不屬于NOIP競賽推薦使用的語言環(huán)境的是（）。20．在C++程序中，表達(dá)式 200|10的值是（） 二．問題求解（共 2題，每題 5分，共計(jì) 10分）書架上有4本不同的書A、B、C、D。其中A和B是紅皮的，C和D是黑皮的。把這4本書擺在書架上，滿足所有黑皮的書都排在一起的擺法有_____種。滿足A必須比C靠左，所有紅皮的書要擺放在一起，所有黑皮的書要擺放在一起，共有______種擺法。2．有6個(gè)城市，任何兩個(gè)城市之間都有一條道路連接，6個(gè)城市兩兩之間的距離如下表所示，則城市1到城市6的最短距離為_____________。城市1城市2城市3城市4城市5城市6城市102311215城市22025312城市3320365城市4153079城市51236702城市615125920三．閱讀程序?qū)懡Y(jié)果（共 4題，每題 8分，共計(jì) 32分）1.#include<iostream>usingnamespacestd;intmain(){inti,a,b,c,d,f[4];for(i=0;i<4;i++)cin>>f[i];a=f[0]+f[1]+f[2]+f[3];a=a/f[0];b=f[0]+f[2]+f[3];b=b/a;c=(b*f[1]+a)/f[2];d=f[(b/c)%4];if(f[(a+b+c+d)%4]>f[2])cout<<a+b<<endl;elsecout<<c+d<<endl;return0;}輸入：9192939輸出：_______________2．#include<iostream>usingnamespacestd;voidfoo(inta,intb,intc){if(a>b)foo(c,a,b);elsecout<<a<<','<<b<<','<<c<<endl;}intmain(){inta,b,c;cin>>a>>b>>c;foo(a,b,c);return0;}輸入:312輸出:__________3．#include<iostream>usingnamespacestd;voidfunc(intary[],intn){inti=0,j,x;j=n-1;while(i<j){while(i<j&&ary[i]>0)i++;while(i<j&&ary[j]<0)j--;if(i<j){x=ary[i];ary[i++]=ary[j];ary[j--]=x;}}}intmain(){inta[20],i,m;m=10;for(i=0;i<m;i++){cin>>a[i];}func(a,m);for(i=0;i<m;i++)cout<<a[i]<<"";cout<<endl;return0;}輸入：54-6-116-5922-6110輸出：____________________________________4.#include<iostream>#include<cstring>usingnamespacestd;#defineMAX100voidsolve(charfirst[],intspos_f,intepos_f,charmid[],intspos_m,intepos_m){inti,root_m;if(spos_f>epos_f)return;for(i=spos_m;i<=epos_m;i++)if(first[spos_f]==mid[i]){root_m=i;break;}solve(first,spos_f+1,spos_f+(root_m-spos_m),mid,spos_m,root_m-1);solve(first,spos_f+(root_m-spos_m)+1,epos_f,mid,root_m+1,epos_m);cout<<first[spos_f];}intmain(){charfirst[MAX],mid[MAX];intlen;cin>>len;cin>>first>>mid;solve(first,0,len-1,mid,0,len-1);cout<<endl;return0;}輸入：

7ABDCEGFBDAGECF輸出：

____________________________________四．完善程序

(前

4空，每空

2.5分，后

6空，每空

3分，共

28分)1．（字符串替換） 給定一個(gè)字符串

S（S僅包含大小寫字母），下面的程序?qū)?/p>

S中的每個(gè)字母用規(guī)定的字母替換，并輸出

S經(jīng)過替換后的結(jié)果。程序的輸入是兩個(gè)字符串，第一個(gè)字符串是給定的字符串

S，第二個(gè)字符串

S’由

26個(gè)字母組成，它是

a-z

的任一排列，大小寫不定，

S’規(guī)定了每個(gè)字母對應(yīng)的替換字母：

S’中的第一個(gè)字母是字母

A和

a的替換字母，即

S中的

A用該字母的大寫替換，

S中的

a用該字母的小寫替換；

S’中的第二個(gè)字母是字母

B和

b的替換字母，即S中的

B用該字母的大寫替換，

S中的

b用該字母的小寫替換；??以此類推。#include<iostream>#include<string.h>charchange[26],str[5000];usingnamespacestd;voidCheckChangeRule(){inti;for(i=0;i<26;i++){if( ①)change[i]-='A'-'a';}}voidChangeString(){inti;for(i=0;i<strlen(str);i++){if( ②)str[i]=change[str[i]-'A']-'a'+'A';else③}}intmain(){inti;cin>>str;cin>>change;CheckChangeRule();④cout<<str<<endl;return0;}2. (

找第

k 大的數(shù))

給定一個(gè)長度為

1,000,000

的無序正整數(shù)序列,

以及另一個(gè)數(shù)n(1<=n<=1000000),

然后以類似快速排序的方法找到序列中第

n大的數(shù)（關(guān)于第

n大的數(shù)：例如序列{1，2，3，4，5，6}中第

3大的數(shù)是

4）。#include<iostream>usingnamespacestd;inta[1000001],n,ans=-1;voidswap(int&a,int&b){intc;c=a;a=b;

b=c;}intFindKth(intleft,intright,intn){inttmp,value,i,j;if(left==right)returnleft;tmp=rand()%(right-left)+left;swap(a[tmp],a[left]);value=①i=left;j=right;while(i<j){while(i<j&& ②)j--;if(i<j){a[i]=a[j];i++;}elsebreak;while(i<j&& ③)i++;if(i<j){a[j]=a[i];j--;}elsebreak;}④if(i<n)returnFindKth( ⑤);if(i>n)return ⑥r(nóng)eturni;}intmain(){inti;intm=1000000;for(i=1;i<=m;i++)cin>>a[i];cin>>n;ans=FindKth(1,m,n);cout<<a[ans];return0;}參考答案一． 選擇題ABCCBDCDABDABBBABABD二． 問題解答1247三． 閱讀程序232.,3,15?4?10?1?6?22?-59?-6?-11?-64.?DBGEFCA?四．完善程序1.（1）change[i]?>=?'A'?&&?ch