《数据结构》期末考试复习题第5章数组和广义表

更新时间：2024-04-03 13:35:01 阅读量：综合文库文档下载

说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。

数据结构期末考试题推荐度：
相关推荐

第 5 章数组和广义表

一、选择题

1.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。

A. 13 B. 33 C. 18 D. 40 2. 有一个二维数组A[1:6，0:7] 每个数组元素用相邻的6个字节存储，存储器按字节编址，那么这个数组的体积是（①）个字节。假设存储数组元素A[1，0]的第一个字节的地址是0，则存储数组A的最后一个元素的第一个字节的地址是（②）。若按行存储，则A[2，4]的第一个字节的地址是（③）。若按列存储，则A[5，7]的第一个字节的地址是（④）。就一般情况而言，当（⑤）时，按行存储的A[I，J]地址与按列存储的A[J，I]地址相等。供选择的答案：

①-④： A．12 B. 66 C. 72 D. 96 E. 114 F. 120

G. 156 H. 234 I. 276 J. 282 K. 283 L. 288

⑤： A．行与列的上界相同 B. 行与列的下界相同

C. 行与列的上、下界都相同 D. 行的元素个数与列的元素个数相同

3. 设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1 到8 ，j的值为1 到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为( )。

A. BA+141 B. BA+180 C. BA+222 D. BA+225

4. 假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=（）。

A. 808 B. 818 C. 1010 D. 1020

5. 数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是( )。

A. 1175 B. 1180 C. 1205 D. 1210

6. 有一个二维数组A[0:8,1:5],每个数组元素用相邻的4个字节存储，存储器按字节编址，假设存储数组元素A[0,1]的第一个字节的地址是0，存储数组A的最后一个元素的第一个字节的地址是（ ① ）。若按行存储，则A[3,5]和 A[5,3]的第一个字节的地址是（ ② ）和（ ③ ）。若按列存储，则A[7,1]和A[2,4]的第一个字节的地址是（ ④ ）和（ ⑤ ）。

①-⑤:A.28 B.44 C.76 D.92 E.108 F.116 G.132 H.176 I.184 J.188

7. 将一个A[1..100，1..100]的三对角矩阵，按行优先存入一维数组B[1‥298]中，A中元素A6665（即该元素下标i=66，j=65），在B数组中的位置K为（）。供选择的答案：

A. 198 B. 195 C. 197

8. 二维数组A的元素都是6个字符组成的串，行下标i的范围从0到8，列下标j的范圈从1到10。从供选择的答案中选出应填入下列关于数组存储叙述中（）内的正确答案。（1）存放A至少需要（）个字节；

（2）A的第8列和第5行共占（）个字节；

（3）若A按行存放，元素A[8，5]的起始地址与A按列存放时的元素（）的起始地址一致。

供选择的答案：

（1）A. 90 B. 180 C. 240 D. 270 E. 540 （2）A. 108 B. 114 C. 54 D. 60 E. 150

（3）A. A[8,5] B. A[3,10] C. A[5,8] D. A[0,9]

9. 二维数组A的每个元素是由6个字符组成的串，其行下标i=0,1,?,8,列下标j=1,2,?,10。若A按行先存储，元素A[8,5]的起始地址与当A按列先存储时的元素（）的起始地址相同。设每个字符占一个字节。

A. A[8,5] B. A[3,10] C. A[5,8] D. A[0,9]

10. 若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B［1..(n(n+1))/2］中，则在B中确定aij（i

A. i*(i-1)/2+j B. j*(j-1)/2+i C. i*(i+1)/2+j D. j*(j+1)/2+i 11. 设A是n*n的对称矩阵，将A的对角线及对角线上方的元素以列为主的次序存放在一维数组B[1..n(n+1)/2]中，对上述任一元素aij(1≤i，j≤n，且i≤j)在B中的位置为( )。

A. i(i-l)/2+j B. j(j-l)/2+i C. j(j-l)/2+i-1 D. i(i-l)/2+j-1 12. A[N，N]是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组T[N（N+1）/2]中，则对任一上三角元素a[i][j]对应T[k]的下标k是（）。

A. i（i-1）/2+j B. j（j-1）/2+i C. i（j-i）/2+1 D. j（i-1）/2+1 13. 设二维数组A[1.. m，1.. n]（即m行n列）按行存储在数组B[1.. m*n]中，则二维数组元素A[i，j]在一维数组B中的下标为( )。

A.（i-1）*n+j B.（i-1）*n+j-1 C. i*（j-1） D. j*m+i-1

14. 有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（）。

A. 60 B. 66 C. 18000 D. 33 15. 数组A[0..4,-1..-3,5..7]中含有元素的个数（）。

A. 55 B. 45 C. 36 D. 16

16. 用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点，使j 沿链移动的操作为( )。

A. j=r[j].next B. j=j+1 C. j=j->next D. j=r[j]-> next 17. 对稀疏矩阵进行压缩存储目的是（）。

A．便于进行矩阵运算 B．便于输入和输出 C．节省存储空间 D．降低运算的时间复杂度

18. 已知广义表L=（（x,y,z），a，（u，t，w）），从L表中取出原子项t的运算是（）。

A. head（tail（tail（L））） B. tail（head（head（tail（L）））） C. head（tail（head（tail（L）））） D. head（tail(head（tail（tail（L）））)） 19. 已知广义表LS＝((a,b,c),(d,e,f)),运用head和tail函数取出LS中原子e的运算是( )。

A. head(tail(LS)) B. tail(head(LS))

