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

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

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

3、十進制數(shù) 28.5625 相等的四進制數(shù)是（）。9. 設字符串 S=”O(jiān)lympic ”， S的非空子串的數(shù)目是（）。10 Web2.0 是近年來互聯(lián)網(wǎng)的熱門概念之一，其核心思想是互動與分享。下列網(wǎng)站中，（）是典型的Web2.0 應用。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 進行二分查找，成功查找元素 19 的查找長度（比較次數(shù)）是（）。16. 面向?qū)ο蟪绦蛟O計（ Object-OrientedProgramming ）是一種程序設計的方法論，它將對象作為程序的基本單元，將數(shù)據(jù)和程序封裝在對象中，以提高軟件的重用性、靈活性和擴展性。下面關于面向?qū)ο蟪绦蛟O計的說法中，不正確的是（）。A. 面向?qū)ο蟪绦蛟O計

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

6、 個頂點的樹，下列說法不正確的是（）。A.T 有 n 條邊 B.T 是連通的 C.T 是無環(huán)的 D.T 有 n-1 條邊19. 下列不屬于 NOIP競賽推薦使用的語言環(huán)境的是（）。20在 C+程序中，表達式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ī)定了每個字母對應的替換字母

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ù)（關于第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'