提高組初賽試題C含答案

1、第十四屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽試題 （ 提高組 C+ 語言 二小時完成 ） 全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效 一、 單項(xiàng)選擇題 （共10題，每題1.5分，共計(jì)15分。每題有且僅有一個正確答案）。1. 在以下各項(xiàng)中，（ ）不是操作系統(tǒng)軟件。A. Solaris B. Linux C. Sybase D. Windows Vista E. Symbian2微型計(jì)算機(jī)中，控制器的基本功能是（ ）。A. 控制機(jī)器各個部件協(xié)調(diào)工作 B. 實(shí)現(xiàn)算術(shù)運(yùn)算和邏輯運(yùn)算 C. 存儲各種控制信息D. 獲取外部信息 E. 存放程序和數(shù)據(jù)3. 設(shè)字符串S=”O(jiān)lympic”，S的非空子串的

2、數(shù)目是（ ）。A. 29 B. 28 C. 16 D. 17 E. 74完全二叉樹共有2*N-1個結(jié)點(diǎn)，則它的葉節(jié)點(diǎn)數(shù)是（ ）。A. N-1 B. 2*N C. N D. 2N-1 E. N/25將數(shù)組8, 23, 4, 16, 77, -5, 53, 100中的元素按從大到小的順序排列，每次可以交換任意兩個元素，最少需要交換（ ）次。A. 4 B. 5 C. 6 D. 7 E. 86設(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. 27. 與十進(jìn)制數(shù)28.5625相等的四

3、進(jìn)制數(shù)是（ ）。A. 123.21 B. 131.22 C. 130.22 D. 130.21 E. 130.208 遞歸過程或函數(shù)調(diào)用時，處理參數(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)描述成具有四個層次功能的網(wǎng)絡(luò)模型,其中提供源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間的信息傳輸服務(wù)，包括尋址和路由器選擇等功能的是（）。A. 鏈路層 B網(wǎng)絡(luò)層 C. 傳輸層 D. 應(yīng)用層 E.會話層10 對有序數(shù)

4、組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分。每題正確答案的個數(shù)大于或等于1。多選或少選均不得分）。11. 在下列關(guān)于圖靈獎的說法中，正確的有（ ）。A. 圖靈獎是美國計(jì)算機(jī)協(xié)會于1966年設(shè)立的，專門獎勵那些對計(jì)算機(jī)事業(yè)作出重要貢獻(xiàn)的個人B. 圖靈獎有“計(jì)算機(jī)界諾貝爾獎”之稱C. 迄今為止，還沒有華裔計(jì)算機(jī)科學(xué)家獲此殊榮D. 圖靈獎的

5、名稱取自計(jì)算機(jī)科學(xué)的先驅(qū)、英國科學(xué)家阿蘭·圖靈12計(jì)算機(jī)在工作過程中，若突然停電，（ ）中的信息不會丟失。A. 硬盤 B. CPU C.ROM D. RAM13. 設(shè)A=true，B=false，C=true，D=false，以下邏輯運(yùn)算表達(dá)式值為真的有（ ）。A. (AB)(CDA) B. (AB)C)D C. (BCD)DA D. A(DC)B 14Web2.0是近年來互聯(lián)網(wǎng)的熱門概念之一，其核心思想是互動與分享。下列網(wǎng)站中，（ ）是典型的Web2.0應(yīng)用。 A. Sina B. Flickr C. Yahoo D. Google15. (2008)10 + (5B)16的結(jié)果是

6、（ ）。16. 二叉樹T，已知其先根遍歷是1 2 4 3 5 7 6（數(shù)字為結(jié)點(diǎn)的編號，以下同），后根遍歷是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ì)的方法論，它將對象作為程序的基本單元，將數(shù)據(jù)和程序封裝在對象中，以提高軟件的重用性、靈活性和擴(kuò)展性。下面關(guān)于面向?qū)ο蟪绦蛟O(shè)計(jì)的說法中，正確的是（ ）。A. 面向?qū)ο蟪绦蛟O(shè)計(jì)通常采用自頂向下設(shè)計(jì)方法

7、進(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ò)展和對以前思想的重新注解。至今，SmallTalk語言仍然被視為面向?qū)ο笳Z言的基礎(chǔ)。18. 設(shè)T是一棵有n個頂點(diǎn)的樹，下列說法正確的是（ ）。A. T是連通的、無環(huán)的 B. T是連通的，有n-1條邊C. T是無環(huán)的，有n-1條邊 D.

