第五章數(shù)組和廣義表答案

1.6.錯(cuò)誤。對(duì)于完全二叉樹，用一維數(shù)組作結(jié)構(gòu)是效率高的（密度大1.順序結(jié) 4.5.1164：LOC(aijk)=LOC(a000)+[v2*v3*(i-c1)+v3*(j-c2)+(k-c3)]*l(l為每個(gè)元素所占單元數(shù)6.7.8.9.1310.(2)27i(i-1)/2+j(1)n(n+1)/2(2)i(i+1)/2j(j+1)/2)(3)i(i-1)/2+j(4)j(j-1)/2+i1038三對(duì)角矩陣按行：k=2(i-1)+j33(k=i(i-1)/2+j) 16.節(jié)省空間元素在一維數(shù)組的下標(biāo)k和二維數(shù)組下標(biāo)關(guān)系:k=((i-1)*(2n-i+2))/2+(j-i+1)=(i-1)(2n-i)/2+j 20.線性 21.其余元素組成的（2）（3）（4）表中元素的個(gè)數(shù)（5）深 （2（）head（head（tail（tail（head（tail（tail（A） 27.（1）528. 29.30. 31. 32. 33.36.（1）(i==k)return（2）i+1（3）i-1（4）i!=kk（k-1k--do

)

若LStag0，且LSval.ptr.tp若LStag 本題要求將1，2，...,n*n個(gè)自然數(shù)，按蛇型方式存放在二位數(shù)組A[n][n即是按“副對(duì)角線”平行的各對(duì)角線，從左下到右上，再?gòu)挠疑系阶笙?，存放n2個(gè)整數(shù)。對(duì)角線共k=1i+j=k+1（1）k<=2*n-12*n-1 //k（i ijm++m=m+1，m1..n*n。9（1）(s+m-1)MOD w[n]s //Knap←Knap(s,n-1、 b對(duì)角矩陣的b條對(duì)角線，在主對(duì)角線上方和下方各有b/2條對(duì)角線(為敘述方便，下面設(shè)數(shù)是b-1，b-2,...,a+1。中間的(n-2a)行，每行元素個(gè)數(shù)都是b。故b條對(duì)角線上元素個(gè)數(shù)為22a(2iaj當(dāng)a1inaa(2ia)

(ina)(ina1)

