数据结构与算法-第1、2章习题

数据结构——第1、2章习题解答第1章绪论4.（2）执行下面程序段的时间复杂度为

.

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

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

a[i][j]=i*j;（3）执行下面程序段时，语句S的执行次数为

。

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

for(intj=0;j<=i;j++)S;5.计算下面程序段中x=x+1的语句频度。

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

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

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

6.编写算法，求一元多项式

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

的值Pn(x0),并确定算法中每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用冪函数。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);}时间复杂度为O(n);语句执行次数为：

1

n1第2章线性表第2章线性表2.(2)已知L是无表头结点的单链表，且p结点既不是首元素结点，也不是尾元素结点，按要求从下列语句中选择合适的语句序列。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结点后插入S结点的语句序列是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结点前插入S结点的语句序列是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结点的语句序列是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结点的语句序列是JAGJGAGJAJEA4.已知顺序表L递增有序，编写一个算法，将X插入到线性表的适当位置上，以保持线性表的有序性。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;} 对吗?4.已知顺序表L递增有序，编写一个算法，将X插入到线性表的适当位置上，以保持线性表的有序性。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递增有序，编写一个算法，将X插入到线性表的适当位置上，以保持线性表的有序性。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.已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试编写一高效的算法，删除表中所有大于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;}}对吗?6.已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试编写一高效的算法，删除表中所有大于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.假设有两个按元素值递增有序排列的线性表A和B，均以单链表作存储结构，请编写算法将A表和B表归并成一个按元素值递减有序排列的线性表C，并要求利用原表的结点空间构造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所指结点头插到Lc表中，更新pa*//*将pb所指结点头插到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);}对吗?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.已知由单链表表示的线性表中含有三类字符的数据元素（如：字母字符、数字字符和其他字符），试编写算法构造三个以循环链表表示的线性表，使每个表中只含同一类字符，且利用原表中的结点空间作为三个表的结点空间，头结点可另辟空间。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.设线性表A=(a1,a2,a3,…,am,)，B=(b1,b2,b3,…,bn)，试编写一个按下列规则合并A，B为线性表C的算法，使得：

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

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