急求pascal初中普及組資料

知識是基礎，能力最重要

NOIP初賽考的知識點，大綱上有3塊：計算機基本常識、計算機基本操作、程序設計基本知識。具體來說：選擇題考查的是計算機基本常識、基本操作和程序設計中的壹些基本數據結構與基本算法；而填空題更加重視能力（尤其是隊列、棧、二叉樹等數據結構、數學問題、歸納法、數列和邏輯推理等）的考查；讀程序寫運行結果考察的是對程序的理解和跟蹤，重在分析推理能力。讀程序的4條題目往往有壹定的層次，試卷中給出程序的並不復雜，語句的含義容易明白，但是悟性好的選手總是很快就能體會到程序的設計思路並得出正確的答案，機械模仿計算機手工逐步算出結果的同學往往做的很慢，造成時間不夠，而且容易失誤；完善程序更是考察程序設計能力，尤其是在明確算法和數據結構的條件下，如何編程。讀程序和完善程序，需要在平時的學習中提高，經常閱讀、討論和研究別人的優秀程序，提高自己的理解力和速度。

壹般是比較容易得分的，不可錯過！

程序設計方面的知識多是平時計算機課堂教學或課外活動中學到的，建議大家找全國計算機等級考試（壹、二級）的題目做做，壹般不超過二級的知識點，知識要復習的系統壹些。新大綱和最近兩年的考試不再考DOS，但有DOS經驗的選手可能會占壹點便宜，因為有些題目可以根據經驗判斷。另外，往更高層次發展的過程中，必要的DOS知識和命令還是必須的。

NOIP初賽談2 填空

填空（15分左右，2-3題）

這部分題目對數學要求要高壹點，往往考查的是數學問題（如代數變形、組合、概論統計等），數列（壹般是考遞推、遞歸、歸納法等），邏輯推理；也考查壹些算法和數據結構知識（如隊列、棧、二叉樹）。建議大家多花壹點時間做，盡量做對。

1.數組A[30..100,20..100]以行優先的方式存儲,每個元素占8個字節,且已知A[40,30]的地址為20000,則A[60,90]的地址為:_________________。如果以列優先存儲,則為:_________________。

解答：設數組首地址為X，則：X+（（40-30）*（100-20+1）+（30-20））* 8 = 20000

(前面的行數*每行的列數+本行中序號)*每個元素的長度+首地址

則：X=13340，用上述的式子，不難算出：A[60，90]的地址：33340

列優先存儲，只要稍微改動上述公式，結果略；

2.（1998年初中組）設棧S的初始狀態為空,現有5個元素組成的序列{1,2,3,4,5},對該序列在S 棧上依次進行如下操作(從序列中的1開始,出棧後不在進棧):進棧,進棧,進棧,出棧,進棧,出棧,進棧,問出棧的元素序列是:_________,棧頂指針的值為______，棧頂元素為:___________________。

解答：出棧序列為{3，4}，棧頂指針值為3，棧頂元素為5。

3．如2002年高中組：設棧S和隊列Q初始狀態為空，元素e 1 ，e 2 ，e 3 ，e 4 ，e 5 ，e 6依次通過棧S，壹個元素出棧後即進入隊列Q，若出隊順序為e 2 ，e 4 ，e 3 ，e 6 ，e 5 ，e 1 ，則棧S的容量至少應該為______________。

解答：為3。

4．（2000年初中組）設循環隊列中數組的下標範圍是1..n，其頭尾指針分別為f和r，則其元素個數為：_____________________。

解答：（r-f+n）mod n

5.中綴表達式、前綴表達式、後綴表達式（1997年初中組）

（1) 已知中綴表達式：A+B*C/D

求它的前綴表達式和後綴表達式？

（2）已知前綴表達式：+△A*B△C {註△表示壹元運算符負號，即△A表示-A}

求它的中綴表達式和後綴表達式？

解答：中綴表達式即為中序遍歷，前綴表達式即為前序遍歷，後綴表達式即為後序遍歷。

