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