第一篇：高中信息技術 全國青少年奧林匹克聯(lián)賽教案 排序算法

全國青少年信息學奧林匹克聯(lián)賽

排序算法

?

一、插入排序(Insertion Sort)

1.基本思想：

每次將一個待排序的數(shù)據(jù)元素，插入到前面已經(jīng)排好序的數(shù)列中的適當位置，使數(shù)列依然有序；直到待排序數(shù)據(jù)元素全部插入完為止。2.排序過程： 【示例】：

[初始關鍵字] [49] 38 65 97 76 13 27 49 J=2(38)[38 49] 65 97 76 13 27 49 J=3(65)[38 49 65] 97 76 13 27 49 J=4(97)[38 49 65 97] 76 13 27 49 J=5(76)[38 49 65 76 97] 13 27 49 J=6(13)[13 38 49 65 76 97] 27 49 J=7(27)[13 27 38 49 65 76 97] 49 J=8(49)[13 27 38 49 49 65 76 97] Procedure InsertSort(Var R : FileType);//對R[1..N]按遞增序進行插入排序, R[0]是監(jiān)視哨// Begin for I := 2 To N Do //依次插入R[2],...,R[n]// begin R[0] := R[I];J := I1 end R[J + 1] := R[0];//插入R[I] // end End;//InsertSort //

二、選擇排序 1.基本思想：

每一趟從待排序的數(shù)據(jù)元素中選出最小（或最大）的一個元素，順序放在已排好序的數(shù)列的最后，直到全部待排序的數(shù)據(jù)元素排完。2.排序過程： 【示例】：

初始關鍵字 [49 38 65 97 76 13 27 49] 第一趟排序后 13 ［38 65 97 76 49 27 49] 第二趟排序后 13 27 ［65 97 76 49 38 49] 第三趟排序后 13 27 38 [97 76 49 65 49] 第四趟排序后 13 27 38 49 [49 97 65 76] 第五趟排序后 13 27 38 49 49 [97 97 76] 第六趟排序后 13 27 38 49 49 76 [76 97] 第七趟排序后 13 27 38 49 49 76 76 [ 97] 最后排序結(jié)果 13 27 38 49 49 76 76 97 Procedure SelectSort(Var R : FileType);//對R[1..N]進行直接選擇排序 // Begin for I := 1 To N1趟選擇排序// begin K := I;For J := I + 1 To N Do //在當前無序區(qū)R[I..N]中選最小的元素R[K]// begin If R[J] < R[K] Then K := J end;If K <> I Then //交換R[I]和R[K] // begin Temp := R[I];R[I] := R[K];R[K] := Temp;end;end End.//SelectSort //

三、冒泡排序(BubbleSort)1.基本思想：

兩兩比較待排序數(shù)據(jù)元素的大小，發(fā)現(xiàn)兩個數(shù)據(jù)元素的次序相反時即進行交換，直到?jīng)]有反序的數(shù)據(jù)元素為止。2.排序過程：

設想被排序的數(shù)組R［1..N］垂直豎立，將每個數(shù)據(jù)元素看作有重量的氣泡，根據(jù)輕氣泡不能在重氣泡之下的原則，從下往上掃描數(shù)組R，凡掃描到違反本原則的輕氣泡，就使其向上“漂浮”，如此反復進行，直至最后任何兩個氣泡都是輕者在上，重者在下為止。【示例】：

13 13 13 13 13 13 13 38 49 27 27 27 27 27 27 65 38 49 38 38 38 38 38 97 65 38 49 49 49 49 49 76 97 65 49 49 49 49 49 13 76 97 65 65 65 65 65 27 27 76 97 76 76 76 76 49 49 49 76 97 97 97 97 Procedure BubbleSort(Var R : FileType)//從下往上掃描的起泡排序// Begin For I := 1 To N-1 Do //做N-1趟排序// begin NoSwap := True;//置未排序的標志// For J := N1 //從右向左掃描，查找第1個小于 X的元素// If I < J Then //已找到R[J] 〈X// begin R[I] := R[J];//相當于交換R[I]和R[J]// I := I + 1 end;While(R[I] <= X)And(I < J)Do I := I + 1 //從左向右掃描，查找第1個大于 X的元素/// end;If I < J Then //已找到R[I] > X // begin R[J] := R[I];//相當于交換R[I]和R[J]// J := J-1 end Until I = J;R[I] := X //基準X已被最終定位// End;//Parttion // Procedure QuickSort(Var R :FileType;S,T: Integer);//對R[S..T]快速排序// Begin If S < T Then //當R[S..T]為空或只有一個元素是無需排序// begin Partion(R, S, T, I);//對R[S..T]做劃分// QuickSort(R, S, I-1);//遞歸處理左區(qū)間R[S,I-1]// QuickSort(R, I+1,T);//遞歸處理右區(qū)間R[I+1..T] // end;End.//QuickSort//

五、堆排序(Heap Sort)1.基本思想：

堆排序是一樹形選擇排序，在排序過程中，將R[1..N]看成是一顆完全二叉樹的順序存儲結(jié)構(gòu)，利用完全二叉樹中雙親結(jié)點和孩子結(jié)點之間的內(nèi)在關系來選擇最小的元素。

2.堆的定義: N個元素的序列K1,K2,K3,...,Kn.稱為堆，當且僅當該序列滿足特性：

Ki≤K2i Ki ≤K2i+1(1≤ I≤ [N/2])

堆實質(zhì)上是滿足如下性質(zhì)的完全二叉樹：樹中任一非葉子結(jié)點的關鍵字均大于等于其孩子結(jié)點的關鍵字。例如序列10,15,56,25,30,70就是一個堆，它對應的完全二叉樹如上圖所示。這種堆中根結(jié)點（稱為堆頂）的關鍵字最小，我們把它稱為小根堆。反之，若完全二叉樹中任一非葉子結(jié)點的關鍵字均大于等于其孩子的關鍵字，則稱之為大根堆。3.排序過程：