畫（二叉）表達式樹。首先從右到左查找（+，-）號（不查找括號內的符號）；如果找到符號將符號左右分為兩部分，符號為樹根，左邊為左子樹；右邊為右子樹。如果沒有找到，再查找（*，/）做同樣操作，如果還找不，壹種為只剩下數字或者有括號，則可以去掉括號。

（1）的結果：+A*B/CD；ABCD/*+

可以將△A先看為壹個整體建樹，然後再分解△A。

（2）的結果：（-A）+B*（-C）；A△BC△*+

6.（1998年初中組） 已知壹個數列U1,U2,U3...Un...,往往可以找到壹個最小的K值和K個數a1,a2,..,ak,使得數列從某項開始都滿足:U(n+k)=a1*U(n+k-1)＋a2*U(n+k-2)+......＋akUn (式A)

例如數列 1,1,2,3,5......可以發現:當K=2,a1=1,a2=1時,從第3項起(N>=1)滿足:

U(n+2)＝U(n+1) ＋ Un

試對數列1^3 ,2^3 ,3^3 ,......,N^3,……,求K和a1,a2,...ak,使得式A成立。

解答：解方程，先設K=2，列出方程組：

a1*23+a2*13=33

a1*33+a2*23=43

以上方程組無整數解。再設K=3，列出方程組：

a1*02+a2*12+a3*22=32

a1*12+a2*22+a3*32=42

a1*22+a2*32+a3*42=52

以上方程的整數解為：a1=1，a2=-3，a3=3，此時K=3。

7.（1998年高中組）給出壹棵二叉樹的中序遍歷:DBGEACHFI與後序遍歷:DGEBHIFCA,畫出此二叉樹。

8.（1996年高中組）下面是壹個利用完全二叉樹特性,用順序表來存儲的壹個二叉樹,結點數據為字符型(結點層次從小到大,同壹層從左到右順序存儲,#表示空結點,@表示存儲數據結束)。

結點 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

數據 A B C # # D E # # # # # G F @

請畫出對應的二叉樹。

解答：以上兩題的圖分別如下：

9．如：（2000年初中組）已知按中序遍歷二叉樹的結果為：abc，問：有多少種不同形態的二叉樹可以得到這壹遍歷結果，並畫出這些二叉樹。

解答：5種，形態如下：

10．（1999年初中組）在磁盤的目錄結構中，我們將與某個子目錄有關聯的目錄數稱為度。例如下圖

該圖表達了A盤的目錄結構：D1，Dll，…，D2均表示子目錄的名字。在這裏，根目錄的度為2，D1子目錄的度為3，D11子目錄的度為4，D12，D2，D111，D112，D113的度均為1。不考慮子目錄的名字，則可簡單的圖示為如下所示的樹結構：

若知道壹個磁盤的目錄結構中，度為2的子目錄有2個，度為3的子目錄有1個，度為4的子目錄有3個。

試問：度為1的子目錄有幾個？

解答：壹種方法是畫圖；另外，可以根據整棵樹的入度=出度（因為任壹根關聯邊連接兩個結點）這壹性質推導，除根結點外的每個結點入度都是1，所以總的入度=1*x+1*2+1*1+1*3-1；每個葉結點的出度為0，分支結點的出度為度數-1，根結點的出度就是它的度，所以總的出度=0*x+（2-1）*2+（3-1）*1+（4-1）*3+1；算出：x=9。

11．（1998年高中組）用鄰接矩陣/鄰接表表示下面的無向/有向圖（略）。

12.（1999年初中）根據Nocomachns定理，任何壹個正整數n的立方壹定可以表示成n個連續的奇數的和。

例如：

13=1

23=3+5

33=7+9+11

43=13+15+17+19

在這裏，若將每壹個式中的最小奇數稱為X，那麽當給出n之後，請寫出X與n之間的關系表達式：_________________________。

解答：X=n*(n-1)+1

13．（2000年高中組）設有壹個***有n級的樓梯，某人每步可走1級，也可走2級，也可走3級，用遞推公式給出某人從底層開始走完全部樓梯的走法。例如：當n=3時，***有4種走法，即1+1+1,1+2,2+1,3。

解答：兩種方法，壹是“猜”+“湊”，從具體的n=1,2,3……算起，只能算比較簡單的，容易錯；二是用組合數學和歸納法進行推導，壹般先假設F（n）= a*F（n-1）+b*F（n-2）+c*F（n-3）+……，然後算a，b，c……直到某個系數=0就結束，再代入式子中。

F（1）＝1 F（2）＝2 F（3）＝4

F（N）＝F（N－3）＋F（N－2）＋F（N－1） （N≥4）

14．（2000年初中組）有2×n的壹個長方形方格，用壹個1×2的骨牌鋪滿方格。例如n=3時，為2×3方格。此時用壹個1×2的骨牌鋪滿方格，***有3種鋪法：

試對給出的任意壹個n（n>0），求出鋪法總數的遞推公式。

解答：F（1）=1 F（2）=2

F（n）=F（n-2）+F（n-1）（n≥3）

15．(2002年初中組) 將N個紅球和M個黃球排成壹行。例如:N=2,M=3可得到以下6種排法:紅紅黃黃黃紅黃紅黃黃 紅黃黃紅黃 黃紅紅黃黃 黃紅黃紅黃 黃黃黃紅紅。

問題：當N=4,M=3時有多少種不同排法?(不用列出每種排法)

解答：35

16．（1999年高中組）將Ln定義為求在壹個平面中用n條直線所能確定的最大區域數目。例如：當n=1時，L1=2,進壹步考慮，用n條折成角的直線（角度任意），放在平面上，能確定的最大區域數目Zn是多少？例如：當n=1時，Z1=2（如下圖所示）

當給出n後，請寫出以下的表達式：

1 Ln = ______________

2 Zn = _______________

解答：本題實質是求直線或折線將壹個平面分成的最大區域數，從兩個方面考慮：

（1） 求在壹個平面中用n條直線所能確定的最大區域數；

n=1,L1=2, F(1)=2

n=2,L2=4, F(2)=F(1)+2

n=3,L3=7, F(3)=F(2)+3

n=4,L4=11, F(4)=F(3)+4

……

所以， F(n)=F(n-1)+n

把上面的n個等式左右相加，化簡得出：F（n）=2+2+3+4+……+n

即：L（n）=n*(n+1)/2+1

（2） 求在壹個平面中用n條折線所能確定的最大區域數；

n=1,Z1=2, F(1)=0+2

n=2,Z2=7, F(2)=1*(2*2-1)+4

n=3,Z3=16, F(3)=2*(2*3-1)+6

n=4,Z4=29, F(4)=3*(2*4-1)+8

……

所以， F(n)=(n-1)*(2*n-1)+2*n

即：Z（n）=(n-1)*(2*n-1)+2*n

17．(1998年初中組)某班有50名學生，每位學生發壹張調查卡，上寫a，b，c三本書的書名，將讀過的書打ü，結果統計數字如下： 只讀a者8人；只讀b者4人；只讀c者3人；全部讀過的有2人；讀過a，b兩本書的有4人；讀過a，c兩本書的有2人；讀過b，c兩本書的有3人；問：

（1）讀過a的人數是 （2）壹本書也沒有讀過的人數是 。

解答：（1）12人 （2）30人

方法：推理或集合表示如下：

a=8；b=4；c=3；abc=2；ab=4-abc=2；ac=2-abc=0；bc=3-abc=1；

讀過a的人數為：a+ab+abc+ac=8+2+2+0=12

壹本未讀過的人：50-a-b-c-abc-ab-ac-bc=30

2002年高中（1）

在書架上放有編號為1 ，2 ，．．．，n的n本書。現將n本書全部取下然後再放回去，當放回去時要求每本書都不能放在原來的位置上。例如：n = 3時：

原來位置為：1 2 3

放回去時只能為：3 1 2 或 2 3 1 這兩種

問題：求當n = 5時滿足以上條件的放法***有多少種？（不用列出每種放法）

解答：f(n)=n*f(n-1)+ -1(n>1,且n為偶數時取+，n為奇數時取-)

f(1)=0

所以，當n=5時，滿足以上條件的方法***有44種。

2002年高中（2）

設有壹棵k叉樹，其中只有度為0和k兩種結點，設n 0 ，n k ，分別表示度為0和度為k的結點個數，試求出n 0 和n k之間的關系（n 0 = 數學表達式，數學表達式僅含n k 、k和數字）。

解答：n0和nk之間的關系為：n0=(k-1) nk+1。

2002年初中（1）

如下圖,有壹個無窮大的的棧S,在棧的右邊排列著1,2,3,4,5***五個車廂。其中每個車廂可以向左行走,也可以進入棧S讓後面的車廂通過。現已知第壹個到達出口的是3號車廂，請寫出所有可能的到達出口的車廂排列總數(不必給出每種排列)。

出口← ← 1 2 3 4 5

S↓

解答：9

2002年初中（2）

將N個紅球和M個黃球排成壹行。例如:N=2,M=3可得到以下6種排法:紅紅黃黃黃紅黃紅黃黃 紅黃黃紅黃 黃紅紅黃黃 黃紅黃紅黃 黃黃黃紅紅

問題:當N=4,M=3時有多少種不同排法?(不用列出每種排法)

解答：35

2001年高中（1）

已知壹棵二叉樹的結點名為大寫英文字母，其中序與後序遍歷的順序分別為：CBGEAFHDIJ與CGEBHFJIDA，則該二叉樹的先序遍歷的順序為：

解答：ABCEGDFHIJ

2001年高中（2）

平面上有三條平行直線，每條直線上分別有7，5，6個點，且不同直線上三個點都不在同壹條直線上。問用這些點為頂點，能組成多少個不同四邊形？

解答：2250

2001年初中（1）

在a,b,c,d,e,f六件物品中，按下面的條件能選出的物品是： 。

(1)a,b兩樣至少有壹樣

(2)a,d不能同時取

(3)a,e,f中必須有2樣

(4)b,c要麽都選，要麽都不選

(5)c,d兩樣中選壹樣

(6)若d不選，則e也不選

解答： a,b,c,f

2001年初中（2）

平面上有三條平行直線，每條直線上分別有7，5，6個點，且不同直線上三個點都不在同壹條直線上。問用這些點為頂點，能組成多少個不同三角形？

解答：751。

NOIP初賽談3 閱讀程序

閱讀程序，寫運行結果(25分左右,3-4題)

其實很容易,目的幾乎是送分，而且占的分數很多，但得分率卻不見得高。很容易不明不白的就把分（全）丟了!!!

這部分程序考3個方面：

1． 程序設計語言本身，如循環、遞歸、值型參和變量型參數、跟蹤變量等；

2． 歸納和數學運算能力；

3． 是否掌握了壹些常用算法（程序段）的框架；

4． 細心、耐心等心理品質；靈感+編程的量等；

壹般做這類題目的核心是找程序目的：

即這個程序想幹什麽。迄今為止考過的題目還沒有“亂寫”的，總有壹點“寫作目的”的。抓住了它，不僅得出答案變得很容易了，而且對自己的結果也會比較有信心。

壹般的解題步驟如下：

1． 從總體上通讀程序，大致把握程序的目的和算法；

2． 猜測變量的作用，跟蹤主要變量值的變化（列表），找出規律；

3． 將程序分段，理清每壹小段的作用和目的（靈感+關鍵表達式和語句的領會）；

4． 看清輸入、按照輸出格式，寫出結果；

5． 帶著得到的結果回到程序進行檢查；

下面舉幾個例子。

? 1．基本題(考語言本身，尤其是循環嵌套。1999年初中組)

Program excpl;

var

x, y, y1, jk, j1, g, e: Integer;

a: array[1..20] of 0..9;

begin

x := 3465; y := 264; jk := 20;

for j1:=1 to 20 do a[j1] := 0;

while y <> 0 do begin

y1 := y mod 10;

y := y div 10;

while y1 <> 0 do begin

g := x;

for e:=Jk downto 1 do begin

g := g + a[e];

a[e] := g mod 10;

g := g div 10

end;

y1 := y1 - 1

end;

jk := jk - 1

end;

j1 := 1;

while a[j1] = 0 do j1 := j1 + 1;

for Jk:=j1 to 20 do write(a[jk]:4);

writeln

end.

程序運行結果為：___________________________。

解答：

程序不長，但是有壹定的難度。高手最多半分鐘就看懂了程序的意思，但初學者往往算了很久得出了結果卻是錯的。下面我們還是先以壹個初學者的身份分析壹下這個程序。記住，不要壹開始就模擬電腦來壹個個語句“執行”-------妳算過自己是多少Hz的CPU沒有？！

首先是看看變量的名字，可惜分區聯賽題目中的變量不是i就是j，很討厭。i和j壹般作為循環計數器，沒有什麽意思，因此不要管它了。然後要看變量在程序的哪裏出現過，著重看它與其它變量的相互引用關系，猜測它的作用。例如上題：x只在g:=x中出現，暫時不要管它，因為它很可能只是壹個初始數據。y有三處：1) while y<>0 do

2) y1:=y mod 10;

3) y:=y div 10;

很明顯，y每次少了最後壹位數字,把這位數字給了y1。有經驗的選手應該體會到了什麽，不過我們繼續。

現在我們知道了：y對程序的作用是：每次提供最後壹位給y1,即y1每次的值依次是：4,6,2

那麽再看y1，它出現在兩個地方:

1)while y1<>0 do

2)y1=y1-1

很明顯就是壹個循環次數嘛！循環y1次！

再看jk:

1)for e:=jk downto 1 do

2)jk:=jk-1

jk作為循環初始值，居然壹次比壹次少...其原因有待進壹步分析。

再看j1:

1)for j1:=1 to 20 do a[j1]:=0;

2)j1:=1;

3)while a[j1]=0 do j1:=j1+1;

4)for Jk:=j1 to 20 do write(a[jk]:4);

顯然，j1和其它變量沒有什麽聯系。1)是初始化，2)3)4)是輸出數組a。

再看g: 出現的位置是幾層循環之內了，應該很重要！壹會兒再分析！

再看e: 作為循環變量，沒有什麽意思。

通過變量分析，我們知道了：x,y是數據，y每次提供最後壹位給y1,循環y1次。j1和g的作用有待分析。

下面根據程序結構，把程序分成幾塊，逐個研究。最主要的程序段是兩個WHILE循環中套壹個FOR循環，三重循環！！！其實，最外面壹層很明確：判斷什麽時候結束（y=0）。前後都很簡單，是壹些變量和數組的初始化、輸入、輸出等，下面重點剖析核心程序段。

1） x:=3465; y:=264; jk:=20;

for j1:=1 to 20 do a[j1]:=0;

輸入與變量、數組的初始化，不要管它。

2)while y <> 0 do begin

y1 := y mod 10;

y := y div 10;

while y1<>0 do begin

g := x;

for e:=Jk downto 1 do begin

g := g + a[e];

a[e] := g mod 10;

g := g div 10

end;

y1 := y1 – 1;

end;

jk := jk - 1;

end;

3)

j1:=1;

while a[j1]=0 do j1:=j1+1;

for Jk:=j1 to 20 do write(a[jk]:4);

writeln

從前往後，找到<>0的位置開始，輸出數組元素的值（輸出結果），也不要管它。

塊2最重要。

它的思想是：每次取Y的最第位y1,執行<<運算>>y1次，每次把jk減1。

現在最重要的是<<運算>>中的在幹什麽？

註意到最後輸出的a[],要留意a[]的變化！

a[e]總是取個位(g mod 10)，g每次少壹位，和a[e-1](別忘了e在循環！)相加...

難道是...高精度加法？RIGHT！

它執行了y1次，y1每次都是y的個位！對了。程序就是在做x*y

所以答案就是 3465*264=914760

再看它的輸出格式，輸出的應該是：___9___1___4___7___6___0

其實有經驗的話，看到g這個變量名和g:=g+a[e]; a[e]:=g mod 10;這幾個標誌句子。就可以壹下子知道程序的用意了。

總結壹下本題：重點考循環嵌套的執行過程以及對除法運算中的商、余數的基本方法；主要程序段可以通過列表了解變量的變化情況；要細心、耐心；題目的本身沒有多少值得研究的價值！！！但有些題目純粹考算法思路，如下面的例子：

program ex2;

var i,j,n:longint;

b:array [0..31] of 0..1;

begin

n=1999;

i:=0;

while n<>0 do begin

b[i]:=n mod 2;

i:=i+1;

n:=n div 2

end;

for j:=i-1 downto 0 do write(b[j]);

end.

輸出什麽？

解答：很明顯，是把十進制整數轉換成二進制數，所以輸出11111001111

program exp1 (imput,output);

var

i, s, max: integer;

a:array [1..10] of integer;

begin

for i:=1 to 10 do read (a[i]);

max:=a[1] ；s:=a[1];

for i:=2 to 10 do begin

if s<0 then s：=0;

s：= s+a[i];

if s>max then max：=s

end;

writeln(‘max=’, max)

end.

輸入：8 9 －1 24 6 5 11 15 －28 9

輸出：max=

解答：本題主要做累加：s：= s+a[i];再根據結果打擂臺。

但最關鍵的語句是：if s<0 then s：=0;它的作用是把s<0的前若幹個元素的和值屏蔽掉（置0）。了解了這壹點，題目就很簡單了。步驟如下：

s<0? s=8 s>max? max=8;

I=2 N 8+9=17 Y max=17;

I=3 N 17-1=16 N max=17;

I=4 N 16+24=40 Y max=40;

I=5 N 10+6=46 Y max=46;

I=6 N 46+5=51 Y max=51;

I=7 N 51+11=62 Y max=62;

I=8 N 62+15=77 Y max=77;

I=9 N 77-28=49 N max=77;

I=10 N 49+9=58 N max=77;

所以結果為：77。

小結：本質是求壹個n長的整數數列的連續x長的子序列，要求子序列的和最大！

註意：s和max！！！另外本題給的輸入數據比較簡單，所以有很多人沒有完全懂也算對了結果，把數據改成如下：-1 12 -103 65 34 -4 -27 8 -1234 9，問結果是多少呢？答：9！！！

PROGRAM EX3；

CONST N=10;

VAR S,I : INTEGER;

FUNCTION CO(I1:INTEGER) : INTEGER;

VAR J1,S1 : INTEGER;

BEGIN

S1:=N;

FOR J1:= (N-1) DOWNTO (N-I1+1) DO

S1:= S1*J1 DIV (N-J1+1);

CO:=S1

END;

BEGIN

S:=N+1;

FOR I:= 2 TO N DO S:=S + CO(I);

WRITELN(‘S=’,S);

END.

解答過程：

（1） 如果有子程序，壹般先讀主程序，了解主程序什麽時候調用子程序？幹什麽的？調用了多少次？本題調用了n-1次，並且累加函數的返回值！

（2） 再單獨閱讀子程序，分析變量、參數和返回值，確定它的功能。本題函數猛壹看好象比較復雜，不過是通過壹個循環結構完成累乘和累除，下面再具體分析！

（3） 通過列表，觀察子程序中的變量變化情況，以便找出規律，確定子程序的作用。本題如下：

CO（2）=10*9/2

CO（3）=10*9*8/2/3

CO（4）=10*9*8*7/2/3/4

……

發現,好象是組合數學的公式：CO（i）=10！/（i!*(10-i)!）

即：C(m,n)=m!/(n!*(m-n)!)=m*(m-1)*……*(m-n+1)/n!

（4） 所以結果很明確：C(10,0)+ C(10,1)+……+C(10,9)+ C(10,10)=722

總結：靈感來源於豐富的數學基礎和經驗！

上篇: 烏蘭察布多蒙德豪生大酒店幾星級 下篇: 在妳看來，《JOJO的奇妙冒險》中哪個替身的能力設計得最巧妙？