1第1章绪论2.(1)×(2)×(3)√3.〔1〕A〔2〕C〔3〕C5.计算以下程序中x=x+1的语句频度for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x=x+1;【解答】x=x+1的语句频度为:T(n)=1+(1+2)+〔1+2+3〕+⋯⋯+〔1+2+⋯⋯+n〕=n(n+1)(n+2)/66.编写算法,求一元多项式pn(x)=a0+a1x+a2x2+⋯⋯.+anxn的值pn(x0),并确定算法中每一语句的执行次数和整个算法的时间复杂度,要求时间复杂度尽可能小,规定算法中不能使用求幂函数。注意:此题中的输入为ai(i=0,1,⋯n)、x和n,输出为Pn(x0)。算法的输入和输出采用以下方法〔1〕通过参数表中的参数显式传递〔2〕通过全局变量隐式传递。讨论两种方法的优缺点,并在算法中以你认为较好的一种实现输入输出。【解答】〔1〕通过参数表中的参数显式传递优点:当没有调用函数时,不占用内存,调用结束后形参被释放,实参维持,函数通用性强,移置性强。缺点:形参须与实参对应,且返回值数量有限。〔2〕通过全局变量隐式传递优点:减少实参与形参的个数,从而减少内存空间以及传递数据时的时间消耗缺点:函数通用性降低,移植性差算法如下:通过全局变量隐式传递参数PolyValue(){inti,n;floatx,a[],p;printf(“nn=”);scanf(“%f”,&n);printf(“nx=”);scanf(“%f”,&x);for(i=0;inext=S;BP->next=P->next->next;CP->next=S->next;DS->next=P->next;ES->next=L;FS->next=NULL;GQ=P;Hwhile(P->next!=Q)P=P->next;Iwhile(P->next!=NULL)P=P->next;JP=Q;KP=L;LL=S;3ML=P;(3)D(4)D(5)D(6)A7试分别以不同的存储结构实现单线表的就地逆置算法,即在原表的存储空间将线性表〔a1,a2,⋯,an〕逆置为(an,an-1,⋯,a1)。【解答】〔1〕用一维数组作为存储结构voidinvert(SeqList*L,int*num){intj;ElemTypetmp;for(j=0;j<=(*num-1)/2;j++){tmp=L[j];L[j]=L[*num-j-1];L[*num-j-1]=tmp;}}〔2〕用单链表作为存储结构voidinvert(LinkListL){Node*p,*q,*r;if(L->next==NULL)return;/*链表为空*/p=L->next;q=p->next;p->next=NULL;/*摘下第一个结点,生成初始逆置表*/while(q!=NULL)/*从第二个结点起依次头插入当前逆置表*/{r=q->next;q->next=L->next;L->next=q;q=r;}}11将线性表A=(a1,a2,⋯⋯am),B=(b1,b2,⋯⋯bn)合并成线性表C,C=(a1,b1,⋯⋯am,bm,bm+1,⋯⋯.bn)当m<=n时,或C=(a1,b1,⋯⋯an,bn,an+1,⋯⋯am)当m>n时,线性表A、B、C以单链表作为存储结构,且C表利用A表和B表中的结点空间构成。注意:单链表的长度值m和n均未显式存储。【解答】算法如下:LinkListmerge(LinkListA,LinkListB,LinkListC){Node*pa,*qa,*pb,*qb,*p;pa=A->next;/*pa表示A的当前结点*/pb=B->next;p=A;/*利用p来...