堆排序正是利用小根堆（或大根堆）來選取當前無序區(qū)中關鍵字小（或最大）的記錄實現(xiàn)排序的。我們不妨利用大根堆來排序。每一趟排序的基本操作是：將當前無序區(qū)調(diào)整為一個大根堆，選取關鍵字最大的堆頂記錄，將它和無序區(qū)中的最后一個記錄交換。這樣，正好和直接選擇排序相反，有序區(qū)是在原記錄區(qū)的尾部形成并逐步向前擴大到整個記錄區(qū)。

【示例】：對關鍵字序列42，13，91，23，24，16，05，88建堆 Procedure Sift(Var R :FileType;I, M : Integer);//在數(shù)組R[I..M]中調(diào)用R[I]，使得以它為完全二叉樹構(gòu)成堆。事先已知其左、右子樹(2I+1 <=M時)均是堆// Begin X := R[I];J := 2*I;//若J <=M, R[J]是R[I]的左孩子// While J <= M Do //若當前被調(diào)整結(jié)點R[I]有左孩子R[J]// begin If(J < M)And R[J].Key < R[J+1].Key Then J := J + 1 //令J指向關鍵字較大的右孩子// //J指向R[I]的左、右孩子中關鍵字較大者// If X.Key < R[J].Key Then //孩子結(jié)點關鍵字較大// begin R[I] := R[J];//將R[J]換到雙親位置上// I := J;J := 2*I //繼續(xù)以R[J]為當前被調(diào)整結(jié)點往下層調(diào)整// end;6

Else Exit //調(diào)整完畢，退出循環(huán)// end R[I] := X;//將最初被調(diào)整的結(jié)點放入正確位置// End;//Sift// Procedure HeapSort(Var R : FileType);//對R[1..N]進行堆排序// Begin

For I := N Div Downto 1 Do //建立初始堆//

Sift(R, I , N)

For I := N Downto 2 do //進行N-1趟排序//

begin

T := R[1];R[1] := R[I];R[I] := T;//將當前堆頂記錄和堆中最后一個記錄交換//

Sift(R, 1, I-1)//將R[1..I-1]重成堆//

end End;//HeapSort//

六、幾種排序算法的比較和選擇

1.選取排序方法需要考慮的因素：(1)待排序的元素數(shù)目n；(2)元素本身信息量的大小；(3)關鍵字的結(jié)構(gòu)及其分布情況；(4)語言工具的條件，輔助空間的大小等。2.小結(jié)：

(1)若n較小(n <= 50)，則可以采用直接插入排序或直接選擇排序。由于直接插入排序所需的記錄移動操作較直接選擇排序多，因而當記錄本身信息量較大時，用直接選擇排序較好。

(2)若文件的初始狀態(tài)已按關鍵字基本有序，則選用直接插入或冒泡排序為宜。(3)若n較大，則應采用時間復雜度為O(nlog2n)的排序方法：快速排序、堆排序或歸并排序。快速排序是目前基于比較的內(nèi)部排序法中被認為是最好的方法。(4)在基于比較排序方法中，每次比較兩個關鍵字的大小之后，僅僅出現(xiàn)兩種可能的轉(zhuǎn)移，因此可以用一棵二叉樹來描述比較判定過程，由此可以證明：當文件的n 7

個關鍵字隨機分布時，任何借助于“比較”的排序算法，至少需要O(nlog2n)的時間。(5)當記錄本身信息量較大時，為避免耗費大量時間移動記錄，可以用鏈表作為存儲結(jié)構(gòu)。

第二篇：高中信息技術 全國青少年奧林匹克聯(lián)賽教案 枚舉法

信息學奧賽中的基本算法(枚舉法)

枚舉法，常常稱之為窮舉法，是指從可能的集合中一一枚舉各個元素，用題目給定的約束條件判定哪些是無用的，哪些是有用的。能使命題成立者，即為問題的解。

采用枚舉算法解題的基本思路：

（1）確定枚舉對象、枚舉范圍和判定條件；（2）一一枚舉可能的解，驗證是否是問題的解

下面我們就從枚舉算法的的優(yōu)化、枚舉對象的選擇以及判定條件的確定，這三個方面來探討如何用枚舉法解題。

枚舉算法應用

例1：百錢買百雞問題：有一個人有一百塊錢，打算買一百只雞。到市場一看，大雞三塊錢一只，小雞一塊錢三只，不大不小的雞兩塊錢一只。現(xiàn)在，請你編一程序，幫他計劃一下，怎么樣買法，才能剛好用一百塊錢買一百只雞？

算法分析：此題很顯然是用枚舉法，我們以三種雞的個數(shù)為枚舉對象（分別設為x,y,z）,以三種雞的總數(shù)（x+y+z）和買雞用去的錢的總數(shù)(x*3+y*2+z)為判定條件，窮舉各種雞的個數(shù)。

下面是解這個百雞問題的程序 var x,y,z:integer;begin for x:=0 to 100 do for y:=0 to 100 do for z:=0 to 100 do{枚舉所有可能的解} if(x+y+z=100)and(x*3+y*2+z div 3=100)and(z mod 3=0)then writeln('x=',x,'y=',y,'z=',z);{驗證可能的解，并輸出符合題目要求的解} end.上面的條件還有優(yōu)化的空間，三種雞的和是固定的，我們只要枚舉二種雞（x,y），第三種雞就可以根據(jù)約束條件求得（z=100-x-y），這樣就縮小了枚舉范圍，請看下面的程序： var x,y,z:integer;begin for x:=0 to 100 do for y:=0 to 100-x do begin z:=100-x-y;if(x*3+y*2+z div 3=100)and(z mod 3=0)then writeln('x=',x,'y=',y,'z=',z);end;end.未經(jīng)優(yōu)化的程序循環(huán)了101 次，時間復雜度為O(n)；優(yōu)化后的程序只循環(huán)了

2（102*101/2）次，時間復雜度為O(n)。從上面的對比可以看出，對于枚舉算法，加強約束條件，縮小枚舉的范圍，是程序優(yōu)化的主要考慮方向。

