(NOI)2008第十四屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽試題

北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 更多競(jìng)賽真題免費(fèi)下載 見北京清北學(xué)堂官方網(wǎng)站 學(xué)習(xí)資源：自主招生 學(xué)科競(jìng)賽 高考等資源 第十四屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽試題 （ 提高組 Pascal 語言 二小時(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ù)是（ ）。 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 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 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 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競(jìng)賽推薦使用的語言環(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ù)包 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 三問題求解（ 共 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. var i,a,b,c,d:integer； f:array0.3 of integer； begin for i:=0 to 3 do read(fi)； a := f0 + f1 + f2 + f3； a := a div f0； b := 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 begin a := a + b； writeln(a)； end else begin 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 c := c + d； writeln(c)； end； end. 輸入： 9 19 29 39 輸出： _ 2 procedure foo(a,b,c:integer)； begin if ab then foo(c,a,b) else writeln(a, , b, , c) end； var a,b,c:integer； begin read(a, b, c)； foo(a,b,c)； end. 輸入： 2 1 3 輸出 :_ 3 procedure f(a,b,c:integer)； begin write(a, b, c, /)； if (a = 3) and (b = 2) and (c = 1) then exit； if bc then f(a,c,b) else if ab then if a= ord(A) and (ord(si) = ord(Z) then si := chr(ord(si) - ord(A) + ord(a)； for i:=1 to len do if (ord(si)ord(x) then si:= chr(ord(si)+3) else si:= chr(ord(si)-23)； write(s)； write(/)； for j:=1 to 3 do begin i:=1； while i=len-j do begin si:=si+j； i:=i+j； end； end； writeln(s)； end. 輸入： 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）。 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 var a:array1.1000000 of integer； n,m,ans:integer； procedure swap(var a,b:integer)； var t:integer； begin if (a b) then begin t := a； a := b； b := t； end； end； function FindKth(left,right,n:integer):integer； var tmp,value,i,j:integer； begin if left = right then exit(left)； tmp:= random(right-left) + left； swap(atmp,aleft)； value := ； i := left； j := right； while ij do begin while (ij) and ( ) do dec(j)； if ij then begin ai := aj； inc(i)； end else break； while (ij) and ( ) do inc(i)； if ij then begin aj := ai； dec(j)； end else break； end； if in then begin dec(i)； exit( )； end； exit(i)； end； var i:integer； begin randomize； ans := -1； m:=5； for i:=1 to m do read(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 0 do begin if an,j k then break； dec(j)； end； 北京清北學(xué)堂 報(bào)名咨詢