NOIP初賽普及組C題目及答案

1、第十四屆全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽初賽試題2008（普及組C+語(yǔ)言二小時(shí)完成）全部試題答案均要求寫(xiě)在答卷紙上，寫(xiě)在試卷紙上一律無(wú)效一、單項(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 DA)B.(AB) C)DC.(B C D) D AD.A (DC) B3. 在下列關(guān)于圖靈獎(jiǎng)的說(shuō)法中，

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

3、十進(jìn)制數(shù) 28.5625 相等的四進(jìn)制數(shù)是（）。9. 設(shè)字符串 S=”O(jiān)lympic ”， S的非空子串的數(shù)目是（）。10 Web2.0 是近年來(lái)互聯(lián)網(wǎng)的熱門(mén)概念之一，其核心思想是互動(dòng)與分享。下列網(wǎng)站中，（）是典型的Web2.0 應(yīng)用。11遞歸過(guò)程或函數(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)213. 二叉樹(shù) T，已知其先根遍歷是 1243576 （數(shù)字為結(jié)點(diǎn)的編號(hào)，以下同），中根遍歷是

4、 2415736，則該二叉樹(shù)的后根遍歷是（）。14 將數(shù)組 8,23,4,16,77,-5,53,100 中的元素按從大到小的順序排列，每次可以交換任意兩個(gè)元素，最少需要交換（）次。15對(duì)有序數(shù)組 5,13,19,21,37,56,64,75,88， 92，100 進(jìn)行二分查找，成功查找元素 19 的查找長(zhǎng)度（比較次數(shù)）是（）。16. 面向?qū)ο蟪绦蛟O(shè)計(jì)（ Object-OrientedProgramming ）是一種程序設(shè)計(jì)的方法論，它將對(duì)象作為程序的基本單元，將數(shù)據(jù)和程序封裝在對(duì)象中，以提高軟件的重用性、靈活性和擴(kuò)展性。下面關(guān)于面向?qū)ο蟪绦蛟O(shè)計(jì)的說(shuō)法中，不正確的是（）。A. 面向?qū)ο蟪绦蛟O(shè)計(jì)

5、通常采用自頂向下設(shè)計(jì)方法進(jìn)行設(shè)計(jì)。B. 面向?qū)ο蟪绦蛟O(shè)計(jì)方法具有繼承性（inheritance ）、封裝性（ encapsulation ）、多態(tài)性（ polymorphism ）等幾大特點(diǎn)。C. 支持面向?qū)ο筇匦缘恼Z(yǔ)言稱為面向?qū)ο蟮木幊陶Z(yǔ)言，目前較為流行的有C+、JAVA、C#等。D. 面向?qū)ο蟮某绦蛟O(shè)計(jì)的雛形來(lái)自于Simula語(yǔ)言，后來(lái)在SmallTalk語(yǔ)言的完善和標(biāo)準(zhǔn)化的過(guò)程中得到更多的擴(kuò)展和對(duì)以前思想的重新注解。至今，SmallTalk語(yǔ)言仍然被視為面向?qū)ο笳Z(yǔ)言的基礎(chǔ)。17. 在 32*32 點(diǎn)陣的“字庫(kù)”中，漢字“北”與“京”的字模占用字節(jié)數(shù)之和是（）。18. 設(shè) T 是一棵有 n

6、 個(gè)頂點(diǎn)的樹(shù)，下列說(shuō)法不正確的是（）。A.T 有 n 條邊 B.T 是連通的 C.T 是無(wú)環(huán)的 D.T 有 n-1 條邊19. 下列不屬于 NOIP競(jìng)賽推薦使用的語(yǔ)言環(huán)境的是（）。20在 C+程序中，表達(dá)式200|10 的值是（）二問(wèn)題求解（共2 題，每題5 分，共計(jì)10 分）1. 書(shū)架上有 4 本不同的書(shū) A、 B、C、 D。其中 A 和 B 是紅皮的， C 和 D 是黑皮的。把這 4 本書(shū)擺在書(shū)架上，滿足所有黑皮的書(shū)都排在一起的擺法有_種。滿足 A 必須比 C 靠左，所有紅皮的書(shū)要擺放在一起，所有黑皮的書(shū)要擺放在一起，共有_種擺法。2 有 6 個(gè)城市，任何兩個(gè)城市之間都有一條道路連接，6

