试分析下面各程序段的时间复杂度。 x=n; //n＞1 y=0; while（x≥（y+1)* （y+1)) y++;

A．O(log2n)

B．O(n)

C．O(nlog2n)

D．O(n2)

A．O(log2n)

B．O(n)

C．O(nlog2n)

D．O(n2)

A．O(log2n)

B．O(n)

C．O(nlog2n)

D．O(n2)

A．O(log2n)

B．O(n)

C．0(nlog2n)

D．O(n2)

A.O(1)

B.O(logn)

C.O(n)

D.O(n^2)

阅读下列函数说明，将应填入(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'的首元，则A<B:否则A>B。

提示：算法的基本思想为：若相等，则j+l，之后继续比较后继元素；否则即可得出比较结果。显然，j的初值应为0，循环的条件是j不超出其中任何一个表的范围。若在循环内不能得出比较结果，则循环结束时有3种可能出现的情况需要区分。

【函数1】

int compare(SqListA，SqList B)

{

//若A<B，则返回-1；若A=B，则返回0:若A>B，则返回1

j=0；

while(i< (1) ＆＆j<

B．length)

if(A．elem[j]<

B．elem[j])return(-1)；

else if(A．elem[j]>

B．elem[j])return (1) ；

else (2) ；

if(A．length==

B．length)return(0)；

else if(A．length<

B．length)return(-1)；

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<m＆＆p)//查找am所在结点

{

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) 。

范围树(176页习题[8-20])稍作调整之后，固然也可交持半无穷范围查询，但若能针对这一特定问题所固有的性质，改用优先级搜索树(priority search tree，PST)之类的数据结构，则不仅可以保持O(r+logn)的最优时间效率，而且更重要的是，可以将空间复杂度从范围树的O(nlogn)优化至O(n)。

如图x10.3所示，优先级搜索树除了首先在拓扑上应是一棵二叉树，还同时遵守以下三条规则。

①首先，各节点的y坐标均不小于其左右孩子(如果存在)——因此，整体上可以视作为以y坐标为优先级的二叉堆。

②此外，相对于任一父节点，左子树中节点的x坐标均不得大于右子树中的节点。

③最后，互为兄弟的每一对左、右子树，在规模上相差不得超过一。

a)试按照以上描述，用C/C++定义并实现优先级搜索树结构;

b)试设计一个算法，在O(nlogn)时间内将平面上的n个点组织为一棵优先级搜索树;

c)试设计一个算法，利用已创建的优先级搜索树，在O(r+logn)时间内完成每次半无穷范围查询，其中r为实际命中并被报告的点数。