C. head(tail(head(tail(LS))) D. head(tail(tail(head(LS)))) 20. 广义表A=(a,b,(c,d),(e,(f,g))),则下面式子的值为（）。

Head(Tail(Head(Tail(Tail(A)))))

A. (g) B. (d) C. c D. d 21. 已知广义表: A=(a,b), B=(A,A), C=(a,(b,A),B), 求下列运算的结果:

tail(head(tail(C))) =( )。

A.（a） B. A C. a D. (b) E. b F. (A) 22. 广义表运算式Tail(((a,b),(c,d)))的操作结果是（）。

A. (c,d) B. c,d C. ((c,d)) D. d 23. 广义表L=（a，（b，c）），进行Tail（L）操作后的结果为（）。【中山大学 1999 一、

10】

A. c B. b，c C.（b，c） D.（（b，c）） 24. 广义表（（a,b,c,d））的表头是（），表尾是（）。

A. a B.（） C.（a,b,c,d） D.（b,c,d） 25. 广义表（a,(b,c),d,e）的表头为（）。

A. a B. a,(b,c) C. (a,(b,c)) D. (a) 26. 设广义表L=（（a,b,c）），则L的长度和深度分别为（）。

A. 1和1 B. 1和3 C. 1和2 D. 2和3 27. 下面说法不正确的是( )。

A. 广义表的表头总是一个广义表 B. 广义表的表尾总是一个广义表 C. 广义表难以用顺序存储结构 D. 广义表可以是一个多层次的结构二、判断题

1. 数组不适合作为任何二叉树的存储结构。（）

2. 从逻辑结构上看，n维数组的每个元素均属于n个向量。（） 3. 稀疏矩阵压缩存储后，必会失去随机存取功能。（） 4. 数组是同类型值的集合。（）

5. 数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。（）

6. 一个稀疏矩阵Am*n采用三元组形式表示，若把三元组中有关行下标与列下标的值互换，并把m和n的值互换，则就完成了Am*n的转置运算。（） 7. 二维以上的数组其实是一种特殊的广义表。（）

8. 广义表的取表尾运算，其结果通常是个表，但有时也可是个单元素值。（） 9. 若一个广义表的表头为空表，则此广义表亦为空表。（）

10. 广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。（） 11. 所谓取广义表的表尾就是返回广义表中最后一个元素。（） 12. 广义表的同级元素（直属于同一个表中的各元素）具有线性关系。（） 13. 对长度为无穷大的广义表，由于存储空间的限制，不能在计算机中实现。（） 14. 一个广义表可以为其它广义表所共享。（）三、填空题

1. 数组的存储结构采用_______存储方式。

2. 设二维数组A[-20..30,-30..20], 每个元素占有4 个存储单元, 存储起始地址为200.如按行优先顺序存储,则元素 A[25,18]的存储地址为__（1）_；如按列优先顺序存储,则元素A[-18,-25]的存储地址为__（2）_。 3. 设数组a[1..50,1..80]的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[45,68]的存储地址为_（1）_;若以列序为主序顺序存储，则元素a[45,68]的存储地址为_（2）_。

4. 将整型数组A[1..8，1..8]按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[7，3]的地址是：_______。

5. 二维数组a[4][5][6]（下标从0开始计，a有4*5*6个元素），每个元素的长度是2，则a[2][3][4]的地址是____。(设a[0][0][0]的地址是1000,数据以行为主方式存储)

6. 设有二维数组A[0..9,0..19],其每个元素占两个字节，第一个元素的存储地址为100，若按列优先顺序存储，则元素A[6,6]存储地址为_______。 7. 已知数组A[0..9,0..9]的每个元素占5个存储单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[6，8]的地址为_______。

8. 已知二维数组A[1..10，0..9]中每个元素占4个单元，在按行优先方式将其存储到起始地址为1000的连续存储区域时，A[5，9]的地址是：_______。

9. 用一维数组B与列优先存放带状矩阵A中的非零元素A[i,j] (1≤i≤n,i-2≤j≤i+2),B中的第8个元素是A 中的第_（1）_行，第_（2）_列的元素。

10. 设数组A[0..8,1..10],数组中任一元素A[i,j]均占内存48个二进制位，从首地址2000开始连续存放在主内存里，主内存字长为16位，那么（l）存放该数组至少需要的单元数是_______;

（2）存放数组的第8列的所有元素至少需要的单元数是_______; （3）数组按列存储时，元素A[5,8]的起始地址是_______。

11．设n行n列的下三角矩阵A已压缩到一维数组B[1..n*（n+1）/2]中，若按行为主序存储，则A[i,j]对应的B中存储位置为_______。

12. n阶对称矩阵a满足a[i][j]=a[j][i],i,j=1..n,，用一维数组t存储时，t的长度为__(1)______，当i=j，a[i][j]=t[(2)],i>j,a[i][j]=t[(3)],i

14. 设有一个10阶对称矩阵A采用压缩存储方式（以行为主序存储：a11=1），则a85 的地址为_______。

15. 所谓稀疏矩阵指的是_______。 16. 对矩阵压缩是为了_______。

17. 上三角矩阵压缩的下标对应关系为：_______。

18. 假设一个15阶的上三角矩阵A按行优先顺序压缩存储在一维数组B中，则非零元素A9,9在B中的存储位置k=_______。（注：矩阵元素下标从1开始）

?a11??a21a22????a31a32a33???..........???an1an2....ann?? 19．设下三角矩阵A=?如果按行序为主序将下三角元素Ai j (i,j)存储在一个一维数组B[ 1..n(n+1)/2]中，对

任一个三角矩阵元素Aij ,它在数组B中的下标为_______。

20. 当广义表中的每个元素都是原子时，广义表便成了_______。 21. 广义表的表尾是指除第一个元素之外，_______。

22. 广义表简称表，是由零个或多个原子或子表组成的有限序列，原子与表的差别仅在于 (1)____。为了区分原子和表，一般用 (2)____表示表，用 (3)_____表示原子。一个表的长度是指 (4)__，而表的深度是指__(5)__

23. 广义表的_______ 定义为广义表中括弧的重数。

24．设广义表L=((),()), 则head(L)是(1)___；tail(L)是(2)____；L的长度是(3)___；深度是 (4)__。

25. 已知广义表A=(9,7,( 8,10,(99)),12)，试用求表头和表尾的操作Head( )和Tail( )将原子元素99从A中取出来。 26. 广义表的深度是_______。

27. 广义表(a,(a,b),d,e,((i,j),k))的长度是（1）_，深度是（2）_。

分）】

28. 已知广义表LS=(a，(b，c，d)，e),运用head和tail函数取出LS中原子b的运算是

_______。

29. 广义表A=（（（a，b），（c，d，e））），取出A中的原子e的操作是: _______。 30. 设某广义表H=（A，（a,b,c）），运用head函数和tail函数求出广义表H中某元素b的运算式_______。

31. 广义表A((( ),(a,(b),c)))，head(tail(head(tail(head(A))))等于。 32. 广义表运算式HEAD(TAIL(((a,b,c),(x,y,z))))的结果是_______。 33. 已知广义表A=（（（a，b），（c），（d，e））），head（tail（tail（head（A））））的结果是_______。

34. 利用广义表的GetHead和GetTail操作，从广义表L=（（apple，pear）（banana，，orange））中分离出原子banana的函数表达式是_______。 35. 已知a数组元素共5个，依次为12，10，5，3，1；b数组元素共4个，依次为4,6,8,15，则执行如下所示的过程语句sort后得到c数组各元素依次为15,12,10,8,6,5,4,3,1；数组a,b,c的长度分别为l=5,m=4,n=9请在程序中方框内填入正确的成分，完成上述要求。 PROCEDURE sort;

VAR i, j, k, x: integer; d: ARRAY[1..m] OF integer; BEGIN

FOR i:=1 TO m DO d[i]:=(1) ; i:=1; j:=1; k:=1;

WHILE (i<=l) AND (j<=m) DO BEGIN

IF a[i]>d[j] THEN BEGIN(2) ; (3) _END

ELSE BEGIN (4)__; (5) __END; c[k]:=x; (6) END;

WHILE(7) _DO

BEGIN c[k]:=a[i]; k:=k+1; i:=i+1；END; WHILE(8) _DO

BEGIN c[k]:=d[j]; k:=k+1; j:=j+1；END; END. {sort}

36. 下列程序段search(a,n,k)在数组a的前n(n>=1)个元素中找出第k(1<=k<=n)小的值。

这里假设数组a中各元素的值都不相同。 #define MAXN 100 int a[MAXN],n,k;

int search_c(int a[], int n, int k) {int low, high, i, j, m, t; k--,;low=0 ;high=n-1;

do {i=low; j=high ; t=a[low];

do{while (i while (i=a[i]) i++ if (i

a[i]=t; if (1) ;

if (i

37. 完善下列程序，每小题在PASCAL语言（a）和C语言（b）中任选一题。下面是一个将广义表逆置的过程。例如原来广义表为（（a,b）,c,（d,e）），经逆置后为：（（e,d）,c,（b,a））。（a）算法的PASCAL语言过程描述（编者略）：（b）算法的C语言过程描述：

typedef struct glistnode {int tag;

struct glistnode *next; union{char data;

struct{struct glistnode *hp,*tp;}ptr; }val; }*glist,gnode; glist reverse(p) glist p;

{glist q,h,t,s; if(p==NULL) q=NULL; else

{if(1) { q=(glist)malloc(sizeof(gnode)); q->tag=0; q->val.data=p->val.data; } else {(2) if (3)

{t=reverse(p->val.ptr.tp); s=t;

while(s->val.ptr.tp!=NULL) s=s->val.ptr.tp; s->val.ptr.tp=(glist)malloc(sizeof(gnode));

s=s->val.ptr.tp;s->tag=1;s->val.ptr.tp=NULL;

s->val.ptr.hp=h; (4) __ }

else {q=(glist)malloc(sizeof(gnode));q->tag=1;

q->val.ptr.tp=NULL; (5) ; }

} }

return(q); }

38. 完善下列程序，每小题在PASCAL语言（a）和C语言（b）中任选一题。下面的程序将数列1,2,3,?,n*n,依次按蛇型方式存放在二维数组A[1..n,1..n]中。即 (示意圖编者略)。（a）算法的PASCAL 语言程序描述（编者略）：（b）算法的C语言程序描述： #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”); } } }

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;

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) _ , _

四应用题

1. 数组A[1..8，-2..6，0..6]以行为主序存储，设第一个元素的首地址是78，每个元素的长度为4，试求元素A[4,2,3]的存储首地址。

2. 已知b对角矩阵（aij）n*n，以行主序将b条对角线上的非零元存储在一维数组中，每个数据元素占Ｌ个存储单元，存储基地址为Ｓ，请用i，j 表示出 aij的存储位置。 3. 数组A中，每个元素A[i,j]的长度均为32个二进位,行下标从-1到9，列下标从1到11，从首地址S开始连续存放主存储器中，主存储器字长为16位。求：

（1）存放该数组所需多少单元？

（2）存放数组第4列所有元素至少需多少单元？

（3）数组按行存放时，元素A[7,4]的起始地址是多少？（4）数组按列存放时，元素A[4,7]的起始地址是多少？

4．假设按低下标优先存储整型数组A（-3:8,3:5,-4:0,0:7）时，第一个元素的字节存储地址是100，每个整数占4个字节，问A（0，4，-2，5）的存储地址是什么？

5．设有三维数组A[-2:4,0:3,-5:1]按列序存放，数组的起始地址为1210，试求A(1,3,-2）

所在的地址。

6. 三维数组A[1..10,-2..6,2..8]的每个元素的长度为4个字节，试问该数组要占多少个字节的存储空间？如果数组元素以行优先的顺序存贮，设第一个元素的首地址是100，试求元素A[5,0,7] 的存贮首地址。

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按列优先方式存储时的哪个元素的起始地址一致？

9. 若按照压缩存储的思想将n×n阶的对称矩阵A的下三角部分（包括主对角线元素）以行序为主序方式存放于一维数组B[1..n(n+1)/2]中，那么，A中任一个下三角元素aij(i≥j),在数组B中的下标位置k是什么？

10. 设m×n阶稀疏矩阵A有t个非零元素，其三元组表表示为LTMA[1..（t+1）,1..3]，试问：非零元素的个数t达到什么程度时用LTMA表示A才有意义？ 11. 利用三元组存储任意稀疏数组时，在什么条件下才能节省存储空间。

12. 对一个有t个非零元素的Amn 矩阵, 用B[0..t][1..3]的数组来表示，其中第0行的三个元素分别为m,n,t, 从第一行开始到最后一行，每行表示一个非零元素；第一列为矩阵元素的行号，第二列为其列号，第三列为其值。对这样的表示法，如果需要经常进行该操作---确定任意一个元素A[i][j]在B中的位置并修改其值，应如何设计算法可以使时间得到改善？

13. 有一个二维数组A[0:8,1:5],每个数组元素用相邻的4个字节存储,存储器按字节编址,假设存储数组元素A[0,1]的第一个字节的地址是0,那么存储数组的最后一个元素的第一个字节的地址是多少?若按行存储,则A[3,5]和A[5,3]的第一个字节的地址是多少?若按列存储,则A[7,1]和A[2,4]的第一个字节的地址是多少?

14. 设有三对角矩阵(ai,j)m╳n,将其三条对角线上的元素逐行的存于数组B(1:3n-2)中，使得B[k]=ai,j，求：

（1）用i,j表示k的下标变换公式；

（2）若n=10,每个元素占用L个单元，则用B[K]方式比常规存储节省多少单元。

15. 已知A为稀疏矩阵，试从空间和时间角度，比较采用两种不同的存储结构（二维数组和

三元组表）完成求

?aiii?1n运算的优缺点。

16. 特殊矩阵和稀疏矩阵哪一种压缩存储后失去随机存取的功能？为什么？ 17. 试叙述一维数组与有序表的异同。

18. 一个n╳n的对称矩阵，如果以行或列为主序存入内存，则其容量为多少？ 19. 给出数组 A∶ARRAY[3..8,2..6] OF INTEGER;当它在内存中按行存放和按列存放时，分别写出数组元素A[i,j]地址计算公式（设每个元素占两个存储单元）。 20. 已知n阶下三角矩阵A（即当i

21. 设有三对角矩阵(aij)n*n，将其三条对角线上的元素逐行地存于数组B(1:3n-2)中，使

得B[k]=aij，求：（1）用i,j表示k的下标变换公式；（2）用k表示i,j的下标变化公式。

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；

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); ]

]

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};

?213??331????121??执行下列语句后，矩阵ｃ和ａ的结果分别是什么？ 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]]

?213??331????121?? 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）中所得结果作比较。

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}

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)时，算法的时间复杂度是多少？

29．上三角阵A（N*N）按行主序压缩存放在数组B中，其中A[i,j]=B[k].写出用i，j表示

的k。

30. 设有上三角矩阵(aij)n*n，将其上三角中的元素按先行后列的顺序存于数组B（1:m）中，使得B[k]= aij且k=f1(i)+f2(j)+c，请推导出函数f1,f2和常数c，要求f1和f2中不含常数项。

?2?0??0?31．设矩阵A=?4003003004?0??0??0?

(1) 若将A视为对称矩阵，画出对其压缩存储的存储表，并讨论如何存取A中元素aij (0<=i,j<4)；

(2) 若将A视为稀疏矩阵，画出A的十字链表结构。

