您所在位置：主题：分区联赛初赛经验谈
究级黑客
[专家分：50] 发布于 2003-08-04 16:08:00
10月份NOI就要开始了，在这里我对一些第一次来到的朋友们说一些经验
这里我就随便写一点自己的体会，希望对初学者有点帮助。
1.知识是基础，能力最重要
初赛考的知识点，大纲如是说：计算机基本常识/基本操作和程序设计基本知识。
选择题考查的是知识，而填空题更加重视能力的考查。例如写程序运行结果，大纲规定是
必考的。试卷中给出程序的并不复杂，语句的含义容易明白，但是悟性好的选手总是很快就能体
会到程序的设计思路并得出正确的答案，机械模仿计算机硬算出结果的同学往往做的慢的多，而
且容易失误。
2.各种题型的解题经验。
1)选择题
一般它们是比较容易得分的，一共30分，不可错过！
我建议大家找一本等级考试二级的书看，知识讲的系统一些。选择题一般不超过二级的知识点。
另外，有DOS经验的选手可能会占一点便宜，因为有些题目可以根据经验判断。
2)填空
这部分题目对数学要求要高一点，往往考查的是代数变形，数列（一般是考递推），也考查
一些算法和数据结构知识。建议大家多花一点时间做，尽量做对。
例题：
1.数组A[30..100,20..100]以行优先的方式存储,每个元素占8个字节,且已知A[40 ,30]
的地址为2000,则A[60,90]的地址为:_________________
如果以列优先存储,则为:_________________
考查了数据结构中数组存储方式。
^^^^^^^^ ^^^^
2.设栈S的初始状态为空,现有6个元素组成的序列{1,3,5,7,9,11},对该序列在S 栈上依
次进行如下操作(从序列中的1开始,出栈后不在进栈):进栈,出栈,进栈,进栈, 进栈,进栈
,出栈,进栈,问出栈的元素序列是:_________,栈顶指针的值为______
栈顶元素为:___________________
考查了数据结构中的栈。
^^^^^^^^ ^^
3.把中缀表达式写成后缀及前缀表达式
(1) (P+Q)*(A-B)/((C+D)/(E-F))-G
后:_________________
前:_________________
(2) A-C*D+B/E*(D/A)
后:_________________
前:_________________
4.根据后缀表达式,写出前缀及中缀表达式
ABC/DE+GH-/*+
前:_________________
中:_________________
这两题实际上考查了数据结构中的表达式树
^^^^^^^^ ^^^^^^^^
5.用一个字节来表示整数,最高位用作符号位(1为正,0为负),其他位表示数值,
(1)这样的表示法称为原码表示法,表示数的范围为:_________________
(2)原码表示法,将出现_________________有两种表示
(3)实际上计算机中是用补码表示数,其表示范围为:_________________
考查了数的原码，补码表示。
6.已知N*N个数据成方阵排列:
A11 A12 A13 ... A1n
A21 A22 A23 ... A2n
...
An1 An2 An3 ... Ann
已知Aij=Aji,
(1)将A11,A21,A22,A31,A32,A33... 存储到一维数组A(1),A(2),A(3)...A(K)
给出i,j 写出求K的表达式:_________________
(2)将A11,A12,...A1n,A22,A23,...A2n,A33... Ann存储到一维数组A(1),A(2),
A(3)...A(K), 给出i,j 写出求K的表达式:_________________
7.已知一个数列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成立.
实质是考数学。
8.给出一棵二叉树的中序遍历:DBGEACHFI与后序遍历:DGEBHIFCA,画出此二叉树
9.给出二叉树的前序遍历与后序遍历,能确定一棵二叉树吗,举例说明.
10.下面是一个利用完全二叉树特性,用顺序表来存储的一个二叉树,结点数据为字符型(结
点层次从小到大,同一层从左到右顺序存储,#表示空结点,@表示存储数据结束)
结点 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
数据 A B C # # D E # # # # # G F @
画出对应的二叉树:
考查了数据结构中的二叉树
^^^^^^^^ ^^^^^^
10.用邻接矩阵表示有向图（图略）
考查了数据结构中的图的表示
^^^^^^^^ ^^
11 根据Nocomachns定理，任何一个正整数n的立方一定可以表示成n个连续的奇数的和。
例如：
13=1
23=3+5
33=7+9+11
43=13+15+17+19
在这里，若将每一个式中的最小奇数称为X，那么当给出n之后，请写出X与n之间的关系表达式：＿＿＿
其实是考代数
12
某班有50名学生，每位学生发一张调查卡，上写a,b,c三本书的书名，将读过的书打“*”，结果统计数字如下：
只读a者8人；只读b者4人；只读c者3人；全部读过的有2人；读过a,b两本书的有4人；读过a,c两本书的有2人；读过b,c两本书的有3人。
（1）读过a的人数是（ ）。
（2）一本书也没读过的人数是（ ）。
数学好的小学生大概都可以做吧？
3)写运行结果
几乎是送分题，而且占的分数奇多，但得分率却不见得高。大家一定不要错过这个得分点啊！
一般做这类题目的核心是找程序目的，即这个程序想干什么。迄今为止考过的题目还没有“乱写”
的，总有一点“写作目的”的。抓住了它，不仅得出答案变得很容易了，而且对自己的结果也会
比较有信心。下面举几个例子。
1．(99年分区联赛)
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没有？！
好了，废话少说。
分析程序一般从以下几点入手：
1.变量
首先是变量的名字。可惜分区联赛题目中的变量不是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的作用有待分析。
2.程序结构
我们把程序分成几块。
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
输出结果，也不要管它。
块2最重要。
它的思想是：
每次取Y的最第位y1,执行<<>>y1次，每次把jk减一。
现在最重要的是<<>>中的在干什么。
^^^^^^
注意到最后输出的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;这几个标志句子。就可以一下子知道程序的用意了。
什么？<<>>那一段我讲的太快，听不懂？
真不好意思，好象是的。如果你真的不懂，我只好多讲一点。
<<>>中只有6行，你可以模拟电脑“执行”几个语句在找规律。
方法是：把循环“展开”，再写一个变量值表
即：
语句 执行后变量情况：
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[e-1]; g=(x+a[e])的前几位+a[e-1];
a[e-1]:=g mod 10; a[e-1]=a[e-1]+(x+a[e])的进位
....
好了，明白了没有？还没有明白就写信给我。
4)完善程序
这部分题目得分率似乎不高。没关系，尽量做吧。把一些简单的填好就行了。
注意：
1）初始化(i:=0; j:=0; for i:=1 to n do a[i]:=0之类的)
2）一些明显的动作：
a.结果没有储存在需要的地方。
b.累加器没有做加法
c.输出
3)关键动作。
例如交换排序程序的“交换”操作等很明显需要完成的操作。
分析方法和写运行结果类似，注意分析变量和程序结构，理解变量和模块的作用是解题的关键。
不熟练是不妨用自然语言描述一下。这里我就不举例子了。
这里我就随便写一点自己的体会，希望对初学者有点帮助。
1.知识是基础，能力最重要
初赛考的知识点，大纲如是说：计算机基本常识/基本操作和程序设计基本知识。
选择题考查的是知识，而填空题更加重视能力的考查。例如写程序运行结果，大纲规定是
必考的。试卷中给出程序的并不复杂，语句的含义容易明白，但是悟性好的选手总是很快就能体
会到程序的设计思路并得出正确的答案，机械模仿计算机硬算出结果的同学往往做的慢的多，而
且容易失误。
2.各种题型的解题经验。
1)选择题
一般它们是比较容易得分的，一共30分，不可错过！
我建议大家找一本等级考试二级的书看，知识讲的系统一些。选择题一般不超过二级的知识点。
另外，有DOS经验的选手可能会占一点便宜，因为有些题目可以根据经验判断。
2)填空
这部分题目对数学要求要高一点，往往考查的是代数变形，数列（一般是考递推），也考查
一些算法和数据结构知识。建议大家多花一点时间做，尽量做对。
例题：
1.数组A[30..100,20..100]以行优先的方式存储,每个元素占8个字节,且已知A[40 ,30]
的地址为2000,则A[60,90]的地址为:_________________
如果以列优先存储,则为:_________________
考查了数据结构中数组存储方式。
^^^^^^^^ ^^^^
2.设栈S的初始状态为空,现有6个元素组成的序列{1,3,5,7,9,11},对该序列在S 栈上依
次进行如下操作(从序列中的1开始,出栈后不在进栈):进栈,出栈,进栈,进栈, 进栈,进栈
,出栈,进栈,问出栈的元素序列是:_________,栈顶指针的值为______
栈顶元素为:___________________
考查了数据结构中的栈。
^^^^^^^^ ^^
3.把中缀表达式写成后缀及前缀表达式
(1) (P+Q)*(A-B)/((C+D)/(E-F))-G
后:_________________
前:_________________
(2) A-C*D+B/E*(D/A)
后:_________________
前:_________________
4.根据后缀表达式,写出前缀及中缀表达式
ABC/DE+GH-/*+
前:_________________
中:_________________
这两题实际上考查了数据结构中的表达式树
^^^^^^^^ ^^^^^^^^
5.用一个字节来表示整数,最高位用作符号位(1为正,0为负),其他位表示数值,
(1)这样的表示法称为原码表示法,表示数的范围为:_________________
(2)原码表示法,将出现_________________有两种表示
(3)实际上计算机中是用补码表示数,其表示范围为:_________________
考查了数的原码，补码表示。
6.已知N*N个数据成方阵排列:
A11 A12 A13 ... A1n
A21 A22 A23 ... A2n
...
An1 An2 An3 ... Ann
已知Aij=Aji,
(1)将A11,A21,A22,A31,A32,A33... 存储到一维数组A(1),A(2),A(3)...A(K)
给出i,j 写出求K的表达式:_________________
(2)将A11,A12,...A1n,A22,A23,...A2n,A33... Ann存储到一维数组A(1),A(2),
A(3)...A(K), 给出i,j 写出求K的表达式:_________________
7.已知一个数列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成立.
实质是考数学。
8.给出一棵二叉树的中序遍历:DBGEACHFI与后序遍历:DGEBHIFCA,画出此二叉树
9.给出二叉树的前序遍历与后序遍历,能确定一棵二叉树吗,举例说明.
10.下面是一个利用完全二叉树特性,用顺序表来存储的一个二叉树,结点数据为字符型(结
点层次从小到大,同一层从左到右顺序存储,#表示空结点,@表示存储数据结束)
结点 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
数据 A B C # # D E # # # # # G F @
画出对应的二叉树:
考查了数据结构中的二叉树
^^^^^^^^ ^^^^^^
10.用邻接矩阵表示有向图（图略）
考查了数据结构中的图的表示
^^^^^^^^ ^^
11 根据Nocomachns定理，任何一个正整数n的立方一定可以表示成n个连续的奇数的和。
例如：
13=1
23=3+5
33=7+9+11
43=13+15+17+19
在这里，若将每一个式中的最小奇数称为X，那么当给出n之后，请写出X与n之间的关系表达式：＿＿＿
其实是考代数
12
某班有50名学生，每位学生发一张调查卡，上写a,b,c三本书的书名，将读过的书打“*”，结果统计数字如下：
只读a者8人；只读b者4人；只读c者3人；全部读过的有2人；读过a,b两本书的有4人；读过a,c两本书的有2人；读过b,c两本书的有3人。
（1）读过a的人数是（ ）。
（2）一本书也没读过的人数是（ ）。
数学好的小学生大概都可以做吧？
3)写运行结果
几乎是送分题，而且占的分数奇多，但得分率却不见得高。大家一定不要错过这个得分点啊！
一般做这类题目的核心是找程序目的，即这个程序想干什么。迄今为止考过的题目还没有“乱写”
的，总有一点“写作目的”的。抓住了它，不仅得出答案变得很容易了，而且对自己的结果也会
比较有信心。下面举几个例子。
1．(99年分区联赛)
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没有？！
好了，废话少说。
分析程序一般从以下几点入手：
1.变量
首先是变量的名字。可惜分区联赛题目中的变量不是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的作用有待分析。
2.程序结构
我们把程序分成几块。
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
输出结果，也不要管它。
块2最重要。
它的思想是：
每次取Y的最第位y1,执行<<>>y1次，每次把jk减一。
现在最重要的是<<>>中的在干什么。
^^^^^^
注意到最后输出的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;这几个标志句子。就可以一下子知道程序的用意了。
什么？<<>>那一段我讲的太快，听不懂？
真不好意思，好象是的。如果你真的不懂，我只好多讲一点。
<<>>中只有6行，你可以模拟电脑“执行”几个语句在找规律。
方法是：把循环“展开”，再写一个变量值表
即：
语句 执行后变量情况：
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[e-1]; g=(x+a[e])的前几位+a[e-1];
a[e-1]:=g mod 10; a[e-1]=a[e-1]+(x+a[e])的进位
....
好了，明白了没有？还没有明白就写信给我。
4)完善程序
这部分题目得分率似乎不高。没关系，尽量做吧。把一些简单的填好就行了。
注意：
1）初始化(i:=0; j:=0; for i:=1 to n do a[i]:=0之类的)
2）一些明显的动作：
a.结果没有储存在需要的地方。
b.累加器没有做加法
c.输出
3)关键动作。
例如交换排序程序的“交换”操作等很明显需要完成的操作。
分析方法和写运行结果类似，注意分析变量和程序结构，理解变量和模块的作用是解题的关键。
不熟练是不妨用自然语言描述一下。这里我就不举例子了。
