分区联赛初赛准备1

　　初赛考的知识点，大纲如是说：计算机基本常识/基本操作和程序设计基本知识。选择题考查的是知识，而填空/问题解决题更加重视能力的考查。一般说来，选择题是不需要单独准备的 -- 也无从准备。只要多用心积累就可以了。到是问题解决题目比较固定，大家应当做做以前的题目。写运行结果需要多做题目，培养良好的程序阅读和分析能力，而完善程序最好总结一下以前题目常常要你填出来的语句类型。

　　1)选择题 一般它们是比较容易得分的，一共30分，不可错过！

　　以前我建议大家找一本等级考试二级的书看，知识讲的系统一些。说选择题一般不超过二级的知识点，现在显然已经不适用了。近几年来，初赛的考查范围有了很大的变化，越来越仅跟潮流了。这是好事情，不过需要大家有比较广泛的知识，包括计算机硬件，软件，网络，数据结构（例如栈，队列，排序算法），程序设计语言以及一些基本的数学知识和技巧（例如排列组合）。

　　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.

　　程序不长，但是有一定的难度。高手最多半分钟就看懂了程序的意思，但初学者往往算了很久得出了结果却是错的。下面我们还是先以一个初学者的身份分析一下这个程序。记住，不要一开始就模拟电脑来一个个语句“执行”