【正文】 的數(shù)據(jù)結(jié)構(gòu)。A．隊列 B．多維數(shù)組 C．線性表 D．鏈表 E．棧9．TCP/IP 是一組構(gòu)成互聯(lián)網(wǎng)基礎(chǔ)的網(wǎng)絡(luò)協(xié)議，字面上包括兩組協(xié)議：傳輸控制協(xié)議（TCP）和網(wǎng)際互聯(lián)協(xié)議（IP）。TCP/IP協(xié)議把Internet網(wǎng)絡(luò)系統(tǒng)描述成具有4個層次功能的網(wǎng)絡(luò)模型，其中提供源節(jié)點和目的節(jié)點之間的信息傳輸服務(wù)，包括尋址和路由器選擇等功能的是（）。A．鏈路層 B．網(wǎng)絡(luò)層 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題，共計15分。每題正確答案的個數(shù)大于或等于1。多選或少選均不得分）。11．下列關(guān)于圖靈的說法正確的有（ ）。A．圖靈獎是美國計算機協(xié)會與1966年設(shè)立的，專門鼓勵那些對計算機做出重要貢獻的個人B．圖靈獎有“計算機界諾貝爾獎”之稱。 C．迄今為止，還沒有華裔計算機科學家獲此殊榮。D．圖靈獎的名稱取自計算機科學先驅(qū)、英國科學家阿蘭圖靈。12．計算機在工作過程中，若突然停電，（ ）中不會丟失信息不會丟失。A．硬盤 B．CPU C．ROM D．RAM13．若A=True，B=False，C=True，D=False，以下邏輯運算表達式真的有（ ）。A．（A∧B）V（C∧DV172。A） B．（（172。A∧B）VC）∧172。B C．（BVCVD）VD∧A D．A∧（DV172。C）∧B14．，其核心是互動與分享。下列網(wǎng)站中，（ ）。A．Sina B．Flickr C．Yahoo D．Google15．(2008)10+ (5B)16 的結(jié)果是（）。A．（833）16 B．（2099）10 C．（4063）8 D．（100001100011）216．二叉樹T，已知其先序遍歷是1 2 4 3 5 7 6（數(shù)字為節(jié)點編號，以下同），后序遍歷是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 4 D．2 4 1 5 7 3 617．面向?qū)ο蟮某绦蛟O(shè)計（ObjectOriented Programming）是一種程序設(shè)計的方法論，它將對象作為程序設(shè)計的基本單元，將數(shù)據(jù)和程序封裝在對象中，以提高軟件的重用性、靈活性、和擴展性。下面關(guān)于面向?qū)ο蟮某绦蛟O(shè)計說法中正確的是（ ）。A．面向?qū)ο蟮某绦蛟O(shè)計方法通常采用自頂向下的設(shè)計方法進行設(shè)計。B．面向?qū)ο蟮某绦蛟O(shè)計方法具有繼承性（inheritance）、封裝性（encapsulation）、多態(tài)性（polymorphism）等幾大特點。C．支持面向?qū)ο筇匦苑Q為面向?qū)ο蟮木幊陶Z言，目前較為流行的有C++，JAVA，C等。D．面向?qū)ο蟮某绦蛟O(shè)計的雛形來自于Simula語言，后來在SmallTalk語言的完善和標準化的過程中得到更多的擴展和對以前的思想的重新注解。至今，SmallTalk語言仍然被視為面向?qū)ο蟮幕A(chǔ)。18．設(shè)T是一棵有n個定點的樹，以下說法正確的是（ ）。A．T是聯(lián)通的，無環(huán)的 B．T是聯(lián)通的，有n1條邊C．T是無環(huán)的，有n1條邊 D．以上都不對19．NOIP競賽推薦使用的語言環(huán)境有（ ）。A．DevC++ B．Visual C++ C．Free Pascal D．Lazarus20．在下列防火墻（Firewall）的說法中，正確的有（ ）。A．防火墻是一項協(xié)助確保信息安全的設(shè)備，其會依照特定的規(guī)則，允許或是限制數(shù)據(jù)通過B．防火墻可能是一臺專屬硬件或是安裝在一般硬件上的一套軟件C．網(wǎng)絡(luò)層防火墻可以視為一種IP數(shù)據(jù)包過濾器，只允許符合特定規(guī)定的數(shù)據(jù)包通過，其余的一概禁止穿越防火墻D．應用層防火墻是在TCP/IP的“應用層”上工作，可以攔截進出某應用程序的所有數(shù)據(jù)包三、問題求解（共2題，每題5分，共計10分）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分，共計32分）。1．var i,a,b,c,d:integer。 f:array[0..3] of integer。begin for i:=0 to 3 do read(f[i])。 a:=f[0]+f[1]+f[2]+f[3]。 a:=a div f[0]。 b:=f[0]+f[2]+f[3]。 c:=(b*f[1]+a) div f[2]。 d:=f[(b div c) mod 4]。 if (f[(a+b+c+d) mod 4]f[2]) then begin a:=a+b。 writeln(a) endelsebegin 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,39。,39。,b,39。,39。,c)end。var a,b,c:integer。begin readln(a,b,c)。 foo(a,b,c)。end.輸入：2 1 3輸出：_________________3．procedure f(a,b,c:integer)。begin write(a,b,c,39。/39。)。 if (a=3)and(b=2)and(c=1) then exit。 if (bc) then f(a,c,b)else if ab then if ac then f(c,a,b) else f(b,c,a)。end。var a,b,c:integer。beginreadln(a,b,c)。f(a,b,c)。end.輸入：1 3 2輸出：____________________4．var s:string。 i,j,len,k:integer。beginreadln(s)。len:=length(s)。for i:=1 to len do if (ord(s[i])=ord(39。A39。)) and (ord(s[i])=ord(39。Z39。)) then s:=chr(ord(s[i])ord(39。A39。)+ord(39。a39。))。for i:=1 to len doif (ord(s[i])ord(39。X39。)) then s:=chr(ord(s[i])+3) else s:=chr(ord(s[i])23)。write(s)。write(39。/39。)。for j:=1 to 3 dobegin i:=1。 while i=lenj do begins[i]:=s[i+j]。i:=i+j。 end。end。writeln(s)。end.輸入：ABCDEFGuvwxyz輸出：________________________________五．完善程序（前6空，每空3分，后5空，每空2分，共28分）。1．（找第k大的數(shù)）給定一個長度為1000000的無序正整數(shù)序列，以及另一個數(shù)n(1=n=1000000)，接下來以類似快速排序的方法找到序列中第n大的數(shù)（關(guān)于第n大的數(shù)：例如序列{1，2，3，4，5，6}中第3大的數(shù)是4）Var a:array[1..1000000] of integer。n,m,ans:integer。procedure swap(var a,b:integer)。var t:integer。begin if (ab) then begint:=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(rightleft)+left。 swap(a[tmp],a[left])。 value:=____①_____ i:=left。 j:=right。while ij do begin while (ij) and (________②______) do dec(j)。 if ij then begin a[i]:=a[j]。inc(i)。 end else break。 while (ij) and (___③___) do inc(i)。 if ij then begin a[j]:=a[i]。 dec(j)。 end else break。 end。 ____④_____ if in then begin inc(i)。 exit(FindKth(_____⑤_____))。end。 if in then begin dec(j)。 exit(______⑥________)。end。 exit(i)。end。var i:integer。begin randomize。 ans:=1。m:=5。for i:=1 to m do read(a[i])。read(n)。ans:=FindKth(1,m,n)。writeln(a[ans])。end.2．（矩陣中的數(shù)字）有一個n*n（1≤n≤5000)的矩陣a，對于1≤in, 1≤j≤n, a[i,j]a[i+1,j] a[j,i]a[j,i+1]。即矩陣中左右相鄰的兩個元素，右邊的元素一定比左邊的大。上下相鄰的兩個元素，下面的元素一定比上面的大。給定矩陣a中的一個數(shù)字k，找出k所在的行列（注意：輸入數(shù)據(jù)保證矩陣中的數(shù)各不相同）。var n,k,answerx,answery:integer。 a:array[1..5000,1..5000] of integer。Procedure FindKPosition。Var I,j:integer。Begin i:=n。 j:=n。 while j0 do begin if a[n,j]k then break。 dec(j)。 end。 ______①_________ while a[i,j]k do begin while (___②_____) and (i1) do dec(i)。 while (___③_____) and (j=n) do inc(j)。 end。 _______④________ _______⑤________end。var i,j:integer。begin read(n)。 for i:=1 to n do for j:=1 to n do read(a[i,j])。 read(k)。 FindKPosition。 writeln(answerx,39。 39。,answery)。end.第十三屆(2007)全國青少年信息學奧林匹克聯(lián)賽初賽試題（ 提高組 Pascal 語言 二小時完成 ）●● 全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效 ●●一、 單項選擇題 （共 10 題，每題 分，共計 15 分。每題有且僅有一個正確答案.）。1. 在以下各項中。（ ）不是 CPU 的組成部分。A. 控制器 B. 運算器 C. 寄存器 D. 主板 E. 算術(shù)邏輯單元(ALU) 2. 在關(guān)系數(shù)據(jù)庫中, 存放在數(shù)據(jù)庫中的數(shù)據(jù)的邏輯結(jié)構(gòu)以( )為主。A. 二叉樹 B. 多叉樹 C. 哈希表 D. B+樹 E. 二維表，只有（ ）不是計算機存儲容量的常用單位。A. Byte B. KB C