第5章习题及解答

⒈假设按行优先存储整数数组A[9][3][5][8]时，第一个元素的字节地址是１００，每个整数占４个字节。问下列元素的存储地址是什么？

⑴a0000 ⑵a1111 ⑶a3125 ⑷a8247

⑴a0000 的存储地址是100。 ⑵a1111 的存储地址是776。 ⑶a3125 的存储地址是1784。 ⑷a8247 的存储地址是4416。

⒉设有三对角矩阵An×n，将其三条对角线上的元素存于数组B[3][n]中，使得元素B[u][v]=aij，试推导出从(i,j)到(u,v)的下标变换公式。 u = i

v = {j if i≤2 | j-i+2 if i>2}

⒊假设一个准对角矩阵：

a11 a12

a21 a22

a33 a34

a43 a44

….

aij

a2m-1,2m-1 a2m-1,2m

a2m,2m-1 a2m,2m

按以下方式存储于一维数组B[4m]中:

0 1 2 3 4 5 6 … k … 4m-1 4m

a 11 a 12 a21 a22 a33 a34 a43 … aij … a2m-1,2m a2m,2m-1 a2m,2m 写出由一对下标(i,j)求k的转换公式。

略

⒋现有如下的稀疏矩阵A（如图所示），要求画出以下各种表示方法。 ⑴三元组表示法。 ⑵十字链表法。 ０ 0 0 22 0 -15 0 13 3 0 0 0 0 0 0 -6 0 0 0 0 0 0 0 0 91 0 0 0 0 0 0 0 28 0 0 0

略

⒌画出下列广义表的存储结构示意图。 ⑴A=((a,b,c),d,(a,b,c)) ⑵B=(a,(b,(c,d),e),f)

略

⒍对于二维数组A[m][n],其中m<=80,n<=80，先读入m,n，然后读该数组的全部元素，对如下三种情况分别编写相应算法：

⑴求数组A靠边元素之和。

⑵求从A[0][0]开始的互不相邻的各元素之和。

⑶当m=n时，分别求两条对角线的元素之和，否则打印m!=n的信息。

⒎有数组A[4][4]，把1到16个整数分别按顺序放入A[0][0]...A[0][3]，A[1][0]...A[1][3]，A[2][0]

...A[2][3]，A[3][0]...A[3][3]中，编写一个算法获取数据并求出两条对角线元素的乘积。

int mul (int A[4][4]) {

int k=1,s=1;

for (i=0; i<4 ;i++) for (j=0 ;j<4 ;j++) {

A[i][j] =k; k++; }

for (i=0; i<4 ;i++) {

s* = A[i][i]; s* = A[i][3-i]; }

return(s); }

⒏n只猴子要选大王，选举办法如下：所有猴子按1，2，...，n编号围坐一圈，从第1号开始按1、2、...、m报数，凡报m号的退出圈外，如此循环报数，直到圈内剩下一只猴子时，这只猴子就是大王。n和m由键盘输入，打印出最后剩下的猴子号。编写一个算法实现。

typedef struct node{

int data;

struct node *next; }Node ,*LkList;

void process (int n, int m) {

L=new Node; L->data=1; L->next =L; rear =L;

for (i=2 ;i<=n ;i++) {

s=new Node; s->data=i;

s->next=rear->next; rear->next = s; rear = s; } p=L;

while (p->next != p) {

i=1;

while (i

q=p;

p=p->next; i++; }

q->next=p->next; cout<data<

delete p; p=q->next; }

cout<<”the last monky is : ” <data<

⒐假设稀疏矩阵A和B（具有相同的大小m*n）都采用三元组表示，编写一个算法计算C=A+B，要求C也采用三元组表示。

参见教科书

⒑假设稀疏矩阵A和B（分别为m*n和n*1矩阵）采用三元组表示，编写一个算法计算C=A*B，要求C也是采用稀疏矩阵的三元组表示。

#define SMAX 1024 typedef struct{

int i; int j;

datatype v; }SPNode;

typedef struct{

SPNode data[SMAX]; /*0号单元未用*/ int mu; int nu; int tu; }SPMatrix;

SPMatrix *Matrix_add (SPMatrix *A,SPMatrix *B) {

SPMatrix *C; C->mu = A->mu; C->nu = A->nu; C->tu = 0;

pa=1 ; pb =1 ; pc=1;

while (pa<=A->tu && pb<=B->tu) {

if ((A->data[pa].i==B->data[pb].i)&&

(A->data[pa].j==B->data[pb].j))

{

C->data[pc].i=A->data[pc].i;

C->data[pc].j=A->data[pc].j;

C->data[pc].v=A->data[pa].v + B->data[pb].v; C->tu++ ;pc++ ; pa++ ; pb++ ; } else

if ((A->data[pa].i < B->data[pb].i)||

(A->data[pa].i==B->data[pb].i&&

A->data[pa].j< B->data[pb].j))

{

C->data[pc].i = A->data[pa].i;

C->data[pc].j = A->data[pa].j; C->data[pc].v = A->data[pa].v; C->tu++; pc++ ;pa++;

} else {

C->data[pc].i = B->data[pb].i;

C->data[pc].j = B->data[pb].j; C->data[pc].v = B->data[pb].v; c->tu++; pc++; pb++; }

}

while ( pa<=A->tu) {

C->data[pc].i = A->data[pa].i; C->data[pc].j = A->data[pa].j; C->data[pc].v = A->data[pa].v; pc++; pa++; }

while ( pb<=B->tu ) {

C->data[pc].i = B->data[pb].i; C->data[pc].j = B->data[pb].j;

C->data[pc].v = B->data[pb].v; pc++; pb++; }

return(c); }

⒒假设稀疏矩阵只存放其非0元素的行号、列号和数值，以一维数组顺次存放，行号为-1结束标志。 例如：如图所示的稀疏矩阵M： 1 0 0 0 10 0 0 0 0 0 0 0 0 0 0 0 0 M = 0 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0

则存在一维数组D中：

D[0]=1， D[1]=1，D[2]=1，D[3]=1，D[4]=5 D[5]=10，D[6]=3，D[7]=9，D[8]=5，D[9]=-1

现有两个如上方法存储的稀疏矩阵A和B，它们均为m行n列，分别存放在数组A和B中，编写求矩阵加法C=A+B的算法，C亦放在数组C中。

void add (int A[ ], int B[ ], int C[ ]) {

pa=0; pb=0; pc=0;

while (A[pa+2] && B[pb+2])

本文来源：https://www.bwwdw.com/article/nxw3.html