NOIP2008提高組初賽試題

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

2、目是（）。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. ND. 2N-1E. N/25 將數(shù)組8, 23, 4, 16, 77, -5, 53, 100 中的元素按從大到小的順序排列，每次可以交換任意兩個(gè)元素， 最少需要交換（ ）次。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. 6B. 5C. 4D. 3E. 27. 與

3、十進(jìn)制數(shù) 28.5625 相等的四進(jìn)制數(shù)是（ ）。A. 123.21 B. 131.22 C. 130.22 D. 130.21E. 130.208. 遞歸過程或函數(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)

4、用層E會(huì)話層10 對(duì)有序數(shù)組5, 13, 19, 21, 37, 56, 64, 75, 88, 92, 100 進(jìn)行二分查找，等概率的情況下查找成功的 平均查找長度（平均比較次數(shù)）是（ ）。A. 35/11B. 34/11C. 33/11D. 32/11E. 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. 迄今為止，還沒有華

5、裔計(jì)算機(jī)科學(xué)家獲此殊榮D. 圖靈獎(jiǎng)的名稱取自計(jì)算機(jī)科學(xué)的先驅(qū)、英國科學(xué)家阿蘭圖靈12 計(jì)算機(jī)在工作過程中，若突然停電， （ ）中的信息不會(huì)丟失。A. 硬盤 B. CPUC.ROM D. RAM13.設(shè)A=true ，B=false，C=true ， D=false，以下邏輯運(yùn)算表達(dá)式值為真的有（）。A. （A AB）V（CAD V A）B. （ A AB） VC） A DC. （B VCVD） VD AAD. A A（D V C）AB14 Web2.0 是近年來互聯(lián)網(wǎng)的熱門概念之一，其核心思想是互動(dòng)與分享。下列網(wǎng)站中， （ ）是典型 的 Web2.0 應(yīng)用。A. SinaB. FlickrC.

6、 YahooD. Google15. (2008) 10+ (5B) 16 的結(jié)果是(）。A. (833) 16B. (2099) 10C. (4063) 8D. (100001100011)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 6B. 2 4 1 7 5 3 6C. 4 2 1 7 5 6 3D. 2 4 1 5 7 3 617. 面向?qū)ο蟪绦蛟O(shè)計(jì)（ Object-Oriented Programming ）是一種程序設(shè)計(jì)的方法論,它

7、將對(duì)象作為 程序的基本單元,將數(shù)據(jù)和程序封裝在對(duì)象中,以提高軟件的重用性、靈活性和擴(kuò)展性。下面關(guān)于面向 對(duì)象程序設(shè)計(jì)的說法中,正確的是（ ）。A. 面向?qū)ο蟪绦蛟O(shè)計(jì)通常采用自頂向下設(shè)計(jì)方法進(jìn)行設(shè)計(jì)。B. 面向?qū)ο蟪绦蛟O(shè)計(jì)方法具有繼承性（inheritanee ）、圭寸裝性（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ì)以前思想的重新注解。至今，

8、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 pascalD.Lazarus20.在下列防火墻（firewall ）的說法中，正確的有（）。A. 防火墻是一項(xiàng)協(xié)助確保信息安全的設(shè)備，其會(huì)依照特定的規(guī)則，允許或是限制數(shù)據(jù)通過B. 防火墻可能是一臺(tái)專屬的硬件或是安裝在一般硬件上的一套軟件C. 網(wǎng)絡(luò)層防火墻可以視為一種IP數(shù)據(jù)包過濾器，只允

9、許符合特定規(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城市102311215城市22025312城市3320365城市4153079城市51236702城市6151259202 書架上有21本書，編號(hào)從1到21，從其中選4本，其中每兩本的編號(hào)都不相鄰的選法一共有K四閱讀程序?qū)懡Y(jié)果（共4題，每題8分，共計(jì)32分）1. #i

10、ncludeusing 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;else cout c + d endl; return 0;輸入：9 19 29 39輸出： 2#includeusing namespace std;void

11、foo(int a, int b, int c)if(a b)foo(c, a, b);elsecouta,b,c a b c;foo(a, b, c);return 0;輸入：2 1 3輸出:3 #include using namespace std; void f(int a, int 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 a b c; f(a, b, c); cout endl; return 0;輸入: 1 3 2輸出： 4. #incl

12、ude #include using namespace std; int i,j,len;char s50;int main()cin s;len = strlen(s);for (i = 0;i = A & si = Z) si -= A - a;for (i = 0;i len; +i)if (si x) si += 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輸出： 五完善程序

13、 （ 前 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 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 rig

14、ht, int n)int tmp,value,i,j;if (left = right) return left;tmp = ran d()% (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) retur nreturn i;int mai n()int i;int m =

15、 1000000;for (i = 1;i ai;cin n;ans = Fin dKth(1, m,n);cout aa ns;return 0;2. （矩陣中的數(shù)字）有一個(gè) n*n（ 1=n=5000）的矩陣 a,對(duì)于 1=i n,1=j=n, ai,j ai + 1,jaj,i aj,i+1。即矩陣中左右相鄰的兩個(gè)元素，右邊的元素一定比左邊的大。上下相鄰的兩個(gè)元素， 下面的元素一定比上面的大。給定矩陣 a中的一個(gè)數(shù)字k，找出k所在的行列（注意：輸入數(shù)據(jù)保證矩 陣中的數(shù)各不相同）。#in elude using n amespace std;int n ,k,a nswerx,a nswe

16、ry;int a50015001;void Fin dKPositio n()int i = n,j = n;while (j 0)if (anj 1) i -;while (& j n;for (i = 1;i = n;i +)for (j = 1;j aij;cin k;Fin dKPositio n();cout an swerx an swery en dl;return 0;第十四屆信息學(xué)奧賽聯(lián)賽提高組 C+ 初賽答案一、單項(xiàng)選擇題：（每題 1.5 分）1. C2. A3. B4. C5. B6. D7. D8. E9. B10. C二、不定項(xiàng)選擇題 （共 10 題，每題 1.5 分，共計(jì) 15 分。每題正確答案的個(gè)數(shù)大于或等于 1 。多選或 少選均不得分）。11. ABD12. AC 13. BC 14. B 15. ABC16. ABD17. BCD 18. ABC19. ACD20. ABCD三、問題求解：（共 2 題，每題 5 分，共計(jì) 10 分）1723060四、閱讀程序?qū)懡Y(jié)果（共 4 題，每題 8 分，共計(jì) 32 分）1. 23 （信心題）2. 1,3,2 （簡單遞歸 ）3. 132/213/231/312/321/ （全排列）4. defghijxyzabc/hfizxjaybcccc