#define NMAX 10 #include “stdio.h” main()
{ int i,j,n,k,p,q,m; int a [NMAX][NMAX]; scanf(“%d”,&n); m=1;
for(k=1；(1) ；k++)
{if（k {if(3) {i=q-p+1；j=p；} else{i=p；j=q-p+1；} if(4) {i=i+n-q；j=j+n-q；} a[i][j]=m；(5) _; } for（i=1；i<=n;i++） { for（j=1；j<=n；j++） printf（“M”,a[i][j]）;printf(“\\n”); } } } 【上海大学 2002 六、1 （10分）】 39. 约瑟夫环问题：设有n个人围坐一圈，并按顺时针方向1—n编号。从第s个人开始进行报数，报数到第m个人，此人出圈，再从他的下一个人重新开始从1到m的报数进行下去 ，直到所有的人都出圈为止。 PROCEDURE Josef (A:ARRAY [1..n] OF integer; s,m:integer); BEGIN FOR i:= 1 TO n DO A[i]:=i; sl:=s; FOR i:=n DOWNTO 2 DO BEGIN sl:= (1) __；//计算出圈人s1 IF sl=0 THEN (2) _； w:=A[sl]; //A[s1]出圈 FOR j:= (3) __ DO A[j]:=A[j+1]; A[i]:=w; END; write('出圈序列为：’)；//输出出圈序列 FOR i :=n DOWNTO 1 DO write(A[i]); writeln ； END; 【华南师范大学 2000 五、2 (9分)】 40. 设有一个背包可以放入的物品重量为S，现有n件物品，重量分别为W1，W2，...，Wn。问能否从这n件物品中选择若干件放入背包，使得放入的重量之和正好是S。设布尔函数Knap(S，n)表示背包问题的解，Wi(i=1,2,...，n)均为正整数，并已顺序存储地在数组W中。请在下列算法的下划线处填空，使其正确求解背包问题。 Knap(S，n) 若S=0 则Knap←true 否则若（S<0）或(S>0且n<1) 则Knap←false 否则若Knap(1) , _=true 则print(W[n])；Knap ←true 否则 Knap←Knap(2) _ , _ 【山东工业大学1996 五（10分）1998 二、1 （4分）】 四 应用题 1. 数组A[1..8，-2..6，0..6]以行为主序存储，设第一个元素的首地址是78，每个元素的长度为4，试求元素A[4,2,3]的存储首地址。【厦门大学 1998 五、1 （5分）】 2. 已知b对角矩阵（aij）n*n，以行主序将b条对角线上的非零元存储在一维数组中，每个数据元素占Ｌ个存储单元，存储基地址为Ｓ，请用i，j 表示出 aij的存储位置。【北方交通大学 1996 三（10分）】 3. 数组A中，每个元素A[i,j]的长度均为32个二进位,行下标从-1到9，列下标从1到11，从首地址S开始连续存放主存储器中，主存储器字长为16位。求： （1）存放该数组所需多少单元？ （2）存放数组第4列所有元素至少需多少单元？ （3）数组按行存放时，元素A[7,4]的起始地址是多少？ （4）数组按列存放时，元素A[4,7]的起始地址是多少？ 【大连海事大学 1996 四、1 (6分)】 4．假设按低下标优先存储整型数组A（-3:8,3:5,-4:0,0:7）时，第一个元素的字节存储地址是100，每个整数占4个字节，问A（0，4，-2，5）的存储地址是什么？【清华大学 1996 三】 5．设有三维数组A[-2:4,0:3,-5:1]按列序存放，数组的起始地址为1210，试求A(1,3,-2）所在的地址。 【长沙铁道学院 1997 三、1 (3分)】 6. 三维数组A[1..10,-2..6,2..8]的每个元素的长度为4个字节，试问该数组要占多少个字节的存储空间？如果数组元素以行优先的顺序存贮，设第一个元素的首地址是100，试求元素A[5,0,7] 的存贮首地址。 【上海海运学院 1995 三（6分） 1997 三（8分）】 7. 设有五对角矩阵A=(aij)20*20，按特殊矩阵压缩存储的方式将其五条对角线上的元素存于数组A[-10：m]中，计算元素A[15,16]的存储位置。【东北大学 1999 一、2（4分）】 8．数组A[0..8, 1..10] 的元素是6 个字符组成的串，则存放A至少需要多少个字节？ A 的第8列和第5行共占多少个字节 ？若A 按行优先方式存储，元素A[8,5]的起始地址与当A按列优先方式存储时的哪个元素的起始地址一致？ 【厦门大学 2000 五、3（14%/3分）】 9. 若按照压缩存储的思想将n×n阶的对称矩阵A的下三角部分（包括主对角线元素）以行序为主序方式存放于一维数组B[1..n(n+1)/2]中，那么，A中任一个下三角元素aij(i≥j),在数组B中的下标位置k是什么？【北京航空航天大学 1998 一、4（4分）】 10. 设m×n阶稀疏矩阵A有t个非零元素，其三元组表表示为LTMA[1..（t+1）,1..3]，试问：非零元素的个数t达到什么程度时用LTMA表示A才有意义？【北京航空航天大学 1998 一、5（4分）】 11. 利用三元组存储任意稀疏数组时，在什么条件下才能节省存储空间。【西北工业大学1998三、2(5分)】 12. 对一个有t个非零元素的Amn 矩阵, 用B[0..t][1..3]的数组来表示，其中第0行的三个元素分别为m,n,t, 从第一行开始到最后一行，每行表示一个非零元素；第一列为矩阵元素的行号， 第二列为其列号，第三列为其值。对这样的表示法，如果需要经常进行该操作---确定任意一个元素A[i][j]在B中的位置并修改其值，应如何设计算法可以使时间得到改善？【长沙铁道学院 1998 四、4 (6分)】 13. 有一个二维数组A[0:8,1:5],每个数组元素用相邻的4个字节存储,存储器按字节编址,假设存储数组元素A[0,1]的第一个字节的地址是0,那么存储数组的最后一个元素的第一个字节的地址是多少?若按行存储,则A[3,5]和A[5,3]的第一个字节的地址是多少?若按列存储,则A[7,1]和A[2,4]的第一个字节的地址是多少?【上海海运学院 1999 三（10分）】 14. 设有三对角矩阵(ai,j)m╳n,将其三条对角线上的元素逐行的存于数组B(1:3n-2)中，使得B[k]=ai,j，求： （1）用i,j表示k的下标变换公式； 3 （2）若n=10,每个元素占用L个单元，则用B[K]方式比常规存储节省多少单元。 【西安电子科技大学 1996 二、4 （5分）】 15. 已知A为稀疏矩阵，试从空间和时间角度，比较采用两种不同的存储结构（二维数组和三元组表）完 成求运算的优缺点。【西安电子科技大学 1996 二、6（5分）】 16. 特殊矩阵和稀疏矩阵哪一种压缩存储后失去随机存取的功能？ 为什么？ 【北京邮电大学 2001 三、1（5分）】 17. 试叙述一维数组与有序表的异同。【西安电子科技大学 1999计应用 一、2（5分）】 18. 一个n╳n的对称矩阵，如果以行或列为主序存入内存，则其容量为多少？ 【西安电子科技大学 1999计应用 一、3（5分）】 19. 给出数组 A∶ARRAY[3..8,2..6] OF INTEGER;当它在内存中按行存放和按列存放时，分别写出数组元素A[i,j]地址计算公式（设每个元素占两个存储单元）。 【南开大学 1998 一 (8分)】 20. 已知n阶下三角矩阵A（即当i 21. 设有三对角矩阵(aij)n*n，将其三条对角线上的元素逐行地存于数组B(1:3n-2)中，使得B[k]=aij，求： （1）用i,j表示k的下标变换公式； （2）用k表示i,j的下标变化公式。 【山东科技大学 2001 一、6 （6分）】【长沙铁道学院 1997 五、1 (10分)】 【东北大学 2002 一 (4分)】【北京工业大学 2000 二、1 (9分)】【南京航空航天大学 2000 四】 22. 算法Print及所引用的数组A的值如下，写出调用Print(1)的运行结果（其中n=15）。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 A B C D E F G O O H 0 I J K L PROCEDURE print（i：integer）； BEGIN IF（i<=n〉 AND （A[i] <>‘0’） THEN BEGIN Print（2*i）；write（A[i]）；Print（2*i+1）； END； END； 【合肥工业大学 1999 四、1（5分）】 23. 设数组A的长度为2N，前N个元素A[1..N]递减有序，后N个元素A[N+1.. 2N]递增有序，且2N是2的整数次幂，即k=log22N为整数。例如A[1..8]=[90,85,50,10,30,65,80,100]满足上述要求，这里N=4,k=3,A的前4个元素和后4个元素分别递减和递增有序。用此例调用如下的Demo过程，并要求： （1）给出for循环中每次执行PerfectShuffle（A,N）和CompareExchange（A,N）的结果； （2）解释Demo的功能； （3）给出Demo的时间复杂度。 PROCEDURE PerfectShuffle(VAR A:arraytype; N:integer) [ i:=1; j:=1; WHILE i<=N DO [ B[j]:=A[i]; B[j+1]:=A[i+N]; i:=i+1; j:=j+2; ] A[1..2N]:=B[1..2N]; //B copy to A ] PROCEDURE CompareExchange(VAR A:arraytype; N:integer) [ j:=1; WHILE j<2N DO [ IF A[j]>A[j+1] THEN A[j]←→A[j+1]; //交换A[j]和A[j+1] j:=j+2; ] ] PROCEDURE Demo (VAR A:arraytype;N:integer) //A的长度为2N,k=log22N为整数 [ FOR i:=1 TO log22N DO [ PerfectShuffle(A,N); CompareExchange(A,N); ] ] 【中科院计算所 1998 四 （15分）】 【中国科技大学 1998 4（15分）】 24. 现有算法及正整数n和数组A如下，求数组C的值。 VAR A,B,C:Array[1..100] of integer; FUNC AAA(s,t:integer):integer; IF s=t THEN IF B[s]=0 THEN AAA:=S ELSE AAA:=-s ELSE BEGIN l:=AAA(s,(s+t) DIV 2); r:=AAA((s+t) DIV 2+1,t); IF l>0 THEN AAA:=l ELSE AAA:=r; IF (r>0) AND (A[l]>A[r]) THEN AAA:=r END ENDF; PROC BBB; FOR i:=1 TO n DO B[i]:=0; FOR i:=1 TO n DO B[AAA(1,n)]:=i; FOR i:=1 TO n DO C[B[i]]:=A[i]; ENDP; 初始值：n=10,A={121,22,323,212,636,939,828,424,55,262}; 【北京邮电大学 2002 五、1（10分）】 25. 设有矩阵ａ且a=执行下列语句后，矩阵ｃ和ａ的结果分别是什么？ （1） FOR i:=1 TO 3 DO FOR j:=1 TO 3 DO c[i,j]:=a[a[i,j],a[j,i]] （2） FOR i:=1 TO 3 DO FOR j:=1 TO 3 DO a[i,j]:=a[a[i,j],a[j,i]] 【浙江大学 1997 三 (8分)】 26. 设矩阵A为 （1）执行语句 FOR i:=1 TO 3 DO FOR j:=1 TO 3 DO ① C[i,j]:=A[A[i,j],A[j,i]] 结果C矩阵的值是什么？ （2）所选择的下标i,j的次序有关系吗？ （3）在语句①中，用A代替C，A的结果值是什么？ （4）对i,j这对下标取反序，即 （3，3），（3，2），（3，1），??，（1，3），（1，2），（1，1） 重复执行（3）,把所得结果与（3）中所得结果作比较。 【吉林大学 1995 二 (15分)】 27. 指出下列算法中错误、低效之处，并将其改成一个正确且高效的算法。 PROCEDURE delk(A, m , last,i, k) ; ｛从数组A[１..last]中删除第i个元素起的 k个元素，m为A上限｝ BEGIN IF(i<1) OR (i>last) OR(k<0) OR(last>m) THEN write ('error') ELSE FOR count: = 1 TO k TO [FOR j:=last DOWNTO i+1 DO A[j-1]:=A[j]; last:=last-1] ENDP;{delk} 【北方交通大学 1997 一 （10分）】 28. 设输入为整数数组A[1..n]，其中1<=A[i]<=k(1<=i<=n)；输出数组为b[1..n]；c[1..k]是临时工作空间；阅读下述算法后，回答下列问题： PROC Demo(A,B,k){ (1)FOR i:=1 TO k DO C[i]:=0; (2)FOR j:=1 TO n DO C[A[j]]:= C[A[j]]+1; (3)FOR i:=2 TO k DO C[i]:= C[i]+ C[i-1] (4)FOR j:=n DOWNTO 1 DO { (5) B[C[A[j]]]:=A[j]; (6)C[A[j]]:=C[A[j]]-1 } } (a).当标号（2）行的循环执行完后，C[i](1<=i<=n)的值有何意义？ (b).当标号（3）行的循环执行完后，C[i](1<=i<=n)的值有何意义？ (c).算法执行后，B的内容有何特点？ (d).当k=O(n)时，算法的时间复杂度是多少？ 【中科院软件所 1997 二、2（9分）】 29．上三角阵A（N*N）按行主序压缩存放在数组B中，其中A[i,j]=B[k].写出用i，j表示的k。 【北京工业大学 2001 二、1 (5分)】 30. 设有上三角矩阵(aij)n*n，将其上三角中的元素按先行后列的顺序存于数组B（1:m）中，使得B[k]= aij且k=f1(i)+f2(j)+c，请推导出函数f1,f2和常数c，要求f1和f2中不含常数项。 【中科院自动化所 1999】 【山东科技大学 2002 一、5 （6分）】 31． 设矩阵A= (1) 若将A视为对称矩阵，画出对其压缩存储的存储表，并讨论如何存取A中元素aij (0<=i,j<4)； (2) 若将A视为稀疏矩阵，画出A的十字链表结构。 【北京科技大学 1997 三 （10分）】 32. 设对称矩阵A= （1）若将A中包括主对角线的下三角元素按列的顺序压缩到数组S中, 即S: 10 0 2 3 0 0 0 5 0 下标：1 2 3 4 5 6 7 8 9 10 试求出A中任一元素的行列下标[i,j](1<=i,j<=4)与S中元素的下标K之间的关系. （2）若将A视为稀疏矩阵时,画出其三元组表形式压缩存储表。【北京科技大学1999 三（10分）】 33. 设对角线矩阵A=（ 行列下标i ,j 满足：1≤i,j≤5） （1）若将矩阵A压缩存储到数组S 中： 1 2 1 0 1 2 1 0 0 0 1 3 5 下标： 1 2 3 4 5 6 7 8 9 10 11 12 13 试求出A中已存储之元素的行列下标（i， j）与S中元素的下标K之间的关系 （2）若将A视为稀疏距阵时，请画出其行逻辑链接顺序表。【北京科技大学2000 三(10分)】 34．设有一个三维数组a[c1:d1,c2:d2,c3:d3]，其中ci:di是第i维的界偶，如该数组在内存中按行排列，且a[c1,c2,c3]的地址为a0，那么请导出下标变量a[i1,i2,i3]的地址，假设每个元素占L个单元。 【山东师范大学 1999 四、1 （5分）】 35．假定有下列nⅹn矩阵（n为奇数）A= 如果用一维数组B按行主次序存储A的非零元素，问： （1）A中非零元素的行下标与列下标的关系； （2）给出A中非零元素aij 的下标(i,j)与B中的下标R的关系; （3）假定矩阵中每个元素占一个存贮单元且B的起始地址为A0，给出利用aij的下标(i,j)定位在B中的位置公式。 【上海交通大学 1998 三(12分)】 36. 对于一个对称矩阵采用压缩存储，只存放它的上三角部分， 并按列存放。例如对于一个n*n的对称矩阵A (如右图) ，用一 个一维数组B来存放它的上三角部分：