7、個(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,f4;for(i=0;i<4;i+)cin>>fi;a=f0+f1+f2+f3;a=a/f0;b=f0+f2+f3;b=b/a;c=(b*f1

8、+a)/f2;d=f(b/c)%4;if(f(a+b+c+d)%4>f2)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;in

9、tmain()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&&aryi>0)i+;while(i<j&&aryj<0)j-;if(i<j)x=aryi;aryi+=aryj;aryj-=x;intmain()inta20,i,m;m

10、=10;for(i=0;i<m;i+)cin>>ai;func(a,m);for(i=0;i<m;i+)cout<<ai<<""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)in

11、ti,root_m;if(spos_f>epos_f)return;for(i=spos_m;i<=epos_m;i+)if(firstspos_f=midi)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<<firstspos_f;intmain()charfirstMAX,midMAX;intlen;cin>&g

12、t;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 僅包含大小寫(xiě)字母），下面的程序?qū)中的每個(gè)字母用規(guī)定的字母替換，并輸出S 經(jīng)過(guò)替換后的結(jié)果。程序的輸入是兩個(gè)字符串，第一個(gè)字符串是給定的字符串S，第二個(gè)字符串S由 26 個(gè)字母組成，它是a-z的任一排列，大小寫(xiě)不定，S規(guī)定了每個(gè)字母對(duì)應(yīng)的替換字母

13、：S中的第一個(gè)字母是字母 A 和 a 的替換字母，即S 中的 A 用該字母的大寫(xiě)替換，S 中的 a 用該字母的小寫(xiě)替換； S中的第二個(gè)字母是字母B 和 b 的替換字母，即S 中的 B 用該字母的大寫(xiě)替換， S中的 b 用該字母的小寫(xiě)替換； 以此類推。#include<iostream>#include<string.h>charchange26,str5000;usingnamespacestd;voidCheckChangeRule()inti;for(i=0;i<26;i+)if( )changei-='A'-'a'voidCh

14、angeString()inti;for(i=0;i<strlen(str);i+)if( )stri=changestri-'A'-'a'+'A'elseintmain()inti;cin>>str;cin>>change;CheckChangeRule();cout<<str<<endl;return0;2. ( 找第 k 大的數(shù) ) 給定一個(gè)長(zhǎng)度為 1,000,000 的無(wú)序正整數(shù)序列 , 以及另一個(gè)數(shù)n(1<=n<=1000000),然后以類似快速排序的方法找到序列中第n

15、大的數(shù)（關(guān)于第n 大的數(shù)：例如序列1 ， 2， 3，4， 5， 6 中第3 大的數(shù)是4）。#include<iostream>usingnamespacestd;inta1000001,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(atmp,aleft);value= i=left;j=right;whi

16、le(i<j)while(i<j&& )j-;if(i<j)ai=aj;i+;elsebreak;while(i<j&& )i+;if(i<j)aj=ai;j-;elsebreak;if(i<n)returnFindKth();if(i>n)returnreturni;intmain()inti;intm=1000000;for(i=1;i<=m;i+)cin>>ai;cin>>n;ans=FindKth(1,m,n);cout<<aans;return0;參考答案一選擇題ABCCBDCDABDABBBABABD二問(wèn)題解答1. 1242. 7三閱讀程序1.232.2.,3,13.5?4?10?1?6?22?-59?-6?-11?-64.?DBGEFCA?四完善程序1.（ 1） changei?>=?'A'?&&?changei?<=?'Z'(只寫(xiě) changei?<=?'Z'