?1?0??0?32. 设对称矩阵A=?21 0 030000050 2?0??5??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视为稀疏矩阵时,画出其三元组表形式压缩存储表。

??12000??10100???02100???00001??33. 设对角线矩阵A=??00035??（行列下标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视为稀疏距阵时，请画出其行逻辑链接顺序表。

34．设有一个三维数组a[c1:d1,c2:d2,c3:d3]，其中ci:di是第i维的界偶，如该数组在内存中按行排列，且a[c1,c2,c3]的地址为a0，那么请导出下标变量a[i1,i2,i3]的地址，假设每个元素占L个单元。

35．假定有下列nⅹn矩阵（n为奇数）

??a110.........0a1n??0a22.........a2,n?10???..................????0......an?12,n?1...0??.......20..??????A=??an100ann???

如果用一维数组B按行主次序存储A的非零元素，问：（1）A中非零元素的行下标与列下标的关系；

（2）给出A中非零元素aij 的下标(i,j)与B中的下标R的关系; （3）假定矩阵中每个元素占一个存贮单元且B的起始地址为A0，给出利用aij的下标(i,j)定位在B中的位置公式。

36. 对于一个对称矩阵采用压缩存储，只存放它的上三角部分， ?A11A并按列存放。例如对于一个n*n的对称矩阵A (如右图) ，用一 ?12A13??A个一维数组B来存放它的上三角部分：

?22A23B=[A?A33...11，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）则不给分） ???37. 用三元数组表示稀疏矩阵的转置矩阵,并简要写出解题步骤。 38. 简述广义表属于线性结构的理由。

39. 数组，广义表与线性表之间有什么样的关系？

40. 什么是广义表？请简述广义表和线性表的主要区别。 41. 求下列广义表的运算结果。

（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)))))

?A1n??A?2n...A?3n?......??......?A?nn????（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））。类似本题的另外叙述有：

(1) 已知广义表L=((((a))),((b)),(c),d)，试利用head和tail运算把原子项c从L中分离出来。

(2) 画出下列广义表的存储结构图，并利用取表头和取表尾的操作分离出原子e。

（ a,（（）,ｂ）,（（（ｅ））））。

(3) 已知广义表A=((a,b,c),(d,e,f)) 试写出从表A中取出原子元素e的运算。 (4)请将香蕉banana用工具 H( )—Head( )，T( )—Tail( )从L中取出。

L=(apple,(orange,(strawberry,(banana)),peach),pear)

(5) 试利用广义表取表头head(ls)和取表尾tail(ls)的基本运算，将原子d从下列表中分解出来，请写出每一步的运算结果。

L=((a,(b)),((c,d)),(e,f))

(6) 画出广义表A=（a,（b,()）,(((),c))）的第一种存储结构（表结点第二指针指向余表）图，并用取首元（head()）和取尾元（tail()）函数表示原子c。 43. 画出下列广义表的两种存储结构图((),A,(B,(C,D)),(E,F))。 44. 假设采用以下两种结点的链表作为广义表的存贮结构，表结点：(tag=1,hp,tp), 元素结点；(tag=0,data)。请画出下列广义表的存储结构图，并求它的深度和长度。 ( ( ) , ( ( ( ) ) , ( ( ( ) ) ) ) ) 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,()）的存贮表示。 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; t:=q; END.

（2）对于 p所指的广义表,画出执行算法A后的表结构以及p，t的值:

0a10d0e?

0b0c?

类似本题的另外叙述有：题目基本相同，差别仅在于子表(b,c)与原子d的前后顺序颠倒。【浙江大学 1994 六 (7分)】

48. 写出对广义表A=(x,((a,b),c,d))作运算head(head(tail(A)))后的结果。 49．写出广义表的运算结果: TAIL[HEAD[TAIL[((a,b),(c,d))]]]=? 50. 广义表中原子个数是否即为广义表的长度？

51. 给出下列所示的3元多项式的广义表表示（分别以X1，X2，X3第一到第三层变元）

5352453342

P（X1X2X3）=X1X2X3+2X1X2X3+5X1X2X3+3X1X2X3+X2X3+6 52. 设某表H如下：

A a1 B a2 b1 C c1 X c2 其中A,B,C为子表名，a1,a2,b1,c1,c2,x为其元素。

（1）试用广义表形式表示H,并写出运算HEAD(H)和TAIL(H) 函数从H中取出单元素a2的

运算；

（2）画出表H的链式存储结构；

五算法设计题

1. 设有大小不等的n 个数据组（n个数据组中数据的总数为m），顺序存放在空间区D内,每个数据占一个存储单元，数据组的首地址由数组S给出，（如下图所示），试编写将新数据x插入到第i个数据组的末尾且属于第i 个数据组的算法，插入后，空间区D和数组S的相互关系仍保持正确。

2. 以三元组表存贮的稀疏矩阵A，B非零元个数分别为m和n。试用类PASCAL语言编写时间复杂度为O（m+n）的算法将矩阵B加到矩阵A上去。A的空间足够大，不另加辅助空间。要求描述所用结构。

3. 设整数x1,x2,?,xN已存放在数组A中，编写一PASCAL递归过程，输出从这n个数中取出所有k 个数的所有组合（k<=n）。例：若A中存放的数是1，2，3，4，5，k为3，则输出结果应为：543，542，541，532，531，521，432，431，421，321。类似本题的另外叙述有：

（1）题目基本相同，只是叙述不同，要求用PASCAL语言。【东南大学 2001 三（10分）】 4．编写一个过程，对一个n×n矩阵，通过行变换，使其每行元素的平均值按递增顺序排列。 5. 设原来将N个自然数1,2,?,N按某个顺序存于数组A中，经过下面的语句计算，使A[I]的值变为A[1]到A[I-1]中小于原A[I]值的个数。

FOR I:=N DOWNTO 1 DO BEGIN C：=0；

FOR J：=1 TO I-1 DO

IF A[J]

编程将经过上述处理后的A还原成原来的A。

6．请编写完整的程序。如果矩阵A中存在这样的一个元素A[i,j]满足条件:A[i,j]是第i行中值最小的元素,且又是第j列中值最大的元素，则称之为该矩阵的一个马鞍点。请编程计算出m*n的矩阵A的所有马鞍点。 7．给定一个整数数组b[0..N-1]，b中连续的相等元素构成的子序列称为平台。试设计算法，求出b中最长平台的长度。

8. 给定nxm矩阵A[a..b,c..d],并设A[i,j]≤A[i,j+1](a≤i≤b,c≤j≤d-1)和A[i,j]≤A[i+1,j](a≤i≤b-1,c≤j≤d).设计一算法判定X的值是否在A中,要求时间复杂度为O(m+n)。

类似本题的另外叙述有：

（1）给定整型数组B[0..m,0..n] 。已知B中数据在每一维方向上都按从小到大的次序排列，且整型变量x在B中存在。试设计一个程序段找出一对满足B[i,j]=x的(i,j)值，要求比较次数不超过m+n.。

(2) 给定n×m矩阵A[a..b,c..d]，并设A[i,j]<=A[i,j+1]（a<=i<=b,c<=j<=d-1）知A[i,j]<=A[i+1,j],(a<=i<=b-1, c<=j<=d)。设计一算法以比O(n*m)小的最坏时间复杂性判定值x是否在A中。

9. 编写算法，将自然数1～n按“蛇形”填入n×n矩阵中。例（1～4）如图所示：（用程序实现） 13410 25911

681215

7131416

10. 设二维数组a[1..m, 1..n] 含有m*n 个整数。

(1) 写出算法(pascal过程或c函数)：判断a中所有元素是否互不相同?输出相关信息(yes/no)；

(2) 试分析算法的时间复杂度。

11. 二项式(a+b)展开式的系数为

C（n，0）=1，C（n，n）=1，对于n>=0

C（n，k）=C（n-1，k）+C（n-1，k-1），对于0

(1)试写一个递归算法，根据以上公式生成C（n,k）。（6分） (2)试画出计算C（6，4）的递归树。（4分）

(3)试写一个非递归算法，既不用数组也不用栈，对于任意的0<=k<=n计算C(n,k)（6分）

1 n=0n=111 211n=23311n=3

64114n=4 15101051n=51615201561n=6

172135352171n=7 n=818285670562881 12．设任意n个整数存放于数组A(1:n)中，试编写程序，将所有正数排在所有负数前面（要求算法复杂性为0( n)）。. 类似本题的另外叙述有：

（1）已知数组A[1..n]的元素类型为整型，设计算法调整A，使其左边的所有元素小于零，右边的所有元素大于等于零。（要求算法的时间复杂度和空间复杂度均为0（n））（2）设计一个算法，把整数数组中所有的偶数放到所有的奇数之前。要求时间、空间效率尽可能高。

（3）设一系列正整数存放在一个数组中，试设计算法，将所有奇数存放在数组的前半部分，将所有的偶数存放在数组的后半部分。要求尽可能少用临时存储单元并使时间最少。请试着分析你实现的算法的时间复杂度和空间复杂度。

（4）设计算法将数组A[1..n]调整为左右两部分，使的左边所有的元素小于右边的所有元素，并给出这一划分的分界位置。要求算法的时间复度为O(n)。

13.若S是n个元素的集合，则S的幂集P(S)定义为S所有子集的集合。例如， S=(a,b,c),P(S)={() ,(a),(b),(c),(a,b),(a,c),(b,c),(a,b,c)}给定S，写一递归算法求P(S)。

14．编写算法打印出由指针Hm指向总表头的以十字链表形式存储的稀疏矩阵中每一行的非

零元的个数。注意：行、列及总表头结点的形式为：

row down col val right 它们已用val域链接成循环链表。非零元的结点形式也同上，每一行（列）的非零元由right（down）域把它们链接成循环链表，该行（列）的表头结点即为该行（列）循环链表的表头。 15. 试编写建立广义表存储结构的算法，要求在输入广义表的同时实现判断、建立。设广义表按如下形式输入（a1,a2,a3,?,an） n>=0，其中ai或为单字母表示的原子或为广义表，n=0时为只含空格字符的空表。(注:算法可用类pascal 或类c书写)

16. 广义表是n(n>=0)个数据元素a1,a2,a3,?,an的有限序列。其中ai (1<=i<=n)或者是单个数据元素（原子），或仍然是一个广义表。广义表的结点具有不同的结构，即原子结点和

