資源簡介 第十四屆全國青少年信息學奧林匹克聯賽初賽試題( 提高組 Pascal 語言 二小時完成 )● 全部試題答案均要求寫在答卷紙上,寫在試卷紙上一律無效 ●●一、 單項選擇題 (共10題,每題1.5分,共計15分。每題有且僅有一個正確答案)。1. 在以下各項中,( )不是操作系統軟件。A. Solaris B. Linux C. Sybase D. Windows Vista E. Symbian2.微型計算機中,控制器的基本功能是( )。A. 控制機器各個部件協調工作 B. 實現算術運算和邏輯運算 C. 存儲各種控制信息D. 獲取外部信息 E. 存放程序和數據3. 設字符串S=”Olympic”,S的非空子串的數目是( )。A. 29 B. 28 C. 16 D. 17 E. 74.完全二叉樹共有2*N-1個結點,則它的葉節點數是( )。A. N-1 B. 2*N C. N D. 2N-1 E. N/25.將數組{8, 23, 4, 16, 77, -5, 53, 100}中的元素按從大到小的順序排列,每次可以交換任意兩個元素,最少需要交換( )次。A. 4 B. 5 C. 6 D. 7 E. 86.設棧S的初始狀態為空,元素a,b,c,d,e,f依次入棧S,出棧的序列為b,d,c,f,e,a,則棧S的容量至少應該是( )。A. 6 B. 5 C. 4 D. 3 E. 27. 與十進制數28.5625相等的四進制數是( )。A. 123.21 B. 131.22 C. 130.22 D. 130.21 E. 130.208. 遞歸過程或函數調用時,處理參數和返回地址,通常使用一種稱為()的數據結構。A. 隊列 B. 多維數組 C. 線性表 D. 鏈表 E. 棧9. TCP/IP是一組構成互聯網基礎的網絡協議,字面上包括兩組協議:傳輸控制協議(TCP)和網際協議(IP)。TCP/IP 協議把Internet網絡系統描述成具有四個層次功能的網絡模型,其中提供源節點和目的節點之間的信息傳輸服務,包括尋址和路由器選擇等功能的是()。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題,每題1.5分,共計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)∨(C∧D∨A) B. ((A∧B)∨C)∧DC. (B∨C∨D)∨D∧A D. A∧(D∨C)∧B14.Web2.0是近年來互聯網的熱門概念之一,其核心思想是互動與分享。下列網站中,( )是典型的Web2.0應用。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 6C. 4 2 1 7 5 6 3 D. 2 4 1 5 7 3 617. 面向對象程序設計(Object-Oriented Programming)是一種程序設計的方法論,它將對象作為程序的基本單元,將數據和程序封裝在對象中,以提高軟件的重用性、靈活性和擴展性。下面關于面向對象程序設計的說法中,正確的是( )。A. 面向對象程序設計通常采用自頂向下設計方法進行設計。B. 面向對象程序設計方法具有繼承性(inheritance)、封裝性(encapsulation)、多態性(polymorphism)等幾大特點。C. 支持面向對象特性的語言稱為面向對象的編程語言,目前較為流行的有C++、JAVA、C#等。D. 面向對象的程序設計的雛形來自于Simula語言,后來在SmallTalk語言的完善和標準化的過程中得到更多的擴展和對以前思想的重新注解。至今,SmallTalk語言仍然被視為面向對象語言的基礎。18. 設T是一棵有n個頂點的樹,下列說法正確的是( )。A. T是連通的、無環的 B. T是連通的,有n-1條邊C. T是無環的,有n-1條邊 D. 以上都不對19. NOIP競賽推薦使用的語言環境有( )。A. Dev-C++ 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城市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 02.書架上有21本書,編號從1到21,從其中選4本,其中每兩本的編號都不相鄰的選法一共有______種。四.閱讀程序寫結果(共4題,每題8分,共計32分)1. vari,a,b,c,d:integer;f:array[0..3] of integer;beginfor i:=0 to 3 doread(f[i]);a := f[0] + f[1] + f[2] + f[3];a := a div f[0];b := f[0] + f[2] + f[3];b := b div a;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]) thenbegina := a + b;writeln(a);end elsebeginc := c + d;writeln(c);end;end.輸入:9 19 29 39輸出:_______________2.procedure foo(a,b,c:integer);beginif a>b then foo(c,a,b)else writeln(a, ',', b, ',', c)end;vara,b,c:integer;beginread(a, b, c);foo(a,b,c);end.輸入:2 1 3輸出:__________3.procedure f(a,b,c:integer);beginwrite(a, b, c, '/');if (a = 3) and (b = 2) and (c = 1) then exit;if belseif aif aend;vara,b,c:integer;beginread(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(s[i]) >= ord('A')) and (ord(s[i]) <= ord('Z')) thens[i] := chr(ord(s[i]) - ord('A') + ord('a'));for i:=1 to len doif (ord(s[i])else s[i]:= chr(ord(s[i])-23);write(s);write('/');for j:=1 to 3 do begini:=1;while i<=len-j dobegins[i]:=s[i+j];i:=i+j;end;end;writeln(s);end.輸入:ABCDEFGuvwxyz輸出:___________________________________________五.完善程序 (前6空,每空3分,后5空,每空2分,共28分)1.(找第k大的數) 給定一個長度為1,000,000的無序正整數序列,以及另一個數n(1<=n<=1000000),接下來以類似快速排序的方法找到序列中第n大的數(關于第n大的數:例如序列{1,2,3,4,5,6}中第3大的數是4)。vara:array[1..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(left);tmp:= random(right-left) + left;swap(a[tmp],a[left]);value := ① ;i := left;j := right;while ibeginwhile (iif ia[i] := a[j]; inc(i);end else break;while (iif ia[j] := a[i]; dec(j);end else break;end;④if iif i>n then begin dec(i); exit( ⑥ ); end;exit(i);end;vari:integer;beginrandomize;ans := -1;m:=5;for i:=1 to m doread(a[i]);read(n);ans:= FindKth(1,m,n);writeln(a[ans]);end.2.(矩陣中的數字)有一個n*n(1<=n<=5000)的矩陣a, 對于1<=i < n,1<=j<=n, a[i,j] < a[i + 1,j] a[j,i] < a[j,i+1]。即矩陣中左右相鄰的兩個元素,右邊的元素一定比左邊的大。上下相鄰的兩個元素,下面的元素一定比上面的大。給定矩陣a中的一個數字k,找出k所在的行列(注意:輸入數據保證矩陣中的數各不相同)。varn,k,answerx,answery:integer;a:array[1..5000,1..5000] of integer;procedure FindKPosition;vari,j:integer;begini:=n;j:=n;while j>0 dobeginif a[n,j] < k then break;dec(j);end;①while a[i,j]<>k dobeginwhile ( ② ) and (i>1) do dec(i);while ( ③ ) and (j<=n) do inc(j);end;④⑤end;vari,j:integer;beginread(n);for i:=1 to n dofor j:=1 to n doread(a[i,j]);read(k);FindKPosition;writeln(answerx, ' ', answery);end. 展開更多...... 收起↑ 資源預覽 縮略圖、資源來源于二一教育資源庫