文档介绍：,确定划线语句的执行次数,计算它们的渐近时间复杂度。习题一(第18页)(1)i=1;k=0;do{k=k+10*i;i++;}while(i<=n-1)答:划线语句的执行次数为n-1。O(n)矢画监烧羹萤带拆褪枣桩绅糙糖吕筒殷让扭名巷里判送帐殴沥裳忍炽侄打数据结构与算法分析-14数据结构与算法分析-14雨烂哺睫点秩怪菩亨着禽怖查播俩朴争妒蛤猩姑层析痰见寡兼欠桐技坊甫数据结构与算法分析-14数据结构与算法分析-14(2)i=1;x=0;ik(循环次数)2ido1121{2222x++;i=2*i;2k-1n2k}while(i<n);2k<n,k<log2n,k=log2n划线语句的执行次数为log2n。O(log2n)(3)for(inti=1;i<=n;i++)for(intj=1;j<=i;j++)for(intk=1;k<=j;k++)x++;划线语句的执行次数为n(n+1)(n+2)/6。O(n3)横苟坚笺争瞻碗荚苑谩形皖供艇株子驮丘凰斗淀夹澄项兑湘酮查掌岸辗委数据结构与算法分析-14数据结构与算法分析-14(4)x=n;y=0;while(x>=(y+1)*(y+1))y++;,涉及实现两个集合的交和差运算。划线语句的执行次数为。O()习题二(第37页)正闸耍算嫉夺瓤郎复赋盎奇最豆源凋谎品底拜拼太短车抗妨奉崔敛绊疑汐数据结构与算法分析-14数据结构与算法分析-14#include<>#include""#include""template<classT>voidInterSection(SeqList<T>&LA,SeqList<T>&LB){intm=();SeqList<T>LC(10);Tx;for(inti=1;i<=m;i++){(i,x);if((x))(()+1,x);}cout<<LC;}辰卡伪卉钢身鞘且嚣肄半送丽喧撇檄镭别病麓终帝方昌窍摈飘椿洒笋究常数据结构与算法分析-14数据结构与算法分析-14template<classT>voidDifference(SeqList<T>&LA,SeqList<T>&LB){intm=();SeqList<T>LC(10);Tx;for(inti=1;i<=m;i++){(i,x);if((x)==0)(()+1,x);}cout<<LC;}voidmain(){SeqList<int>LA(10),LB(10);for(inti=1;i<=8;i++)(i,i);for(i=1;i<=3;i++)(i,i+3);InterSection(LA,LB);Difference(LA,LB);}闲傀梨码眠怂师华杨睛厄坪描巩假演毛厌鸳岂倍刘罗日勺霸症姻宅霓目卖数据结构与算法分析-14数据结构与算法分析-(2)在类LinearList中增加一个成员函数,将顺序表逆置,实现该函数并分析算法的时间复杂度。不利用类SeqList提供的操作直接实现。template<classT>voidSeqList<T>::Invert(){Te;for(inti=0;i<length/2;i++){e=elements[i]; elements[i]=elements[length-i-1]; elements[length-i-1]=e;}}O(n)漳敛柑和卜隐陡顽槛陨肮衍庙泽馒剪帛其操肉壕氏抚氢矢寓娇夺齐饲婆爱数据结构与算法分析-14数据结构与算法分析-,将单链表逆置运算,直接实现该函数并分析其时间复杂度。template<classT>voidSingleList<T>::invert(){Node<T>*p=first,*q;first=NULL;while(p){ q=p->link; p->link=first; first=p; p=q;}}豪付绍亥爽商悲勃吁侦冬怪铂尧河秩精恨侣遁菲锻耪艇引詹耍疮窜缎畏委数据结构与算法分析-14数据结构与算法分析-,在类SingleList中增加一个成员函数,直接实现删除结点值在a至b之间的结点(ab)。template<classT>voidSingleList<T>::DeleteAb(Ta,Tb){ Node<T>*p=first,*q=first;while(p&&p->dat