初赛练习题1
- 格式：docx
- 大小：49.82 KB
- 文档页数：14
初赛练习题1
信息学基础知识练习题（一）
一.数据结构及其它练习题
1.请将以下程序段表示的计算公式写出来(假设X的值已给出)
e：=1；
a：=1；
for n：=1 to 10 do
a：=a*x／n；
e：=e+a；
endfor；
2. 列举一个算法，使算法的解能对应相应的问题。
用5角钱换成5分、2分、1分的硬币，可有多少种换法?请列出问题的算法。
3.已知如下N*(N+1)/2个数据,按行的顺序存入数组A[1],A[2],.....中:
A11
A21 A22
A31 A32 A33
.........
AN1 AN2 AN3 ．．．．．. ANN ；
其中：第一个下标表示行，第二个下标表示列。若Aij(i>=j，j=1,2，，N)存入A[K]中，试问：K和i，j之间的关系如何表示?给定K值(K ≤ N*(N+1)／2)后,写出能决定相应的i，j值的算法。
4.有红、黄、黑、白四色球各一个，放置在一个内存编号为1、2、3、4四个格子的盒中，每个格子放置一只球，它们的顺序不知。甲、乙、丙三人猜测放置顺序如下：
甲：黑编号1，黄编号2；
乙：黑编号2，白编号3；
丙：红编号2，白编号4。 结果证明甲乙丙三人各猜中了一半，写出四色球在盒子中放置情况及推理过程。
5.已知:a1,a2,...a81共81个数,其中只有一个数比其他数大,以下是用最少的次数找出来。
将下列算法补充完整。
第一步：s1＝a1＋a2＋...+a27
s2=a28+a29+...+a54
第一次比较(s1,s2):
s1>s2 取k=0
s1
s1=s2 取k=54
第二步：s1＝a k+1＋a k+2＋...+a9
s2=a k+10+a k+11+...+a k+18
第二次比较(s1,s2):
s1>s2 取k=
s1
s1=s2 取k=
第三步：s1＝a k+1＋a k+2＋a k+3
s2=a k+4+a k+5+a k+6
第三次比较(s1,s2):
s1>s2 取k=
s1
s1=s2 取k=
第四步:s1=a k+1
s2=a k+2
第四次比较(s1,s2):
s1>s2: 为最大数
s1
s1=s2: 为最大数
6.已知，按中序遍历二叉树的结果为：abc。问：有多少种不同形态的二叉树可以得到这一遍历结果，并画出这些二叉树。
7.有2×n的一个长方形方格，用一个1×2的骨牌铺满方格。例如n=3时，为2×3方格。此时用一个1×2的骨牌铺满方格，共有3种铺法：
试对给出的任意一个n(n 〉0)，求出铺法总数的递推公式。
设有一个共有n级的楼梯，某人每步可走1级，也可走2级，也可走3级，用递推公式给出某人从底层开始走完全部楼梯的走法。例如：当n=3时，共有4种走法，即1+1+1，1+2，
2+1，3。
8.有标号为A、B、C、D和1、2、3、4的8个球，每两个球装一盒，分装4盒。标号为字母的球与标号为数字的球有着某种一一对应的关系(称为匹配)并已知如下条件：
①匹配的两个球不能在一个盒子内；
②2号匹配的球与1号球在一个盒子里；
③A号和2号球在一个盒子里；
④B匹配的球和C号球在一个盒子里；
③3号匹配的球与冬号匹配的球在一个盒子里；
⑥4号是A或B号球的匹配球；
⑦D号与1号或2号球匹配。
请写出这四对球匹配的情况。
9.电线上停着两种鸟（A，B），可以看出两只相邻的鸟就将电线分为了一个线段。这些线段可分为两类；一类是两端的小鸟相同；另一类则是两端的小鸟不相同。已知：电线两个顶点上正好停着相同的小鸟，试问两端为不同小鸟的线段数目一定是（）。
A.奇数
B. 偶数
C. 可奇可偶
D. 数目固定
10.已知数组中A中，每个元素A（I，J）在存贮时要占3个字节，设I从1变化到8，J从1
变化到10，分配内存时是从地址SA开始连续按行存贮分配的。试问：A（5，8）的起始地址为（）
A.SA+141
B. SA+180
C. SA+222
D. SA+225
11.某数列有1000个各不相同的单元，由低至高按序排列；现要对该数列进行二分法检索（binary-search），在最坏的情况下，需检视（）个单元。
A.1000
B. 10
C. 100
D. 500
12.公式推导：根据Nocomachns定理，任何一个正整数n的立方一定可以表示成n个连续的奇数的和。例如：
13＝1
23＝3＋5
33＝7＋9 ＋11
43=13十15+17+19
. 在这里，若将每一个式中的最小奇数称为X，那么当给出n之后，请写出X与n之间的关系表达式：＿＿＿
13.在磁盘的目录结构中，我们将与某个子目录有关联的目录数称为度。例如下图：
该图表达了A盘的目录结构：DI，Dll，……D2均表示子目录的名字.在这里，根目录的度为2，D1子目录的度为3，D11子目录的度为4，D12，D2，D111，D112，D113的度均为1。又不考虑子目录的名字，则可简单的图示为如下的树结构： 若知道一个磁盘的目录结构中，度为2的子目录有2个，度为3的子目录有1个，度为4的子目录有3个。
试问：度为1的子目录有几个？
14.已知:ack(m,n)函数的计算公式如下:
n+1 m=0
ack[m,n]={ack(m-1,1) n=0
ack(m-1,ack(m,n-1)) m,n<>0
计算ack(1,2),ack(1,3),ack(2,2),ack(2,4).
15.将表达式A+B*(C/D)和A-C*D+B^E写成前缀和后缀表达式.
16.给出一棵二叉树的中序遍历:DBGEACHFI与后序遍历:DGEBHIFCA,它的中序遍历是-------.
二.写出下列程序的运行结果：
1.program ex1;
var i,x1,x2,x:integer;
begin
x1:=3;
x2:=8;
for i:=1 to 5 do
begin
x:=(x1+x2)*2;
x1:=x2;x2:=x;
end;
writeln('x=',x);
end.
2.program ex2;
var a:array[1..11] of integer; i,k:integer; begin
a[1]:=1;a[2]:=1;k:=1;
repeat
a[k+2]:=1;
for i:=k downto 2 do
a[i]:=a[i]+a[i-1];
k:=k+1;
until k>=10;
for i:=1 to 11 do
write(a[i]:4);
writeln;
end.
3.program ex3;
var i,s,max:integer;
a:array[1..10] of integer;
begin
for i:=1 to 10 do read(a[i]);
max:=a[1];s:=a[1];
for i:= 2 to 10 do
begin
if s<0 then s:=0;
s:=s+a[i];
if s>max then max:=s;
end;
writeln('max=',max)
end.
输入:-2 13 -1 4 7 8 -1 -18 24 6 输出:max=输入:8 9 -1 24 6 5
11 15 -28 9 输出:max=
4.program ex4;
const n=5; var i,j,k:integer;
a:array[1..2*n,1..2*n] of integer;
begin
k:=1;
for i:=1 to 2*n-1 do
if i<=n then
if odd(i) then
for j:=i downto 1 do
begin
a[i-j+1,j]:=k;k:=k+1;
end
else for j:= 1 to i do
begin
a[i-j+1,j]:=k;k:=k+1;
end
else if odd(i) then
for j:=n downto i-n+1 do
begin
a[i-j+1,j]:=k;k:=k+1;
end
else for j:=i-n+1 to n do
begin
a[i-j+1,j]:=k;k:=k+1;
end;
for i:=1 to n do
begin
for j:=1 to n do
write(a[i,j]:3);
writeln
end; end.
5.program ex5;
const n=10;
var s,i:integer;
function co(i1:integer):integer;
var j1,s1:integer;
begin
s1:=n;
for j1:=n-1 downto n-i1+1 do
s1:=s1*j1 div (n-j1+1);
co:=s1;
end;
begin
s:=n+1;
for i:=2 to n do s:=s+co(i);
writeln('s=',s);
end.
6.program ex6;
const n=3;
var i,j,s,x:integer;
p:array[0..n+1] of integer;
g:array[0..100] of integer;
begin
for i:=0 to 100 do g[i]:=0;
p[0]:=0;p[n+1]:=100;
for i:=1 to n do read(p[i]);
readln;
for i:=0 to n do
for j:=i+1 to n+1 do
g[abs(p[j]-p[i])]:=g[abs(p[j]-p[i])]+1;