j當(dāng)na1i 4(i1j1(當(dāng)1in時(shí)k=4(i1j2(當(dāng)ink=A[15,16]是第71個(gè)元素，在向量[-10:m]中的位置是608（1）540 9．k=i(i-A有tmunutu(也算一個(gè)三元組)，共占用三元組表LTMA的3(t+1)個(gè)單元，用二維數(shù)組時(shí)占用m*n個(gè)單元，只有當(dāng)3(t+1)<m*n時(shí)，LTMA表示At<m*n/3-1。順序查找，時(shí)間復(fù)雜度為O(n)。若使查找時(shí)間得到改善，可以建立索引，將各行行號(hào)及各行第一個(gè)O(logn)。13（1）176 14（1）k=3(i-1) k=3(i-1)+1 (主對(duì)角線上，即i=j)k=3(i- 由以上三式，得k=2(i- (1i,jn;1k3n-比二維數(shù)組節(jié)省單元；但在求Σaii(1<=i<=n)時(shí)，要掃描整個(gè)三元組表，以便找到行列值相等的（對(duì)值相同元素只分配一個(gè)單元將非零元素在向量中，元素的下標(biāo)i和j和該元素在向量中的下標(biāo)有一定規(guī)律，可以用簡(jiǎn)單表示，仍具有隨機(jī)存取功能。而稀疏矩陣是指非零元素和矩陣容量相比很?。╰<<m*n，且分布沒(méi)有規(guī)律。用十字鏈表作結(jié)構(gòu)自然失去了隨機(jī)存取的功能。即使用三元組表的順序結(jié)構(gòu)，存取下標(biāo)為i和j的元素時(shí)，要掃描三元組表，下標(biāo)不同的元素，存取時(shí)間也不同，最好情況下存取時(shí)間為O(1)，情況下是O(n)，因此也失去了隨機(jī)存取的功能。18．n(n+1)/2（壓縮 或n2（不采用壓縮 A[i][j]1<=i,j<=n,i>=所以n階下三角矩陣A按列，其元素aij在一維數(shù)組B中的位置k與i和j的關(guān)系為：三對(duì)角矩陣第一行和最后一行各有兩個(gè)非零元素，其余每行均有三個(gè)非零元素，所以共有3n-i=j+1kijk=3(i-1);主對(duì)角間有關(guān)系i=j-1，k與i和j的關(guān)系為k=3(i-1)+2。綜合以上三等式，有k=2(i-1)+ji=k/3+1（1≤k≤3n-1A[1..8]=[90,30,85,65,50,80,10,100]23PerfectShuffleWHILE2N，WHILE2NDemo的時(shí)間復(fù)雜度為：最好情況：O(4N*log22N)≈O(Nlog(2*N))；情況：O((4N+3N)*log22N)≈

對(duì)cij（ji）32）（1）（2）OR（i+k>last+1（3）FORDOWNTO（4）count刪除kk TYPEARR=ARRAY[1..m]OFPROCEDUREdelk（VARA:ARR；VARlast:integer;i,k：integerA[1..last]ik，mAVARcount：integer；THENwrite（’errorELSE[FORcount：=i+kTOlastDOA[count-k]：=A[count]；ni-1n-（i-1）+1i-1，而第i行上第j個(gè)元素（即aij）是第i行上第j-i+1個(gè)元素故元素Aij在一維數(shù)組中的位置（k）為： 則得f（i）=（n+1/2）i-i2/2，f H4， （當(dāng)i≥j時(shí)，本題n=4） 33.（1）k=2（i-1）+j（1≤i，j≤n，|i- floor（a）a（2）行邏輯順序表是稀梳矩陣壓縮的一種形式。為了隨機(jī)存取任意一行的非零元，需要typedefintmu,nu,tu;//稀梳矩陣的行數(shù)、列數(shù)和非零元素個(gè)數(shù)intrpos[maxrow+1];Triple因篇幅所限，不再畫出行邏輯順序表c1（d3-c3+1（d2-c2（d2-35．i=jiji+j=n+1（1）i=ji=n+1-j）余每行都有兩個(gè)元素。主對(duì)角線上的元素，在向量B中的下標(biāo)是k=2i-1(i=j,1≤i，j≤n，副對(duì)角線上的元素，在中心元素前，在向量B中的下標(biāo)是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)。A02(i-A02(i-1)A0A02(i-1)-aij在BK

(ij,1i,j(ij,1i,jn/2)(ij,n/21i,jn)上三角矩陣共有n(n+1)/2個(gè)元素這些元素到一個(gè)向量B[n(n+1)/2+1]中可以看到B[k]aij之間存在著一一對(duì)應(yīng)關(guān)系：j(j1)

當(dāng)ik

i(i1)2

當(dāng)i

2

( intMAX(intx,int{}intMIN(intx,int{}mu,nutu表示稀疏矩陣行數(shù)，列數(shù)和非零元素個(gè)數(shù)，則轉(zhuǎn)置矩陣的行數(shù)，列數(shù)和非零元素nu,mutu。轉(zhuǎn)置可按轉(zhuǎn)置矩陣的三元組表中的元素順序進(jìn)行，即按稀疏矩陣的列序，1nu列，每列中按行值遞增順序，找出非零元素，逐個(gè)放入轉(zhuǎn)置矩陣的三元組表中，轉(zhuǎn)時(shí)行列值互換，元素值。按這種方法，第1列到第1個(gè)非零元素一定是轉(zhuǎn)置后矩陣的三元組表中的第1個(gè)元素，第1零元素在第2零元素的前面。這種方法時(shí)間復(fù)雜度是O(n*P)，其中pm*nO(n3)另一種轉(zhuǎn)置方法稱作快速轉(zhuǎn)置，使時(shí)間復(fù)雜度降為O(m*n)。它是按稀疏矩陣三元組表中元素的n-1383841.（1（c,d） （2（b） （4（f） （5（）Head（Tail（Head（Head（L1）HeadHead（HeadTailHead（TailL）（1）headheadtail（tailLL=（a（c，b（e）head（head（head（head（tail（tail（L）head（tail（head（tail（A）（4）H（H（T（H（T（H（T（L）（5）tail（L）=（c,d（e,fhead（tail（L）=（c,dhead（head（tail（L）=（c,d）tail（head（head（tail（L）=（d）headtail（headhead（tail（）（6）head（tail（head（head（tail（tail（A）“充線性結(jié)構(gòu)。這種結(jié)構(gòu)中，原子和表均采用三個(gè)域的結(jié)點(diǎn)結(jié)構(gòu)同構(gòu)。結(jié)點(diǎn)中都有一個(gè)指針tag=0DATAtag=1和指向子表的指針hp。在畫結(jié)構(gòu)時(shí)，從左往右一個(gè)元素一個(gè)元素的畫，直至最后一個(gè)元素。下面是本題的第二種結(jié)構(gòu)圖。由于結(jié)構(gòu)圖占篇幅較大，下面這類題均不再解答45.（1）head（tail（head（head（head（tail（tail（tail（tail（A）A=（b,c，d（a（a（b,c，d，e（） 1 p（xxx）=2x5x2x4+5x HEAD(TAIL(HEAD(H）=a2（2）1.[Dxi給出。其次，數(shù)據(jù)x插入后，還要數(shù)組s，以保持空間區(qū)D和數(shù)組s的正確的相互關(guān)系。voidInsert（ints[]，datatypeD[]，x，int//在mDixisi>n｛printf；exit（０｝if（i==n）D[m]=x；//在第n個(gè)數(shù)據(jù)組末入元素。else｛for（j=m-1;j>=s[i+1];j--）D[j+1]=D[j];//第i＋１個(gè)數(shù)據(jù)組及以后元素后移 //將新數(shù)據(jù)x插入for(j=i+1;j<=n;j++) //空間區(qū)D和數(shù)組s的的關(guān)系 Insert0m-1。設(shè)空間區(qū)容量足夠大，未O（n2.[題目分析]設(shè)稀疏矩陣的非零元素的三元組以行序?yàn)橹髟谌M表中。矩陣的相加是對(duì)應(yīng)元O（m+n1CONSTmaxnum=大于非零元素?cái)?shù)的某個(gè)常量TYPEtuple=RECORDi,j：integer；v：elemtp；data:ARRAY[1..maxnum]OFtuple；PROCAddMatrix（VARA：sparmattp；B：sparmattp//稀疏矩陣A和B各有m和n個(gè)非零元素，以三元組表。A的空間足夠大，本算法實(shí)現(xiàn)兩AL:=m；p:=n；k:=m+nL,pA，B，k（下標(biāo)A.tu:=m+n[CASE//行號(hào)不等時(shí)，行號(hào)大者的三元組為結(jié)果三元組表中一項(xiàng)。A.data[L].i>B.data[p].i：A.data[k]:=A.data[L]；L:=L-1；//ACASE//行號(hào)相等時(shí)，比較列號(hào)A.data[L].j=B.data[p].j：IFA.data[L].v+B.data[p].v≠0THEN[A.data[L].v=A.data[L].v+B.data[p].v；A.data[k]:=A.data[L]；] k:=k-1；（WHILEp>0DO[A.data[k]:=B.data[p]；k:=k-1；p:=p-1；]//處理BWHILEL>1DO[A.data[k]:=A.data[L]；k:=k-1；L:=L-1；]//處理AIFk>1THEN//稀疏矩陣相應(yīng)元素相加時(shí)，有和為零的元素，因而元素總數(shù)<m+n[FORp:=kTOm+nDOA[p-k+1]:=A[p]；//三元組前移，使第一個(gè)三元組的下標(biāo)為1。 //修改結(jié)果三元組表中非零元素個(gè)數(shù)。ENDP；BL和pkCASE（k:=k-1B”A個(gè)元素向前平移一次，時(shí)間復(fù)雜度為O（m+nA[n]A[n]A[n]A[1..n-1k-1A[nA[1..n-1kCONSTTYPEARR=ARRAY[1..n]OFVARA，B：ARR；//An，BPROCoutresultFORj：=1TOkDOwrite（B[j]；wrin； bination（i,j,k：integer//從ik，iAjBIFk=0THENELSEIF（i-k≥0）THEN[1，j1；]n，k≤i，j子，用bination（5，1，3）123，124i-k≥0i+k-1≤n，n，i1，i-1i+1。voidTranslation（float*matrix，int//本算法對(duì)n×nmatrix，{intfloat //sum暫存各行元float*p,*pi,*pk;for(i=0;i<n;i++){sum=0.0; for(j=0;j<n;j++){sum+=*(pk); //求一行 和 //將一行元和存入一維數(shù)組}//forfor(i=0;i<n-1;i++)p{min=*(p+i);k=i;//初始設(shè)第i行元和最小for(j=i+1;j<n;j++)if(p[j]<min){k=j;min=p[j];}//記新的最小值及行號(hào). //若最小行不是當(dāng)前行,要進(jìn)行交換(行元素及行元和{pk=matrix+n*k;//pkk1pi=matrix+n*i;//pii1for(j=0;j<n;j++)//交換兩行中對(duì)應(yīng)元素.{sum=*(pk+j);*(pk+j)=*(pi+j);sum=p[i];p[i]=p[k];p[k]=sum;//交換一維數(shù)組中元和}//for(p);p}//[算法分析]算法中使用選擇法排序,比較次數(shù)較多,但數(shù)據(jù)交換(移動(dòng))較少.若用其它排序方法,O(n2).存放的是A[1]到A[i-1]中比原A[i]小的數(shù)據(jù)元素的個(gè)數(shù)。易見(jiàn)A[N]+1就是原A[N]的值(假定是AA:VARflag:ARRAY[1..N]OFFORi:=1TONDOflag[i]:=1; FORi:=NDOWNTO1DOBEGINsum:=0;j:=1;found:=false;WHILEj<=NANDNOTfoundBEGINIFsum=A[i]+1THENBEGINflag[j]:=0;found:=true;6.[題目分析]尋找馬鞍點(diǎn)最直接的方法,是在一行中找出一個(gè)最小值元素,然后檢查該元素是否是元素所在列的最大元素,如是,則輸出一個(gè)馬鞍點(diǎn),時(shí)間復(fù)雜度是O(m*(m+n)).本算法使用兩個(gè)輔助數(shù)O（m*n+m但比較次數(shù)比前種算增加，也多使用向量空間。intm=10,voidSaddle(int{intmax[n]={0},//maxmin[m]={0},//min0;i,j;for(i=0;i<m;i++){if(A[max[j]][j]<A[i][j]) if(A[i][min[i]]>A[i][j]) }for i }}//（列是列向量，存放一行中最大值的列號(hào)。對(duì)最大值也同樣處理，使用另一二維數(shù)組max2，第一維是列（j（i（k=j，直b，lvoidtform(intb[],int{while(i<n-1&&b[i]==b[i+1])if(i-j+1>l){l=i-j+1;k=j;} i++;j=i;} }//O（m+nvoidsearch(datatypeA[][],inta,b,c,d,datatype//n*mA,行下標(biāo)從ab,cdxA{i=a;j=d;flag=0;//flagxwhile(i<=b&&j>=c)if(A[i][j]==x)elseif(A[i][j]>x)j--;elseif(flag)printf(“A[%d][%d]=%d”,i,j,x); //假定xelseprintf(“矩陣A%d元素”，x)；，x<A[i,j]（A[b,c]故算法時(shí)間復(fù)雜度是O(m+n，9．[題目分析]本題的一種算法前面已討論（38。這里給出另一中解法。分j=j+2，j>n-1i=i+2n*nvoidSnake_Number(intA[n][n],int1..n*n,nA{i=0;j=0;k=1; while(i<n&&j<n){while(i<n&&j>-1){A[i][j]=k++;i++;j--if((j<0)&&(i<n))j=0;i,jelse{j=j+2;i=n-1;}//副對(duì)角線以下的新的i,jwhile(i>-1&&j<n){A[i][j]=k++;i--;if(i<0&&j<n)i=0;else{i=i+2;j=n-k和pforintJudgEqual(inga[m][n],int{for(p=j+1;p<n;p++)//和其它元素比if(a[i][j]==a[i][p]){printf(“no”);return(0); if(a[i][j]==a[k][p]){printf(“no”);return(0);}//for(j=0;j<n-printf(yes”); （2）m*n1m*n-12m*-2m*-1(m*n)比較一次,所以在元素互不相等時(shí)總的比較次數(shù)為(m*n1)+(m*-2)+…+2+1=（m*n）(m*n-1)/2。在有相同元素時(shí),可能第一次比較就相同,也可能最后一次比較時(shí)相同,設(shè)在(m*n-1)個(gè)位置上均可能相同,這時(shí)的平均比較次數(shù)約為（m*n(m*n-1)/4O(n4C(n,k)=C(n1kC(n1k1)當(dāng)(0

n(n1)...(nknC(n,k)=Ck=1*2*...*(k1)*nintBiForm(int {if(n<0||k<0||k>=n){printf(“參數(shù)錯(cuò)誤\nif(k==0||k==n)elsereturn(BiForm(n-1,k)+BiForm(n-1,k-}5

+

4

1

1 C(1,1)+C(1,0)C(1,1)+C(1,0)

C(n,k)(0<=k<=n)的非遞歸算法intcnk(intn,intk){inti;longx=1,y=1;for(i=1;i<=k;i++)x*=i;for(i=n-k+1;i<=n;i++)y*=i; 自小至大搜索到負(fù)數(shù)停止，jiji=jvoidArrange(intA[],int{inti=0,j=n- {while(i<j&&A[i]>0)i++;while(i<j&& if(i<j){x=A[i];A[i++]=A[j];A[j--]=x;A[i]}O(1).12O(n)CAC（低下標(biāo)）到右（高下標(biāo)）C將（2intPartition(intA[],int//將nA{inti=0,j=n-1,rp=A[0]; {while(i<j&&A[j]>=rp) while(i<j if(i<j){x=A[i];A[i]=A[j];A[j]=x;}A[i]=rp; }//13.nA[1..nSACONSTTYPEVARA:array[1..n]OFdatatype;PROCpowerset(s:setOFdatatype) SFORi:=1TOnDOSintMatrixNum(Olink{Olinkrch=Hm->uval.next,intA[];i=1;/A,i{p=rch->right;num=0;//p,numnum++;p=p->right;printf(“\n”);//指針后移}}{num+=A[j];printf(“第%dd\n”,j,A[j]);（’就遞歸的typedefstruct{int structnode*link; union{structnode*slink;//指向子表的指針char Glist*creat//建立廣義表的結(jié){charch;Glist*gh;if(ch==’’)gh=null;elseif(ch==‘(’){gh->tag=1;gh->element.slink=creat();else{gh->tag=0;gh->element.data=ch;}//原子結(jié)點(diǎn)}if(gh!=null)if(ch==‘,’)gh->link=creat(elsegh->link=null;}PROCNumber(p:glist;VARn:integer)VARm:integer;IFp<>NIL[IFp^.tag=0THENn:=1ELSENumber(p^.sublist,m)n:=n+m;Number(p^.link,m); n:=n+m;]intCount(glist{if(gl==null)elseif(gl->tag==0)return((p->data)+count(gl->link));elsereturn(count(gl->sublist)+count(gl- }//O(nlognintr[1000];r[1000（2）voidsift(intr[],intwhile(j<=m){if {if(j<m&&r[j]>r[j+1j++;//沿關(guān)鍵字小的方向篩選if(r[j]<x)){r[i]=r[j];i=j;j=2*i;}elsebreak;}else//建立大根堆{if(j<m&&r[j]<r[j+1j++;//沿關(guān)鍵字小的方向篩選if(r[j]>x){r[i]=r[j];i=j;j=2*i;}else}main(intargc,char{int for(i=0;i<m;i++)scanf(“%d”,&r[i]);1000if //輸出n{for(i=m/2;i>0;i--)sift(r,i,m,1)printf(“%d個(gè)最大數(shù)依次為\n”,n); sift(r,1,i-1,1);}else //輸出n{for(i=m/2;i>0;i--)sift(r,i,m,2)printf(