在枚舉算法中，枚舉對象的選擇也是非常重要的，它直接影響著算法的時間復雜度，選擇適當?shù)拿杜e對象可以獲得更高的效率。如下例：

3例

2、將1,2...9共9個數(shù)分成三組,分別組成三個三位數(shù),且使這三個三位數(shù)構(gòu)成1:2:3的比例,試求出所有滿足條件的三個三位數(shù).例如:三個三位數(shù)192,384,576滿足以上條件.(NOIP1998pj)算法分析：這是1998年全國分區(qū)聯(lián)賽普及組試題（簡稱NOIP1998pj，以下同）。此題數(shù)據(jù)規(guī)模不大，可以進行枚舉，如果我們不加思地以每一個數(shù)位為枚舉對象，一位一位地去枚舉：

for a:=1 to 9 do for b:=1 to 9 do ………

for i:=1 to 9 do

９這樣下去，枚舉次數(shù)就有9次，如果我們分別設三個數(shù)為x,2x,3x，以x為枚舉對象，３窮舉的范圍就減少為９，在細節(jié)上再進一步優(yōu)化，枚舉范圍就更少了。程序如下： var t,x:integer;s,st:string;c:char;begin for x:=123 to 321 do{枚舉所有可能的解} begin t:=0;str(x,st);{把整數(shù)x轉(zhuǎn)化為字符串，存放在st中} str(x*2,s);st:=st+s;str(x*3,s);st:=st+s;for c:='1' to '9' do{枚舉9個字符，判斷是否都在st中} if pos(c,st)<>0 then inc(t)else break;{如果不在st中，則退出循環(huán)} if t=9 then writeln(x,' ',x*2,' ',x*3);end;end.在枚舉法解題中，判定條件的確定也是很重要的，如果約束條件不對或者不全面，就窮舉不出正確的結(jié)果，我們再看看下面的例子。例３ 一元三次方程求解(noip2001tg)

32問題描述 有形如：ax+bx+cx+d=0 這樣的一個一元三次方程。給出該方程中各項的系數(shù)(a，b，c，d 均為實數(shù))，并約定該方程存在三個不同實根(根的范圍在-100至100之間)，且根與根之差的絕對值>=1。

要求由小到大依次在同一行輸出這三個實根(根與根之間留有空格)，并精確到小數(shù)點后2位。

提示：記方程f(x)=0，若存在2個數(shù)x1和x2，且x1

樣例

輸入：1-5-4 20 輸出：-2.00 2.00 5.00 算法分析：由題目的提示很符合二分法求解的原理，所以此題可以用二分法。用二分法解題相對于枚舉法來說很要復雜很多。此題是否能用枚舉法求解呢？再分析一下題目，根的范圍在-100到100之間，結(jié)果只要保留兩位小數(shù)，我們不妨將根的值域擴大100倍 2

（-10000<=x<=10000），再以根為枚舉對象，枚舉范圍是-10000到10000，用原方程式進行一一驗證，找出方程的解。

有的同學在比賽中是這樣做 var k:integer;a,b,c,d,x :real;begin read(a,b,c,d);for k:=-10000 to 10000 do begin x:=k/100;if a*x*x*x+b*x*x+c*x+d=0 then write(x:0:2,' ');end;end.用這種方法，很快就可以把程序編出來，再將樣例數(shù)據(jù)代入測試也是對的，等成績下來才發(fā)現(xiàn)這題沒有全對，只得了一半的分。

這種解法為什么是錯的呢？錯在哪里？前面的分析好象也沒錯啊，難道這題不能用枚舉法做嗎？ 看到這里大家可能有點迷惑了。

在上面的解法中，枚舉范圍和枚舉對象都沒有錯，而是在驗證枚舉結(jié)果時，判定條件用

32錯了。因為要保留二位小數(shù)，所以求出來的解不一定是方程的精確根，再代入ax+bx+cx+d

32中，所得的結(jié)果也就不一定等于0，因此用原方程ax+bx+cx+d=0作為判斷條件是不準確的。

32我們換一個角度來思考問題，設f(x)=ax+bx+cx+d，若x為方程的根，則根據(jù)提示可知，必有f(x-0.005)*(x+0.005)<0，如果我們以此為枚舉判定條件，問題就逆刃而解。另外，如果f(x-0.005)=0，哪么就說明x-0.005是方程的根，這時根據(jù)四舍5入，方程的根也為x。所以我們用(f(x-0.005)*f(x+0.005)<0)和(f(x-0.005)=0)作為判定條件。為了

32程序設計的方便，我們設計一個函數(shù)f(x)計算ax+bx+cx+d的值，程序如下： {$N+} var k:integer;a,b,c,d,x:extended;

32function f(x:extended):extended;{計算ax+bx+cx+d的值} begin f:=((a*x+b)*x+c)*x+d;end;begin read(a,b,c,d);for k:=-10000 to 10000 do begin x:=k/100;if(f(x-0.005)*f(x+0.005)<0)or(f(x-0.005)=0)then write(x:0:2,' ');{若x兩端的函數(shù)值異號或x-0.005剛好是方程的根，則確定x為方程的根} end;end.用枚舉法解題的最大的缺點是運算量比較大，解題效率不高，如果枚舉范圍太大（一般以不超過兩百萬次為限），在時間上就難以承受。但枚舉算法的思路簡單，程序編寫和調(diào)

試方便，比賽時也容易想到，在競賽中，時間是有限的，我們競賽的最終目標就是求出問題解，因此，如果題目的規(guī)模不是很大，在規(guī)定的時間與空間限制內(nèi)能夠求出解，那么我們最好是采用枚舉法，而不需太在意是否還有更快的算法，這樣可以使你有更多的時間去解答其他難題。

第三篇：全國青少年信息學奧林匹克聯(lián)賽

全國青少年信息學奧林匹克聯(lián)賽

目錄

高考加分和保送 聯(lián)賽命題宗旨 普及的內(nèi)容

