分析下列程序的上界O和下界W。 p=1 for i=1 to n^2 do for j=1 to i do p=p+i 该程序时间复杂度的上界是O（____）、下界是W（_____）。

程序 for i:=1 to n do for j:=1 to n do A[i, j]:=0; 的算法复杂性为【 】

下面的程序段中，对x的赋值语句的频度为()FORi:=1TOnDOFORj:=1TOnDOx:=x+1;

A、O(2n)

B、O(n)

C、O(n^2)

D、O(log2n)

A、n

B、n^3

C、n^2

D、nlogn

阅读程序：

Function fac(ByVal As Integer)As Integer

Dim temp As Integer

temp=1

For i％=1 To n

temp=temp*i％

Next i％

fac=temp

End Function

Private Sub Form. Click（ ）

Dim nsum As Integer

nsum=1

For i％=2 T0 4

nsum=nsum+fac(i％)

Next i％

Print nsum

End Sub

程序运行后，单击窗体，输出结果是（ ）。

A.35

B.31

C.33

D.37

Items (58) and (59) are based on the following Pascal code. for i:=1 to n -1 do begin k:=i: for j :=i+1 to n do if A[j]＜A[k] then k:=j: if k＜＞i then begin X:=A[k]; A[k]:=A[i]; A[i]:=x end; end;The sorting method described by the code is called

A．Insertion sort

B．Selection sort

C．Radix sort

D．Merge sort

线性搜索算法如下：

  Linear Search(A，x)  //数组A[1..n]，待查找对象x

  1．for i←1 to ndo

  2．if A[i]=x then return i  //查找成功

  3．return "no"  //查找失败

  设A的n个元素都不相同，x已在A中的概率为p(0≤p≤1)，并且当x在A中时，x等于A的每一个元素的可能性相等．试分析算法的平均时间复杂度．

The sorting method described by the following code is called( ). FOR i:=1 TO n—1 do BEGIN k: =i; FOR j: =i+1 TO n DO IF A[j]＜A[K] THEN k:=j; IF k＜＞i THEN BEGIN x:=A[k]; A[k]: = A[i]; A[i]:=x END END;

A．insertion sort

B．selection sort

C．radix sort

D．merge sort