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

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

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

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

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

5、, 88，92， 100 進行二分查找，成功查找元素 19 的查找長度（比較次數(shù)）是（）。A. 1B. 2C. 3D. 416. 面向?qū)ο蟪绦蛟O(shè)計（ Object-Oriented Programming）是一種程序設(shè)計的方法論，它將對象作為程序的基本單元，將數(shù)據(jù)和程序封裝在對象中，以提高軟件的重用性、靈活性和擴展性。下面關(guān)于面向?qū)ο蟪绦蛟O(shè)計的說法中，不正確的是（）。A. 面向?qū)ο蟪绦蛟O(shè)計通常采用自頂向下設(shè)計方法進行設(shè)計。B. 面向?qū)ο蟪绦蛟O(shè)計方法具有繼承性（ inheritance ）、封裝性（ encapsulation ）、多態(tài)性（ polymorphism ）等幾大特點。C. 支持面向

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

7、推薦使用的語言環(huán)境的是（B. Visual C+C. free pascal）。D.Lazarus20在 C+程序中，表達(dá)式 200|10 A. 20 B. 1 C. 220的值是（ D. 202）二問題求解（共2 題，每題5 分，共計10 分）1. 書架上有 4 本不同的書 A、 B、 C、 D。其中 A 和 B 是紅皮的， C 和 D 是黑皮的。把這 4本書擺在書架上，滿足所有黑皮的書都排在一起的擺法有_種。滿足A 必須比 C 靠左，_2 有6 個城市，任何兩個城市之間都有一條道路連接，6 個城市兩兩之間的距離如下表所示，則城市1 到城市6 的最短距離為_。城市1城市2城市3城市4城市5城

8、市6城市102311215城市 2202城市 3320城市 4153城市 51236城市 615125三閱讀程序?qū)懡Y(jié)果（共4 題，每題8 分，共計1. #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

9、;elsecout c + d endl; return 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;531236507970292032 分）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)

10、 i+;while (ij&aryj0) j-;if (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_

11、m, intepos_m)int i, 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 len;cin first mid;s

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

13、母的大寫替換，S 中的 a 用該字母的小寫替換；S中的第二個字母是字母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 e

14、ndl;return 0;2.( 找第k 大的數(shù) )給定一個長度為1,000,000的無序正整數(shù)序列,以及另一個數(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;fo