第十四屆全國(guó)青少年信息學(xué)(計(jì)算機(jī))奧林匹克分區(qū)聯(lián)賽初賽

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

2、點(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中的元素按從大到小的順序排列，每次可以交換任意兩個(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. 6 B. 5 C. 4 D. 3 E. 27. 與十進(jìn)制數(shù)28.5625相等的四進(jìn)制數(shù)是（ ）。A. 123.21 B. 131.22 C. 130.22 D. 130.21 E. 130.20

3、8 遞歸過(guò)程或函數(shù)調(diào)用時(shí)，處理參數(shù)和返回地址，通常使用一種稱(chēng)為（）的數(shù)據(jù)結(jié)構(gòu)。A. 隊(duì)列 B. 多維數(shù)組 C. 線(xiàn)性表 D. 鏈表 E. 棧E. 存放程序和數(shù)據(jù) A. Solaris B. Linux C. Sybase D. Windows Vista 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ì)話(huà)層10 對(duì)

4、有序數(shù)組5, 13, 19, 21, 37, 56, 64, 75, 88, 92, 100進(jìn)行二分查找，等概率的情況下查找成功的平均查找長(zhǎng)度（平均比較次數(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)的說(shuō)法中，正確的有（ ）。A. 圖靈獎(jiǎng)是美國(guó)計(jì)算機(jī)協(xié)會(huì)于1966年設(shè)立的，專(zhuān)門(mén)獎(jiǎng)勵(lì)那些對(duì)計(jì)算機(jī)事業(yè)作出重要貢獻(xiàn)的個(gè)人B. 圖靈獎(jiǎng)有“計(jì)算機(jī)界諾貝爾獎(jiǎng)”之稱(chēng)C. 迄今為止，還沒(méi)有華裔計(jì)算機(jī)科學(xué)家獲此殊榮D. 圖

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

6、. (833)16 B. (2099)10 C. (4063)8 (100001100011)216. 二叉樹(shù)T，已知其先根遍歷是1 2 4 3 5 7 6（數(shù)字為結(jié)點(diǎn)的編號(hào)，以下同），后根遍歷是4 2 7 5 6 3 1，則該二叉樹(shù)的可能的中根遍歷是（ ）。 。 ）D. ）A. 4 2 1 7 5 3 6 B. 2 4 1 7 5 3 6C. 4 2 1 7 5 6 3 D. 2 4 1 5 7 3 617. 面向?qū)ο蟪绦蛟O(shè)計(jì)（Object-Oriented Programming）是一種程序設(shè)計(jì)的方法論，它將對(duì)象作為程序的基本單元，將數(shù)據(jù)和程序封裝在對(duì)象中，以提高軟件的重用性、靈活性和擴(kuò)展

7、性。下面關(guān)于面向?qū)ο蟪绦蛟O(shè)計(jì)的說(shuō)法中，正確的是（ ）。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(yǔ)言稱(chēng)為面向?qū)ο蟮木幊陶Z(yǔ)言，目前較為流行的有C+、JAVA、C#等。D. 面向?qū)ο蟮某绦蛟O(shè)計(jì)的雛形來(lái)自于Simula語(yǔ)言，后來(lái)在SmallTalk語(yǔ)言的完善和標(biāo)準(zhǔn)化的過(guò)程中得到更多的擴(kuò)展和對(duì)以前思想的重新注解。至今，SmallTalk語(yǔ)言仍然被視為面向?qū)ο笳Z(yǔ)言的基礎(chǔ)。18. 設(shè)T是一棵有n個(gè)頂點(diǎn)的樹(shù)，下列說(shuō)法正確的是

8、（ ）。A. T是連通的、無(wú)環(huán)的 B. T是連通的，有n-1條邊C. T是無(wú)環(huán)的，有n-1條邊 D. 以上都不對(duì)19. NOIP競(jìng)賽推薦使用的語(yǔ)言環(huán)境有（ ）。A. Dev-C+ B. Visual C+ C. free pascal D. Lazarus20. 在下列防火墻（firewall）的說(shuō)法中，正確的有（ ）。A. 防火墻是一項(xiàng)協(xié)助確保信息安全的設(shè)備，其會(huì)依照特定的規(guī)則，允許或是限制數(shù)據(jù)通過(guò)B. 防火墻可能是一臺(tái)專(zhuān)屬的硬件或是安裝在一般硬件上的一套軟件C. 網(wǎng)絡(luò)層防火墻可以視為一種 IP 數(shù)據(jù)包過(guò)濾器，只允許符合特定規(guī)則的數(shù)據(jù)包通過(guò)，其余的一概禁止穿越防火墻D. 應(yīng)用層防火墻是在 T

