數(shù)據(jù)結(jié)構(gòu)與算法-第1、2章習(xí)題

數(shù)據(jù)結(jié)構(gòu)——第1、2章習(xí)題解答第1章緒論4.（2）執(zhí)行下面程序段的時(shí)間復(fù)雜度為

.

for(inti=0;i<m;i++)

for(intj=0;j<n;j++)

a[i][j]=i*j;（3）執(zhí)行下面程序段時(shí)，語(yǔ)句S的執(zhí)行次數(shù)為

。

for(inti=0;i<=n;i++)

for(intj=0;j<=i;j++)S;5.計(jì)算下面程序段中x=x+1的語(yǔ)句頻度。

for(i=1;i<=n;i++)

for(j=1;j<=i;j++)

for(k=1;k<=j;k++)x=x+1;

6.編寫算法，求一元多項(xiàng)式

Pn(x)=a0+a1x+a2x2+a3x3+…+anxn

的值Pn(x0),并確定算法中每一語(yǔ)句的執(zhí)行次數(shù)和整個(gè)算法的時(shí)間復(fù)雜度，要求時(shí)間復(fù)雜度盡可能小，規(guī)定算法中不能使用冪函數(shù)。int

f(inta[],int

x,intn){

int

s,i;s=a[n];

for(i=n-1;i>=0;i--)s=s*x+a[i];

return(s);}時(shí)間復(fù)雜度為O(n);語(yǔ)句執(zhí)行次數(shù)為：

1