8、 以上都不對19. NOIP競賽推薦使用的語言環(huán)境有（ ）。A. Dev-C+ B. Visual C+ C. free pascal D. Lazarus20. 在下列防火墻（firewall）的說法中，正確的有（ ）。A. 防火墻是一項(xiàng)協(xié)助確保信息安全的設(shè)備，其會依照特定的規(guī)則，允許或是限制數(shù)據(jù)通過B. 防火墻可能是一臺專屬的硬件或是安裝在一般硬件上的一套軟件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ì)1

9、0分）1有6個城市，任何兩個城市之間都有一條道路連接，6個城市兩兩之間的距離如下表所示，則城市1到城市6的最短距離為_。城市1城市2城市3城市4城市5城市6城市102311215城市22025312城市3320365城市4153079城市51236702城市6151259202書架上有21本書，編號從1到21，從其中選4本，其中每兩本的編號都不相鄰的選法一共有_種。四閱讀程序?qū)懡Y(jié)果（共4題，每題8分，共計(jì)32分）1. #include<iostream>using namespace std;int main()int i, a, b, c, d, f4;for(i = 0; i

10、< 4; i+) cin >> 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;else cout << c + d << endl;return 0;輸入：9 19 29 39 輸出：_2#include<iostream>using namespace

11、std;void foo(int a, int b, int c)if(a > b) foo(c, a, b);elsecout<<a<<','<<b<<','<<c<<endl;int main()int a, b, c;cin >> a >> b >> c;foo(a, b, c);return 0;輸入：2 1 3輸出:_3#include<iostream>using namespace std;void f(int a, int

12、 b, int c)cout << 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);elsef(b, c, a);int main()int a, b, c;cin >> a >> b >> c;f(a, b, c);cout << endl;return 0;輸入: 1 3 2輸出： _4

13、. #include <iostream>#include <cstring>using namespace std;int i,j,len;char s50;int main()cin >>s;len = strlen(s);for (i = 0;i < len; +i)if (si >= 'A' && si <= 'Z') si -= 'A' - 'a'for (i = 0;i < len; +i)if (si < 'x') si

14、 += 3; else si += -23;cout << s << '/'for (j = 1;j < 4;j +)for (i = 0;i < len-j; i = i + j)si = si + j ;cout << s << endl;return 0;輸入：ABCDEFGuvwxyz輸出：_五完善程序 (前6空，每空3分，后5空，每空2分，共28分)1(找第k大的數(shù)) 給定一個長度為1,000,000的無序正整數(shù)序列，以及另一個數(shù)n(1<=n<=1000000)，接下來以類似快速排序的方法找到序列

15、中第n大的數(shù)（關(guān)于第n大的數(shù)：例如序列1，2，3，4，5，6中第3大的數(shù)是4）。#include <iostream>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,a

16、left);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) return FindKth( );if (i > n) return return i;int main()int i;int m = 1000000;for (i = 1;i

17、 <= m;i +)cin >> ai;cin >> n;ans = FindKth(1,m,n);cout << aans; return 0;2（矩陣中的數(shù)字）有一個n*n(1<=n<=5000)的矩陣a， 對于1<=i < n,1<=j<=n, ai,j < ai + 1,j aj,i < aj,i+1。即矩陣中左右相鄰的兩個元素，右邊的元素一定比左邊的大。上下相鄰的兩個元素，下面的元素一定比上面的大。給定矩陣a中的一個數(shù)字k，找出k所在的行列（注意：輸入數(shù)據(jù)保證矩陣中的數(shù)各不相同）。#includ

18、e <iostream>using namespace std;int n,k,answerx,answery;int a50015001;void FindKPosition()int i = n,j = n;while (j > 0)if (anj < k) break; j -; while (aij != k)while ( && i > 1) i -;while ( && j <= n) j +; int main()int i,j;cin >> n;for (i = 1;i <= n;i +)fo

19、r (j = 1;j <= n;j +)cin >> aij;cin >> k;FindKPosition();cout << answerx << " " << answery << endl; return 0;第十四屆信息學(xué)奧賽聯(lián)賽提高組C+初賽答案一、單項(xiàng)選擇題：（每題1.5分） 1. C      2. A      3. B      4. C      5. B6. D      7. D      8. E      9. B      10. C二、 不定項(xiàng)選擇題 （共10題，每題1.5分，共計(jì)15分。每題正確答案的個數(shù)大于或等于1。多選或少選均不得分）。1