1999年至歷年信息學奧賽提高組初賽試題-資料下載頁

　　

【正文】 的數據結構。A．隊列 B．多維數組 C．線性表 D．鏈表 E．棧9．TCP/IP 是一組構成互聯網基礎的網絡協議，字面上包括兩組協議：傳輸控制協議（TCP）和網際互聯協議（IP）。TCP/IP協議把Internet網絡系統描述成具有4個層次功能的網絡模型，其中提供源節點和目的節點之間的信息傳輸服務，包括尋址和路由器選擇等功能的是（）。A．鏈路層 B．網絡層 C．傳輸層 D．應用層 E．會話層10．對有序數組{5,13,19,21,37,56,64,75,88,92,100}進行二分查找，等概率情況下，查找成功的平均查找長度（平均比較次數）是（）。A．35/11 B．34/11 C．33/11 D．32/11 E．34/10二、不定項選擇題（共10題，共計15分。每題正確答案的個數大于或等于1。多選或少選均不得分）。11．下列關于圖靈的說法正確的有（ ）。A．圖靈獎是美國計算機協會與1966年設立的，專門鼓勵那些對計算機做出重要貢獻的個人B．圖靈獎有“計算機界諾貝爾獎”之稱。 C．迄今為止，還沒有華裔計算機科學家獲此殊榮。D．圖靈獎的名稱取自計算機科學先驅、英國科學家阿蘭圖靈。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．，其核心是互動與分享。下列網站中，（ ）。A．Sina B．Flickr C．Yahoo D．Google15．(2008)10+ (5B)16 的結果是（）。A．（833）16 B．（2099）10 C．（4063）8 D．（100001100011）216．二叉樹T，已知其先序遍歷是1 2 4 3 5 7 6（數字為節點編號，以下同），后序遍歷是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．面向對象的程序設計（ObjectOriented Programming）是一種程序設計的方法論，它將對象作為程序設計的基本單元，將數據和程序封裝在對象中，以提高軟件的重用性、靈活性、和擴展性。下面關于面向對象的程序設計說法中正確的是（ ）。A．面向對象的程序設計方法通常采用自頂向下的設計方法進行設計。B．面向對象的程序設計方法具有繼承性（inheritance）、封裝性（encapsulation）、多態性（polymorphism）等幾大特點。C．支持面向對象特性稱為面向對象的編程語言，目前較為流行的有C++，JAVA，C等。D．面向對象的程序設計的雛形來自于Simula語言，后來在SmallTalk語言的完善和標準化的過程中得到更多的擴展和對以前的思想的重新注解。至今，SmallTalk語言仍然被視為面向對象的基礎。18．設T是一棵有n個定點的樹，以下說法正確的是（ ）。A．T是聯通的，無環的 B．T是聯通的，有n1條邊C．T是無環的，有n1條邊 D．以上都不對19．NOIP競賽推薦使用的語言環境有（ ）。A．DevC++ B．Visual C++ C．Free Pascal D．Lazarus20．在下列防火墻（Firewall）的說法中，正確的有（ ）。A．防火墻是一項協助確保信息安全的設備，其會依照特定的規則，允許或是限制數據通過B．防火墻可能是一臺專屬硬件或是安裝在一般硬件上的一套軟件C．網絡層防火墻可以視為一種IP數據包過濾器，只允許符合特定規定的數據包通過，其余的一概禁止穿越防火墻D．應用層防火墻是在TCP/IP的“應用層”上工作，可以攔截進出某應用程序的所有數據包三、問題求解（共2題，每題5分，共計10分）1．有6個城市，任何兩個城市之間有一條道路連接，6個城市之間兩兩之間的距離如下表表示，則城市1到城市6的最短距離為____________。城市1城市2城市3城市4城市5城市6城市102311215城市22025312城市3320365城市4153079城市51236702城市6151259202．書架上有21本書，編號從1 到 21 從中選4 本，其中每兩本的編號都不相鄰的選法一共有___________________種。四、閱讀程序寫結果（共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大的數）給定一個長度為1000000的無序正整數序列，以及另一個數n(1=n=1000000)，接下來以類似快速排序的方法找到序列中第n大的數（關于第n大的數：例如序列{1，2，3，4，5，6}中第3大的數是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．（矩陣中的數字）有一個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中的一個數字k，找出k所在的行列（注意：輸入數據保證矩陣中的數各不相同）。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)全國青少年信息學奧林匹克聯賽初賽試題（ 提高組 Pascal 語言 二小時完成 ）●● 全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效 ●●一、 單項選擇題 （共 10 題，每題 分，共計 15 分。每題有且僅有一個正確答案.）。1. 在以下各項中。（ ）不是 CPU 的組成部分。A. 控制器 B. 運算器 C. 寄存器 D. 主板 E. 算術邏輯單元(ALU) 2. 在關系數據庫中, 存放在數據庫中的數據的邏輯結構以( )為主。A. 二叉樹 B. 多叉樹 C. 哈希表 D. B+樹 E. 二維表，只有（ ）不是計算機存儲容量的常用單位。A. Byte B. KB C