设n为正整数。则下面程序段的时间复杂度为()。 i=1;k=0; while(i<=n-1){ @ k+=10*i; i++; }
A.O(1)
B.O(n
C.O(nlogn)
D.O(n2)
A.O(1)
B.O(n
C.O(nlogn)
D.O(n2)
阅读下列函数说明,将应填入(n)处的字句写在答卷纸的对应栏内。
【函数1说明】
函数compare(SqList A,SqList B)的功能是:设A=(al,…,am)和B=(bl,…,bn)均为顺序表,"比较",两个顺序表A和B的大小。设A'和B'分别为A和B中除去最大共同前缀后的子表(例如,A=(y,x,x,z,x,z),B=(y,x,x,z,y,x,x,z),则两者中最大的共同前缀为(y,x,x,z),在两表中除去最大共同前缀后的子表分别为A′=(x,z)和B′=(y,x,x,z))。若A′=B′=空表,则A=B;若A′=空表,而B′≠空表,或者两者均不为空表,且A′的首元小于B'的首元,则AB。
提示:算法的基本思想为:若相等,则j+l,之后继续比较后继元素;否则即可得出比较结果。显然,j的初值应为0,循环的条件是j不超出其中任何一个表的范围。若在循环内不能得出比较结果,则循环结束时有3种可能出现的情况需要区分。
【函数1】
int compare(SqListA,SqList B)
{
//若AB,则返回1
j=0;
while(i< (1) &&j$amp;B.length);$br>
if(A.elem[j]$amp;B.elem[j])return(-1);;$br>
else if(A.elem[j]>
B.elem[j])return (1) ;
else (2) ;
if(A.length==
B.length)return(0);
else if(A.length$amp;B.length)return(-1);;$br>
else return (1) ;
}//compare
//函数1的时间复杂度是 (3) 。
【函数2说明】
函数exchange_L(SLink&L,int m)的功能是:用尽可能少的辅助空间将单链表中前m个结点和后n个结点的互换。即将单链表(a1,a2…,am,b1,b2,…,bn)改变成(b1,b2,…,bn,a1,a2,…,am)。
【函数2】
void exchange_L(SLink &L,int m)
{
if((4) &&L->next)//链表不空且m!=0
{
P=L->next;k=1;
while(k
{
P= (5) ;++k;
}
if((6) &&p->next)//n!=0时才需要修改指针
{
ha=L->next;//以指针ha记a1结点的位置
L->next=p->next;//将b1结点链接在头结点之后
p->next=NULL;//设am的后继为空
q= (7) ;//令q指向b1结点
while(q->next)q= (8) ;//查找bn结点
q->next= (9) ;//将a1结点链接到bn结点之后
}
}
}
//函数2的时间复杂度是 (10) 。
B、O(n)
C、O(nlogn)
D、O(n^2)
为了保护您的账号安全,请在“简答题”公众号进行验证,点击“官网服务”-“账号验证”后输入验证码“”完成验证,验证成功后方可继续查看答案!