noip2008 初賽普及組c++試題及答案

第十四屆全國青少年信息學奧林匹克聯(lián)賽初賽試題（普及組C++語言二小時完成）??全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效??一、 單項選擇題（共20題，每題1.5分，共計30分。每題有且僅有一個正確答案.）。1．微型計算機中，控制器的基本功能是（）。控制機器各個部件協(xié)調(diào)工作 B.實現(xiàn)算術運算和邏輯運算C.獲取外部信息 D.存放程序和數(shù)據(jù)^A=true，B=falseC=true,D=false以下邏輯運算表達式值為真的是（）。A.（aAb）V（CAdV「A） B.（（「aAb）VC）A「Dc.（bVcVd）AdAa d.aA（dV「C）Ab在下列關于圖靈獎的說法中，不正確的是（）。圖靈獎是美國計算機協(xié)會于1966年設立的，專門獎勵那些對計算機事業(yè)作出重要貢獻的個人圖靈獎有“計算機界諾貝爾獎”之稱迄今為止，還沒有華裔計算機科學家獲此殊榮圖靈獎的名稱取自計算機科學的先驅、英國科學家阿蘭?圖靈4．計算機在工作過程中，若突然停電（，）中的信息不會丟失。A.ROM和RAMB.CPU C.ROMD.RAM完全二叉樹共有2*N-1個結點，則它的葉節(jié)點數(shù)是（）。A.N-1 B.N C.2*N D.2N-1在以下各項中，（）不是操作系統(tǒng)軟件。A.SolarisB.Linux C.WindowsVista D.Sybase設棧S的初始狀態(tài)為空，元素a,b,c,d,e,f依次入棧S,出棧的序列為o,d,f,e,c,a,則棧S的容量至少應該是（）。A.6 B.5 C.4 D.3與十進制數(shù)28.5625相等的四進制數(shù)是（）。A.123.21 B.131.22 C.130.22 D.130.21設字符串S=^Olympidr,,S的非空子串的數(shù)目是（）。A.28B.29 C.16 D.17Web2.0是近年來互聯(lián)網(wǎng)的熱門概念之一，其核心思想是互動與分享。下列網(wǎng)站中，)是典型的Web2.0應用。A.Sina B.Flickr C.Yahoo D.Google遞歸過程或函數(shù)調(diào)用時，處理參數(shù)和返回地址，通常使用一種稱為()的數(shù)據(jù)結構。A.隊列B.多維數(shù)組C.線性表D.棧12.(2008)10+(5B)16的結果是(16)。A.(833)16B.(2089)10C.(4163)8D.(100001100011)2二叉樹T,已知其先根遍歷是L243576(數(shù)字為結點的編號，以下同)中根遍歷是2415736，則該二叉樹的后根遍歷是()。A.4257631 B.4275631C.7425631 D.4276531將數(shù)組｛8,23,4,16,77,-5,53,100中｝的元素按從大到小的順序排列，每次可以交換任意兩個元素，最少需要交換()次。A.4 B.5 C.6 D.7對有序數(shù)組｛5,13,19,21,37,56,64,75,8，892，100｝進行二分查找，成功查找元素19的查找長度(比較次數(shù))是()。A.1 B.2 C.3 D.4面向對象程序設計Object-OrientedProgramming是一種程序設計的方法論，它將對象作為程序的基本單元，將數(shù)據(jù)和程序封裝在對象中，以提高軟件的重用性、靈活性和擴展性。下面關于面向對象程序設計的說法中，不正確的是()。面向對象程序設計通常采用自頂向下設計方法進行設計。面向對象程序設計方法具有繼承性(inheritance)、封裝性(encapsulation)＞多態(tài)性(polymorphism)等幾大特點。支持面向對象特性的語言稱為面向對象的編程語言，目前較為流行的有、JAVA、C#等。面向對象的程序設計的雛形來自于Simula語言，后來在SmallTalk語言的完善和標準化的過程中得到更多的擴展和對以前思想的重新注解。至今mallTalk語言仍然被視為面向對象語言的基礎。在32*32點陣的“字庫”中，漢字“北”與“京”的字模占用字節(jié)數(shù)之和是(。A.512 B.256 C.384 D.128

設T是一棵有n個頂點的樹，下列說法不正確的是（）。A.T有n條邊 B.T是連通的C.T是無環(huán)的 D.T有n-1條邊下列不屬于NOIP競賽推薦使用的語言環(huán)境的是（）。A.Dev-C++B.VisualC++C.freepascalD.LazarusA.Dev-C++B.VisualC++C.freepascalD.Lazarus在C++程序中，表達式200|10的值是（）A.20 B.1 C.220 D.202問題求解（共2題，每題5分，共計10分）書架上有4本不同的書A、B、C、D。其中A和B是紅皮的，C和D是黑皮的。把這!本書擺在書架上，滿足所有黑皮的書都排在一起的擺法有__J種。滿足A必須比C靠左，所有紅皮的書要擺放在一起，所有黑皮的書要擺放在一起，共_有 種擺法。有6個城市，任何兩個城市之間都有一條道路連接6，個城市兩兩之間的距離如下表所示，則城市1到城市6的最短距離為 。城市1城市2城市3城市4城市5城市6城市102311215城市22025312城市3320365城市4153079城市51236702城市615125920閱讀程序寫結果（共4題，每題8分，共計32分）#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輸出： #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.(字符串替換)給定一個字符串S(S僅包含大小寫字母)，下面的程序將S中的每個字母用規(guī)定的字母替換，并輸出S經(jīng)過替換后的結果。程序的輸入是兩個字符串，第一個字符串是給定的字符串第二個字符串S'由26個字母組成，它是a-z的任一排列，大小寫不定,S'規(guī)定了每個字母對應的替換字母：S'中的第一個字母是字母和a的替換字母，即S中的A用該字母的大寫替換,S中的a用該字母的小寫替換；'中的第二個字母是字母和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;}（找第k大的數(shù)）給定一個長度為1,000,000的無序正整數(shù)序列,以及另一個數(shù)（1<=n<=1000000）,然后以類似快速排序的方法找到序列中第大的數(shù)（關于第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 ⑥ returni;}intmain(){inti；intm=1000000；for(i=1；i<=m；i++)cin>>a[i];cin>>n;ans=FindKth（1,m,n）;cout<<a[ans];return0;}NOIP2008年普及組（C++語言）參考答案與評分標準、單項選擇題：（每題1.5分）1.A2.B3.C4.C5.B6.D7.C8.D9.A10.B11.D12.A13.B14.B15.B16.A17.B18.A19.B20.D二、問題求解：（共2題，每題5分，共計10分）1．1242．7（1->2->5->6）三、閱讀程序寫結果（共4題，每題8分，共計32分）1.232.2,3,13.54101622-59-6-11-64.DBGEFCA（求樹的后序遍歷）四．完善程序(前4空，每空2.5分，后6空，每空3分，共28分)(說明：以下各程序填空可能還有一些等價的寫法，各省可請本省專家審定和上機