1、信息学基础知识练习题一doc信息学基础知识练习题(一) 一 .数据结构及其它练习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个数据，按行的顺序存入数组A1,A2,.中:A11A21 A22A31 A32 A33AN1 AN2 AN3 ANN ；其中：第一个下标表示行，第二个下标表示列。若Aij(i=j, j=1,2, ,
2、 N)存入AK中,试问：K和i, j之间的关系如何表示?给定K值(Ks2 取 k=0s1s2 取 k=s1s2 取 k=s1s2:为最大数s1s2:为最大数s1=s2:为最大数6.已知，按中序遍历二叉树的结果为：abc0 有多少种不同形态的二叉树可以得到这一遍历结果，并画出这些二叉树。7.有2xn的一个长方形方格，用一个仆2的骨牌铺满方格。例如n=3时，为2x3方格。此时用一个仆2 的骨牌铺满方格，共有3种铺法：试对给出的任意一个n（n0）,求出铺法总数的递推公式。设有一个共有n级的楼梯，某人每步可走1级，也可走2级，也可走3级，用递推公式给出某人从底层 开始走完全部楼梯的走法。例如：当n=3
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）,可以看出两只相邻的鸟就将电线分为了一个线段。这些线段可分为两类;一类是两端的小鸟相同；
4、另一类则是两端的小鸟不相同。已知：电线两个顶点上正好停着相同的小鸟， 试问两端为不同小鸟的线段数目一定是（ ）。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+22511.某数列有1000个各不相同的单元，由低至高按序排列；现要对该数列进行二分法检索(binary-search),在最坏的情况下，需检视( )个单元。A.1000 B. 1
5、0 C. 100 D. 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。
6、又不考虑子目录 的名字，则可简单的图示为如下的树结构：若知道一个磁盘的目录结构中，度为2的子目录有2个，度为3的子目录有1个，度为4的子目录 有3个。试问：度为1的子甘录有几个？14.已知:ack(m,n)函数的计算公式如下：n+1 m=0ackm,n=ack(mlJ) n=0ack(m-1,ack(m,n.1) m,n0计算 ack(1,2),ack(1,3),ack(2,2),ack(2,4).15.将表达式A+B*(C/D)和A-C*D+BAE写成前缀和后缀表这式.16.给出一棵二叉树的中序遍历:DBGEACHFI与后序遍历:DGEBHIFCA,它的中序遍历是.二.写出下列程序的运行结果
7、：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:array1.11 of integer;j,k:integer;begina1:=1;a2:=1;k:=1;repeatak+2:=1;for j：=k downto 2 doai:=ai+ai-1;k:=k+1;until k=10;for i:=1 to 11 dowrite(ai:4);writeln
8、;end.3.program ex3;var i,s,max:integer;a:array1.10 of integer;beginfor i:=1 to 10 do read(ai);max:=a1;s:=a1;for i:= 2 to 10 dobeginif smax then max:=s;end;writeln(,max=,max) end.输入:-2 13-1 4 78-1 -18 24 6 输出：max二 输入:8 91 24 6 5 11 1528 9 输出：max二4.program ex4;const n=5;var ij,k:integer;a:array1.2*n,1
9、.2*n of integer;begink:=1;for i:=1 to 2*n-1 doif i0 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输出：/.program excpl;varx,y,y1 jkj1,g,e:integer;a:array1.2O of 0.9;beginx:=3465;y:=264;jk:=20;forj1:=1 to 20 do aj1:=0;whi
10、le y0 dobeginy1:=y mod 10;y:=y div 10;while y10 dobeging：=x;for e:=jk downto 1 dobeging:=g+ae;ae:=g mod 10;g:=g div 10end;y1:=y1-1end;jk:=jk-1end;j1:=1;while aj1=0 doj1:=j1+1;forjk:=j1 to 20 do write(ajk:4);writelnend.8.program ex9;varij:integer;a:array1.14 of integer;procedure sw(i1J1 integer);var
11、k1:integer;beginfork1:=1 toQ1-i1+1)div2dobeginai1+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;end;end;beginj：=211;for i:=1 to 14 dobegin ai:=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(ai:3);j：=j-ai；end;writeln
12、end.9.program ex10;var ij,l,n,k,s,t:integer;b:array1.1O of 0.9;beginreadln(l,n);s:=l;l:=1;t:=l;while s0 dobeginj:=j-1;bj:=n mod l;n:=n div I;end;for i:=10-k+1 to 10 dowrite(chr(ord(a)+bi);end.输A: 4 167输出：10.program exp3;var i,j,s:integer;b:array0.5 of integer;begins:=1;for i:=1 to 5 do bi:=i;j：=1；wh
13、ile j0 dobeginj：=5；while (j0) and (bj=10+j-5) do j:=j-1;if j0 thenbegins:=s+1;bj:=bj+1;for i:=j+1 to 5 do bi:=bj+i-jend;end;writeln(,s=l,s);end.11.program ex11;vari,j,j1,j2,p,q:integer;p1:boolean;b,c:array1.100 of integer;beginreadln(q, p);j:=1 ;p1 :=true;j1:=0;fillchar(b,sizeof(b),0);bj:=q;while (q
14、0) and p1 dobeginj1:=j1+1;cj1:=q*10divp;q:=q*10-cj1*p;if q0 thenbeginj2:=1；while (bj2q) and (j2disp(i,j,x2,y2) and (gi,j=O) then begind:=disp(i,j,x2,y2);xO:=i;yO:=j;end;if (x0x1) or (y0y1) thenbeginx1 :=x0;y1 :=yO;p:=true; gx1,y1:=1;end;d:=disp(x1,y1,x2,y2);x0:=x2;y0:=y2;for i:=0 to 3 dofor j:=0 to m doif (ddisp(x1,y1,i,j) and (gi,j=O) then begind:=disp(x1,y1,ij);xO:=i;yO:=j;end;if (x0x2) or (y0y2) thenbeginx2:=x0;y2:=y0;p:=true; gx2,y2:=1;end;end;writeln(x1,y11x2,y2)end.输入:7 6 0 0输出：
