数据结构 | 每日一练（5）

数据结构

合抱之木,生于毫末;九层之台,起于累土;千里之行,始于足下

——老子

1

每日一练

1．已知如下程序段

FOR i:= n DOWNTO 1 DO {语句 1}

BEGIN

x:=x+1； {语句 2}

FOR j:=n DOWNTO i DO {语句 3}

y:=y+1; {语句 4}

END；

语句 1 执行的频度为 （1） ；语句 2 执行的频度为 （2） ；语句 3 执行的频度为 （3） ；语句 4 执

行的频度为 （4） 。

2．在下面的程序段中，对ｘ的赋值语句的频度为______（表示为 n 的函数）

FOR i：＝１ TO n DO

FOR j：＝１ TO i DO

FOR k：＝1 TO j DO

ｘ：＝ｘ＋delta；

3.下面程序段中带下划线的语句的执行次数的数量级是：

i：=1； WHILE i<n DO i：=i*2;

4. 下面程序段中带下划线的语句的执行次数的数量级是( )。

i:=1;

WHILE i<n BEGIN FOR j:=1 TO n DO x:=x+1;i:=i*2 END；

5. 下面程序段中带有下划线的语句的执行次数的数量级是( )

i：=n*n WHILE i<>1 DO i:=i div 2;

6. 计算机执行下面的语句时，语句 s 的执行次数为 _______ 。

FOR(i=l；i<n-l；i++)

FOR(j=n;j>=i;j--)

s;

7 下面程序段的时间复杂度为________。(n>1)

sum=1；

for (i=0;sum<n;i++) sum+=1;

正确答案

1.（1）n+1 （2）n （3）n(n+3)/2 （4）n(n+1)/2。

2.（1+2++（1+2+3）+…+（1+2+…+n）=n(n+1)(n+2)/6 O(n 3 )

3. log 2 n

4. nlog 2 n

5. log 2 n ^2

6. (n+3)(n-2)/2

7. O(n)

如果您觉得本篇文章对您有作用，请转发给更多的人，点一下好看就是对小编的最大支持！

-end-