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

用5角钱换成5分、2分、1分的硬币，可有多少种换法？请列出问题的算法。

3. 已知如下N*(N+1)/2个数据，按行的顺序存入数组A[1],A[2],.....中:A11A21 A22A31 A32 A33AN1 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+...+a27s2=a28+a29+...+a54第一次比较(s1,s2):s1>s2 取k=0s1<s2 取k=27s1=s2 取k=54第一步：s1=a k+1+a k+2+...+a9s2=ak+i°+ak+ii+...+ak+i8第二次比较(s1,s2):s1>s2 取k=s1<s2 取k=s1=s2 取k=第三步：s1=a k+i+a k+2+a k+3S2=3k+4+3k+5+a k+6第三次比较（S1,S2）：s1>s2 取k=s1<s2 取k=s1=s2 1R k=第四/P:s1=a k+1s2 = ak+2第四次比较（s1,s2）:s1>s2:为最大数s1<s2:为最大数s1=s2:为最大数6. 已知，按中序遍历二叉树的结果为：abc0有多少种不同形态的二叉树可以得到这一•遍历结果，并画出这些二叉树。

7. 有2xn的一个长方形方格，用一个仆2的骨牌铺满方格。

例如n=3时，为2x3方格。

此时用一个仆2 的骨牌铺满方格，共有3种铺法：试对给出的任意一个n（n〉0）,求出铺法总数的递推公式。

设有一个共有n级的楼梯，某人每步可走1级，也可走2级，也可走3级，用递推公式给出某人从底层开始走完全部楼梯的走法。

例如：当n=3时，共有4种走法，即1+1+1, 1+2, 2+1, 3o8. 有标号为A、B、C、D和1、2、3、4的8个球，每两个球装一盒，分装4盒。

标号为字母的球与标号为数字的球有着某种一一对应的关系（称为匹配）并已知如下条件：%1匹配的两个球不能在一个盒子内；%12号匹配的球与1号球在一个盒子里；%1A号和2号球在一个盒子里；%1B匹配的球和C号球在一个盒子里；③3号匹配的球与冬号匹配的球在一个盒子里；%14号是A或B号球的匹配球；%1D号与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+141B. SA+180C. SA+222D. SA+22511. 某数列有1000个各不相同的单元，由低至高按序排列；现要对该数列进行二分法检索(binary-search),在最坏的情况下，需检视( )个单元。

A.1000B. 10C. 100D. 50012. 公式推导：根据Nocomachns定理，任何一个正整数n的立方一定可以表示成n个连续的奇数的和。

例如：13= 123= 3+ 533= 7+ 9 +1143=13 | - 15+17+19.在这里，若将每一个式中的最小奇数称为X,那么当给出n之后，清写出X与n之间的关系表达式：13. 在磁盘的目荥结构中，我们将与某个子目荥有关联的目荥数称为度。

