【正文】 方程的整數(shù)解為：a1=1，a2=3，a3=3，此時K=3。216。 實質是考數(shù)學。7.（1998年高中組）給出一棵二叉樹的中序遍歷:DBGEACHFI與后序遍歷:DGEBHIFCA,畫出此二叉樹。8.（1996年高中組）下面是一個利用完全二叉樹特性,用順序表來存儲的一個二叉樹,結點數(shù)據為字符型(結點層次從小到大,同一層從左到右順序存儲,表示空結點,@表示存儲數(shù)據結束)。結點 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15數(shù)據 A B C D E G F @請畫出對應的二叉樹。解答：以上兩題的圖分別如下：216。 以上兩題實質是考數(shù)據結構中的二叉樹。還經?？级鏄涞挠嫈?shù)！如下題：9．如：（2000年初中組）已知按中序遍歷二叉樹的結果為：abc，問：有多少種不同形態(tài)的二叉樹可以得到這一遍歷結果，并畫出這些二叉樹。 解答：5種，形態(tài)如下：10．（1999年初中組）在磁盤的目錄結構中，我們將與某個子目錄有關聯(lián)的目錄數(shù)稱為度。例如下圖 該圖表達了A盤的目錄結構：D1，Dll，…，D2均表示子目錄的名字。在這里，根目錄的度為2，D1子目錄的度為3，D11子目錄的度為4，D12，D2，D111，D112，D113的度均為1。不考慮子目錄的名字，則可簡單的圖示為如下所示的樹結構： 若知道一個磁盤的目錄結構中，度為2的子目錄有2個，度為3的子目錄有1個，度為4的子目錄有3個。 試問：度為1的子目錄有幾個？ 解答：一種方法是畫圖；另外，可以根據整棵樹的入度=出度（因為任一根關聯(lián)邊連接兩個結點）這一性質推導，除根結點外的每個結點入度都是1，所以總的入度=1*x+1*2+1*1+1*31；每個葉結點的出度為0，分支結點的出度為度數(shù)1，根結點的出度就是它的度，所以總的出度=0*x+（21）*2+（31）*1+（41）*3+1；算出：x=9。216。 考查了計算機中的目錄結構和樹結構中的“度”的概念和性質。11．（1998年高中組）用鄰接矩陣/鄰接表表示下面的無向/有向圖（略）。216。 考查了數(shù)據結構中的圖的表示。12.（1999年初中）根據Noachns定理，任何一個正整數(shù)n的立方一定可以表示成n個連續(xù)的奇數(shù)的和。 例如： 13=1 23=3+5 33=7+9+11 43=13+15+17+19 在這里，若將每一個式中的最小奇數(shù)稱為X，那么當給出n之后，請寫出X與n之間的關系表達式：_________________________。 解答：X=n*(n1)+1216。 考查代數(shù)和遞推能力！13．（2000年高中組）設有一個共有n級的樓梯，某人每步可走1級，也可走2級，也可走3級，用遞推公式給出某人從底層開始走完全部樓梯的走法。例如：當n=3時，共有4種走法，即1+1+1,1+2,2+1,3。 解答：兩種方法，一是“猜”+“湊”，從具體的n=1,2,3……算起，只能算比較簡單的，容易錯；二是用組合數(shù)學和歸納法進行推導，一般先假設F（n）= a*F（n1）+b*F（n2）+c*F（n3）+……，然后算a，b，c……直到某個系數(shù)=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年初中組）有2n的一個長方形方格，用一個12的骨牌鋪滿方格。例如n=3時，為23方格。此時用一個12的骨牌鋪滿方格，共有3種鋪法： 試對給出的任意一個n（n0），求出鋪法總數(shù)的遞推公式。 解答：F（1）=1 F（2）=2 F（n）=F（n2）+F（n1）（n≥3）216。 以上兩題，考察了歸納+加法原理+乘法原理+遞歸關系式！這是近年來的常見題。15．(2002年初中組) 將N個紅球和M個黃球排成一行。例如:N=2,M=3可得到以下6種排法:紅紅黃黃黃 紅黃紅黃黃 紅黃黃紅黃 黃紅紅黃黃 黃紅黃紅黃 黃黃黃紅紅。問題：當N=4,M=3時有多少種不同排法?(不用列出每種排法) 解答：35216。 排列組合和概率統(tǒng)計！16．（1999年高中組）將Ln定義為求在一個平面中用n條直線所能確定的最大區(qū)域數(shù)目。例如：當n=1時，L1=2,進一步考慮，用n條折成角的直線（角度任意），放在平面上，能確定的最大區(qū)域數(shù)目Zn是多少？例如：當n=1時，Z1=2（如下圖所示） 當給出n后，請寫出以下的表達式： 1 Ln = ______________ 2 Zn = _______________ 解答：本題實質是求直線或折線將一個平面分成的最大區(qū)域數(shù)，從兩個方面考慮：（1） 求在一個平面中用n條直線所能確定的最大區(qū)域數(shù)； n=1,L1=2, F(1)=2n=2,L2=4, F(2)=F(1)+2n=3,L3=7, F(3)=F(2)+3n=4,L4=11, F(4)=F(3)+4……所以， F(n)=F(n1)+n把上面的n個等式左右相加，化簡得出：F（n）=2+2+3+4+……+n即：L（n）=n*(n+1)/2+1（2） 求在一個平面中用n條折線所能確定的最大區(qū)域數(shù)；n=1,Z1=2, F(1)=0+2n=2,Z2=7, F(2)=1*(2*21)+4n=3,Z3=16, F(3)=2*(2*31)+6n=4,Z4=29, F(4)=3*(2*41)+8……所以， F(n)=(n1)*(2*n1)+2*n即：Z（n）=(n1)*(2*n1)+2*n216。 幾何+歸納+組合數(shù)學！17．(1998年初中組)某班有50名學生，每位學生發(fā)一張調查卡，上寫a，b，c三本書的書名，將讀過的書打252。，結果統(tǒng)計數(shù)字如下： 只讀a者8人；只讀b者4人；只讀c者3人；全部讀過的有2人；讀過a，b兩本書的有4人；讀過a，c兩本書的有2人；讀過b，c兩本書的有3人；問：（1）讀過a的人數(shù)是 （2）一本書也沒有讀過的人數(shù)是 。 解答：（1）12人 （2）30人 方法：推理或集合表示如下： 下圖中：a=8；b=4；c=3；abc=2；ab=4abc=2；ac=2abc=0；bc=3abc=1； 讀過a的人數(shù)為：a+ab+abc+ac=8+2+2+0=12 一本未讀過的人：50abcabcabacbc=30216。 邏輯推理+集合運算及變形！第三部分：閱讀程序（4*8=32分）其實很容易,目的幾乎是送分，而且占的分數(shù)很多，但得分率卻不見得高。很容易不明不白的就把分（全）丟了!!!這部分程序考3個方面：1． 程序設計語言本身，如循環(huán)、遞歸、值型參和變量型參數(shù)、跟蹤變量等；2． 歸納和數(shù)學運算能力；3． 是否掌握了一些常用算法（程序段）的框架；4． 細心、耐心等心理品質；靈感+編程的量等；一般做這類題目的核心是找程序目的：即這個程序想干什么。迄今為止考過的題目還沒有“亂寫”的，總有一點“寫作目的”的。抓住了它，不僅得出答案變得很容易了，而且對自己的結果也會比較有信心。一般的解題步驟如下：1． 從總體上通讀程序，大致把握程序的目的和算法；2． 猜測變量的作用，跟蹤主要變量值的變化（列表），找出規(guī)律；3． 將程序分段，理清每一小段的作用和目的（靈感+關鍵表達式和語句的領會）；4． 看清輸入、按照輸出格式，寫出結果；5． 帶著得到的結果回到程序進行檢查；下面舉幾個例子。216。 1．基本題(考語言本身，尤其是循環(huán)嵌套。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 y0 do begin y1:=y mod 10。 y:=y div 10。 while y10 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:=y11 end。 jk:=jk1 end。 j1:=1。 while a[j1]=0 do j1:=j1+1。 for Jk:=j1 to 20 do write(a[jk]:4)。 writelnend.程序運行結果為：___________________________。解答：程序不長，但是有一定的難度。高手最多半分鐘就看懂了程序的意思，但初學者往往算了很久得出了結果卻是錯的。下面我們還是先以一個初學者的身份分析一下這個程序。記住，不要一開始就模擬電腦來一個個語句“執(zhí)行”你算過自己是多少Hz的CPU沒有？！首先是看看變量的名字，可惜分區(qū)聯(lián)賽題目中的變量不是i就是j，很討厭。i和j一般作為循環(huán)計數(shù)器，沒有什么意思，因此不要管它了。然后要看變量在程序的哪里出現(xiàn)過，著重看它與其它變量的相互引用關系，猜測它的作用。例如上題：x只在g:=x中出現(xiàn)，暫時不要管它，因為它很可能只是一個初始數(shù)據。y有三處：1) while y0 do2) y1:=y mod 10。3) y:=y div 10。很明顯，y每次少了最后一位數(shù)字,把這位數(shù)字給了y1。有經驗的選手應該體會到了什么，不過我們繼續(xù)。現(xiàn)在我們知道了：y對程序的作用是：每次提供最后一位給y1,即y1每次的值依次是：4,6,2那么再看y1，它出現(xiàn)在兩個地方:1)while y10 do2)y1=y11很明顯就是一個循環(huán)次數(shù)嘛！循環(huán)y1次！再看jk:1)for e:=jk downto 1 do2)jk:=jk1jk作為循環(huán)初始值，居然一次比一次少...其原因有待進一步分析。再看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和其它變量沒有什么聯(lián)系。1)是初始化，2)3)4)是輸出數(shù)組a。再看g: 出現(xiàn)的位置是幾層循環(huán)之內了，應該很重要！一會兒再分析！ 再看e: 作為循環(huán)變量，沒有什么意思。通過變量分析，我們知道了：x,y是數(shù)據，y每次提供最后一位給y1,循環(huán)y1次。j1和g的作用有待分析。下面根據程序結構，把程序分成幾塊，逐個研究。最主要的程序段是兩個WHILE循環(huán)中套一個FOR循環(huán)，三重循環(huán)?。?！其實，最外面一層很明確：判斷什么時候結束（y=0）。前后都很簡單，是一些變量和數(shù)組的初始化、輸入、輸出等，下面重點剖析核心程序段。1） x:=3465。 y:=264。 jk:=20。 for j1:=1 to 20 do a[j1]:=0。 輸入與變量、數(shù)組的初始化，不要管它。2)while y0 do中只有6行，你可以模擬電腦“執(zhí)行”幾個語句在找規(guī)律。方法是：把循環(huán)“展開”，再寫一個變量值表即：語句 執(zhí)行后變量情況：g:=x。 g:=g+a[e]。 g=x+a[e]。a[e]:=g mod 10。 a[e]:=x+a[e]的個位g:=g div 10。 g=(x+a[e])的前幾位g:=g+a[e1]。 g=(x+a[e])的前幾位+a[e1]。a[e1]:=g mod 10。 a[e1]=a[e1]+(x+a[e])的進位…… begin y1:=y mod 10。 y:=y div 10。 while y10 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:=y11 end。 jk:=jk1 end。3) j1:=1。 while a[j1]=0