競賽形式和成績評定 試題的知識范圍

全國青少年信息學奧林匹克聯(lián)賽(National Olympiad in Informatics in Provinces簡稱NOIP)自1995年至今已舉辦16次。每年由中國計算機學會統(tǒng)一組織。NOIP在同一時間、不同地點以各省市為單位由特派員組織。全國統(tǒng)一大綱、統(tǒng)一試卷。初、高中或其他中等專業(yè)學校的學生可報名參加聯(lián)賽。聯(lián)賽分初賽和復賽兩個階段。初賽考察通用和實用的計算機科學知識，以筆試為主。復賽為程序設計，須在計算機上調(diào)試完成。參加初賽者須達到一定分數(shù)線后才有資格參加復賽。聯(lián)賽分普及組和提高組兩個組別，難度不同，分別面向初中和高中階段的學生。獲得提高組復賽一等獎的選手即可免高考，而通過大學的保送生考試直接被錄取。

高考加分和保送

NOIP的部分一等獎具有保送名校或者高考加分(分數(shù)的多少視該校自主招生考試結(jié)果而定)的資格。NOIP的部分一等獎有參加省隊選拔賽的資格，省隊的選手可以參加NOI，NOI獲獎選手有保送資格。

聯(lián)賽命題宗旨

全國青少年信息學奧林匹克聯(lián)賽（NOIP）是一項面向全國青少年的信息學競賽和普及活動，旨在向那些在中學階段學習的青少年普及計算機科學知識；給學校的信息技術教育課程提供動力和新的思路；給那些有才華的學生提供相互交流和學習的機會；通過競賽和相關的活動培養(yǎng)和選拔優(yōu)秀的計算機人才。

競賽的目的是為了在更高層次上推動普及。本競賽及其相關活動遵循開放性原則，任何有條件和有興趣的學校和個人，都可以在業(yè)余時間自愿參加。本活動不和現(xiàn)行的學校教學相沖突，也不列入教學計劃，是課外性質(zhì)的因材施教活動。參加者可為初高中學生或其他中等專業(yè)學校的青少年。

普及的內(nèi)容

．計算機的基本組成；

．計算機操作系統(tǒng)使用（windows等）； ．計算機工作的基本原理；

．計算機程序設計的基本方法； ．至少一門高級程序設計語言； ．程序設計中常用的數(shù)據(jù)結(jié)構(gòu)。

普及的重點是根據(jù)中學生的特點，培養(yǎng)學生學習計算機的興趣，使得他們對信息技術的一些本質(zhì)和核心的東西有更多的了解，提高他們創(chuàng)造性地運用程序設計知識解決實際問題的能力。

對學生的能力培養(yǎng)注重

．想象力與創(chuàng)造力；

．對問題的理解和分析能力；

．數(shù)學能力和邏輯思維能力；

．對客觀問題和主觀思維的口頭和書面表達能力；

．人文精神。包括與人的溝通和理解能力，團隊精神與合作能力，恒心和毅力，審美能力等。

競賽形式和成績評定

聯(lián)賽分兩個年齡組：初中組和高中組(普及組和提高組)。每組競賽分兩輪：初試和復試。

．初試形式為筆試，側(cè)重考察學生的計算機基礎知識和編程的基本能力，并對知識面的廣度進行測試。程序設計的描述語言采用Basic（2005年被取消）、C/C++或Pascal。各省市初試成績在本賽區(qū)前百分之十五的學生進入復賽，其分數(shù)不計入復賽的成績。初賽時間為10月的第二個星期六下午 2:30-4:30舉行。

．復試形式為上機，側(cè)重考察學生對問題的分析理解能力，數(shù)學抽象能力，駕馭編程語言的能力和編程技巧、想象力和創(chuàng)造性等。程序設計語言可采用Basic（2005年后被取消）、Pascal、C或C++。各省市競賽的等第獎在復試的優(yōu)勝者中產(chǎn)生。時間為 3小時。只進行一試，約在當年的11 月的第三個周六進行。

試題形式

每次聯(lián)賽的試題分四組：初中組初試賽題；初中組復試賽題；高中組初試賽題；高中組復試賽題。其中，初中組初試賽題和高中組初試賽題類型相同，初中組復試賽題和高中組復試賽題類型相同，但初中組和高中組的題目不完全相同，高中組難度略高；以體現(xiàn)年齡特點和層次要求。

* 初試：初試全部為筆試，滿分100分。試題由四部分組成：

1、選擇題：共20題，每題1．5分，共30分。每題有4個備選方案。試題內(nèi)容包括計算機基本組成與原理、計算機基本操作、信息科技與人類社會發(fā)展的關系等等。

2、問題求解題：共2題，每題5分，共10分。試題給出一個敘述較為簡單的問題，要求學生對問題進行分析，找到一個合適的算法，并推算出問題的解。答案以字符串方式給出，考生給出的答案與標準答案的字符串相同，則得分；否則不得分。

3、程序閱讀理解題：共4題，每題8分，共32分。題目給出一段程序（沒有關于程序功能的說明），有時也會給出程序的輸入，要求考生通過閱讀理解該段程序給出程序的輸出。輸出以字符串的形式給出，如果與標準答案一致，則得分；否則不得分。

4、程序完善題：共 2題，第一題10分，共4空，每空2.5分；第二題18分，共6空，每空3分。兩題共28分。題目給出一段關于程序功能的文字說明，然后給出一段程序代碼，在代碼中略去了若干個語句并在這些位置給出空格，要求考生根據(jù)程序的功能說明和代碼的上下文，填出被略去的語句。填對的，則得分；否則不得分。

（2009年普及組試題為第一題5空，每空3分，第二題前三空每空3分，后兩空每空2分）