例如下图:该图表达了A盘的甘录结构：DI, DII, ......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=0ack[m,n]={ack(mlJ) n=0ack(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+BAE写成前缀和后缀表这式.16. 给出一棵二叉树的中序遍历:DBGEACHFI与后序遍历:DGEBHIFCA,它的中序遍历是——.二.写出下列程序的运行结果：1. program ex1;var i,x1 ,x2,x:integer;beginx1:=3;x2:=8;for j：=1 to 5 dobeginx:=(x1+x2)*2;x1:=x2;x2:=x;end;writeln('x =’,x);end.2. program ex2;var a:array[1..11] of integer;j,k:integer;begina[1]:=1;a[2]:=1;k:=1;repeata[k+2]:=1;for j：=k downto 2 doa[i]:=a[i]+a[i-1];k:=k+1;until k>=10;for i:=1 to 11 dowrite(a[i]:4);writeln;end.3. program ex3;var i,s,max:integer;a:array[1..10] of integer;beginfor i:=1 to 10 do read(a[i]);max:=a[1];s:=a[1];for i:= 2 to 10 dobeginif s<0 then s:=0;s:=s+a[i];if s>max then max:=s;end;writeln(,max=,,max) end.输入:-2 13-1 4 78-1 -18 24 6 输出：max二输入:8 9・1 24 6 5 11 15・28 9 输出：max二4. program ex4;const n=5;var ij,k:integer;a:array[1..2*n,1..2*n] of integer;begink:=1;for i:=1 to 2*n-1 doif i<=n thenif odd(i) thenfor j:=i downto 1 dobegina[i-j+1,j]:=k;k:=k+1;endelse for j:= 1 to i dobegina[i-j+1,j]:=k;k:=k+1;endelse if odd(i) thenfor j:=n downto i-n+1 dobegina[i-j+1,j]:=k;k:=k+1;endelse for j:=i-n+1 to n dobegina[i-j+1,j]:=k;k:=k+1;end;for i:=1 to n dobeginfor j:=1 to n dowrite(a[i,j]:3);writelnend;end.5. program ex5;const n=10;var s,i:integer;function co(i1:integer):integer;var j1,s1 integer;begins1:=n;for j1:=n-1 downto n-i1+1 do s1:=s1*j1 div (n-j1+1); co:=s1;end;begins:=n+1;for i:=2 to n do s:=s+co(i);writelnCs=\s);end.6. program ex6;const n=3;var ij,s,x:integer;p:array[0..n+1] of integer;g:array[0..100] of integer;beginfor 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 dofor j:=j+1 to n+1 dog[abs(p[j]-p[i])]:=g[abs(p[j]-p[i])]+1;s:=0;for i:=0 to 100 doif g[i]>0 then begin write(i:4);s:=s+1 ;end; writeln;writeln('s=',s);writeln(,input data:');readln(x);writeln(g[x])end.输入:10 20 65input data: 10输出：/.program excpl;varx,y,y1 jkj1,g,e:integer;a:array[1..2O] of 0..9;beginx:=3465;y:=264;jk:=20;forj1:=1 to 20 do a[j1]:=0;while y<>0 dobeginy1:=y mod 10;y:=y div 10;while y1<>0 dobeging：=x;for e:=jk downto 1 dobeging:=g+a[e];a[e]:=g mod 10;g:=g div 10end;y1:=y1-1end;jk:=jk-1end;j1:=1;while a[j1]=0 doj1:=j1+1;forjk:=j1 to 20 do write(a[jk]:4);writelnend.8. program ex9;varij:integer;a:array[1..14] of integer;procedure sw(i1J1 integer);var k1:integer;beginfork1:=1 toQ1-i1+1)div2dobegina[i1+k1-1]:=a[i1+k1-1]+a[j1-k1+1];a[i1-k1+1]:=a[i1+k1-1]-a[j1-k1+1];a[i1+k1-1]:=a[i1-k1+1]-a[j1-k1+1];end;end;beginj：=211;for i:=1 to 14 dobegin a[i]:=i;j:=j-i end;sw(1,4);sw(5,10);sw(11,14);sw( 1,14); for i:=1 to 14 dobeginif (j mod i)=1 then write(a[i]:3);j：=j-a[i]；end;writelnend.9. program ex10;var ij,l,n,k,s,t:integer;b:array[1..1O] of 0..9;beginreadln(l,n);s:=l;l:=1;t:=l;while s<n dobegink:=k+1;t:=t*l;s:=s+t;end;s:=s-t;n:=n-s-1;for i:=1 to 10 do b[i]:=0;j：=11；while n>0 dobeginj:=j-1;b[j]:=n mod l;n:=n div I;end;for i:=10-k+1 to 10 dowrite(chr(ord('a')+b[i]));end.输A: 4 167输出：10. program exp3;var i,j,s:integer;b:array[0..5] of integer;begins:=1;for i:=1 to 5 do b[i]:=i;j：=1；while j>0 dobeginj：=5；while (j>0) and (b[j]=10+j-5) do j:=j-1; if j>0 thenbegins:=s+1;b[j]:=b[j]+1;for i:=j+1 to 5 do b[i]:=b[j]+i-jend;end;writeln(,s=l,s);end.11. program ex11;vari,j,j1,j2,p,q:integer;p1:boolean;b,c:array[1..100] of integer;beginreadln(q, p);j:=1 ;p1 :=true;;j1:=0;fillchar(b,sizeof(b),0);b[j]:=q;while (q>0) and p1 dobeginj1:=j1+1;c[j1]:=q*10divp;q:=q*10-c[j1]*p;if q>0 thenbeginj2:=1；while (b[j2]<>q) and (j2<=j) do j2:=j2+1;if b[j2]=q thenbeginp1:=false; writefO.');for i:=1 to j2-1 do write(c[i]:1);writeCf)；for i:=j2 toj1 do write(c[i]:1);writelnf}');end else begin j:=j+1;b[j]:=q end;end;end;if q=0 then begin write('0.');for i:=1 to j1 do write(c[i]:1);writelnend;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:array[0..n,0..m] of 0..1; function disp(x1 ,y1 ,x2,y2:integer):real;begindisp:=sqrt((x1 -x2 )*(x1 -x2)+(y 1 -y2)*(y1 -y2)); end;beginfor i:=0 to n dofor j:=0 to m dog[i,j]：=o；readln(x1,y1,x2,y2);g[x1,y1]:=1;g[x2,y2]:=1;p:=true;while p dobeginp:=false;d:=disp(x1 ,y1 ,x2,y2);x0:=x1;y0:=y1;for i:=4 to n dofor j:=0 to m doif (d>disp(i,j,x2,y2)) and (g[i,j]=O) then begind:=disp(i,j,x2,y2);xO:=i;yO:=j;end;if (x0<>x1) or (y0<>y1) thenbeginx1 :=x0;y1 :=yO;p:=true; g[x1,y1]:=1;end;d:=disp(x1,y1,x2,y2);x0:=x2;y0:=y2;for i:=0 to 3 dofor j:=0 to m doif (d<disp(x1,y1,i,j)) and (g[i,j]=O) then begind:=disp(x1,y1,ij);xO:=i;yO:=j;end;if (x0<>x2) or (y0<>y2) thenbeginx2:=x0;y2:=y0;p:=true; g[x2,y2]:=1;end;end;writeln(x1,y11x2,y2)end.输入:7 6 0 0输出：。