子表元素结点，为了将两者统一，用了一个标志tag，当其为0时表示是原子结点，其data域存储结点值，link域指向下一个结点，当其tag为1时表示是子表结点，其sublist为指向子表的指针。因此，广义表可采用如下结构存储：

TYPE glist=^gnode; gnode=RECORD

link:glist;

CASE tag:0..1 OF

0:(data:char); 1:(sublist:glist) END;

（1）画出广义表((a,b),c)的存储结构；

（2）写出计算一个广义表的原子结点个数的递归算法表示式；（3）编写实现上述算法的过程或函数程序。

17. 广义表GL=(a1,a2 ,?,an),其中 ak(k=1,2,...,n)或是单个数据元素（原子），或仍然是个广义表。给定如下有关广义表的类型定义：

TYPE tagtype=0..1; glist=^gnode;

gnode=RECORD

link:glist; {link 域指向下一个结点}

CASE tag:tagtype OF ｛tag=0 表示原子结点｝ 0: (data :integer);

1:(sublist: glist)

END;

编写一个过程或函数计算一个广义表的所有原子结点数据域之和，例如对广义表(3,(2,4,5),(6,3）) 数据域之和为23。

18. 数组 H[ 1：1000] 中存放着1000个大小不同的正整数;

（1）选择一分类算法使能最快地得到其中10个最大的数，简要说明理由；（2）编写一程序seek() ，执行该程序时，在命令行中提供二个参数； seek a n 表示需打印H[ ]中n个最大数。

seek I n 表示需打印H[ ]中n个最小数。

19．已知两个定长数组，它们分别存放两个非降序有序序列，请编写程序把第二个数组序列中的数逐个插入到前一个数组序列中，完成后两个数组中的数分别有序（非降序）并且第一数组中所有的数都不大于第二个数组中的任意一个数。注意，不能另开辟数组，也不能对任意一个数组进行排序操作。例如，

第一个数组为：4,12,28 第二个数组为：1,7,9,29,45

输出结果为：1,4,7--------------第一个数组

9,12,28,29,45---------第二个数组

20. 设数组A[1..n]中，A[n-2k+1..n-k]和[n-k+1..n]中元素各自从小到大排好序，试设计一个算法使A[n-2k+1..n]按从小到大次序排好序。并分析算法所需的计算时间。

21. 设A[1..100]是一个记录构成的数组，B[1..100]是一个整数数组，其值介于1至100之间，现要求按B[1..100]的内容调整A中记录的次序，比如当B[1]=ll时，则要求将A[1]的内容调整到A[11]中去。规定可使用的附加空间为O(1)。2

22. 给定有m个整数的递增有序数组a[1..m]和有n个整数的递减有序数组b[1..n]，试写

出算法:将数组a和b归并为递增有序数组c[l..m+n]。(要求：算法的时间复杂度为O(m+n)) 23．在数组 A[1..n]中有n个数据，试建立一个带有头结点的循环链表，头指针为h，要求链中数据从小到大排列，重复的数据在链中只保存一个。

第五章数组和广义表

一、选择题 1.B 2.1L 2.2J 2.3C 2.4I 2.5C 3.B 8.1E 8.2A 8.3B 9.B 4.B 5.A 6.1H 6.2C 6.3E 6.4A 6.5F 7.B 27.A 10.B 11.B 12.B 13.A 14.B 15.B 16.A 17.C 18.D 19.C 20.D 21.F 22.C 23.D 24.C 25.A 26.C 二、判断题 1. × 2.√ 3.√ 4.× 5.× 6. × 7.√ 8.× 9.× 10.× 11.× 12.√ 13.√ 14.√ 部分答案解释如下。

1. 错误。对于完全二叉树，用一维数组作存储结构是效率高的（存储密度大）。

4. 错误。数组是具有相同性质的数据元素的集合，数据元素不仅有值，还有下标。因此，可以说数祖是元素值和下标构成的偶对的有穷集合。

5. 错误。数组在维数和界偶确定后，其元素个数已经确定，不能进行插入和删除运算。 6. 错误。稀疏矩阵转置后，除行列下标及行列数互换外，还必须确定该元素转置后在新三元组中的位置。

8. 错误。广义表的取表尾运算，是非空广义表除去表头元素，剩余元素组成的表，不可能是原子。

9. 错误。广义表的表头就是广义表的第一个元素。只有非空广义表才能取表头。 10. 错误。广义表中元素可以是原子，也可以是表（包括空表和非空表）。 11. 错误。广义表的表尾，指去掉表头元素后，剩余元素所组成的表。

三、填空题

1. 顺序存储结构 2.（1）9572（2）1228 3.（1）9174（2）8788 4. 1100 5. 1164 公式：LOC(aijk)=LOC(a000)+[v2*v3*(i-c1)+v3*(j-c2)+(k-c3)]*l (l为每个元素所占单元数)

6. 232 7. 1340 8. 1196 9. 第1行第3列 10. (1)270 (2)27 (3)2204 11. i(i-1)/2+j (1<=i,j<=n)

12. (1)n(n+1)/2 (2)i(i+1)/2 (或j(j+1)/2) (3)i(i-1)/2+j (4)j(j-1)/2+i (1<=i,j<=n) 13. 1038 三对角矩阵按行存储：k=2(i-1)+j (1<=i,j<=n) 14. 33 (k=i(i-1)/2+j) (1<=i,j<=n)

15. 非零元很少(t<

17. 上三角矩阵中，主对角线上第r(1?r?n) 行有n-r+1个元素，aij所在行的元素数是j-i+1。所以，元素在一维数组的下标k和二维数组下标关系:k=((i-1)*(2n-i+2))/2+(j-i+1)=(i-1)(2n-i)/2+j (i?j) 18. 93 19. i(i-1)/2+j 20. 线性表 21. 其余元素组成的表

22. （1）原子（单元素）是结构上不可再分的，可以是一个数或一个结构；而表带结构，本质就是广义表，因作为广义表的元素故称为子表。

（2）大写字母（3）小写字母（4）表中元素的个数（5）表展开后所含括号的层数

23. 深度 24.（1）（）（2）（（））（3）2 （4）2 25. head（head（tail（tail（head（tail（tail（A））））））） 26. 表展开后所含括号的层数 27.（1）5 （2）3

28. head(head(tail(LS))) 29. head(tail(tail(head(tail(head(A)))))) 30. head(tail(head(tail(H)))) 31. (b) 32. (x,y,z) 33. (d,e) 34. GetHead(GetHead(GetTail(L))) 35. 本算法中，首先数组b中元素以逆置顺序放入d数组中，然后数组a和数组d的元素比较，将大者拷贝到数组c。第一个WHILE循环到数组a或数组d结尾，第二个和第三个WHILE语句只能执行其中的一个。

（1）b[m-i+1]（2）x:=a[i]（3）i:=i+1（4）x:=d[j]（5）j:=j+1 （6）k:=k+1（7）i<=l（8）j<=m

36.（1）(i==k) return（2）i+1（3）i-1（4）i!=k

本算法利用快速排序思想，找到第k个元素的位置（下标k-1因而开初有k--）。内层do循环以t(t=a[low])为“枢轴”找到其应在i位置。这时若i等于k，则算法结束。（即第一个空格处if(i==k) return)。否则，若ik，则在low到i-1间去找，直到找到i=k为止。 37.逆置广义表的递归模型如下

?null 若LS为空?若LS为原子，且tail(LS)为空?LS ?ail(LS)),head(LS)) 若LS-?tag?0，且LS-?val.ptr.tp!?null)?append(f(t?append(f(tail(LS)),f(head(LS))) 若LS-?tag?1f(LS)=?

上面appEND(a,b)功能是将广义表a和b作为元素的广义表连接起来。（1）(p->tag==0) //处理原子（2）h=reverse(p->val.ptr.hp) //处理表头

（3）(p->val.ptr.tp) //产生表尾的逆置广义表（4）s->val.ptr.tp=t; //连接

（5）q->val.ptr.hp=h //头结点指向广义表

38. 本题要求将1，2，...,n*n个自然数，按蛇型方式存放在二位数组A[n][n]中。“蛇型”

方式，即是按“副对角线”平行的各对角线，从左下到右上，再从右上到左下，存放n个整数。对角线共2n-1条，在副对角线上方的对角线，题目中用k表示第k条对角线（最左上角k=1），数组元素x和y方向坐标之和为k+1（即题目中的i+j=k+1）。副对角线下方第k条对角线与第2n-k条对角线对称，其元素的下标等于其对称元素的相应坐标各加(k-n)。（1）k<=2*n-1 //共填2*n-1条对角线

（2）q=2*n-k //副对角线以下的各条对角线上的元素数（3）k%2！=0 //k为偶数时从右上到左下，否则从左下向右上填数。（本处计算下标i和j）（4）k>=n //修改副对角线下方的下标i和j。

（5）m++；或m=m+1 //为填下个数作准备，m变化范围1..n*n。本题解法的另一种思路见本章算法设计题第9题。 39.本题难点有二：一是如何求下一出圈人的位置，二是某人出圈后对该人的位置如何处理。

按题中要求，从第s个人开始报数，报到第m个人，此人出圈。n个人围成一圈，可看作环状，则下个出圈人，其位置是(s+m-1)%n。n是人数，是个变量，出圈一人减1，算法中

用i表示。对第二个问题，算法中用出圈人后面人的位置依次前移，并把出圈人的位置（下标）存放到当时最后一个人的位置（下标）。算法最后打印出圈人的顺序。（1）(s+m-1) MOD i //计算出圈人s1

（2）s1:=i //若s1=0,说明是第i个人出圈（i%i=0）

（3）s1 TO i-1 //从s1到i依次前移，使人数减1，并将出圈人放到当前最后一个位置A[i]=w。

40. 若第n件物品能放入背包，则问题变为能否再从n-1件物品中选出若干件放入背包（这时背包可放入物品的重量变为s-w[n]）。若第n件物品不能放入背包，则考虑从n-1件物品选若干件放入背包（这时背包可放入物品仍为s）。若最终s=0,则有一解；否则，若s<0或虽然s>0但物品数n<1,则无解。

（1）s-w[n],n-1 //Knap(s-w[n],n-1)=true （2）s,n-1 // Knap←Knap(s,n-1)

四、应用题

1、958 三维数组以行为主序存储，其元素地址公式为：

LOC(Aijk)=LOC(Ac1c2c3)+[(i-c1)V2V3+(j-c2)V3+(k-c3)]*L+1

其中ci,di是各维的下界和上界，Vi=di-ci+1是各维元素个数，L是一个元素所占的存储单元数。

2. b对角矩阵的b条对角线，在主对角线上方和下方各有?b/2?条对角线(为叙述方便，下面设a=?b/2?)。从第1行至第a行，每行上的元素数依次是a+1,a+2,...,b-2,b-1,最后的a行上的元素个数是 b-1，b-2,...,a+1。中间的(n-2a )行，每行元素个数都是b。故b条对角线上元素个数为 (n-2a)b+a*(a+b)。存放在一维数组V[1..nb-a(b-a)]中，其下标k与元素在二维数组中下标i和j的关系为：

（i?1)(i?2a)??j当1??i??a?1?2??a(2i?a)?j当a?1?i??n?a?1?(i?n?a)(i?n?a?1)?a(2i?a)??j当n?a?1?i??n2 k=?

3．每个元素32个二进制位，主存字长16位，故每个元素占2个字长，行下标可平移至1

到11。

（1）242 （2）22 （3）s+182 （4）s+142

4．1784 (公式：Loc(Aijkl)=100(基地址)+[(i-c1)v2v3v4+(j-c2)v3v4+(k-c3)v4+(l-c4)]*4 5. 1210+108L (LOC(A[1,3,-2])=1210+[(k-c3)v2v1+(j-c2)v1+(i-c1)]*L（设每个元素占L个存储单元）

6. 数组占的存储字节数=10*9*7*4=2520；A[5,0,7]的存储地址=100+[4*9*7+2*7+5]*4=1184 7. 五对角矩阵按行存储，元素在一维数组中下标（从1开始）k与i,j的关系如下:

?4(i?1)?j(当i?1时)??4(i?1)?j?1(当1?i?n时)?4(i?1)?j?2(当i?n时)?

A[15,16]是第71个元素，在向量[-10:m]中的存储位置是60 。 8．（1）540 （2）108 （3）i=3,j=10，即A[3,10] 9． k=i(i-1)/2+j 10. 稀疏矩阵A有t个非零元素，加上行数mu、列数nu和非零元素个数tu(也算一个三元

组)，共占用三元组表LTMA的3(t+1)个存储单元，用二维数组存储时占用m*n个单元，只有当3(t+1)

12. 题中矩阵非零元素用三元组表存储，查找某非零元素时，按常规要从第一个元素开始查找，属于顺序查找，时间复杂度为O(n)。若使查找时间得到改善，可以建立索引，将各行行号及各行第一个非零元素在数组B中的位置（下标）偶对放入一向量C中。若查找非零元素，可先在数组C中用折半查找到该非零元素的行号，并取出该行第一个非零元素在B中的位置，再到B中顺序（或折半）查找该元素，这时时间复杂度为O(logn)。 13．（1）176 （2）76和108 （3）28和116。 14．（1）k = 3(i-1) (主对角线左下角，即i=j+1)

k = 3(i-1)+1 (主对角线上，即i=j) k = 3(i-1)+2 (主对角线上，即i=j-1)

由以上三式，得 k=2(i-1)+j (1?i,j?n; 1?k?3n-2)

333

（2）10*10-(3*10-2)

15. 稀疏矩阵A采用二维数组存储时，需要n*n个存储单元，完成求Σaii(1<=i<=n)时，由于a[i][i]随机存取，速度快。但采用三元组表时，若非零元素个数为t，需3(t+1)个存储单元（第一个分量中存稀疏矩阵A的行数，列数和非零元素个数，以后t个分量存各非零元素的行值、列值、元素值），比二维数组节省存储单元；但在求Σaii(1<=i<=n)时，要扫描整个三元组表，以便找到行列值相等的非零元素求和，其时间性能比采用二维数组时差。 16. 特殊矩阵指值相同的元素或零元素在矩阵中的分布有一定规律，因此可以对非零元素分配单元（对值相同元素只分配一个单元），将非零元素存储在向量中，元素的下标i和j和该元素在向量中的下标有一定规律，可以用简单公式表示，仍具有随机存取功能。而稀疏矩阵是指非零元素和矩阵容量相比很小（t<

17．一维数组属于特殊的顺序表，和有序表的差别主要在于有序表中元素按值排序（非递增或非递减），而一维数组中元素没有按元素值排列顺序的要求。

18．n(n+1)/2（压缩存储）或n（不采用压缩存储）

19．LOC（A[i,j]）=LOC（A[3，2]）+[（i-3）*5+（j-2）]×2 （按行存放） LOC（A[i,j]）=LOC（A[3，2]）+[（j-2）*6+（i-3）]×2 （按列存放） 20．n阶下三角矩阵元素A[i][j]（1<=i,j<=n,i>=j）。第1列有n个元素，第j列有n-j+1个元素，第1列到第j-1列是等腰梯形，元素数为(n+(n-j+2)(j-1)/2，而aij在第j列上的位置是为i-j+1。所以n阶下三角矩阵A按列存储，其元素aij在一维数组B中的存储位置k与i和j的关系为：

k=(n+(n-(j-1)+1)(j-1)/2+(i-j+1)=(2n-j)(j-1)/2+i

21．三对角矩阵第一行和最后一行各有两个非零元素，其余每行均有三个非零元素，所以共有3n-2个元素。（1）主对角线左下对角线上的元素下标间有i=j+1关系，k与i和j的关系为k=3(i-1);主对角线上元素下标间有关系i=j，k与i和j的关系为k=3(i-1)+1; 主对角线右上那条对角线上元素下标间有关系i=j-1，k与i和j的关系为k=3(i-1)+2。综合以上三等式，有k=2(i-1)+j (1<=i,j<=n, |i-j|<=1) （2）i=k/3+1；（1≤k≤3n-2） // k/3取小于k/3的最大整数。下同

j=k-2(i-1)=k-2(k/3)=k%3+k/3

22．这是一个递归调用问题，运行结果为：DBHEAIFJCKGL

23.（1）FOR循环中，每次执行PerfectShuffle(A,N)和CompareExchange(A,N)的结果：

第1次：A[1..8]=[90,30,85,65,50,80,10,100] A[1..8]=[30,90,65,85,50,80,10,100] 第2次：A[1..8]=[30,50,90,80,65,10,85,100] A[1..8]=[30,50,80,90,10,65,85,100] 第3次：A[1..8]=[30,10,50,65,80,85,90,100] A[1..8]=[10,30,50,65,80,85,90,100] （2）Demo的功能是将数组A中元素按递增顺序排序。

（3）PerfectShuffle 中WHILE循环内是赋值语句，共2N次，WHILE外成组赋值语句，相当2N个简单赋值语句；CompareExchange中WHILE循环内是交换语句，最好情况下不发生交换，最差情况下发生N次交换，相当于3N个赋值语句；Demo中FOR循环循环次数log22N，故按赋值语句次数计算Demo的时间复杂度为：最好情况：O(4N*log22N)≈O(Nlog(2*N))；最差情况：O((4N+3N)*log22N)≈O(Nlog(2*N))。

24. 这是一个排序程序。运行后B数组存放A数组各数在排序后的位置。结果是： A={121,22,323,212,636,939,828,424,55,262} B={3,1,6,4,8,10,9,7,2,5}

C={22,55,121,212,262,323,424,639,828,939}

?331??111????332?? 25.（1）c=??331??113????333?? （2）a=?26.（1）同上面26题（1）

（2）对c数组的赋值同所选择的下标i和j的次序（指外层循环用j内层用i）没有关系

（3）同上题26（2）

（4）对i,j下标取反序后，重复执行第（3）步，A数组所有元素均变为2。（在机器上验证，反复循环3次后，所有元素均变为2） 27．错误有以下几处：

（1）过程参数没有类型说明；（2）出错条件判断：缺少OR（i+k>last+1）；（3）删除元素时FOR循环应正向，不应用反向DOWNTO；（4）count没定义；

低效体现在两处：

（1）删除k个元素时，不必一个一个元素前移，而应一次前移k个位置；（2）last指针不应一次减1，而应最后一次减k。正确的高效算法如下： const m=64；

TYPE ARR=ARRAY[1..m] OF integer；

PROCEDURE delk（VAR A:ARR；VAR last:integer;i,k：integer）； {从数组A[1..last]中删除第i个元素起的k个元素，m为A的上限} VAR count：integer； BEGIN

IF（i<0）OR（i>last）OR（k<0）OR（last>m）OR（i+k>last+1）

THEN write（’error’）

ELSE[FOR count：= i+k TO last DO A[count-k]：=A[count]；

last：=last-k；]

END；

28. 这是计数排序程序。

（a）c[i](1<=i<=n)中存放A数组中值为i的元素个数。（b）c[i](1<=i<=n)中存放A数组中小于等于i的个数。（c）B中存放排序结果，B[1..n]已经有序。

（d）算法中有4个并列for循环语句，算法的时间复杂度为O(n)。

29．上三角矩阵第一行有n个元素，第i-1行有n-（i-1）+1个元素，第一行到第i-1行是等腰梯形，而第i行上第j个元素（即aij）是第i行上第j-i+1个元素，故元素Aij在一维数组中的存储位置（下标k）为：

k=(n+(n-(i-1)+1))(i-1)/2+(j-i+1)=(2n-i+2)(i-1)/2+j-i+1 30．将上面29题的等式进一步整理为：

k=（n+1/2）i-i/2+j-n，

则得f1（i）=（n+1/2）i-i/2，f2（j）=j，c=-n。

31.（1）将对称矩阵对角线及以下元素按行序存入一维数组中，结果如下：

（2）因行列表头的“行列域”值用了0和0，下面十字链表中行和列下标均从1开始。

注：上侧列表头Hi和左侧行表头Hi是一个（即H1、H2、H3和H4），为了清楚，画成了两个。

32.（1）k=(2n-j+2)(j-1)/2+i-j+1 （当i≥j时，本题n=4） k=(2n-i+2)(i-1)/2+j-i+1 （当i

i=floor（k/3）+1 // floor（a）是取小于等于a的最大整数

j=k-2（i-1）

推导过程见上面第25题。

（2）行逻辑链接顺序表是稀梳矩阵压缩存储的一种形式。为了随机存取任意一行的非零元，需要知道每一行第一个非零元在三元组表中的位置。为此，除非零元的三元组表外，还需要一个向量，其元素值是每行第一个非零元在三元组表中的位置。其类型定义如下： typedef struct

{ int mu,nu,tu; //稀梳矩阵的行数、列数和非零元素个数 int rpos[maxrow+1]; //行向量，其元素值是每行第一个非零元在三元组表中的位置。

Triple data[maxsize]; }SparsMatrix;

因篇幅所限，不再画出行逻辑链接顺序表。

34．各维的元素数为di-ci+1，则a[i1，i2，i3]的地址为：

a0+[（i1-c1）（d3- c3+1）（d2- c2+1）+（i2-c2）（d2- c2+1）+（i3-c3）]*L

35．主对角线上元素的坐标是i=j，副对角线上元素的坐标i和j有i+j=n+1的关系（1）i=j或i=n+1-j （1≤i，j≤n）

（2）非零元素分布在两条主、副对角线上，除对角线相交处一个元素（下称“中心元素”）外，其余每行都有两个元素。主对角线上的元素，在向量B中存储的下标是k=2i-1(i=j, 1≤i，j≤n，1<=k<=2n-1)。

副对角线上的元素，在中心元素前，在向量B中存储的下标是k=2i(i<>j, 1≤i，j≤n/2)；在中心元素后，其下标是k=2(i-1)(i<>j，n/2+1≤i，j≤n, 1<=k<=2n-1)。

（3）aij在B中的位置K=

?A0?2(i-1) (i?j ,1??i,j??n)??A0?2(i-1)?1 (i??j, 1??i,j??n/2)?A0?2(i-1)-1 (i??j,n/2?1?i,j??n)?

36. 由于对称矩阵采用压缩存储，上三角矩阵第一列一个元素，第二列两个元素，第j列j个元素。上三角矩阵共有n (n+1)/2个元素。我们将这些元素存储到一个向量B[n(n+1)/2+1]中。可以看到B[k]和矩阵中的元素aij之间存在着一一对应关系：

?j(j?1)?2?ik??i(i?1)??j?2当i??j当i?j

MAX(i,j)*(MAX(i,j)-1)? MIN(i,j)2则其对应关系可表示为：k=( 1<=i,j<=n,

1<=k<=n(n+1)/2)

int MAX(int x,int y)

{ return(x>y?x:y); }

int MIN(int x,int y) { return(x

37. 设用mu,nu和tu表示稀疏矩阵行数，列数和非零元素个数，则转置矩阵的行数，列数

和非零元素的个数分别是nu,mu和tu。转置可按转置矩阵的三元组表中的元素顺序进行，即按稀疏矩阵的列序，从第1列到第nu列，每列中按行值递增顺序，找出非零元素，逐个放入转置矩阵的三元组表中，转时行列值互换，元素值复制。按这种方法，第1列到第1个非零元素一定是转置后矩阵的三元组表中的第1个元素，第1列非零元素在第2列非零元素的前面。这种方法时间复杂度是O(n*P)，其中p是非零元素个数，当p和m*n同量级时，时间复杂度为O(n3)。

另一种转置方法称作快速转置，使时间复杂度降为O(m*n)。它是按稀疏矩阵三元组表中元素的顺序进行。按顺序取出一个元素，放到转置矩阵三元组表的相应位置。这就要求出每列非零元素个数和每列第一个非零元素在转置矩阵三元组表中的位置，设置了两个附加向量。

38. 广义表中的元素，可以是原子，也可以是子表，即广义表是原子或子表的有限序列，满足线性结构的特性：在非空线性结构中，只有一个称为“第一个”的元素，只有一个成为“最后一个”的元素，第一元素有后继而没有前驱，最后一个元素有前驱而没有后继，其余每个元素有唯一前驱和唯一后继。从这个意义上说，广义表属于线性结构。 39. 数组是具有相同性质的数据元素的集合，同时每个元素又有唯一下标限定，可以说数组是值和下标偶对的有限集合。n维数组中的每个元素，处于n个关系之中，每个关系都是线性的，且n维数组可以看作其元素是n-1维数组的一个线性表。而广义表与线性表的关系，见上面38题的解释。

40．线性表中的元素可以是各种各样的，但必须具有相同性质，属于同一数据对象。广义表中的元素可以是原子，也可以是子表。其它请参见38 41.（1）（c,d）（2）（b）（3）b （4）（f）（5）（） 42. Head（Tail（Head（Head（L1））））

Head（Head（Head（Tail（Head（Tail（L2））））））类似本题的另外叙述的几个题解答如下：（1）head（head（tail（tail（L）））），设L=（a，（c），b），（（（e））））（2）head（head（head（head（tail（tail（L））））））

（3）head（tail（head（tail（A））））（4）H（H（T（H（T（H（T（L）））））））（5）tail（L）=（（（c,d）），（e,f））

head（tail（L））=（（c,d）） head（head（tail（L）））=（c,d） tail（head（head（tail（L））））=（d） head（tail（head（head（tail（L）））））=d

（6）head（tail（head（head（tail（tail（A））））））

43. 广义表的第一种存储结构的理论基础是，非空广义表可唯一分解成表头和表尾两部分，而由表头和表尾可唯一构成一个广义表。这种存储结构中，原子和表采用不同的结点结构（“异构”，即结点域个数不同）。

原子结点两个域：标志域tag=0表示原子结点，域DATA表示原子的值；子表结点三个域：tag=1表示子表，hp和tp分别是指向表头和表尾的指针。在画存储结构时，对非空广义表不断进行表头和表尾的分解，表头可以是原子，也可以是子表，而表尾一定是表（包括空表）。上面是本题的第一种存储结构图。

广义表的第二种存储结构的理论基础是，非空广义表最高层元素间具有逻辑关系：第一个元素无前驱有后继，最后一个元素无后继有前驱，其余元素有唯一前驱和唯一后继。有人将这种结构看作扩充线性结构。这种存储结构中，原子和表均采用三个域的结点结构（“同构”）。结点中都有一个指针域指向后继结点。原子结点中还包括标志域tag=0和原子值域DATA；子表结点还包括标志域tag=1和指向子表的指针hp。在画存储结构时，从左往右一个元素一个元素的画，直至最后一个元素。下面是本题的第二种存储结构图。

由于存储结构图占篇幅较大，下面这类题均不再解答。 44.深度为5，长度为2 45.（1）略

（2）表的长度为5，深度为4

（3）head（tail（head（head（head（tail（tail（tail（tail（A））））））））） 46.共享结构广义表A=（（（b,c），d），（a），（（a），（（b,c），d）），e，（））的存储表示：

47.（1）算法A的功能是逆置广义表p（即广义表由p指针所指）。逆置后的广义表由t指向。

（2）逆置后的广义表由t指向，这时p=nil。

48.（a,b） 49.（d）

50.否。广义表的长度不是广义表中原子个数，而是指广义表中所含元素的个数，广义表中的元素可以是原子，也可以是子表。广义表元素多于1个时，元素间用逗号分开。

5245334253

51. p（x1 x2 x3）=2 x1 x2 x3+5 x1 x2 x3+3 x1 x2 x3+（x1 x2+ x2）x3+6

52.（1）H(A(a1,a2）,B(b1）,C(c1，c2）,x）

HEAD(TAIL(HEAD(H）））=a2

（2）略

五.算法设计题

1.[题目分析]本题是在向量D内插入元素问题。首先要查找插入位置，数据x插入到第i个数据组的末尾，即是第i+1个数据组的开始，而第i（1≤i≤n）个数据组的首地址由数组s（即数组元素s[i]）给出。其次，数据x插入后，还要维护数组s，以保持空间区D和数组s的正确的相互关系。

void Insert（int s[]，datatype D[]，x，int i,m）

//在m个元素的D数据区的第i个数据组末尾，插入新数据x，第i个数据组的首址由数组s给出。

｛if（i<１|| i>n）｛printf（“参数错误”）；exit（０）；｝ if（i==n） D[m]=x； // 在第n个数据组末尾插入元素。 else｛for（j=m-1;j>=s[i+1];j--）D[j+1]=D[j]; // 第i＋１个数据组及以后元素后移

D[s[i+1]]=x; // 将新数据x插入

for(j=i+1;j<=n;j++) s[j]++; // 维护空间区D和数组s的的关系。 } //结束元素插入

m++; //空间区D的数据元素个数增1。 }// 算法Insert结束

[算法讨论] 数据在空间区从下标0开始，最后一个元素的下标是m-1。设空间区容量足够大，未考虑空间溢出问题。数组s随机存数，而向量D数据插入，引起数组元素移动，时间复杂度是O（n）。

2. [题目分析]设稀疏矩阵的非零元素的三元组以行序为主存储在三元组表中。矩阵的相加

是对应元素的相加。对两非零元素相加，若行号不等，则行号大者是结果矩阵中的非零元素。若行号相同，则列号大者是结果中一非零元素；若行号列号相同，若对应元素值之和为零，不予存储，否则，作为新三元组存到三元组表中。题目中要求时间复杂度为O（m+n）。因此需从两个三元组表的最后一个元素开始相加。第一个非零元素放在A矩阵三元组表的第m+n位置上。结果的三元组至多是m+n个非零元素。最后若发生对应元素相加和为零的情况，对三元组表中元素要进行整理，以便使第一个三元组存放在下标1的位置上。

CONST maxnum=大于非零元素数的某个常量 TYPE tuple=RECORD

i,j：integer； v：elemtp； END；

sparmattp=RECORD

mu，nu，tu：integer；

data: ARRAY[1..maxnum] OF tuple； END；

PROC AddMatrix（VAR A：sparmattp；B：sparmattp）；

// 稀疏矩阵A和B各有m和n个非零元素，以三元组表存储。A的空间足够大，本算法实现两个稀疏矩阵相加，结果放到A中。 L:=m；p:=n；k:=m+n；// L,p为A，B三元组表指针，k为结果三元组表指针（下标）。 A.tu:=m+n；// 暂存结果矩阵非零元素个数 WHILE（L≥1）AND（p≥1）DO

[CASE // 行号不等时，行号大者的三元组为结果三元组表中一项。 A.data[L].i>B.data[p].i：A.data[k]:=A.data[L]；L:=L-1；// A中当前项为结果项

A.data[L].i

A.data[L].i=B.data[p].i：

CASE //行号相等时，比较列号

A.data[L].j>B.data[p].j：A.data[k]:=A.data[L]；L:=L-1；

A.data[L].j

THEN

[A.data[L].v=A.data[L].v+ B.data[p].v；

A.data[k]:= A.data[L]；] L:=L-1；p:=p-1；

ENDC； //结束行号相等时的处理

ENDC； //结束行号比较处理。

k:=k-1； //结果三元组表的指针前移（减1） ]//结束WHILE循环。

WHILE p>0 DO[A.data[k]:=B.data[p]；k:=k-1；p:=p-1；] //处理B的剩余部分。 WHILE L>1 DO[A.data[k]:=A.data[L]；k:=k-1；L:=L-1；] //处理A的剩余部分。 IF k>1 THEN //稀疏矩阵相应元素相加时，有和为零的元素，因而元素总数

ENDP； // 结束addmatrix

[算法讨论]算法中三元组的赋值是“成组赋值”，可用行值、列值和元素值的三个赋值句代替。A和B的三元组表的当前元素的指针L和p，在每种情况处理后均有修改，而结果三元组表的指针k在CASE语句后统一处理（k:=k-1）。算法在B的第一个元素“大于”A的最后一个元素时，时间复杂度最佳为O（n），最差情况是每个元素都移动（赋值）了一次，且出现了和为零的元素，致使最后（m+n-k+1）个元素向前平移一次，时间复杂度最差为O（m+n）。

3.[题目分析]从n个数中，取出所有k个数的所有组合。设数已存于数组A[1..n]中。为使结果唯一，可以分别求出包括A[n]和不包括A[n]的所有组合。即包括A[n]时，求出从A[1..n-1]中取出k-1个元素的所有组合，不包括A[n]时，求出从A[1..n-1]中取出k个元素的所有组合。

CONST n=10；k=3；

TYPE ARR=ARRAY[1..n] OF integer；

VAR A，B：ARR；// A中存放n个自然数，B中存放输出结果。 PROC outresult；//输出结果

FOR j：=1 TO k DO write（B[j]）；writeln； ENDP；

PROC nkcombination（i,j,k：integer）；

//从i个数中连续取出k个数的所有组合，i个数已存入数组A中，j为结果数组B中的下标。

IF k=0 THEN outresult

ELSE IF（i-k≥0）THEN [ B[j]:=A[i]；j:=j+1；

nkcombination（i-1，k-1，j）；

nkcombination（i-1，k，j-1）；]

ENDP；

[算法讨论]本算法调用时，i是数的个数（题目中的n），k≤i，j是结果数组的下标。按题中例子，用nkcombination（5，1，3）调用。若想按正序输出，如123，124，?，可将条件表达式i-k≥0改为i+k-1≤n，其中n是数的个数，i初始调用时为1，两个调用语句中的i-1均改为i+1。 4. [题目分析]题目中要求矩阵两行元素的平均值按递增顺序排序，由于每行元素个数相等，按平均值排列与按每行元素之和排列是一个意思。所以应先求出各行元素之和，放入一维数组中，然后选择一种排序方法，对该数组进行排序，注意在排序时若有元素移动，则与之相应的行中各元素也必须做相应变动。

void Translation（float *matrix，int n）

//本算法对n×n的矩阵matrix，通过行变换，使其各行元素的平均值按递增排列。 {int i,j,k,l；

float sum，min； //sum暂存各行元素之和 float *p, *pi, *pk; for(i=0; i

{sum=0.0; pk=matrix+i*n; //pk指向矩阵各行第1个元素.

for (j=0; j

*(p+i)=sum; //将一行元素之和存入一维数组.

}//for i

for(i=0; i

{min=*(p+i); k=i; //初始设第i行元素之和最小.

for(j=i+1;j

{pk=matrix+n*k; //pk指向第k行第1个元素. pi=matrix+n*i; //pi指向第i行第1个元素. for(j=0;j

{sum=*(pk+j); *(pk+j)=*(pi+j); *(pi+j)=sum;}

sum=p[i]; p[i]=p[k]; p[k]=sum; //交换一维数组中元素之和. }//if }//for i

free(p); //释放p数组. }// Translation

[算法分析] 算法中使用选择法排序,比较次数较多,但数据交换(移动)较少.若用其它

排序方法,虽可减少比较次数,但数据移动会增多.算法时间复杂度为O(n).

5. [题目分析] 因为数组中存放的是从1到N的自然数，原程序运行后,数组元素A[i](1<=i<=N)中存放的是A[1]到A[i-1]中比原A[i]小的数据元素的个数。易见A[N]+1就是原A[N]的值(假定是j,1<=j<=N)。设一元素值为1的辅助数组flag，采用累加，确定一个值后，flag中相应元素置零。下面程序段将A还原成原来的A: VAR flag:ARRAY[1..N] OF integer;

FOR i:=1 TO N DO flag[i]:=1; //赋初值 FOR i:=N DOWNTO 1 DO

BEGIN sum:=0; j:=1; found:=false;

WHILE j<=N AND NOT found DO BEGIN sum:=sum+flag[j];

IF sum=A[i]+1 THEN BEGIN flag[j]:=0; found:=true; END;

END; A[i]:=j;

END;

6.[题目分析] 寻找马鞍点最直接的方法,是在一行中找出一个最小值元素,然后检查该元素是否是元素所在列的最大元素,如是,则输出一个马鞍点,时间复杂度是O(m*(m+n)).本算法使用两个辅助数组max和min,存放每列中最大值元素的行号和每行中最小值元素的列号,时间复杂度为O（m*n+m），但比较次数比前种算法会增加，也多使用向量空间。

int m=10, n=10;

void Saddle(int A[m][n])

//A是m*n的矩阵,本算法求矩阵A中的马鞍点.

{int max[n]={0}, //max数组存放各列最大值元素的行号,初始化为行号0;

min[m]={0}, //min数组存放各行最小值元素的列号,初始化为列号0; i, j;

for(i=0;i

for(j=0;j

{if(A[max[j]][j]A[i][j]) min[i]=j; //修改第i行最小元素的列号. }

for (i=0;i

{j=min[i]; //第i行最小元素的列号

if(i==max[j])printf(“A[%d][%d]是马鞍点，元素值是%d”,i,j,A[i][j]); //是马鞍点

}

}// Saddle

[算法讨论] 以上算法假定每行（列）最多只有一个可能的马鞍点，若有多个马鞍点,因为一行(或一列)中可能的马鞍点数值是相同的，则可用二维数组min2，第一维是行向量，是各行行号，第二维是列向量，存放一行中最大值的列号。对最大值也同样处理，使用另一二维数组max2，第一维是列向量，是各列列号，第二维存该列最大值元素的行号。最后用类似上面方法，找出每行(i)最小值元素的每个列号（j），再到max2数组中找该列是否有最大值元素的行号（i），若有，则是马鞍点。 7．[题目分析]我们用l代表最长平台的长度，用k指示最长平台在数组b中的起始位置（下标）。用j记住局部平台的起始位置，用i指示扫描b数组的下标，i从0开始，依次和后续元素比较，若局部平台长度（i-j）大于l时，则修改最长平台的长度k（l=i-j）和其在b中的起始位置（k=j），直到b数组结束，l即为所求。

void Platform (int b[ ], int N)

//求具有N个元素的整型数组b中最长平台的长度。 {l=1;k=0;j=0;i=0; while(i

{while(i

if(i-j+1>l) {l=i-j+1;k=j;} //局部最长平台 i++; j=i; } //新平台起点

printf(“最长平台长度%d，在b数组中起始下标为%d”，l，k)； }// Platform

8．[题目分析]矩阵中元素按行和按列都已排序，要求查找时间复杂度为O（m+n），因此不能采用常规的二层循环的查找。可以先从右上角（i=a,j=d）元素与x比较，只有三种情况：一是A[i,j]>x，这情况下向j 小的方向继续查找；二是A[i,j]

void search(datatype A[ ][ ], int a,b,c,d, datatype x)

//n*m矩阵A,行下标从a到b,列下标从c到d,本算法查找x是否在矩阵A中. {i=a; j=d; flag=0; //flag是成功查到x的标志 while(i<=b && j>=c)

if(A[i][j]==x) {flag=1;break;}

else if (A[i][j]>x) j--; else i++;

if(flag) printf(“A[%d][%d]=%d”,i,j,x); //假定x为整型. else printf(“矩阵A中无%d 元素”，x)； }算法search结束。

[算法讨论]算法中查找x的路线从右上角开始，向下（当x>A[i,j]）或向左（当x

9．[题目分析]本题的一种算法前面已讨论（请参见本章三、填空题38）。这里给出另一中解法。分析数的填法，是按“从右上到左下”的”蛇形”，沿平行于副对角线的各条对角线上，将自然数从小到大填写。当从右上到左下时，坐标i增加，坐标j减小，当j减到小于

0时结束，然后j从0开始增加，而i从当前值开始减少，到i<0时结束。然后继续如此循环。当过副对角线后，在i>n-1时，j=j+2，开始从左下向右上填数；而当j>n-1时i=i+2，开始从右上向左下的填数，直到n*n个数填完为止。

void Snake_Number(int A[n][n],int n)

//将自然数1..n*n,按”蛇形”填入n阶方阵A中.

{i=0; j=0; k=1; //i,j是矩阵元素的下标,k是要填入的自然数. while(i

{while(i-1) //从右上向左下填数, {A[i][j]=k++; i++ ;j--;}

if((j<0)&&(i-1 && j

10.[题目分析]判断二维数组中元素是否互不相同，只有逐个比较,找到一对相等的元素，就可结论为不是互不相同。如何达到每个元素同其它元素比较一次且只一次？在当前行，每个元素要同本行后面的元素比较一次（下面第一个循环控制变量p的for循环），然后同第i+1行及以后各行元素比较一次，这就是循环控制变量k和p的二层for循环。

int JudgEqual(ing a[m][n],int m,n)

//判断二维数组中所有元素是否互不相同，如是，返回1；否则，返回0。 {for(i=0;i

{ for(p=j+1;p

if(a[i][j]==a[i][p]) {printf(“no”); return(0); }

//只要有一个相同的，就结论不是互不相同

for(k=i+1;k

if(a[i][j]==a[k][p]) {printf(“no”); return(0); } }// for(j=0;j

printf(yes”); return(1); //元素互不相同 }//算法JudgEqual结束

（2）二维数组中的每一个元素同其它元素都比较一次，数组中共m*n个元素，第1个元素同其它m*n-1个元素比较，第2个元素同其它m*n-2 个元素比较，??，第m*n-1个元素同最后一个元素(m*n)比较一次,所以在元素互不相等时总的比较次数为 (m*n-1)+(m*n-2)+?+2+1=（m*n）(m*n-1)/2。在有相同元素时,可能第一次比较就相同,也可能最后一次比较时相同,设在(m*n-1)个位置上均可能相同,这时的平均比较次数约为

（m*n）(m*n-1)/4，总的时间复杂度是O(n)。

11．二项式(a+b）展开式的系数的递归定义为：

C(n,k)=

?1当k?0或k?n(n??0)??C(n?1,k)?C(n?1,k?1)当(0?k?n)

n(n?1)...(n?k?1)k

C(n,k)=Cn=1*2*...*(k?1)*k

(1)int BiForm(int n,k) //二项式展开式的系数的递归算法 {if(n<0 || k<0 || k>=n) {printf(“参数错误\\n ”);exit(0);} if(k==0 || k==n) return(1);

else return(BiForm(n-1,k)+BiForm(n-1,k-1); }

(2)C(6,4)的递归树

C(6,4) 15

+ C(5,4) C(5,3) 10 5 C(4,3) C(4,4)+C(4,3) C(4,2) + 6 4 1 4 C(3,2) C(3,3)+C(3,2) C(3,3)+C(3,2) + C(3,1) 3 3 3 3 1 1 C(2,1)+C(2,0) C(2,2)+C(2,1) C(2,2)+C(2,1) C(2,2)+C(2,1) 1 1 1 2 1 2 2 2 C(1,1)+C(1,0) C(1,1)+C(1,0) C(1,1)+C(1,0) C(1,1)+C(1,0) 1 1 1 1 1 1 1 1 (3)计算C(n,k)(0<=k<=n)的非递归算法 int cnk(int n,int k) {int i; long x=1,y=1; for (i=1;i<=k;i++) x*=i; for (i=n-k+1;i<=n;i++) y*=i; return(y/x) }//cnk

12.[题目分析]本题属于排序问题，只是排出正负，不排出大小。可在数组首尾设两个指针i和j，i自小至大搜索到负数停止，j自大至小搜索到正数停止。然后i和j所指数据交换，继续以上过程，直到 i=j为止。

void Arrange(int A[],int n)

//n个整数存于数组A中，本算法将数组中所有正数排在所有负数的前面 {int i=0,j=n-1,x; //用类C编写，数组下标从0开始 while(i

{while(i0) i++; while(i

if(i

}//算法Arrange结束.

[算法讨论]对数组中元素各比较一次，比较次数为n。最佳情况(已排好,正数在前,负数在后)不发生交换，最差情况(负数均在正数前面)发生n/2次交换。用类c编写，数组界偶是0..n-1。空间复杂度为O(1). 类似本题的其它题的解答:：

（1）与上面12题同，因要求空间复杂度也是O(n)，可另设一数组C，对A数组从左到右扫描，小于零的数在C中从左（低下标）到右（高下标）存，大于等于零的数在C中从右到

左存。

（2）将12题中判定正数(A[i]>0)改为判偶数(A[i]%2==0)，将判负数(A[j]<0)改为(A[j]%2!=0)。（3）同（2），只是要求奇数排在偶数之前。（4）利用快速排序思想，进行一趟划分。 int Partition(int A[],int n)

//将n个元素的数组A调整为左右两部分，且左边所有元素小于右边所有元素，返回分

界位置。

{int i=0,j=n-1,rp=A[0]; //设数组元素为整型 while(i

{while(i=rp) j--; while(i

if(i

A[i]=rp; return(i); //分界元素 }// Partition

13. [题目分析] 设n个元素存放在数组A[1..n]中。设S初始为空集，可依次将数组A的每一个元素并入S，产生了含一个元素的若干集合，再以含一个元素的集合为初始集合，依次并入A的第二个（异于S的那个元素）元素并入S，形成了含两个元素的若干集合，??，如此下去，直至A[i]的全部元素并入。

CONST n=10;

TYPE datatype=char;

VAR A: array[1..n] OF datatype; PROC powerset(s:set OF datatype) [outset(s); //输出集合S

FOR i:=1 TO n DO powerset(S+A[i]); ] ENDP;

调用本过程时，参数S为空集[]。

14、[题目分析]设稀疏矩阵是Amxn,Hm是总表头指针。设rch是行列表头指针，则rch->right=rch时该行无非零元素，用i记行号，用一维数组元素A[i]记第i行非零元个数。（为方便输出，设元素是整数。）

int MatrixNum(Olink Hm)

//输出由Hm指向的十字链表中每一行的非零元素个数 {Olink rch=Hm->uval.next, p;

int A[]; i=1;//数组A记各行非零元个数,i记行号 while(rch!=Hm)//循环完各行列表头

{p=rch->right; num=0; //p是稀疏矩阵行内工作指针,num记该行非零个数 while(p!=rch)//完成行内非零元的查找

{printf(“M[%d][%d]=%d”,p->row,p->col,p->uval.e); num++;p=p->right; printf(“\\n”);//指针后移 }

A[i++]=num;//存该行非零元个数

rch=rch->uval.next;//移到下一行列表头 }

num=0

for(j=1;j

{num+=A[j]; printf(“第%d行非零元个数为%d\\n”,j,A[j]); } return(num);//稀疏矩阵非零元个数 }算法结束

15、[题目分析] 广义表的元素有原子和表。在读入广义表“表达式”时，遇到左括号‘（’就递归的构造子表，否则若是原子，就建立原子结点；若读入逗号‘，’，就递归构造后续子表；若n=0，则构造含空格字符的空表，直到碰到输入结束符号（‘#’）。设广义表的形式定义如下：

typedef struct node

{int tag; //tag=0为原子，tag=1为子表 struct node *link; //指向后继结点的指针 union {struct node *slink; //指向子表的指针 char data; //原子

}element;

}Glist;

Glist *creat ()

//建立广义表的存储结构 {char ch; Glist *gh; scanf(“%c”,&ch); if(ch==’’) gh=null;

else {gh=(Glist*)malloc(sizeof(Glist)); if(ch==‘(’){gh->tag=1; //子表

gh->element.slink=creat(); } //递归构造子表 else {gh->tag=0;gh->element.data=ch;} //原子结点 }

scanf(“%c”,&ch);

if(gh!=null) if(ch==‘,’) gh->link=creat()； //递归构造后续广义表 else gh->link=null; return(gh); }

}算法结束 16、(1)略

(2)求广义表原子个数的递归模型如下

?1?f(p^.link)如果p^.tag?0?f(p^.sublist)?f(p^.link)如果p^.tag?1

f(p)=?PROC Number(p:glist; VAR n: integer) VAR m:integer; n:=0;

IF p<>NIL THEN

[IF p^.tag=0 THEN n:=1 ELSE Number(p^.sublist,m)

n:=n+m; Number(p^.link,m); n:=n+m; ] ENDP;

17. int Count(glist *gl)

//求广义表原子结点数据域之和，原子结点数据域定义为整型 {if(gl==null) return(0);

else if (gl->tag==0) return((p->data)+count(gl->link)); else return(count(gl->sublist)+count(gl->link)); } }// Count

18.（1）在n个正整数中，选出k(k<

//已知r[k+1..m]是堆，本算法将r[k..m]调整成堆，tag=1建立大根堆,tag=2建立小根堆

{i=k;j=2*i;x=r[k]; while (j<=m)

{if (tag==2) //建立小根堆

{if (jr[j+1]) j++;//沿关键字小的方向筛选 if(r[j]

{if (jx) {r[i]=r[j];i=j;j=2*i;} else break;} }

r[i]=x; }//sift

main(int argc,char *argv[])

//根据命令行中的输入，从1000个数中选取n个最大数或n个最小数 {int m=1000,i,j;

n=augv[2]; //从命令行输入的第二个参数是需要输出的数的个数 if(n>m){printf(“参数错误\\n”);exit(0);}

for(i=0;i0;i--) sift(r,i,m,1) printf(“%d个最大数依次为\\n”,n);

for(i=m;i>m-n+1;i--) //输出n个最大数 {printf(“]”,r[i]); j++; if((j+1)%5==0) printf(“\\n”);//一行打印5个数

sift(r,1,i-1,1); } //调堆 }

else //(augv[1]==‘i’) //输出n个最小数，要求建立小根堆 {for(i=m/2;i>0;i--) sift(r,i,m,2) printf(“%d个最小数依次为\\n”,n);

for(i=m;i>m-n+1;i--) //输出n个最小数

{printf(“]”,r[i]); j++; if((j+1)%5==0) printf(“\\n”);//一行打印5个数

sift(r,1,i-1,2); } //调堆 } }//main

[算法讨论]算法讨论了建堆，并输出n（n小于等于m）个最大(小)数的情况，由于要求输出n个最大数或最小数，必须建立极大化堆和极小化堆。注意输出时的for循环控制到变量i从m变化到m-n+1，这是堆的性质决定的，只有堆顶元素才是最大(小)的。要避免使i从1到n来输出n个最大(小)数的错误。

19、[题目分析] 题目要求调整后第一数组（A）中所有数均不大于第二个数组（B）中所有数。因两数组分别有序，这里实际是要求第一数组的最后一个数A[m-1]不大于第二个数组的第一个数B[0]。由于要求将第二个数组的数插入到第一个数组中。因此比较A[m-1]和B[0]，如A[m-1]>B[0]，则交换。交换后仍保持A和B有序。重复以上步骤，直到A[m-1]<=B[0]为止。

void ReArranger (int A[],B[],m,n)

//A和B是各有m个和n个整数的非降序数组，本算法将B数组元素逐个插入到A中，使A中各元素均不大于B中各元素，且两数组仍保持非降序排列。 { while (A[m-1]>B[0])

{x=A[m-1];A[m-1]=B[0]; //交换A[m-1]和B[0] j=1;

wkile(j

x=A[m-1];i=m-2;

wkile(i>=0 && A[i]>x) A[i+1]=A[i--]; //寻找B[0]的插入位置 A[i+1]=x; } }算法结束

20、[题目分析]本题中数组A的相邻两段分别有序，要求将两段合并为一段有序。由于要求附加空间为O(1),所以将前段最后一个元素与后段第一个元素比较，若正序，则算法结束；若逆序则交换，并将前段的最后一个元素插入到后段中，使后段有序。重复以上过程直到正序为止。

void adjust(int A[],int n)

//数组A[n-2k+1..n-k]和[n-k+1..n]中元素分别升序，算法使A[n-2k+1..n]升序 {i=n-k;j=n-k+1; while(A[i]>A[j])

{x=A[i]; A[i]=A[j]; //值小者左移，值大者暂存于x k=j+1;

while (kA[k]) A[k-1]=A[k++]; //调整后段有序 A[k-1]=x;

i--; j--; //修改前段最后元素和后段第一元素的指针 }