*復試：復試的題型和形式向全國信息學奧賽（NOI）靠攏，全部為上機編程題，但難度略低。復試為決出競賽成績的最后一個環(huán)節(jié)。題目包括 4道題，每題100分，共計400分。難度有易有難，既考慮普及面，又考慮選拔的梯度要求。每一道試題包括：題目、問題描述、樣例說明（輸入、輸出及必要的說明）、數(shù)據(jù)范圍（數(shù)據(jù)限制條件）。測試時，測試程序為每道題提供了5~10組測試數(shù)據(jù)，考生程序每答對一組得10~20 分；累計分即為該道題的得分。

試題的知識范圍

考試內(nèi)容主要包括：計算機發(fā)展史、計算機組成、計算機基本原理、計算機程序設計、計算機日常應用等。要求考生掌握至少一門高級程序設計語言（詳見競賽大綱）。為了保持競賽內(nèi)容的相對連續(xù)性，試題涵蓋的知識點和題型至少60％應出現(xiàn)在普及類的參考書目中，其余內(nèi)容可能超出該范圍。

為了考核學生的基礎知識、綜合應用能力，激發(fā)學生的求知欲和創(chuàng)新思維，體現(xiàn)“與時俱進”的特點，競賽題型在保持大綱相對穩(wěn)定、優(yōu)秀學生可能接受和理解的基礎上，按照下述趨勢適當變化

1、增大與課內(nèi)知識結(jié)合的緊密度；

2、增大解題方法的多樣性和靈活程度；

3、增大開放性試題的比例。

試題的知識范圍具體如下：

一．初賽內(nèi)容與要求：

A．計算機的基本常識：

1．計算機和信息社會（信息社會的主要特征、計算機的主要特征、數(shù)字通信網(wǎng)絡的主要特征、數(shù)字化）

2．信息輸入輸出基本原理（信息交換環(huán)境、文字圖形多媒體信息的輸入輸出方式）

3．信息的表示與處理（信息編碼、微處理部件MPU、內(nèi)存儲結(jié)構(gòu)、指令，程序，和存儲程序原理、程序的三種基本控制結(jié)構(gòu)）

4．信息的存儲、組織與管理（存儲介質(zhì)、存儲器結(jié)構(gòu)、文件管理、數(shù)據(jù)庫管理）

5．信息系統(tǒng)組成及互連網(wǎng)的基本知識（計算機構(gòu)成原理、槽和端口的部件間可擴展互連方式、層次式的互連結(jié)構(gòu)、互聯(lián)網(wǎng)絡、TCP/IP協(xié)議、HTTP協(xié)議、WEB應用的主要方式和特點）

6．人機交互界面的基本概念（窗口系統(tǒng)、人和計算機交流信息的途徑（文本及交互操作））

7．信息技術的新發(fā)展、新特點、新應用等。

B．計算機的基本操作：

1.Windows和LINUX的基本操作知識

2.互聯(lián)網(wǎng)的基本使用常識（網(wǎng)上瀏覽、搜索和查詢等）

3.常用的工具軟件使用（文字編輯、電子郵件收發(fā)等）

C．數(shù)據(jù)結(jié)構(gòu)：

1．程序語言中基本數(shù)據(jù)類型(字符、整數(shù)、長整數(shù)、浮點)

2.浮點運算中的精度和數(shù)值比較

3．一維數(shù)組（串）與線性表

4．記錄類型（PASCAL）/ 結(jié)構(gòu)類型（C）

D．程序設計：

1．結(jié)構(gòu)化程序設計的基本概念

2．閱讀理解程序的基本能力

3．具有將簡單問題抽象成適合計算機解決的模型的基本能力

4．具有針對模型設計簡單算法的基本能力

5．程序流程描述（自然語言/偽碼/NS圖/其他）

6．程序設計語言（PASCAL/C/C++，2003仍允許BASIC）

E．基本算法處理：

1．初等算法（計數(shù)、統(tǒng)計、數(shù)學運算等）

2．排序算法（冒泡法、插入排序、合并排序、快速排序）

3．查找（順序查找、二分法）

4．回溯算法

二、復賽內(nèi)容與要求：

在初賽的內(nèi)容上增加以下內(nèi)容：

A．數(shù)據(jù)結(jié)構(gòu)：

1．指針類型

2．多維數(shù)組

3．單鏈表及循環(huán)鏈表

4．二叉樹

5．文件操作（從文本文件中讀入數(shù)據(jù)，并輸出到文本文件中）

B．程序設計

1．算法的實現(xiàn)能力

2．程序調(diào)試基本能力

3．設計測試數(shù)據(jù)的基本能力

4．程序的時間復雜度和空間復雜度的估計

C．算法處理

1．離散數(shù)學知識的應用（如排列組合、簡單圖論、數(shù)理邏輯）

2．分治思想

3．模擬法

4．貪心法

5．簡單搜索算法（深度優(yōu)先 廣度優(yōu)先）搜索中的剪枝

6．動態(tài)規(guī)劃的思想及基本算法

評測環(huán)境

NOIP2010比賽環(huán)境規(guī)范依照使用Linux平臺、統(tǒng)一編譯器、提供多種集成開發(fā)環(huán)境選擇的原則制定。

NOIP2010的比賽環(huán)境中，操作系統(tǒng)平臺選擇Linux；在固定的操作系統(tǒng)平臺下，對應不同的語言，使用統(tǒng)一的編譯器，消除編譯器不同給選手帶來的不利影響；對應每種語言，提供了多種集成開發(fā)環(huán)境，選手可以根據(jù)自己的習慣選擇集成開發(fā)環(huán)境。

在全國評測時，評測環(huán)境保持與比賽環(huán)境的操作系統(tǒng)及編譯器一致。也就是說全國評測時，使用與選手比賽時一致的平臺對選手的程序進行評測，以消除平臺不一致帶來的不利影響。

以下是NOIP2010比賽環(huán)境要求的詳細描述：

使用Linux操作系統(tǒng)平臺：

（1）Linux操作系統(tǒng)必須使用NOI linux,基于ubuntu開發(fā)；

（2）Pascal語言，必須使用Free Pascal 2.0.4版本作為編譯器；

