資源簡介

第十四屆全國青少年信息學奧林匹克聯賽初賽試題
（ 普及組 C語言 二小時完成 ）
● 全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效 ●●
一、 單項選擇題 （共20題，每題1.5分，共計30分。每題有且僅有一個正確答案.）。
1．微型計算機中，控制器的基本功能是（ ）。
A. 控制機器各個部件協調工作 B. 實現算術運算和邏輯運算
C. 獲取外部信息 D. 存放程序和數據
2. 設A=true，B=false，C=true，D=false，以下邏輯運算表達式值為真的是（ ）。
A. (A∧B)∨(C∧D∨A) B. ((A∧B)∨C)∧D
C. (B∨C∨D)∧D∧A D. A∧(D∨C)∧B
3. 在下列關于圖靈獎的說法中，不正確的是（ ）。
A. 圖靈獎是美國計算機協會于1966年設立的，專門獎勵那些對計算機事業作出重要貢獻的個人
B. 圖靈獎有“計算機界諾貝爾獎”之稱
C. 迄今為止，還沒有華裔計算機科學家獲此殊榮
D. 圖靈獎的名稱取自計算機科學的先驅、英國科學家阿蘭·圖靈
4．計算機在工作過程中，若突然停電，（ ）中的信息不會丟失。
A. ROM和RAM B. CPU C.ROM D. RAM
5．完全二叉樹共有2*N-1個結點，則它的葉節點數是（ ）。
A. N-1 B. N C. 2*N D. 2N-1
6. 在以下各項中，（ ）不是操作系統軟件。
A. Solaris B. Linux C. Windows Vista D. Sybase
7．設棧S的初始狀態為空，元素a，b，c，d，e，f依次入棧S，出棧的序列為b，d，f，e，c，a，則棧S的容量至少應該是（ ）。
A. 6 B. 5 C. 4 D. 3
8. 與十進制數28.5625相等的四進制數是（ ）。
A. 123.21 B. 131.22 C. 130.22 D. 130.21
9. 設字符串S=”Olympic”，S的非空子串的數目是（ ）。
A. 28 B. 29 C. 16 D. 17
10．Web2.0是近年來互聯網的熱門概念之一，其核心思想是互動與分享。下列網站中，（ ）是典型的Web2.0應用。
A. Sina B. Flickr C. Yahoo D. Google
11． 遞歸過程或函數調用時，處理參數和返回地址，通常使用一種稱為（ ）的數據結構。
A. 隊列 B. 多維數組 C. 線性表 D. 棧
12. (2008)10 + (5B)16的結果是（ ）。
A. (833)16 B. (2089)10 C. (4163)8 D. (100001100011)2
13. 二叉樹T，已知其先根遍歷是1 2 4 3 5 7 6（數字為結點的編號，以下同），中根遍歷是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．將數組{8, 23, 4, 16, 77, -5, 53, 100}中的元素按從大到小的順序排列，每次可以交換任意兩個元素，最少需要交換（ ）次。
A. 4 B. 5 C. 6 D. 7
15． 對有序數組{5, 13, 19, 21, 37, 56, 64, 75, 88，92，100}進行二分查找，成功查找元素19的查找長度（比較次數）是（ ）。
A. 1 B. 2 C. 3 D. 4
16. 面向對象程序設計（Object-Oriented Programming）是一種程序設計的方法論，它將對象作為程序的基本單元，將數據和程序封裝在對象中，以提高軟件的重用性、靈活性和擴展性。下面關于面向對象程序設計的說法中，不正確的是（ ）。
A. 面向對象程序設計通常采用自頂向下設計方法進行設計。
B. 面向對象程序設計方法具有繼承性（inheritance）、封裝性（encapsulation）、多態性（polymorphism）等幾大特點。
C. 支持面向對象特性的語言稱為面向對象的編程語言，目前較為流行的有C++、JAVA、C#等。
D. 面向對象的程序設計的雛形來自于Simula語言，后來在SmallTalk語言的完善和標準化的過程中得到更多的擴展和對以前思想的重新注解。至今，SmallTalk語言仍然被視為面向對象語言的基礎。
17. 在32*32點陣的“字庫”中，漢字“北”與“京”的字模占用字節數之和是（ ）。
A. 512 B. 256 C. 384 D. 128
18. 設T是一棵有n個頂點的樹，下列說法不正確的是（ ）。
A. T有n條邊 B. T是連通的
C. T是無環的 D. T有n-1條邊
19. 下列不屬于NOIP競賽推薦使用的語言環境的是（ ）。
A. Dev-C++ B. Visual C++ C. free pascal D. Lazarus
20．在C程序中，表達式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
三．閱讀程序寫結果（共4題，每題8分，共計32分）
1. #include
int main()
{
int i, a, b, c, d, f[4];
for(i = 0; i < 4; i++)
scanf("%d", &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])
printf("%d\n", a + b);
else
printf("%d\n", c + d);
return 0;
}
輸入：9 19 29 39
輸出：_______________
2．#include
void foo(int a, int b, int c)
{
if(a > b)
foo(c, a, b);
else
printf("%d,%d,%d\n", a, b, c);
}
int main()
{
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
foo(a, b, c);
return 0;
}
輸入: 3 1 2
輸出: __________
3．#include
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; iscanf("%d", &a[i]);
func(a, m);
for (i=0; iprintf( "%d ", a[i] );
printf("\n");
return 0;
}
輸入：5 4 -6 -11 6 -59 22 -6 1 10
輸出：____________________________________
4. #include
#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);
printf("%c", first[spos_f]);
}
int main()
{
char first[MAX], mid[MAX];
int len;
scanf("%d", &len);
scanf("%s", first);
scanf("%s", mid);
solve(first, 0, len - 1, mid , 0, len - 1);
printf("\n");
return 0;
}
輸入： 7
ABDCEGF
BDAGECF
輸出：____________________________________
四．完善程序 (前4空，每空2.5分，后6空，每空3分，共28分)
1．（字符串替換）給定一個字符串S（S僅包含大小寫字母），下面的程序將S中的每個字母用規定的字母替換，并輸出S經過替換后的結果。程序的輸入是兩個字符串，第一個字符串是給定的字符串S，第二個字符串S’由26個字母組成，它是a-z的任一排列，大小寫不定，S’規定了每個字母對應的替換字母：S’中的第一個字母是字母A和a的替換字母，即S中的A用該字母的大寫替換，S中的a用該字母的小寫替換；S’中的第二個字母是字母B和b的替換字母，即S中的B用該字母的大寫替換，S中的b用該字母的小寫替換；…… 以此類推。
#include
#include
char change[26], str[5000];
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;
scanf("%s", str);
scanf("%s", change);
CheckChangeRule();
④
printf("%s\n", str);
return 0;
}
1. (找第k大的數) 給定一個長度為1,000,000的無序正整數序列, 以及另一個數n (1<=n<=1000000), 然后以類似快速排序的方法找到序列中第n大的數（關于第n大的數：例如序列{1，2，3，4，5，6}中第3大的數是4）。
#include
#include
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 ++)
scanf("%d", &a[i]);
scanf("%d", &n);
ans = FindKth(1,m,n);
printf("%d\n", a[ans]);
return 0;
}

展開更多......

收起↑