求时间复杂度

求时间复杂度 答案 一、 选择 1 A 2 C 3 B 4 D 5 B 6 B 7 A 8 D 9 C 10 C 二、求时间复杂度 1、(n-1)*(m-1)～O,m*n, log1n，2、 ～O,logn, ,,33，， 23、n*,n-1,/2～O,n, 三、以下算法中的循环链不带头结点 Struct list {float price; Int number; Struct list *next; }sp; sp *insert(sp *head,int m,float h) { sp *q,*s;*p; s=(sp*)malloc(sizeof(sp)); s->price=h; s->number=m; if(head==NULL) //如果原链表中没有元素则建立一个单循环链表 {head=s; head->next=head; } Else //第一个结点的price值〉h,则把s所指结点作为第一个结点插入 {if,head->price > h, {q=head->next; //查找该循环链表的最后一个结点～由q指向 While(q!=head) q=q->next; s->next=head; head=s; q->next=head; } Else //查找相应的结点,q指向,～在之后插入s {q=head->next; While(q->data< h && q!=head){p=q; q=q->next;} s->next=q , //q前即p后插入结点s p->next=s; } } return(head); } 四、XSXXXSSSXXSXXSXXSSSS 五、 法一:orderstring *delall(orderstring *x,char ch) {int i=0,j,k,n; While(ilen) //找到该结点先用*代替 {if(x->vec[i]==ch)x->vec[i]=’*’; i++; } for(j=x->len-1;j>=0;j- -) //一次性从后向前删除值 为*的结点,减少结点移动次数～提高效率, if(x->vec[j]==’*’) {for(k=j;jlen;k++) x->vec[k]=x->vec[k+1]; x->len- -; } } 法二:直接从后往前查找并删除 法三:一空间换取时间，即增加一个响亮空间把不等于ch的字符都复制过去