資源簡介

第十四屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽試題
（ 提高組 C 語言 二小時(shí)完成 ）
● 全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效 ●●
一、 單項(xiàng)選擇題 （共10題，每題1.5分，共計(jì)15分。每題有且僅有一個(gè)正確答案）。
1. 在以下各項(xiàng)中，（ ）不是操作系統(tǒng)軟件。
A. Solaris B. Linux C. Sybase D. Windows Vista E. Symbian
2．微型計(jì)算機(jī)中，控制器的基本功能是（ ）。
A. 控制機(jī)器各個(gè)部件協(xié)調(diào)工作 B. 實(shí)現(xiàn)算術(shù)運(yùn)算和邏輯運(yùn)算 C. 存儲(chǔ)各種控制信息
D. 獲取外部信息 E. 存放程序和數(shù)據(jù)
3. 設(shè)字符串S=”O(jiān)lympic”，S的非空子串的數(shù)目是（ ）。
A. 29 B. 28 C. 16 D. 17 E. 7
4．完全二叉樹共有2*N-1個(gè)結(jié)點(diǎn)，則它的葉節(jié)點(diǎn)數(shù)是（ ）。
A. N-1 B. 2*N C. N D. 2N-1 E. N/2
5．將數(shù)組{8, 23, 4, 16, 77, -5, 53, 100}中的元素按從大到小的順序排列，每次可以交換任意兩個(gè)元素，最少需要交換（ ）次。
A. 4 B. 5 C. 6 D. 7 E. 8
6．設(shè)棧S的初始狀態(tài)為空，元素a，b，c，d，e，f依次入棧S，出棧的序列為b，d，c，f，e，a，則棧S的容量至少應(yīng)該是（ ）。
A. 6 B. 5 C. 4 D. 3 E. 2
7. 與十進(jìn)制數(shù)28.5625相等的四進(jìn)制數(shù)是（ ）。
A. 123.21 B. 131.22 C. 130.22 D. 130.21 E. 130.20
8． 遞歸過程或函數(shù)調(diào)用時(shí)，處理參數(shù)和返回地址，通常使用一種稱為（）的數(shù)據(jù)結(jié)構(gòu)。
A. 隊(duì)列 B. 多維數(shù)組 C. 線性表 D. 鏈表 E. 棧
9. TCP/IP是一組構(gòu)成互聯(lián)網(wǎng)基礎(chǔ)的網(wǎng)絡(luò)協(xié)議，字面上包括兩組協(xié)議：傳輸控制協(xié)議（TCP）和網(wǎng)際協(xié)議（IP）。TCP/IP 協(xié)議把Internet網(wǎng)絡(luò)系統(tǒng)描述成具有四個(gè)層次功能的網(wǎng)絡(luò)模型,其中提供源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間的信息傳輸服務(wù)，包括尋址和路由器選擇等功能的是（）。
A. 鏈路層 B．網(wǎng)絡(luò)層 C. 傳輸層 D. 應(yīng)用層 E.會(huì)話層
10． 對(duì)有序數(shù)組{5, 13, 19, 21, 37, 56, 64, 75, 88, 92, 100}進(jìn)行二分查找，等概率的情況下查找成功的平均查找長度（平均比較次數(shù)）是（ ）。
A. 35/11 B. 34/11 C. 33/11 D. 32/11 E. 34/10
二、 不定項(xiàng)選擇題 （共10題，每題1.5分，共計(jì)15分。每題正確答案的個(gè)數(shù)大于或等于1。多選或少選均不得分）。
11. 在下列關(guān)于圖靈獎(jiǎng)的說法中，正確的有（ ）。
A. 圖靈獎(jiǎng)是美國計(jì)算機(jī)協(xié)會(huì)于1966年設(shè)立的，專門獎(jiǎng)勵(lì)那些對(duì)計(jì)算機(jī)事業(yè)作出重要貢獻(xiàn)的個(gè)人
B. 圖靈獎(jiǎng)有“計(jì)算機(jī)界諾貝爾獎(jiǎng)”之稱
C. 迄今為止，還沒有華裔計(jì)算機(jī)科學(xué)家獲此殊榮
D. 圖靈獎(jiǎng)的名稱取自計(jì)算機(jī)科學(xué)的先驅(qū)、英國科學(xué)家阿蘭·圖靈
12．計(jì)算機(jī)在工作過程中，若突然停電，（ ）中的信息不會(huì)丟失。
A. 硬盤 B. CPU C.ROM D. RAM
13. 設(shè)A=true，B=false，C=true，D=false，以下邏輯運(yùn)算表達(dá)式值為真的有（ ）。
A. (A∧B)∨(C∧D∨A) B. ((A∧B)∨C)∧D
C. (B∨C∨D)∨D∧A D. A∧(D∨C)∧B
14．Web2.0是近年來互聯(lián)網(wǎng)的熱門概念之一，其核心思想是互動(dòng)與分享。下列網(wǎng)站中，（ ）是典型的Web2.0應(yīng)用。
A. Sina B. Flickr C. Yahoo D. Google
15. (2008)10 + (5B)16的結(jié)果是（ ）。
A. (833)16 B. (2099)10 C. (4063)8 D. (100001100011)2
16. 二叉樹T，已知其先根遍歷是1 2 4 3 5 7 6（數(shù)字為結(jié)點(diǎn)的編號(hào)，以下同），后根遍歷是4 2 7 5 6 3 1，則該二叉樹的可能的中根遍歷是（ ）。
A. 4 2 1 7 5 3 6 B. 2 4 1 7 5 3 6
C. 4 2 1 7 5 6 3 D. 2 4 1 5 7 3 6
17. 面向?qū)ο蟪绦蛟O(shè)計(jì)（Object-Oriented Programming）是一種程序設(shè)計(jì)的方法論，它將對(duì)象作為程序的基本單元，將數(shù)據(jù)和程序封裝在對(duì)象中，以提高軟件的重用性、靈活性和擴(kuò)展性。下面關(guān)于面向?qū)ο蟪绦蛟O(shè)計(jì)的說法中，正確的是（ ）。
A. 面向?qū)ο蟪绦蛟O(shè)計(jì)通常采用自頂向下設(shè)計(jì)方法進(jìn)行設(shè)計(jì)。
B. 面向?qū)ο蟪绦蛟O(shè)計(jì)方法具有繼承性（inheritance）、封裝性（encapsulation）、多態(tài)性（polymorphism）等幾大特點(diǎn)。
C. 支持面向?qū)ο筇匦缘恼Z言稱為面向?qū)ο蟮木幊陶Z言，目前較為流行的有C++、JAVA、C#等。
D. 面向?qū)ο蟮某绦蛟O(shè)計(jì)的雛形來自于Simula語言，后來在SmallTalk語言的完善和標(biāo)準(zhǔn)化的過程中得到更多的擴(kuò)展和對(duì)以前思想的重新注解。至今，SmallTalk語言仍然被視為面向?qū)ο笳Z言的基礎(chǔ)。
18. 設(shè)T是一棵有n個(gè)頂點(diǎn)的樹，下列說法正確的是（ ）。
A. T是連通的、無環(huán)的 B. T是連通的，有n-1條邊
C. T是無環(huán)的，有n-1條邊 D. 以上都不對(duì)
19. NOIP競賽推薦使用的語言環(huán)境有（ ）。
A. Dev-C++ B. Visual C++ C. free pascal D. Lazarus
20. 在下列防火墻（firewall）的說法中，正確的有（ ）。
A. 防火墻是一項(xiàng)協(xié)助確保信息安全的設(shè)備，其會(huì)依照特定的規(guī)則，允許或是限制數(shù)據(jù)通過
B. 防火墻可能是一臺(tái)專屬的硬件或是安裝在一般硬件上的一套軟件
C. 網(wǎng)絡(luò)層防火墻可以視為一種 IP 數(shù)據(jù)包過濾器，只允許符合特定規(guī)則的數(shù)據(jù)包通過，其余的一概禁止穿越防火墻
D. 應(yīng)用層防火墻是在 TCP/IP的“應(yīng)用層”上工作，可以攔截進(jìn)出某應(yīng)用程序的所有數(shù)據(jù)包
三．問題求解（共2題，每題5分，共計(jì)10分）
1．有6個(gè)城市，任何兩個(gè)城市之間都有一條道路連接，6個(gè)城市兩兩之間的距離如下表所示，則城市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
2．書架上有21本書，編號(hào)從1到21，從其中選4本，其中每兩本的編號(hào)都不相鄰的選法一共有______種。
四．閱讀程序?qū)懡Y(jié)果（共4題，每題8分，共計(jì)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;
}
輸入：2 1 3
輸出:__________
3．#include
void f(int a, int b, int c)
{
printf("%d%d%d/", a, b, c);
if(a == 3 && b == 2 && c == 1)
return;
if(b < c)
f(a, c, b);
else if(a < b)
{
if(a < c)
f(c, a, b);
else
f(b, c, a);
}
}
int main()
{
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
f(a, b, c);
printf("\n");
return 0;
}
輸入: 1 3 2
輸出： ________________________________________
4. #include
#include
int i,j,len;
char s[50];
int main()
{
scanf("%s", s);
len = strlen(s);
for (i = 0;i < len; ++i)
{
if (s[i] >= 'A' && s[i] <= 'Z') s[i] -= 'A' - 'a';
}
for (i = 0;i < len; ++i)
{
if (s[i] < 'x') s[i] += 3; else s[i] += -23;
}
printf("%s/", s);
for (j = 1;j < 4;j ++)
{
for (i = 0;i < len-j; i = i + j)
{
s[i] = s[i + j] ;
}
}
printf("%s\n", s);
return 0;
}
輸入：ABCDEFGuvwxyz
輸出：___________________________________________
五．完善程序 (前6空，每空3分，后5空，每空2分，共28分)
1．(找第k大的數(shù)) 給定一個(gè)長度為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
#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;
}
2．（矩陣中的數(shù)字）有一個(gè)n*n(1<=n<=5000)的矩陣a， 對(duì)于1<=i < n,1<=j<=n, a[i,j] < a[i + 1,j] a[j,i] < a[j,i+1]。即矩陣中左右相鄰的兩個(gè)元素，右邊的元素一定比左邊的大。上下相鄰的兩個(gè)元素，下面的元素一定比上面的大。給定矩陣a中的一個(gè)數(shù)字k，找出k所在的行列（注意：輸入數(shù)據(jù)保證矩陣中的數(shù)各不相同）。
#include
int n,k,answerx,answery;
int a[5001][5001];
void FindKPosition()
{
int i = n,j = n;
while (j > 0)
{
if (a[n][j] < k) break;
j --;
}
①
while (a[i][j] != k)
{
while ( ② && i > 1) i --;
while ( ③ && j <= n) j ++;
}
④
⑤
}
int main()
{
int i,j;
scanf( "%d", &n );
for (i = 1;i <= n;i ++)
for (j = 1;j <= n;j ++)
scanf( "%d", &a[i][j]);
scanf( "%d", &k );
FindKPosition();
printf("%d %d\n", answerx, answery);
return 0;
}

展開更多......

收起↑