信息学基础知识练习题(一)

1、信息学基础知识练习题（一）一.数据结构及其它练习题1.请将以下程序段表示的计算公式写出来(假设X的值已给出)    e：=1；    a：=1；    for n：=1 to 10 do    a：=a*xn；    e：=e+a；      endfor；  2.    列举一个算法，使算法的解能对应相应的问题。用5角钱换成5分、2分、1分的硬币

2、，可有多少种换法?请列出问题的算法。3.已知如下N*(N+1)/2个数据,按行的顺序存入数组A1,A2,.中:    A11                                     &

3、#160;                              A21    A22                

4、0;                                             A31    A32  &

5、#160; A33     .     AN1    AN2    AN3    .    ANN    ；                      

6、60;   其中：第一个下标表示行，第二个下标表示列。若Aij(i>=j，j=1,2，N)存入AK中，试问：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

7、共81个数,其中只有一个数比其他数大,以下是用最少的次数找出来。将下列算法补充完整。第一步：s1a1a2.+a27       s2=a28+a29+.+a54 第一次比较(s1,s2):    s1>s2 取 k=0    s1<s2 取 k=27    s1=s2 取k=54第二步：s1ak+1ak+2.+a9       s2=ak+10+ak+11+.+ak

8、+18 第二次比较(s1,s2):    s1>s2 取 k=                  s1<s2 取 k=                 s1=s2 取k=     

9、0;         第三步：s1ak+1ak+2ak+3        s2=ak+4+ak+5+ak+6 第三次比较(s1,s2):    s1>s2 取 k=                  s1<s2 取 k= 

10、60;               s1=s2 取k=               第四步:s1=ak+1      s2=ak+2第四次比较(s1,s2): s1>s2:       

11、0;   为最大数 s1<s2:           为最大数 s1=s2:           为最大数6.已知，按中序遍历二叉树的结果为：abc。问：有多少种不同形态的二叉树可以得到这一遍历结果，并画出这些二叉树。 7.有2×n的一个长方形方格，用一个1×2的骨牌铺满方格。例如n=3时，为2×3方格。此时用一

12、个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号球在一个盒子里； 

13、60;  A号和2号球在一个盒子里；    B匹配的球和C号球在一个盒子里；    3号匹配的球与冬号匹配的球在一个盒子里；    4号是A或B号球的匹配球；    D号与1号或2号球匹配。    请写出这四对球匹配的情况。9.电线上停着两种鸟（A，B），可以看出两只相邻的鸟就将电线分为了一个线段。这些线段可分为两类；一类是两端的小鸟相同；另一类则是两端的小鸟不相同。已知：电线两个顶点上正好停着相同的小鸟，试问两端为不同小鸟的线段数目一

14、定是（）。A.奇数B. 偶数C. 可奇可偶D. 数目固定10.已知数组中A中，每个元素A（I，J）在存贮时要占3个字节，设I从1变化到8，J从1变化到10，分配内存时是从地址SA开始连续按行存贮分配的。试问：A（5，8）的起始地址为（）A.SA+141B. SA+180C. SA+222D. SA+22511.某数列有1000个各不相同的单元，由低至高按序排列；现要对该数列进行二分法检索（binary-search），在最坏的情况下，需检视（）个单元。A.1000B. 10C. 100D. 50012.公式推导： 根据Nocomachns定理，任何一个正整数n的立方一定可以表示成n个连续的奇数

15、的和。例如： 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个。 试问：度为

16、1的子目录有几个？14.已知:ack(m,n)函数的计算公式如下:              n+1                 m=0   ackm,n=ack(m-1,1)         &

17、#160;    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+BE写成前缀和后缀表达式.16.给出一棵二叉树的中序遍历:DBGEACHFI与后序遍历:DGEBHIFCA,它的中序遍历是-.二.写出下列程序的运行结果：

18、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);gram ex2;var a:array1.11 of integer;    i,k:integer;begin a1:=1;a2:=1;k:=1;

19、0;repeat  ak+2:=1;  for i:=k downto 2 do    ai:=ai+ai-1;  k:=k+1; until k>=10;for i:=1 to 11 do write(ai:4); writeln;gram ex3;var i,s,max:integer;    a:array1.10 of integer;begin for i:=1 to 10 do read(ai); max:=a1;s:=

20、a1; for i:= 2 to 10 do  begin   if s<0 then s:=0;   s:=s+ai;   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;&

21、#160;   a:array1.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

22、i-j+1,j:=k;k:=k+1;        end       else for j:= 1 to i do        begin         ai-j+1,j:=k;k:=k+1;        end  