（3）C語言，必須使用gcc 3.2.2作為編譯器；

（4）C++語言，必須使用g++ 3.2.2作為編譯器。

第四篇：第十四屆全國青少年信息學(計算機)奧林匹克分區(qū)聯(lián)賽初賽匯總

第十四屆全國青少年信息學奧林匹克聯(lián)賽初賽試題（提高組 Pascal 語言 二小時完成）

●● 全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效 ●●

一、單項選擇題（共10題，每題1.5分，共計15分。每題有且僅有一個正確答案）。

1.在以下各項中，（）不是操作系統(tǒng)軟件。

Symbian 2．微型計算機中，控制器的基本功能是（）。

A.控制機器各個部件協(xié)調(diào)工作 B.實現(xiàn)算術運算和邏輯運算 C.存儲各種控制信息 D.獲取外部信息

3.設字符串S=”O(jiān)lympic”，S的非空子串的數(shù)目是（）。A.29 B.28 C.16 D.17 E.7 4．完全二叉樹共有2*N-1個結(jié)點，則它的葉節(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ù)是（）。

A.123.21 B.131.22 C.130.22 D.130.21 E.130.20 8． 遞歸過程或函數(shù)調(diào)用時，處理參數(shù)和返回地址，通常使用一種稱為（）的數(shù)據(jù)結(jié)構(gòu)。

A.隊列 B.多維數(shù)組 C.線性表 D.鏈表 E.棧

E.存放程序和數(shù)據(jù) A.Solaris B.Linux C.Sybase D.Windows Vista E.9.TCP/IP是一組構(gòu)成互聯(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 15.(2008)10 +(5B)16的結(jié)果是（）。

A.(833)16 B.(2099)10 C.(4063)8(100001100011)2 16.二叉樹T，已知其先根遍歷是1 2 4 3 5 7 6（數(shù)字為結(jié)點的編號，以下同），后根遍歷是4 2 7 5 6 3 1，則該二叉樹的可能的中根遍歷是（）。）D.）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ù)包

三．問題求解（共2題，每題5分，共計10分）

1．有6個城市，任何兩個城市之間都有一條道路連接，6個城市兩兩之間的距離如下表所示，則城市1到城市6的最短距離為_____________。

2．書架上有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];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])then begin a := a + b;writeln(a);end else begin c := c + d;writeln(c);end;end.輸入：9 19 29 39 輸出：_______________ 2．procedure foo(a,b,c:integer);begin if a>b 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 b

s:string;i,j,len,k:integer;begin read(s);len:=length(s);for i:=1 to len do if(ord(s[i])>= ord('A'))and(ord(s[i])<= ord('Z'))then s[i] := chr(ord(s[i])-ord('A')+ ord('a'));for i:=1 to len do if(ord(s[i]) 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(a[tmp],a[left]);value := ①;i := left;j := right;while i

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(a[i]);read(n);ans:= FindKth(1,m,n);writeln(a[ans]);end.2．（矩陣中的數(shù)字）有一個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中的一個數(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 j>0 do begin if a[n,j] < k then break;dec(j);end;①

while a[i,j]<>k do begin while(②)and(i>1)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, ' ', answery);end.

第五篇：第十三屆全國青少年信息學奧林匹克聯(lián)賽初賽試題

第十三屆全國青少年信息學奧林匹克聯(lián)賽初賽試題（普及組 Pascal 語言 二小時完成）

●

● 全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效 ●●

一、單項選擇題（共20題，每題1.5分，共計30分。每題有且僅有一個正確答案。）

1．在以下各項中，（）不是CPU的組成部分。A．控制器

B．運算器

C．寄存器

D．主板

2．在關系數(shù)據(jù)庫中，存放在數(shù)據(jù)庫中的數(shù)據(jù)的邏輯結(jié)構(gòu)以（）為主。A．二叉樹

B．多叉樹

C．哈希表

D．二維表

3．在下列各項中，只有（）不是計算機存儲容量的常用單位。A．Byte

B．KB

C．UB

D．TB

4．ASCII碼的含義是（）。

A．二→十進制轉(zhuǎn)換碼

B．美國信息交換標準代碼

C．數(shù)字的二進制編碼

D．計算機可處理字符的唯一編碼

5．一個完整的計算機系統(tǒng)應包括（）。

A．系統(tǒng)硬件和系統(tǒng)軟件

B．硬件系統(tǒng)和軟件系統(tǒng)

C．主機和外部設備

D．主機、鍵盤、顯示器和輔助存儲器

6．IT的含義是（）。

A．通信技術

B．信息技術

C．網(wǎng)絡技術

D．信息學

7．LAN的含義是（）。

A．因特網(wǎng)

B．局域網(wǎng)

C．廣域網(wǎng)

D．城域網(wǎng) 8．冗余數(shù)據(jù)是指可以由其它數(shù)據(jù)導出的數(shù)據(jù)。例如，數(shù)據(jù)庫中已存放了學生的數(shù)學、語文和英語的三科成績，如果還存放三科成績的總分，則總分就可以看作冗余數(shù)據(jù)。冗余數(shù)據(jù)往往會造成數(shù)據(jù)的不一致。例如，上面4個數(shù)據(jù)如果都是輸入的，由于操作錯誤使總分不等于三科成績之和，就會產(chǎn)生矛盾。下面關于冗余數(shù)據(jù)的說法中，正確的是（）。A．應該在數(shù)據(jù)庫中消除一切冗余數(shù)據(jù)

B．用高級語言編寫的數(shù)據(jù)處理系統(tǒng)，通常比用關系數(shù)據(jù)庫編寫的系統(tǒng)更容易消除冗余數(shù)據(jù) C．為了提高查詢效率，在數(shù)據(jù)庫中可以保留一些冗余數(shù)據(jù)，但更新時要做相容性檢驗 D．做相容性檢驗會降低效率，可以不理睬數(shù)據(jù)庫中的冗余數(shù)據(jù)

9．在下列各軟件，不屬于NOIP競賽（復賽）推薦使用的語言環(huán)境有（）。A．gcc

B．g++

C．Turbo C

D．Free Pascal

10．以下斷電后仍能保存數(shù)據(jù)的有（）。

A．硬盤

B．高速緩存

C．顯存

D．RAM 11．在下列關于計算機語言的說法中，正確的有（）。A．高級語言比匯編語言更高級，是因為它的程序的運行效率更高

B．隨著Pascal、C等高級語言的出現(xiàn)，機器語言和匯編語言已經(jīng)退出了歷史舞臺 C．高級語言比匯編語言程序更容易從一種計算機上移植到另一種計算機上 D．C是一種面向?qū)ο蟮母呒売嬎銠C語言

