层次从小到大,同一层从左到右顺序存储,#表示空结点,@表示存储数据结束)。
结点 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。
? 考查了计算机中的目录结构和树结构中的“度”的概念和性质。
16
11．（1998年高中组）用邻接矩阵/邻接表表示下面的无向/有向图（略）。 ? 考查了数据结构中的图的表示。
12.（1999年初中）根据Nocomachns定理，任何一个正整数n的立方一定可以表示成n个连续的奇数的和。 例如：
3
1=1
3
2=3+5
3
3=7+9+11
3
4=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
17
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
? 逻辑推理+集合运算及变形！
第三部分：阅读程序（4*8=32分）
其实很容易,目的几乎是送分，而且占的分数很多，但得分率却不见得高。很容易不明不白的就把分（全）丢了!!!
这部分程序考3个方面：
1． 程序设计语言本身，如循环、递归、值型参和变量型参数、跟踪变量等； 2． 归纳和数学运算能力；
18
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.
程序运行结果为：___________________________。
解答：
程序不长，但是有一定的难度。高手最多半分钟就看懂了程序的意思，但初学者往往算了很久得出了结果却是错的。下面我们还是先以一个初学者的身份分析一下这个程序。记住，不要一开始就模拟电脑来一个个语
19
句“执行”-------你算过自己是多少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 <<>>中只有6行，你可以模拟电脑“执行”几个语句在 y1:=y mod 10; 找规律。方法是：把循环“展开”，再写一个变量值表 y:=y div 10; 即： while y1<>0 do 语句 执行后变量情况： begin g:=x; << g:=x; g:=g+a[e]; g=x+a[e]; for e:=Jk downto 1 do a[e]:=g mod 10; a[e]:=x+a[e]的个位 begin g:=g div 10; g=(x+a[e])的前几位 g:=g+a[e]; g:=g+a[e-1]; g=(x+a[e])的前几位+a[e-1]; a[e]:=g mod 10; a[e-1]:=g mod 10; a[e-1]=a[e-1]+(x+a[e])的进位 g:=g div 10 ?? end; >>
y1:=y1-1
20
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库Noip初赛复习指南、题目分类解析(4)在线全文阅读。
相关推荐：