23、60; else if odd(i) then        for j:=n downto i-n+1 do         begin          ai-j+1,j:=k;k:=k+1;         end     else

24、for j:=i-n+1 to n do       begin       ai-j+1,j:=k;k:=k+1;       end; for i:=1 to n do  begin   for j:=1 to n do    write(ai,j:3);    writeln  end;end.5.pr

25、ogram 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(&

26、#39;s=',s); gram ex6;const n=3;var i,j,s,x:integer;    p:array0.n+1 of integer;    g:array0.100 of integer;begin for i:=0 to 100 do gi:=0; p0:=0;pn+1:=100; for i:=1 to n do read(pi); readln; for i:=0 to n do  for j:=i+1 to

27、 n+1 do   gabs(pj-pi):=gabs(pj-pi)+1; s:=0; for i:=0 to 100 do  if gi>0 then begin write(i:4);s:=s+1;end; writeln; writeln('s=',s); writeln('input data:');readln(x); writeln(gx) end.输入:10 20 65input data: 10输出:7.program excp1;var&#

28、160;x,y,y1,jk,j1,g,e:integer; a:array1.20 of 0.9;begin  x:=3465;y:=264;jk:=20;  for j1:=1 to 20 do aj1:=0;  while y<>0 do   begin    y1:=y mod 10;    y:=y div 10;   while y1<>0 do     begin 

29、60;   g:=x;     for e:=jk downto 1 do      begin       g:=g+ae;       ae:=g mod 10;       g:=g div 10      end;   &

30、#160;  y1:=y1-1     end;     jk:=jk-1    end;    j1:=1;    while aj1=0 do j1:=j1+1;    for jk:=j1 to 20 do write(ajk:4);    writeln   gram ex9;var i,j:integ

31、er; a:array1.14 of integer; procedure sw(i1,j1:integer);  var k1:integer;  begin  for k1:=1 to (j1-i1+1) div 2 do   begin    ai1+k1-1:=ai1+k1-1+aj1-k1+1;    ai1-k1+1:=ai1+k1-1-aj1-k1+1;    ai1+k1-1:=ai1-k1+1-aj1-k1+1;

32、60;  end;  end; begin  j:=211;  for i:=1 to 14 do   begin ai:=i;j:=j-i end;  sw(1,4);sw(5,10);sw(11,14);sw(1,14);  for i:=1 to 14 do   begin    if (j mod i)=1 then write(ai:3);    j:=j-ai;   end;  wri

33、gram ex10;var i,j,l,n,k,s,t:integer;    b:array1.10 of 0.9;begin readln(l,n);s:=l;l:=1;t:=l; while s<n do  begin   k:=k+1;t:=t*l;s:=s+t;  end; s:=s-t;n:=n-s-1; for i:=1 to 10 do bi:=0; j:=11; while n>0 do  begin

34、   j:=j-1;bj:=n mod l;n:=n div l;  end; for i:=10-k+1 to 10 do  write(chr(ord('a')+bi);end.输入: 4 167输出:10.program exp3;var i,j,s:integer;    b:array0.5 of integer;begin s:=1; for i:=1 to 5 do bi:=i; j:=1; while j>0 do  begin

35、  j:=5;  while (j>0) and (bj=10+j-5) do j:=j-1;  if j>0 then   begin    s:=s+1;bj:=bj+1;    for i:=j+1 to 5 do bi:=bj+i-j   end;  end; writeln('s=',s);gram ex11;var i,j,j1,j2,p,q:integer;  &#

36、160; p1:boolean;    b,c:array1.100 of integer;begin readln(q, p);j:=1;p1:=true;j1:=0; fillchar(b,sizeof(b),0);bj:=q; while (q>0) and p1 do  begin   j1:=j1+1;cj1:=q*10 div p;q:=q*10-cj1*p;   if q>0 then    begin  &#

37、160; j2:=1;    while (bj2<>q) and (j2<=j) do j2:=j2+1;    if bj2=q then     begin     p1:=false; write('0.');     for i:=1 to j2-1 do write(ci:1);     write('');

38、0;    for i:=j2 to j1 do write(ci:1);     writeln('');    end else begin j:=j+1;bj:=q end;    end;    end;   if q=0 then begin write('0.');   for i:=1 to j1 do write(ci:1);  

39、 writeln   end; readlnend.输入:1  8 输出:输入:2  7 输出:12.program ex12;const n=7;m=6;var i,j,x0,y0,x1,y1,x2,y2:integer; d:real;p:boolean;g:array0.n,0.m of 0.1;function disp(x1,y1,x2,y2:integer):real; begin  disp:=sqrt(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2); end;begin for i:=0 to n do