我下vip免费资源网 www.woxia.net 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分）】
我下vip免费资源网 www.woxia.net 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)的值有何意义？
我下vip免费资源网 www.woxia.net (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 0 0 2 3 0 0 0 5 0 （1）若将A中包括主对角线的下三角元素按列的顺序压缩到数组S中, 即S:
下标：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个单元。
我下vip免费资源网 www.woxia.net 【山东师范大学 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来存放它的上三角部分：
B=[A11，A12，A22，A13，A23，A33，A14，?，A1n，A2n，?，Ann] 同时有两个函数：MAX(i,j)和MIN(i,j)，分别计算下标i和 j中的大者与小者。试利用它们给出求任意一个Aij在B中存放 位置的公式。（若式中没有MAX(I,j)和MIN（i，j）则不给分）
【清华大学 1997 五 (10分)】
37. 用三元数组表示稀疏矩阵的转置矩阵,并简要写出解题步骤。【山东工业大学 1995 五 （10分）】
38. 简述广义表属于线性结构的理由。【西北大学 2000 一、5 (3分)】
39. 数组，广义表与线性表之间有什么样的关系？【西北工业大学 1998 一、2 (4分)】 40. 什么是广义表？请简述广义表和线性表的主要区别。 【北京大学 1997 二、2 （5分）】 41. 求下列广义表的运算结果。【南京航空航天大学 1998 三 （10分）】
（1）CAR(CDR(((a,b),(c,d),(e,f)))) （2）CDR(CAR(((a,b),(c,d),(e,f)))) （3）CAR(CDR(CAR(((a,b),(e,f))))) （4）CDR(CAR(CDR(((a,b),(e,f))))) （5）CDR(CDR(CAR(((a,b),(e,f)))))
注：CAR运算相当于有些教材中的Head运算，CDR运算相当于Tail运算。
42. 利用广义表的Head和Ｔail运算，把原子d分别从下列广义表中分离出来，L1＝(((((a),b),d),e))；L2＝（a,(b,((d)),e））。 【北方交通大学 1996 一、2（5分）】 类似本题的另外叙述有：
(1) 已知广义表L=((((a))),((b)),(c),d)，试利用head和tail运算把原子项c从L中分离出来。
【北京邮电大学 1992 三、2（25/4分）】【青岛海洋大学 1999 一、6 （5分）】 (2) 画出下列广义表的存储结构图，并利用取表头和取表尾的操作分离出原子e。
（ a,（（）,ｂ）,（（（ｅ））））。
我下vip免费资源网 www.woxia.net 【清华大学 1995 二 （10分）】
(3) 已知广义表A=((a,b,c),(d,e,f)) 试写出从表A中取出原子元素e的运算。 【西安电子科技大学 1996 二、3 （5分）】
(4)请将香蕉banana用工具 H( )—Head( )，T( )—Tail( )从L中取出。
L=(apple,(orange,(strawberry,(banana)),peach),pear) 【北京邮电大学 2000 三、2 （5分）】
(5) 试利用广义表取表头head(ls)和取表尾tail(ls)的基本运算，将原子d从下列表中分解出来，请写出每一步的运算结果。
L=((a,(b)),((c,d)),(e,f)) 【北京工商大学 2001 三 （10分）】
(6) 画出广义表A=（a,（b,()）,(((),c))）的第一种存储结构（表结点第二指针指向余表）图，并用取首元（head()）和取尾元（tail()）函数表示原子c。【北京工业大学 2001 二、2 (5分)】
43. 画出下列广义表的两种存储结构图((),A,(B,(C,D)),(E,F))。【南京航空航天大学 1999 三（10分）】
44. 假设采用以下两种结点的链表作为广义表的存贮结构，表结点：(tag=1,hp,tp), 元素结点；(tag=0,data)。请画出下列广义表的存储结构图，并求它的深度和长度。 ( ( ) , ( ( ( ) ) , ( ( ( ) ) ) ) )
【北方交通大学 1998 一（13分）】 45．知广义表A=（（（a）），（b），c，（a），（（（d，e））））
（1）画出其一种存贮结构图； （2）写出表的长度与深度；
（3）用求头部，尾部的方式求出e。【东北大学 1997 一、2 (5分)】
46．画出具有共享结构广义表（（（b,c）,d）,(a),((a),((b,c),d)),e,()）的存贮表示。
【北京工业大学 1996 一、3 (6分)】
47. 广义表的结点结构如下:(TAG,DATA,LINK)。其中LINK为指向表中下一元素的指针;TAG为标志域；DATA为数据域，具体含义如下: TAG=0表示该结点为原子结点，DATA为其数据；TAG=1表示该结点为一个子表，DATA为指向该子表的指针。 （1）说明下列算法A的功能(注:算法中p,t,m,n,r,q为指针;算法中的NIL对应图中的^)
PROCEDURE A(p,t) BEGIN q:=NIL;
WHILE p<>NIL DO BEGIN
IF p^.TAG<>0 THEN BEGIN
m:=p^.DATA; A(m,n); p^.DATA:=n; END;
r:=p^.LINK; p^.LINK:=q; q:=p; p:=r
END;