資源簡介

第十四屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽試題
（ 普及組 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∧D∨A) B. ((A∧B)∨C)∧D
C. (B∨C∨D)∧D∧A D. A∧(D∨C)∧B
3. 在下列關(guān)于圖靈獎的說法中，不正確的是（ ）。
A. 圖靈獎是美國計算機協(xié)會于1966年設(shè)立的，專門獎勵那些對計算機事業(yè)作出重要貢獻(xiàn)的個人
B. 圖靈獎有“計算機界諾貝爾獎”之稱
C. 迄今為止，還沒有華裔計算機科學(xué)家獲此殊榮
D. 圖靈獎的名稱取自計算機科學(xué)的先驅(qū)、英國科學(xué)家阿蘭·圖靈
4．計算機在工作過程中，若突然停電，（ ）中的信息不會丟失。
A. ROM和RAM B. CPU C.ROM D. RAM
5．完全二叉樹共有2*N-1個結(jié)點，則它的葉節(jié)點數(shù)是（ ）。
A. N-1 B. N C. 2*N D. 2N-1
6. 在以下各項中，（ ）不是操作系統(tǒng)軟件。
A. Solaris B. Linux C. Windows Vista D. Sybase
7．設(shè)棧S的初始狀態(tài)為空，元素a，b，c，d，e，f依次入棧S，出棧的序列為b，d，f，e，c，a，則棧S的容量至少應(yīng)該是（ ）。
A. 6 B. 5 C. 4 D. 3
8. 與十進(jìn)制數(shù)28.5625相等的四進(jìn)制數(shù)是（ ）。
A. 123.21 B. 131.22 C. 130.22 D. 130.21
9. 設(shè)字符串S=”O(jiān)lympic”，S的非空子串的數(shù)目是（ ）。
A. 28 B. 29 C. 16 D. 17
10．Web2.0是近年來互聯(lián)網(wǎng)的熱門概念之一，其核心思想是互動與分享。下列網(wǎng)站中，（ ）是典型的Web2.0應(yīng)用。
A. Sina B. Flickr C. Yahoo D. Google
11． 遞歸過程或函數(shù)調(diào)用時，處理參數(shù)和返回地址，通常使用一種稱為（ ）的數(shù)據(jù)結(jié)構(gòu)。
A. 隊列 B. 多維數(shù)組 C. 線性表 D. 棧
12. (2008)10 + (5B)16的結(jié)果是（ ）。
A. (833)16 B. (2089)10 C. (4163)8 D. (100001100011)2
13. 二叉樹T，已知其先根遍歷是1 2 4 3 5 7 6（數(shù)字為結(jié)點的編號，以下同），中根遍歷是2 4 1 5 7 3 6，則該二叉樹的后根遍歷是（ ）。
A. 4 2 5 7 6 3 1 B. 4 2 7 5 6 3 1
C. 7 4 2 5 6 3 1 D. 4 2 7 6 5 3 1
14．將數(shù)組{8, 23, 4, 16, 77, -5, 53, 100}中的元素按從大到小的順序排列，每次可以交換任意兩個元素，最少需要交換（ ）次。
A. 4 B. 5 C. 6 D. 7
15． 對有序數(shù)組{5, 13, 19, 21, 37, 56, 64, 75, 88，92，100}進(jìn)行二分查找，成功查找元素19的查找長度（比較次數(shù)）是（ ）。
A. 1 B. 2 C. 3 D. 4
16. 面向?qū)ο蟪绦蛟O(shè)計（Object-Oriented Programming）是一種程序設(shè)計的方法論，它將對象作為程序的基本單元，將數(shù)據(jù)和程序封裝在對象中，以提高軟件的重用性、靈活性和擴(kuò)展性。下面關(guān)于面向?qū)ο蟪绦蛟O(shè)計的說法中，不正確的是（ ）。
A. 面向?qū)ο蟪绦蛟O(shè)計通常采用自頂向下設(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)化的過程中得到更多的擴(kuò)展和對以前思想的重新注解。至今，SmallTalk語言仍然被視為面向?qū)ο笳Z言的基礎(chǔ)。
17. 在32*32點陣的“字庫”中，漢字“北”與“京”的字模占用字節(jié)數(shù)之和是（ ）。
A. 512 B. 256 C. 384 D. 128
18. 設(shè)T是一棵有n個頂點的樹，下列說法不正確的是（ ）。
A. T有n條邊 B. T是連通的
C. T是無環(huán)的 D. T有n-1條邊
19. 下列不屬于NOIP競賽推薦使用的語言環(huán)境的是（ ）。
A. Dev-C++ B. Visual C++ C. free pascal D. Lazarus
20．在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 城市6
城市1 0 2 3 1 12 15
城市2 2 0 2 5 3 12
城市3 3 2 0 3 6 5
城市4 1 5 3 0 7 9
城市5 12 3 6 7 0 2
城市6 15 12 5 9 2 0
三．閱讀程序?qū)懡Y(jié)果（共4題，每題8分，共計32分）
1. #include
using namespace std;
int main()
{
int i, 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;
else
cout << c + d << endl;
return 0;
}
輸入：9 19 29 39
輸出：_______________
2．#include
using namespace std;
void foo(int a, int b, int c)
{
if(a > b)
foo(c, a, b);
else
cout<}
int main()
{
int a, b, c;
cin >> a >> b >> c;
foo(a, b, c);
return 0;
}
輸入: 3 1 2
輸出: __________
3．#include
using namespace std;
void func(int ary[], int n )
{
int i=0, j, x;
j=n-1;
while(i{
while (i0) i++;
while (iif (ix=ary[i];
ary[i++]=ary[j];
ary[j--]=x;
}
}
}
int main()
{
int a[20], i, m;
m=10;
for(i=0; i{
cin>>a[i];
}
func(a, m);
for (i=0; icout<cout<< endl;
return 0;
}
輸入：5 4 -6 -11 6 -59 22 -6 1 10
輸出：____________________________________
4. #include
#include
using namespace std;
#define MAX 100
void solve(char first[], int spos_f, int epos_f, char mid[], int spos_m, int epos_m)
{
int i, 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];
}
int main()
{
char first[MAX], mid[MAX];
int len;
cin >> len;
cin >> first >> mid;
solve(first, 0, len - 1, mid , 0, len - 1);
cout << endl;
return 0;
}
輸入： 7
ABDCEGF
BDAGECF
輸出：____________________________________
四．完善程序 (前4空，每空2.5分，后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用該字母的大寫替換，S中的a用該字母的小寫替換；S’中的第二個字母是字母B和b的替換字母，即S中的B用該字母的大寫替換，S中的b用該字母的小寫替換；…… 以此類推。
#include
#include
char change[26], str[5000];
using namespace std;
void CheckChangeRule()
{
int i;
for (i = 0;i < 26;i ++)
{
if ( ① )
change[i] -= 'A' - 'a';
}
}
void ChangeString()
{
int i;
for (i = 0;i {
if ( ② )
str[i] = change[str[i] - 'A'] -'a' + 'A';
else
③
}
}
int main()
{
int i;
cin >> str ;
cin >> change;
CheckChangeRule();
④
cout << str << endl;
return 0;
}
(找第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 a[1000001],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(a[tmp],a[left]);
value = ①
i = left;
j = right;
while (i < j)
{
while (i < j && ② ) j --;
if (i < j) {a[i] = a[j]; i ++;} else break;
while (i < j && ③ ) i ++;
if (i < j) {a[j] = a[i]; j - -;} else break;
}
④
if (i < n) return FindKth( ⑤ );
if (i > n) return ⑥
return i;
}
int main()
{
int i;
int m = 1000000;
for (i = 1;i <= m;i ++)
cin >> a[i];
cin >> n;
ans = FindKth(1,m,n);
cout << a[ans];
return 0;
}

展開更多......

收起↑