9、CP/IP的“應(yīng)用層”上工作，可以攔截進(jìn)出某應(yīng)用程序的所有數(shù)據(jù)包三問(wèn)題求解（共2題，每題5分，共計(jì)10分）1有6個(gè)城市，任何兩個(gè)城市之間都有一條道路連接，6個(gè)城市兩兩之間的距離如下表所示，則城市1到城市6的最短距離為_(kāi)。2書(shū)架上有21本書(shū)，編號(hào)從1到21，從其中選4本，其中每?jī)杀镜木幪?hào)都不相鄰的選法一共有_種。四閱讀程序?qū)懡Y(jié)果（共4題，每題8分，共計(jì)32分）1. vari,a,b,c,d:integer;f:array0.3 of integer; beginfor i:=0 to 3 do read(fi);a := f0 + f1 + f2 + f3; a := a div f0;b :=

10、 f0 + f2 + f3; b := b div a;c := (b * f1 + a) div f2; d := f(b div c) mod 4;if (f(a + b + c + d) mod 4 > f2) then begina := a + b; writeln(a); end else beginc := c + d; writeln(c); end; end.輸入：9 19 29 39 輸出：_2procedure foo(a,b,c:integer);beginif a>b then foo(c,a,b)else writeln(a, ',',

11、b, ',', c)end;vara,b,c:integer;beginread(a, b, c);foo(a,b,c);end.輸入：2 1 3輸出:_3procedure f(a,b,c:integer);beginwrite(a, b, c, '/');if (a = 3) and (b = 2) and (c = 1) then exit; if b<c then f(a,c,b)elseif a<b thenif a<c then f(c,a,b) else f(b,c,a);end;vara,b,c:integer;beginrea

12、d(a, b, c);f(a,b,c);end.輸入: 1 3 2輸出： _4. vars:string;i,j,len,k:integer;beginread(s);len:=length(s);for i:=1 to len doif (ord(si) >= ord('A') and (ord(si) <= ord('Z') then si := chr(ord(si) - ord('A') + ord('a');for i:=1 to len doif (ord(si)<ord('x') t

13、hen si:= chr(ord(si)+3) else si:= chr(ord(si)-23);write(s);write('/');for j:=1 to 3 do begini:=1;while i<=len-j dobeginsi:=si+j;i:=i+j;end;end;writeln(s);end.輸入：ABCDEFGuvwxyz輸出：_五完善程序 (前6空，每空3分，后5空，每空2分，共28分)1(找第k大的數(shù)) 給定一個(gè)長(zhǎng)度為1,000,000的無(wú)序正整數(shù)序列，以及另一個(gè)數(shù)n(1<=n<=1000000)，接下來(lái)以類(lèi)似快速排序的方法找到序列

14、中第n大的數(shù)（關(guān)于第n大的數(shù)：例如序列1，2，3，4，5，6中第3大的數(shù)是4）。vara:array1.1000000 of integer;n,m,ans:integer;procedure swap(var a,b:integer);var t:integer;beginif (a <> b) then begint := a;a := b;b := t;end;end;function FindKth(left,right,n:integer):integer;vartmp,value,i,j:integer;beginif left = right then exit(le

15、ft);tmp:= random(right-left) + left;swap(atmp,aleft);value := ;i := left;j := right;while i<j dobeginwhile (i<j) and ( ) do dec(j);if i<j then beginai := aj; inc(i);end else break;while (i<j) and ( ) do inc(i);if i<j then beginaj := ai; dec(j);end else break;end;if i<n then begin i

16、nc(i); exit(FindKth( );end; if i>n then begin dec(i); exit( ); end; exit(i);end;vari:integer;beginrandomize;ans := -1;m:=5;for i:=1 to m doread(ai);read(n);ans:= FindKth(1,m,n);writeln(aans);end.2（矩陣中的數(shù)字）有一個(gè)n*n(1<=n<=5000)的矩陣a， 對(duì)于1<=i < n,1<=j<=n, ai,j < ai + 1,j aj,i < aj,i+1。即矩陣中左右相鄰的兩個(gè)元素，右邊的元素一定比左邊的大。上下相鄰的兩個(gè)元素，下面的元素一定比上面的大。給定矩陣a中的一個(gè)數(shù)字k，找出k所在的行列（注意：輸入數(shù)據(jù)保證矩陣中的數(shù)各不相同）。varn,k,answerx,answery:integer;a:array1.5000,1.5000 of integer;procedure FindKPosition;vari,j:integer;begini:=n;j:=n;while j>0 dobeginif an,j <