數(shù)據(jù)結(jié)構(gòu)課后習(xí)題答案第五章數(shù)組與廣義表

22一、

第五章數(shù)與廣義假設(shè)有二維數(shù)組A，每個(gè)元素用相鄰的6個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址。已知A的起始存儲(chǔ)位置（基地址）為。計(jì)算：1、數(shù)A的體積（即存儲(chǔ)量2、數(shù)A的最后一個(gè)元素的第一個(gè)字節(jié)的地址；3、按行存時(shí)，元素的第一個(gè)字節(jié)的地址；4、按列存時(shí)，元素的第一個(gè)字節(jié)的地址；答案：16*8）*6=2882、loc(a57)=1000+(5*8+7)*6=1282=1000+（）=12823、loc(a14)=1000+(1*8+4)*6=10724、loc(a47)=1000+(7*6+4)*6=1276二、假設(shè)按低下標(biāo)(行優(yōu)先優(yōu)先存儲(chǔ)整數(shù)數(shù)組A時(shí)第一個(gè)元素的字節(jié)地址9*3*5*8是100，每個(gè)整數(shù)占四個(gè)節(jié)。問下列元素的存儲(chǔ)地址是什么？（1）a0000

1111

8247答案1）100（2）)=100+(1*3*5*8+1*5*8+1*8+1)*4=7761111(3))=100+(3*3*5*8+1*5*8+2*8+5)*4=17843125(4))=100+(8*3*5*8+2*5*8+4*8+7)*4=44168247五、設(shè)有一個(gè)上三角矩陣（aij）n*n,將其上三角元素逐行存于數(shù)組B[m]中充分大使得且k=f1(i)+f2(j)+c。試推出函數(shù)f1,f2和常數(shù)（要求f1和f2中不含常數(shù)項(xiàng)答：…..+(n-(i-1)+1)+j-i=(i-1)(n+(n-i+2))/2+j-i所以f1(i)=(n+1/2)i-1/2if2(j)=j九已知A為稀疏矩陣試從空間和時(shí)間角度比較采用兩種不同的存儲(chǔ)結(jié)（二

維數(shù)組和三元組表）完成∑aii運(yùn)算的優(yōu)缺點(diǎn)對(duì)角線求和）解：1、二維數(shù)組For(i=1;i<=n;i++)S=s+a[i][i];時(shí)間復(fù)雜度：On）2、If(a.data[k].i==a.data[k].j)時(shí)間復(fù)雜度：On）二十一當(dāng)稀疏矩陣A和B均以三元組表作為存儲(chǔ)結(jié)構(gòu)時(shí)試寫出矩陣相加的算法，其結(jié)果存放在三元組表C中。解：矩陣相加就是將兩個(gè)矩陣中同一位置的元素值相加于兩個(gè)稀疏矩陣的非零元素按三元組表形式存放在建立新的三元組表時(shí)為了使三元組元素仍按行優(yōu)先排列，所以每次插入的三元組不一定是A，按照矩陣元素的行列去找A中的三元組，若有，則加入，同時(shí)，這個(gè)元素如果在B中也有，則加上B的這個(gè)元素值，否則這個(gè)值就不;如果A中沒有，則找B，有則插C，無則查找下一個(gè)矩陣元素。#defineMaxSize10//用戶自定義typedefintDataType;//戶自定義typedefstruct{//定義三元組inti,j;DataTypev;}TriTupleNode;typedefstruct{//定義三元組表

TriTupleNodedata[MaxSize];intm,n,t;//矩陣行，列及三元組表長(zhǎng)度}TriTupleTable;//以下為矩陣加算法voidAddTriTuple(TriTupleTable*A,TriTupleTableTriTupleTable*C){//三元組表表示的稀疏矩陣相加intk,l;DataTypetemp;C->m=A->m;//矩陣行數(shù)C->n=A->n;//矩陣列數(shù)C->t=0;//三元組表長(zhǎng)度k=0;l=0;while(k<A->t&&l<B->t){if((A->data[k].i==B->data[l].i)&&(A->data[k].j==B->data[l].j)){temp=A->data[k].v+B->data[l].v;if(!temp)//相加不為零，加入C{C->data[c->t].i=A->data[k].i;C->data[c->t].j=A->data[k].j;C->data[c->t++].v=temp;}k++;l++;}if((A->data[k].i==B->data[l].i)&&(A->data[k].j<B->data[l].j))||(A->data[k].i<B->data[l].i)//A中三元組加入C{C->data[c->t].i=A->data[k].i;

C->data[c->t].j=A->data[k].j;C->data[c->t++].v=A->data[k].v;k++;}if((A->data[k].i==B->data[l].i)&&(A->data[k].j>B->data[l].j))||(A->data[k].i>B->data[l].i)//B中三元組加入C{C->data[c->t].i=B->data[l].i;C->data[c->t].j=B->data[l].j;C->data[c->t++].v=B->data[l].v;l++;}}while(k<A->t)//將A中剩余三元組加入C{C->data[c->t].i=A->data[k].i;C->data[c->t].j=A->data[k].j;C->data[c->t++].v=A->data[k].v;k++;}while(l<B->t)//將B中剩余三元組加入C{C->data[c->t].i=B->data[l].i;C->data[c->t].j=B->data[l].j;C->data[c->t++].v=B->data[l].v;l++;}}二十六編寫一個(gè)以三元組形式輸出用十字鏈表表示的稀疏矩陣中非零元素及其下標(biāo)的算法。解：

voidPrint_OLMatrix(OLMatrixA)//以三元組格式輸出十字鏈表表示的矩陣{for(i=0;i<A.mu;i++){if(A.rhead[i])for(p=A.rhead[i];p;p=p->right)//次遍歷每一個(gè)行鏈表printf("%d%d%d\n",i,p->j,p->e;}}//Print_OLMatrix補(bǔ)充題：一、現(xiàn)有如下的稀疏矩陣A（如圖所示求畫出以下各種表示方法。（1）三元組表示法。（2）十字鏈表法。０

22

-13000

-60000000028000①三元組表示法1234567

ijv14221-1522356

②略二、畫出下列廣義表的存儲(chǔ)結(jié)構(gòu)示意圖。（1）A=((a,b,c),d,(a,b,c))（2）三、有數(shù)組A[4][4]，把1到16個(gè)整數(shù)分別按順序放入A[0][0]...A[0][3]，A[1][0]...A[1][3]，A[2][0]...A[2][3]A[3][0]...A[3][3]中，編寫一個(gè)算法獲取數(shù)據(jù)并求出兩條對(duì)角線元素的乘積。intmul(intA[4][4]){inti,j;intk,s;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=s*A[i][i];s=s*A[i][3-i];

}//計(jì)算兩條對(duì)角線元素的乘積returns;}四、19.已知廣義表LS＝((a,b,c),(d,e,f)),運(yùn)用head和tail函數(shù)取出LS原子e的運(yùn)算是()。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.cD.d21.已知廣義表:A=(a,b),B=(A,A),C=(a,(b,A),B),求下列運(yùn)算的結(jié)果tail(head(tail(C)))=()（a）B.AC.aD.(b)E.bF.(A)22.廣義表運(yùn)算式Tail(((a,b),(c,d)))的操作結(jié)果是（A.(c,d)B.c,dC.((c,d))D.d23.廣義表L=（a，cTail（L）操作后的結(jié)果為（A.cB.bc（bc）c24.廣義表a,b,c,d表頭是（尾是（A.aB.（）C.（a,b,c,d）D.（b,c,d）25.廣義表（a,(b,c),d,e）的表頭為（A.aB.a,(b,c)C.(a,(b,c))D.(a)26