P最新初賽普及組++題目及答案

1、第十四屆全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽初賽試題2008（ 普及組C+ 語言二小時(shí)完成）全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效一、 單項(xiàng)選擇題（共 20 題，每題分，共計(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)(CDA)B. (AB)C)D. ）。）。C. (BCD)DAD. A (DC)B3.在下列關(guān)于圖靈獎(jiǎng)的說法中，不正確的是（）

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

3、d，e， f 依次入棧 S，出棧的序列為b， d， f ，e， c， a，則棧 S 的容量至少應(yīng)該是（）。A. 6B. 5C. 4D. 38.與十進(jìn)制數(shù)相等的四進(jìn)制數(shù)是（）。A.B. 131.22C.D.9.設(shè)字符串 S=” Olympic ”， S的非空子串的數(shù)目是（）。A. 28B. 29C. 16D. 1710是近年來互聯(lián)網(wǎng)的熱門概念之一，其核心思想是互動(dòng)與分享。下列網(wǎng)站中，（）是典型的應(yīng)用。A. SinaB. FlickrC. YahooD. Google11 遞歸過程或函數(shù)調(diào)用時(shí)，處理參數(shù)和返回地址，通常使用一種稱為（）的數(shù)據(jù)結(jié)構(gòu)。A. 隊(duì)列B.多維數(shù)組C.線性表D.棧12. (20

4、08)10 + (5B)16 的結(jié)果是（）。A. (833)16B. (2089)10C. (4163)8D. ()213. 二叉樹 T，已知其先根遍歷是1 243576（數(shù)字為結(jié)點(diǎn)的編號(hào)，以下同），中根遍歷是 2415736，則該二叉樹的后根遍歷是（）。A.4257631B.4275631C.7425631D.427653114將數(shù)組 8, 23, 4, 16, 77, -5, 53, 100中的元素按從大到小的順序排列，每次可以交換任意兩個(gè)元素，最少需要交換（）次。A. 4B. 5C. 6D. 715 對(duì)有序數(shù)組 5, 13, 19, 21, 37, 56, 64, 75, 88，92，

5、100 進(jìn)行二分查找，成功查找元素 19 的查找長(zhǎng)度（比較次數(shù)）是（）。A. 1B. 2C. 3D. 416. 面向?qū)ο蟪绦蛟O(shè)計(jì)（ Object-Oriented Programming）是一種程序設(shè)計(jì)的方法論，它將對(duì)象作為程序的基本單元，將數(shù)據(jù)和程序封裝在對(duì)象中，以提高軟件的重用性、靈活性和擴(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)。支持面向?qū)ο筇匦缘恼Z言稱為面向?qū)ο蟮木幊陶Z言

6、，目前較為流行的有C+、 JAVA、C#等。D. 面向?qū)ο蟮某绦蛟O(shè)計(jì)的雛形來自于 Simula 語言，后來在準(zhǔn)化的過程中得到更多的擴(kuò)展和對(duì)以前思想的重新注解。至今，SmallTalkSmallTalk語言的完善和標(biāo)語言仍然被視為面向?qū)ο笳Z言的基礎(chǔ)。17.在A. 51232*32點(diǎn)陣的“字庫”中，漢字“北”與“京”的字模占用字節(jié)數(shù)之和是（ B. 256 C. 384 D. 128）。18.設(shè)T 是一棵有n 個(gè)頂點(diǎn)的樹，下列說法不正確的是（）。A. T有 n 條邊B. T是連通的C. T是無環(huán)的D. T有n-1條邊19.下列不屬于 A. Dev-C+NOIP競(jìng)賽推薦使用的語言環(huán)境的是（B. Vis

7、ual C+C. free pascal）。D.Lazarus20在 C+程序中，表達(dá)式 200|10 A. 20 B. 1 C. 220的值是（ D. 202）二問題求解（共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城市 2202城

8、市 3320城市 4153城市 51236城市 615125三閱讀程序?qū)懡Y(jié)果（共4 題，每題8 分，共計(jì)#include using namespace std; int main()int i, a, b, c, d, f4;for(i = 0; i fi; a = f0 + f1 + f2 + f3;a = a / f0;b = f0 + f2 + f3; b = b / a;c = (b * f1 + a) / f2; d = f(b / c ) % 4;if(f(a + b + c + d) % 4 f2) cout a + b endl;elsecout c + d endl; re

9、turn 0;輸入： 9 19 29 39輸出： _2 #includeusing namespace std;void foo(int a, int b, int c)if(a b)foo(c, a, b);elsecouta,b,c a b c;5312365079702920分）foo(a, b, c);return 0;輸入:312輸出 : _3 #include using namespace std;void func(int ary, int n )int i=0, j, x;j=n-1;while(ij)while (i0) i+;while (ij&aryj0) j-;if

10、(ij)x=aryi;aryi+=aryj;aryj-=x;int main()int a20, i, m;m=10;for(i=0; iai;func(a, m);for (i=0; im; i+)coutai ;cout endl;return 0;輸入：54-6-116-5922-6110輸出： _4. #include#includeusing namespace std;#define MAX 100void solve(char first, int spos_f, int epos_f, char mid, int spos_m, intepos_m)int i, root_m;

11、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 len;cin first mid;solve(first, 0, len - 1, mid

12、 , 0, len - 1);cout endl;return 0;輸入：7ABDCEGFBDAGECF輸出： _四完善程序( 前 4 空，每空分，后6 空，每空3 分，共 28 分 )1（字符串替換）給定一個(gè)字符串S（ S 僅包含大小寫字母），下面的程序?qū) 中的每個(gè)字母用規(guī)定的字母替換，并輸出S 經(jīng)過替換后的結(jié)果。程序的輸入是兩個(gè)字符串，第一個(gè)字符串是給定的字符串S，第二個(gè)字符串S由 26 個(gè)字母組成，它是a-z 的任一排列，大小寫不定， S規(guī)定了每個(gè)字母對(duì)應(yīng)的替換字母：S中的第一個(gè)字母是字母A 和 a 的替換字母，即S中的 A 用該字母的大寫替換，S 中的 a 用該字母的小寫替換；S中的

13、第二個(gè)字母是字母B和 b 的替換字母，即S 中的 B 用該字母的大寫替換，S 中的 b 用該字母的小寫替換；以此類推。#include #include char change26, str5000;using namespace std;void CheckChangeRule()int i;for (i = 0;i 26;i +)if ()changei -= A - a;void ChangeString()int i;for (i = 0;i str ;cin change;CheckChangeRule();cout str endl;return 0;2.( 找第k 大的數(shù) )給定

14、一個(gè)長(zhǎng)度為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 using namespace std;int a1000001,n,ans = -1;void swap(int &a,int &b)int c;c = a; a = b;b = c;int FindKth(int left, int right, int n)int tmp,value,i,j;if (left = right) return left;tmp = rand()% (right - left) + left;swap(atmp,aleft);value =i = left;j = right;while (i j)while (i j &) j -;if (i j) ai = aj; i +; else break;while (i j &) i +;if (i j) aj = ai; j - -; else break;if (i n) returnreturn i;int main()int i;int m = 1000000;for