您好,欢迎访问三七文档
11.4、试编写算法,求一元多项式Pn(x)=a0+a1x+a2x2+a3x3+…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;in;i++)scanf(“%f”,&a[i]);/*执行次数:n次*/p=a[0];for(i=1;i=n;i++){p=p+a[i]*x;/*执行次数:n次*/x=x*x;}printf(“%f”,p);}算法的时间复杂度:T(n)=O(n)通过参数表中的参数显式传递floatPolyValue(floata[],floatx,intn){floatp,s;inti;p=x;s=a[0];for(i=1;i=n;i++){s=s+a[i]*p;/*执行次数:n次*/p=p*x;}return(p);}算法的时间复杂度:T(n)=O(n)[techer's]#includestdio.h#defineMAXSIZE10floatpnx(floata[],floatx,intn){intj;floatsum=0.0;for(j=n;j0;j--)/*a[0]=a0,[a1]=a1,...*/sum=(sum+a[j])*x;sum=sum+a[0];return(sum);}voidmain(){2intn,i;floata[MAXSIZE],x,result;printf(Inputthevalueofx:\n);scanf(%f,&x);printf(\n);printf(InputThen:\n);scanf(%d,&n);printf(\n);printf(Inputa0,a1,...an:);for(i=0;i=n;i++)scanf(%f,&a[i]);printf(\n);result=pnx(a,x,n);printf(Theresultis:%f\n,result);}2.4已知线性表L递增有序。试写一算法,将X插入到L的适当位置上,以保持线性表L的有序性。StatusInsert_SqList(SqList&va,intx)//把x插入递增有序表va中{if(va.length+1va.listsize)returnERROR;va.length++;for(i=va.length-1;va.elem[i]x&&i=0;i--)va.elem[i+1]=va.elem[i];va.elem[i+1]=x;returnOK;}//Insert_SqList[teacher's]intInsList_Sort(SeqList*L,elemtypee){inti;if(L-last=MAXSIZE-1){printf(表已满无法插入!);return(0);}i=L-last;while((i=0)&&(eL-elem[i]))/*寻找插入位置并移动元素*/{L-elem[i+1]=L-elem[i];i--;}L-elem[i+1]=e;/*即使L为空,处理也相同*/L-last++;return(1);}2.5写一算法,从顺序表中删除自第i个元素开始的k个元素。[提示]:注意检查i和k的合法性。(集体搬迁,“新房”、“旧房”)方法1以待移动元素下标m(“旧房号”)为中心,计算应移入位置(“新房号”):for(m=i-1+k;m=L-last;m++)L-elem[m-k]=L-elem[m];3方法2同时以待移动元素下标m和应移入位置j为中心:方法2以应移入位置j为中心,计算待移动元素下标:[teacher's]intDelList_k(SeqList*L,inti,intk){/*假定从i往后的元素个数不足k个时,仅删除其后的所有元素*/intcount,j;if((iL-last+1)||(k1))return(0);count=L-last-i+1;/*计算i后的元素个数*/j=i+k-1;while(j=L-last)/*将i+k位置以后的元素向前移动*/{L-elem[j-k]=L-elem[j];j++;/*原算法中的count--;去掉*/}if(count=k)L-last=L-last-k;/*改变指向尾元的位置值*/elseL-last=L-last-count;/*被删元素数少于k个时*/return(1);}2.6已知线性表中的元素(整数)以值递增有序排列,并以单链表作存储结构。试写一高效算法,删除表中所有大于mink且小于maxk的元素(若表中存在这样的元素),分析你的算法的时间复杂度(注意:mink和maxk是给定的两个参变量,它们的值为任意的整数)。StatusDelete_Between(Linklist&L,intmink,intmaxk)//删除元素递增排列的链表L中值大于mink且小于maxk的所有元素{p=L;while(p-next-data=mink)p=p-next;//p是最后一个不大于mink的元素if(p-next)//如果还有比mink更大的元素{q=p-next;while(q-datamaxk)q=q-next;//q是第一个不小于maxk的元素p-next=q;}}//Delete_Between2.7试分别以不同的存储结构实现线性表的就地逆置算法,即在原表的存储空间将线性表(a1,a2...,an)逆置为(an,an-1,...,a1)。(1)以一维数组作存储结构,设线性表存于a(1:arrsize)的前elenum个分量中。(2)以单链表作存储结构。[方法1]:在原头结点后重新头插一遍[方法2]:可设三个同步移动的指针p,q,r,将q的后继r改为p[teacher's]#includestdio.h//2.7.1#defineMAXSIZE10voidcreatedata(intx[],intn){inti;if(n=MAXSIZE){printf(ERROR!);exit();}for(i=0;in;i++)x[i]=i+i;}4voidreverse1(intx[],intn){inttmp,i,k;if(n=MAXSIZE){printf(OverFlow!);exit();}k=0;for(i=n-1;i=n/2;i--){tmp=x[i];x[i]=x[k];x[k]=tmp;k++;}}voiddisparray(intx[],intn){inti;if(n=MAXSIZE){printf(ERROR!);exit();}for(i=0;in;i++)printf(%d,x[i]);}voidmain(){inta[MAXSIZE];createdata(a,8);reverse1(a,8);disparray(a,8);}#includestdio.h//2.7.2typedefstructnode{intx;structnode*next;}snode,*Linklist;Linklistcreate(){snode*head,*rear,*s;inty;head=(Linklist)malloc(sizeof(snode));rear=head;scanf(%d,&y);while(y!=-1){s=(Linklist)malloc(sizeof(snode));s-x=y;rear-next=s;rear=s;5scanf(%d,&y);}rear-next=NULL;return(head);}Linklistreverse2(snode*head){Linklistp,q;p=head-next;head-next=NULL;while(p){q=p;/*采用头插法,q指向待插节点,p指向下一个*/p=p-next;q-next=head-next;head-next=q;}return(head);}main(){Linklisth,p;h=create();p=h-next;while(p){printf(%5d,p-x);p=p-next;}h=reverse(h);printf(\n);p=h-next;while(p){printf(%5d,p-x);p=p-next;}}2.8假设两个按元素值递增有序排列的线性表A和B,均以单链表作为存储结构,请编写算法,将A表和B表归并成一个按元素值递减有序的排列的线性表C,并要求利用原表(即A表和B表的)结点空间存放表C.[teacher's]/*ch2_8合并并逆置链表*/#includestdio.htypedefstructnode{intx;structnode*next;}snode,*Linklist;6Linklistcreate(){snode*head,*rear,*s;inty;head=(Linklist)malloc(sizeof(snode));rear=head;scanf(%d,&y);while(y!=-1){s=(Linklist)malloc(sizeof(snode));s-x=y;rear-next=s;rear=s;scanf(%d,&y);}rear-next=NULL;return(head);}Linklistmerge(snode*head1,snode*head2){Linklisthead,p,q,s;p=head1-next;/*指向A的首元节点*/q=head2-next;/*指向B的首元节点*/head=head1;/*以链表A的头节点做C的头节点*/head-next=NULL;free(head2);/*释放B的头节点*/while(p!=NULL&&q!=NULL)/*用头插法挑选元素插入*/{if(p-xq-x){s=p;p=p-next;}else{s=q;q=q-next;}s-next=head-next;head-next=s;}if(p==NULL)p=q;while(p){s=p;p=p-next;s-next=head-next;head-next=s;}return(head);}main(){Linklisth,h1,h2,p,q;h1=create();h2=create();printf(\n******************************\n);p=h1-next;while(p)/*显示链表A的数据*/{printf(%5d,p-x);7p=p-next;}printf(\n******************************\n);q=h2-next;while(q)/*显示链表B的数据*/{printf(%5d,q-x);q=q-next;}h=merge(h1,h2);p=h-next;printf(\n*********************
本文标题:第一章第二章算法题
链接地址:https://www.777doc.com/doc-2204503 .html