经验分享 – 数据结构 | 每日一练(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.在下面的程序段中,对x的赋值语句的频度为______(表示为 n 的函数)

FOR i:=1 TO n DO

FOR j:=1 TO i DO

FOR k:=1 TO j DO

x:=x+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-

正文完