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

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

2、不正確的是（）。A. 圖靈獎是美國計算機協(xié)會于1966 年設(shè)立的，專門獎勵那些對計算機事業(yè)作出重要貢獻(xiàn)的個人B. 圖靈獎有“計算機界諾貝爾獎”之稱C. 迄今為止，還沒有華裔計算機科學(xué)家獲此殊榮D. 圖靈獎的名稱取自計算機科學(xué)的先驅(qū)、英國科學(xué)家阿蘭·圖靈4計算機在工作過程中，若突然停電，（）中的信息不會丟失。A.ROM和5完全二叉樹共有2*N-1 個結(jié)點，則它的葉節(jié)點數(shù)是（）。N-16. 在以下各項中，（）不是操作系統(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 是近年來互聯(lián)網(wǎng)的熱門概念之一，其核心思想是互動與分享。下列網(wǎng)站中，（）是典型的Web2.0 應(yīng)用。11遞歸過程或函數(shù)調(diào)用時，處理參數(shù)和返回地址，通常使用一種稱為（）的數(shù)據(jù)結(jié)構(gòu)。A. 隊列 B. 多維數(shù)組 C. 線性表 D.棧12.(2008)10+(5B) 16 的結(jié)果是（）。A.(833)16B.(2089)10C.(4163)8D.(100001100011)213. 二叉樹 T，已知其先根遍歷是 1243576 （數(shù)字為結(jié)點的編號，以下同），中根遍歷是

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

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

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

7、個城市兩兩之間的距離如下表所示，則城市 1 到城市 6 的最短距離為 _。城市 1城市 2城市 3城市 4城市 5城市 6城市 102311215城市 22025312城市 3320365城市 4153079城市 51236702城市 615125920三閱讀程序?qū)懡Y(jié)果（共4 題，每題8 分，共計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（字符串替換）給定一個字符串S（ S 僅包含大小寫字母），下面的程序?qū)中的每個字母用規(guī)定的字母替換，并輸出S 經(jīng)過替換后的結(jié)果。程序的輸入是兩個字符串，第一個字符串是給定的字符串S，第二個字符串S由 26 個字母組成，它是a-z的任一排列，大小寫不定，S規(guī)定了每個字母對應(yīng)的替換字母

13、：S中的第一個字母是字母 A 和 a 的替換字母，即S 中的 A 用該字母的大寫替換，S 中的 a 用該字母的小寫替換； S中的第二個字母是字母B 和 b 的替換字母，即S 中的 B 用該字母的大寫替換， S中的 b 用該字母的小寫替換； 以此類推。#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ù) ) 給定一個長度為 1,000,000 的無序正整數(shù)序列 , 以及另一個數(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二問題解答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'(只寫 changei?<=?'Z'