信息學(xué)基礎(chǔ)知識練習(xí)題(一)

1、信息學(xué)基礎(chǔ)知識練習(xí)題（一）一.數(shù)據(jù)結(jié)構(gòu)及其它練習(xí)題1.請將以下程序段表示的計算公式寫出來(假設(shè)X的值已給出)    e：=1；    a：=1；    for n：=1 to 10 do    a：=a*xn；    e：=e+a；      endfor；  2.    列舉一個算法，使算法的解能對應(yīng)相應(yīng)的問題。用5角錢換成5分、2分、1分的硬幣

2、，可有多少種換法?請列出問題的算法。3.已知如下N*(N+1)/2個數(shù)據(jù),按行的順序存入數(shù)組A1,A2,.中:    A11                                     &

3、#160;                              A21    A22                

4、0;                                             A31    A32  &

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

6、60;   其中：第一個下標(biāo)表示行，第二個下標(biāo)表示列。若Aij(i>=j，j=1,2，N)存入AK中，試問：K和i，j之間的關(guān)系如何表示?給定K值(K N*(N+1)2)后 ,寫出能決定相應(yīng)的i，j值的算法。4.有紅、黃、黑、白四色球各一個，放置在一個內(nèi)存編號為1、2、3、4四個格子的盒中，每個格子放置一只球，它們的順序不知。甲、乙、丙三人猜測放置順序如下：  甲：黑編號1，黃編號2；  乙：黑編號2，白編號3；  丙：紅編號2，白編號4。結(jié)果證明甲乙丙三人各猜中了一半，寫出四色球在盒子中放置情況及推理過程。5.已知:a1,a2,.a81

7、共81個數(shù),其中只有一個數(shù)比其他數(shù)大,以下是用最少的次數(shù)找出來。將下列算法補充完整。第一步：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;   為最大數(shù) s1<s2:           為最大數(shù) s1=s2:           為最大數(shù)6.已知，按中序遍歷二叉樹的結(jié)果為：abc。問：有多少種不同形態(tài)的二叉樹可以得到這一遍歷結(jié)果，并畫出這些二叉樹。 7.有2×n的一個長方形方格，用一個1×2的骨牌鋪滿方格。例如n=3時，為2×3方格。此時用一

12、個1×2的骨牌鋪滿方格，共有3種鋪法：試對給出的任意一個n(n 0)，求出鋪法總數(shù)的遞推公式。設(shè)有一個共有n級的樓梯，某人每步可走1級，也可走2級，也可走3級，用遞推公式給出某人從底層開始走完全部樓梯的走法。例如：當(dāng)n=3時，共有4種走法，即1+1+1，1+2，2+1，3。8.有標(biāo)號為A、B、C、D和1、2、3、4的8個球，每兩個球裝一盒，分裝4盒。標(biāo)號為字母的球與標(biāo)號為數(shù)字的球有著某種一一對應(yīng)的關(guān)系(稱為匹配)并已知如下條件：    匹配的兩個球不能在一個盒子內(nèi)；    2號匹配的球與1號球在一個盒子里； 

13、60;  A號和2號球在一個盒子里；    B匹配的球和C號球在一個盒子里；    3號匹配的球與冬號匹配的球在一個盒子里；    4號是A或B號球的匹配球；    D號與1號或2號球匹配。    請寫出這四對球匹配的情況。9.電線上停著兩種鳥（A，B），可以看出兩只相鄰的鳥就將電線分為了一個線段。這些線段可分為兩類；一類是兩端的小鳥相同；另一類則是兩端的小鳥不相同。已知：電線兩個頂點上正好停著相同的小鳥，試問兩端為不同小鳥的線段數(shù)目一

14、定是（）。A.奇數(shù)B. 偶數(shù)C. 可奇可偶D. 數(shù)目固定10.已知數(shù)組中A中，每個元素A（I，J）在存貯時要占3個字節(jié)，設(shè)I從1變化到8，J從1變化到10，分配內(nèi)存時是從地址SA開始連續(xù)按行存貯分配的。試問：A（5，8）的起始地址為（）A.SA+141B. SA+180C. SA+222D. SA+22511.某數(shù)列有1000個各不相同的單元，由低至高按序排列；現(xiàn)要對該數(shù)列進(jìn)行二分法檢索（binary-search），在最壞的情況下，需檢視（）個單元。A.1000B. 10C. 100D. 50012.公式推導(dǎo)： 根據(jù)Nocomachns定理，任何一個正整數(shù)n的立方一定可以表示成n個連續(xù)的奇數(shù)

15、的和。例如： 13 1 23 3 5 33 7 9 11 43=13十15+17+19. 在這里，若將每一個式中的最小奇數(shù)稱為X，那么當(dāng)給出n之后，請寫出X與n之間的關(guān)系表達(dá)式：13.在磁盤的目錄結(jié)構(gòu)中，我們將與某個子目錄有關(guān)聯(lián)的目錄數(shù)稱為度。例如下圖： 該圖表達(dá)了A盤的目錄結(jié)構(gòu)：DI，Dll，D2均表示子目錄的名字.在這里，根目錄的度為2，D1子目錄的度為3，D11子目錄的度為4，D12，D2，D111，D112，D113的度均為1。又不考慮子目錄的名字，則可簡單的圖示為如下的樹結(jié)構(gòu)： 若知道一個磁盤的目錄結(jié)構(gòu)中，度為2的子目錄有2個，度為3的子目錄有1個，度為4的子目錄有3個。 試問：度為

16、1的子目錄有幾個？14.已知:ack(m,n)函數(shù)的計算公式如下:              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.將表達(dá)式A+B*(C/D)和A-C*D+BE寫成前綴和后綴表達(dá)式.16.給出一棵二叉樹的中序遍歷:DBGEACHFI與后序遍歷:DGEBHIFCA,它的中序遍歷是-.二.寫出下列程序的運行結(jié)果：

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