12．近20年來，許多計算機專家都大力推崇遞歸算法，認為它是解決較復雜問題的強有力的工具。在下列關于遞歸算法的說法中，正確的是（）。

A．在1977年前后形成標準的計算機高級語言“FORTRAN77”禁止在程序使用遞歸，原因之一是該方法可能會占用更多的內(nèi)存空間

B．和非遞歸算法相比，解決同一個問題，遞歸算法一般運行得更快一些 C．對于較復雜的問題，用遞歸方式編程一般比非遞歸方式更難一些

D．對于已經(jīng)定義好的標準數(shù)學函數(shù) sin(x)，應用程序中的語句“y=sin(sin(x));”就是一種遞歸調(diào)用

13．一個無法靠自身的控制終止的循環(huán)成為“死循環(huán)”，例如，在C語言程序中，語句“while(1)printf(“*”);”就是一個死循環(huán)，運行時它將無休止地打印*號。下面關于死循環(huán)的說法中，只有（）是正確的。A．不存在一種算法，對任何一個程序及相應的輸入數(shù)據(jù)，都可以判斷是否會出現(xiàn)死循環(huán)，因而，任何編譯系統(tǒng)都不做死循環(huán)檢查

B．有些編譯系統(tǒng)可以檢測出死循環(huán)

C．死循環(huán)屬于語法錯誤，既然編譯系統(tǒng)能檢查各種語法錯誤，當然也應該能檢查出死循環(huán) D．死循環(huán)與多進程中出現(xiàn)的“死鎖”差不多，而死鎖是可以檢測的，因而，死循環(huán)也可以檢測的

14．在Pascal語言中，表達式（23 or 2 xor 5）的值是（）。A．18

B．1

C．23

D．32

15．在Pascal語言中，判斷整數(shù)a等于0或b等于0或c等于0的正確的條件表達式是（）。A．not((a<>0)or(b<>0)or(c<>0))B．not((a<>0)and(b<>0)and(c<>0))C．not((a=0)and(b=0))or(c<>0)D．(a=0)and(b=0)and(c=0)

16．地面上有標號為A、B、C的三根柱，在A柱上放有10個直徑相同中間有孔的圓盤，從上到下依次編號為1，2，3……，將A柱上的部分盤子經(jīng)過B柱移入C柱，也可以在B柱上暫存。如果B柱上的操作記錄為“進、進、出、進、進、出、出、進、進、出、進、出、出”。那么，在C柱上，從下到上的編號為（）。

A．2 4 3 6 5 7

B．2 4 1 2 5 7

C．2 4 3 1 7 6

D．2 4 3 6 7 5

17．與十進制數(shù)1770對應的八進制數(shù)是（）。

A．3350

B．3351

C．3352

D．3540

18．設A=B=True，C=D=False，一下邏輯運算表達式值為假的有（）。A．(﹁A∧B)∨(C∧D∨A)

B．﹁(((A∧B)∨C)∧D)C．A∧(B∨C∨D)∨D

D．(A∧(D∨C))∧B

19．(2070)16 +(34)8 的結(jié)果是（）。A．（8332）10

B．（208A）16

C．（100000000110）2 D．(20212)8

20．已知7個節(jié)點的二叉樹的先根遍歷是1 2 4 5 6 3 7（數(shù)字為節(jié)點的編號，以下同），中根遍歷是4 2 6 5 1 7 3，則該二叉樹的后根遍歷是（）。

A．4 6 5 2 7 3 1

B．4 6 5 2 1 3 7 C．4 2 3 1 5 4 7

D．4 6 5 3 1 7 2

二、問題求解（共2題，每題5分，共計10分）。

1、（子集劃分）將n個數(shù)（1，2，…，n）劃分成r個子集。每個數(shù)都恰好屬于一個子集，任何兩個不同的子集沒有共同的數(shù)，也沒有空集。將不同劃分方法的總數(shù)記為S(n,r)。例如，S(4,2)=7，這7種不同的劃分方法依次為{(1),(234)}，{(2),(134)}，{(3),(124)}，{(4),(123)}，{(12),(34)}，{(13),(24)}，{(14),(23)}。當n=6，r=3時，S(6,3)=______________。（提示：先固定一個數(shù)，對于其余的5個數(shù)考慮S(5,3)與S(5,2)，再分這兩種情況對原固定的數(shù)進行分析。）

2、（最短路線）某城市的街道是一個很規(guī)整的矩形網(wǎng)絡（見下圖），有7條南北向的縱街，5條東西向的橫街。現(xiàn)要從西南角的A走到東北角的B，最短的走法共有多少種？___________

B

A

三、閱讀程序?qū)懡Y(jié)果（共4題，每題8分，共計32分。）

1、program j301;var i,a,b,c,x,y:integer;

p:array[0..4] of integer;begin

y:=20;

for i:=0 to 4 do read(p);

readln;

a:=(p[0]+p[1])+(p[2]+p[3]+p[4])div 7;

b:=p[0]+p[1] div((p[2]+p[3])div p[4]);

c:=p[0]*p[1] div p[2];

x:=a+b-p[(p[3]+3)mod 4];

if(x>10)

then y:=y+(b*100-a)div(p[p[4] mod 3]*5)

else

y:=y+20+(b*100-c)div(p[p[4] mod 3]*5);

