分区联赛初赛复习
初赛考的知识点就是计算机基本常识、基本操作和程序设计基础知识。其中选择题考查的是知识，而问题解决类型的题目更加重视能力的考查。一般说来，选择题只要多用心积累就可以了。问题解决题目的模式比较固定，大家应当做做以前的题目。写运行结果和程序填空也需要多做题目，并且培养良好的程序阅读和分析能力，就像语文的阅读理解一样。
近几年来，初赛的考查范围有了很大的变化，越来越紧跟潮流了。这就需要大家有比较广泛的知识，包括计算机硬件、软件、网络、简单的数据结构（例如栈、队列、树和图等）和简单的算法（例如排序、查找和搜索等），程序设计语言以及一些基本的数学知识和技巧（例如排列组合）。但最主要的，还是取决于你对程序设计语言的熟悉程度，再加上认真仔细的心态。
练习
下面四个不同进制的数中，最小的一个是 。
（A）（11011001）2 （B）（75）10 （C）（37）8 （D）（A7）16
如果52-19=33是成立的，则52、19、33分别是 。
（A）八进制、十进制、十六进制 （B）十进制、十六进制、八进制
（C）八进制、十六进制、十进制 （D）十进制、八进制、十六进制
把下列二进制数分别化成八进制数、十六进制数和十进制数。
（1）1110B （2）-101010B （3）10.0101B (4) 101101.11B
把下列十进制数转换成二进制数（按0舍1入取6位二进制小数）。
（1） 75 （2）1024 （3）0.2 (4)18.692
用8位二进制定点整数或定点小数写出下列真值的原码、补码形式，然后用2位十六进制数表示。
（1）11001B （2）-10010B （3）100000B （4）-100000B （5）0.1B
（6）-0.1B (7) 0.100111B (8) –0.100111B (9)-15/128D
已知x的补码，写出补码的十六进制表示，再求出x的原码。
（1）[x]补=01010011B （2）[x]补=10001001B
（3）[x]补=11111111B （4）[x]补=11000000B
已知[x]原=10011011是定点纯小数，写出x的浮点数规格化形式。设其阶码是4位补码，尾数是8位原码。
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）一本书也没读过的人数是（ ）。
一个商场有m种颜色的小球，每种小球足够多，在这m种小球中挑选n个小球的选法有多少种？
如 m=2，n=3 时有4种选法分别是：两种小球的个数分别为03，12，21，30．问：当m=4，n=4时
选法数=__________。35
如果一棵m度树中有n1个度为1的结点，n2个度为2的结点，…….有
nm个度为m的结点,则该树中叶结点的的个数=______________. n2+2n3+…+(m-1)nm+1
program t1;
var n:integer;
function count(n:integer):integer;
begin
if n=1 then count:=0 else
if n mod 2=0 then count:=count(n div 2)+1 else
count:=count(n*3+1)+1;
end;
begin
readln(n);
writeln(count(n));
end.
输入:99 输出: 25
2.program t2;
var hi,lo:integer;
procedure pl(m,n:integer;var hi,lo:integer);
var I:integer;
begin
I:=n;hi:=0;lo:=0;
Repeat
I:=I-1;lo:=lo+m;
If lo>=10000 then
begin
Lo:=lo-10000;
Hi:=hi+1;
End;
Until I=0;
Write(hi:4,’, ‘,lo:4);
End;
Begin
P1(200,343,hi,lo);
End.
输出: 6.8600
3.program t3;
Var d1,d2,X,Min : real;
begin
Min:=10000; X:=3;
while X < 15 do
begin
d1:=sqrt(9+(X-3)*(X-3));
d2:=sqrt(4+(15-X)*(15-X));
if (d1+d2) < Min then Min:=d1+d2;
X:=x+0.001;
end;
writeln(Min:10:2);
end.
输出：13.00
4.program t4;
var i,k,n:integer;
x,w:array[1..500] of integer;
begin
readln(n);
for i:=1 to n do
begin
x[i]:=0;w[i]:=1;
end;
for i:=2 to trunc(sqrt(n))+1 do
if x[i]=0 then
begin
k:=i*i;
while K<=n do
begin
x[k]:=i;
k:=k+i;
end;
end;
for i:=n downto 1 do
if x[i]<>0 then
begin
w[x[i]]:=w[x[i]]+w[i];
w[i div x[i]]:=w[i div x[i]]+w[i];
w[i]:=0;
end;
writeln(w[2],w[3]:5,w[5]:5);
end.
输入:20 输出: 18 8 4
降序组合.给定两个自然数n,r(n>r),输出从数1 到n中按降序顺序取r个自然数的所有
组合.例如,n=5,r=3时,有如下组合:
5 4 3
5 4 2
5 4 1
5 3 2
5 3 1
5 2 1
4 3 2
4 3 1
4 2 1
3 2 1
程序如下:
program tk1;
var n,r,i,j:integer;
a:array[1..20] of integer;
begin
write('n,r=');
repeat
readln(n,r);
until n>r;
i:=1;a[1]:=n;writeln('result:');
repeat
if i<>r then
if a[i]>r-i then
begin
___(1)___;i:=i+1;
end
else begin
___(2)___;
a[I]:=a[I]-1 end
else
begin
for j:=1 to r do write(a[j]:3);
writeln;
if a[r]=1 then
begin
i:=i-1; a[i]:=a[i]-1;
end else ___(3)___
end;
until a[1]=r-1;
end.
1.a[i+1]:=a[i]-1
2. i:=i-1;
3. a[i]:=a[i]-1或a[r]:=a[r]-1;
2. 现在政府计划在某个区域内的的城市间架设高速公路，以使任意两个城市间能够直接或
间接到达，怎样修路，费用最小。
输入文件：第一行一个整数 n(n<=100)表示城市数目。
第二行至第n+1行每行两个数xi,yi(0<=xi,yi<=100)表示第i个城市的坐标(单位:千米)；
输出最小费用(每千米一个单位价格)。
程序如下:
program t6;
const maxn=100;
type tcity=record
x,y:real
end;
var c:array[1..maxn] of tcity;
d:array[1..maxn,1..maxn] of real;
p:array[1..maxn] of integer;
n,i,j,k:integer;
a,min:real;
begin
readln(n);
for i:=1 to n do readln(c[i].x,c[i].y);
for i:=1 to n do
for j:=1 to n do
d[i,j]:=sqrt(sqr(c[i].x-c[j].x)+sqr(c[i].y-c[j].y));
p[1]:=0;
for i:=2 to n do ___(4)___
for i:=1 to n-1 do
begin
min:=1e10;
for j:=1 to n do
if ___(5)___ then
begin
min:=d[p[j],j];
___(6)___
end;
a:=a+d[p[k],k];
p[k]:=0;
for j:=1 to n do
if ___(7)___ then p[j]:=k;
end;
writeln(a:0:2);
end.
4. p[i]:=1;
5. (p[j]>0) and (d[p[j],j]) < min)
6. k:=j;
参考资料：无敌复习资料。。共享~