n1第2章線性表第2章線性表2.(2)已知L是無(wú)表頭結(jié)點(diǎn)的單鏈表，且p結(jié)點(diǎn)既不是首元素結(jié)點(diǎn)，也不是尾元素結(jié)點(diǎn)，按要求從下列語(yǔ)句中選擇合適的語(yǔ)句序列。A.P->next=S;B.P->next=P->next->next;C.P->next=S->next;E.S->next=P->next;F.S->next=L;G.S->next=NULL;H.Q=P;I.while(P->next!=Q)P=P->next;J.while(P->next!=NULL)P=P->nextK.P=Q;L.P=L;M.L=S;N.L=P;A.在P結(jié)點(diǎn)后插入S結(jié)點(diǎn)的語(yǔ)句序列是EAA.P->next=S;B.P->next=P->next->next;C.P->next=S->next;E.S->next=P->next;F.S->next=L;G.S->next=NULL;H.Q=P;I.while(P->next!=Q)P=P->next;J.while(P->next!=NULL)P=P->nextK.P=Q;L.P=L;M.L=S;N.L=P;B.在P結(jié)點(diǎn)前插入S結(jié)點(diǎn)的語(yǔ)句序列是HLIEAA.P->next=S;B.P->next=P->next->next;C.P->next=S->next;E.S->next=P->next;F.S->next=L;G.S->next=NULL;H.Q=P;I.while(P->next!=Q)P=P->next;J.while(P->next!=NULL)P=P->nextK.P=Q;L.P=L;M.L=S;N.L=P;C.在表首插入S結(jié)點(diǎn)的語(yǔ)句序列是FMA.P->next=S;B.P->next=P->next->next;C.P->next=S->next;E.S->next=P->next;F.S->next=L;G.S->next=NULL;H.Q=P;I.while(P->next!=Q)P=P->next;J.while(P->next!=NULL)P=P->nextK.P=Q;L.P=L;M.L=S;N.L=P;D.在表尾插入S結(jié)點(diǎn)的語(yǔ)句序列是JAGJGAGJAJEA4.已知順序表L遞增有序，編寫一個(gè)算法，將X插入到線性表的適當(dāng)位置上，以保持線性表的有序性。voidsqinsert(SeqList*L,ElemTypex){inti=0,j;while(L->elem[i]<x)i++;for(j=i;j<L->last;j++)L->elem[j+1]=L->elem[j];L->elem[i]=x;} 對(duì)嗎?4.已知順序表L遞增有序，編寫一個(gè)算法，將X插入到線性表的適當(dāng)位置上，以保持線性表的有序性。voidsqinsert(SeqList*L,ElemTypex){inti=0,j;while(i<=L-last&&L->elem[i]<x)i++;for(j=L->last;j>=i;j--)L->elem[j+1]=L->elem[j];L->elem[i]=x;

L->last++;} 4.已知順序表L遞增有序，編寫一個(gè)算法，將X插入到線性表的適當(dāng)位置上，以保持線性表的有序性。voidsqinsert(SeqList*L,ElemTypex){inti=L->last;while(i>=0&&L->elem[i]>x){L->elem[i+1]=L->elem[i];i--;}L->elem[i+1]=x;L->last++;} 6.已知線性表中的元素（整數(shù)）以值遞增有序排列，并以單鏈表作存儲(chǔ)結(jié)構(gòu)。試編寫一高效的算法，刪除表中所有大于mink且小于maxk的元素（若表中存在這樣的元素）delList(LinkL,Elemtypemink,Elemtypemaxk){Node*p;p=L->next;while(p!=NULL&&p->data<mink)p=p->next;while(p!=NULL&&p->data<maxk){q=p->next;p->next=q->next;free(q);p=p->next;}}對(duì)嗎?6.已知線性表中的元素（整數(shù)）以值遞增有序排列，并以單鏈表作存儲(chǔ)結(jié)構(gòu)。試編寫一高效的算法，刪除表中所有大于mink且小于maxk的元素（若表中存在這樣的元素）delList(LinkL,Elemtypemink,Elemtypemaxk){Node*p;p=L;while(p->next!=NULL&&p->next->data<=mink)p=p->next;q=p->next;while(q!=NULL&&q->data<maxk){p->next=q->next;free(q);q=p->next;}}8.假設(shè)有兩個(gè)按元素值遞增有序排列的線性表A和B，均以單鏈表作存儲(chǔ)結(jié)構(gòu)，請(qǐng)編寫算法將A表和B表歸并成一個(gè)按元素值遞減有序排列的線性表C，并要求利用原表的結(jié)點(diǎn)空間構(gòu)造C表。LinkmergeAB(LinkLa,LinkLb){Node*pa,*pb,*q;LinkLc

pa=La->next;pb=Lb->next;Lc=La;Lc->next=NULL;free(Lb);

while(pa&&pb){if(pa->data<=pb->data){

}else{}}pa->next=Lc->next;Lc->next=pa;pa=pa->next;q=pa;pa->next=Lc->next;Lc->next=pa;pa=q->next;q=pa;q->next=Lc->next;Lc->next=q;pa=pa->next;q=pa->next;pa->next=Lc->next;Lc->next=pa;pa=q;q=pa;pa=pa->next;q->next=Lc->next;Lc->next=q;q=pb;pb=pb->next;q->next=Lc->next;Lc->next=q;/*將pa所指結(jié)點(diǎn)頭插到Lc表中，更新pa*//*將pb所指結(jié)點(diǎn)頭插到Lc表中，更新pb*/

if(pa){q=pa;pa=pa->next;q->next=Lc->next;Lc->next=q;}if(pb){q=pb;pb=pb->next;q->next=Lc->next;Lc->next=q;}return(Lc);}對(duì)嗎?while(pa){q=pa;pa=pa->next;q->next=Lc->next;Lc->next=q;}while(pb){q=pb;pb=pb->next;q->next=Lc->next;Lc->next=q;}return(Lc);}10.已知由單鏈表表示的線性表中含有三類字符的數(shù)據(jù)元素（如：字母字符、數(shù)字字符和其他字符），試編寫算法構(gòu)造三個(gè)以循環(huán)鏈表表示的線性表，使每個(gè)表中只含同一類字符，且利用原表中的結(jié)點(diǎn)空間作為三個(gè)表的結(jié)點(diǎn)空間，頭結(jié)點(diǎn)可另辟空間。departThr(LinkL,Link*LA,Link*LN;Link*LO){Node*q,*t;q=L->next;(*LA)=L;(*LA)->next=(*LA);(*LN)=(Link)malloc(sizeof(Node));(*LN)->next=(*LN);(*LO)=(Link)malloc(sizeof(Node));(*LO)->next=(*LO);while(q){t=q;q=q->next;if(isAlpha(t->data)){t->next=(*LA)->next;(*LA)->next=t;}elseif(isNum(t->data)){t->next=(*LN)->next;(*LN)->next=t;}else{t->next=(*LO)->next;(*LO)->next=t;}}}11.設(shè)線性表A=(a1,a2,a3,…,am,)，B=(b1,b2,b3,…,bn)，試編寫一個(gè)按下列規(guī)則合并A，B為線性表C的算法，使得：

C=(a1，b1，…，am，bm，bm+1，…，bn)，m≤n或者

C=(a1，b1，…，an，bn，an+1，…，