writeln(x,',',y);end.{注：本例中，給定的輸入數(shù)據(jù)可以避免分母為0或數(shù)組元素下表越界。} 輸入：6 6 5 5 3 輸出：______________________

2、program j302;var a,b:integer;var x,y:^integer;procedure fun(a,b:integer);var k:integer;begin k:=a;a:=b;b:=k;end;begin

a:=3;b:=6;

x:=@a;y:=@b;

fun(x^,y^);

writeln(a,',',b);end.輸出：_______________________________

3、program j303;var a1:array[1..50] of integer;var i,j,t,t2,n,n2:integer;begin

n:=50;

for i:=1 to n do a1:=0;

n2:=round(sqrt(n));

for i:=2 to n2 do

if(a1=0)then

begin

t2:=n div i;

for j:=2 to t2 do a1[i*j]:=1;

end;

t:=0;

for i:=2 to n do

if(a1=0)then

begin

write(i:4);inc(t);

if(t mod 10=0)then writeln;

end;

writeln;end.輸出：_____________________________________________

_____________________________________________

4、Program j304;Type str1=string[100];

Str2=string[200];Var

S1:str1;s2:str2;Function isalpha(c:char):Boolean;Var i:integer;Begin

i:=ord(c);

if((i>=65)and(i<=90))or((i>=97)and(i<=122))then

isalpha:=true

else isalpha:=false;end;function isdigit(c:char):Boolean;var i:integer;begin

i:=ord(c);if(i>=48)and(i<=57)then isdigit:=true

else isdigit:=false;end;procedure expand(s1:str1;var s2:str2);var i,j:integer;a,b,c:char;begin

j:=1;c:=char(1);i:=0;

while(i<=ord(s1[0]))do

begin inc(i);c:=s1;

if c='-' then begin {1}

a:=s1[i-1];b:=s1[i+1];

if(isalpha(a)and isalpha(b))or(isdigit(a)and isdigit(b))then begin

dec(j);

while(ord(upcase(a))

begin

s2[j]:=a;inc(j);inc(a);end;

end

else begin s2[j]:=c;inc(j);end;end{1} else begin s2[j]:=c;inc(j);end;end;s2[0]:=char(j-2);end;begin readln(s1);expand(s1,s2);writeln(s2);end.輸入：wer2345d-h454-82qqq

輸出：__________________________

四、完善程序（前4空，每空2.5分，后6空，每空3分，共28分）。

1、（求字符的逆序）下面的程序的功能是輸入若干行字符串，每輸入一行，就按逆序輸出該行，最后鍵入-1終止程序。

請將程序補充完整。Program j401;type str1=string[100];var line:str1;kz:integer;procedure reverse(var s:str1);var I,j:integer;t:char;begin

i:=1;j:=length(s);

while(i

t:=s;s:=s[j];s[j]:=t;

;;

end;end;begin

writeln(?continue?-1 for end.?);

readln(kz);

while()do

begin

readln(line);

;

writeln(line);

writeln(?continue?-1 for end.?);

readln(kz);

end;end.2 3 3 2-1 1 3 4 1 1 5 4 4 5 5

2、（棋盤覆蓋問題）在一個2k×2 k個方格組成的棋盤中恰有一個方格與其它方格不同（圖中標記為-1的方格），稱之為特殊方格。現(xiàn)用L型（占3個小方格）紙片覆蓋棋盤上除特殊方格的所有部分，各紙片不得重疊，于是，用到的紙片數(shù)恰好是（4 k-1）/3。在下表給出的一個覆蓋方案中，k=2，相同的3各數(shù)字構(gòu)成一個紙片。

下面給出的程序使用分治法設計的，將棋盤一分為四，依次處理左上角、右上角、左下角、右下角，遞歸進行。請將程序補充完整。

Program j402;type arr1=array[1..65] of integer;

arr2=array[1..65] of arr1;var board:arr2;tile:integer;size,dr,dc:integer;procedure chessboard(tr,tc:integer;dr,dc:integer;var size:integer);var t,s:integer;begin

if(size=1)then;

t:=tile;inc(tile);

s:=size div 2;

if then chessboard(tr,tc,dr,dc,s)else begin

board[tr+s-1]:=t;;end;if(dr=tc+s)then chessboard(tr,tc+s,dr,dc,s)

else begin board[tr+s-1][tc+s]:=t;

;end;if(dr>=tr+s)and(dc

board[tr+s][tc+s]:=t;

;end;if(dr>=tr+s)and(dc>=tc+s)then chessboard(tr+s,tc+s,dr,dc,s)else begin board[tr+s][tc+s]:=t;;end;end;procedure prt1(n:integer);var I,j:integer;begin

for I:=1 to n do begin

for j:=1 to n do write(board[j]:3);

writeln;end;end;begin

writeln(?input size(4/8/16/64):?);

readln(size);writeln(?input the position of special block(x,y):?);

readln(dr,dc);board[dr][dc]:=-1;

tile:=1;chessboard(1,1,dr,dc,size);prt1(size);end.NOIP2007年普及組（Pascal語言）參考答案與評分標準

一、單項選擇題：（每題1.5分）

題號 2 3 4 5 6 7 8 9 10 答案

D D C B B B B C C A 題號 12 13 14 15 16 17 18 19 20 答案

C A A A B D C D A A

二、問題求解：（每題 5分）

1．90 2．210

三、閱讀程序?qū)懡Y(jié)果

1.15, 46（對1個數(shù)給4分，無逗號扣1分）2.3, 6

3.2 3 5 7 11 13 17 19 23 29

47

4.wer2345defgh45456782qqq

四、完善程序(前4空（①--④），每空2.5分，后6空（⑤--⑩），每空3分)

（說明：以下各程序填空可能還有一些等價的寫法，各省可請本省專家審定和上機驗證，不一定上報科學委員會審查）

1．① inc(i)或i:=i+1 ② dec(j)或 j:=j-1 ③ kz<>-1 ④ reverse(line)2.⑤ exit ⑥(dr