数据结构第1章 绪论[6]

分析下面程序段中循环语句的执行次数

i:=;s:=;n:=;

REPEAT

i:=i+;

s:=s+*i;

UNTIL NOT((i

【北京邮电大学 1998 四、1(5分)】

21.下列算法对一n位二进制数加1，假如无溢出，该算法的最坏时间复杂性是什么?并分析它的平均时间复杂性。

TYPE num=ARRAY [1..n] of [0..1];

PROCEDURE Inc (VAR a：num);

VAR i：integer;

BEGIN i：=n;

WHILE A[i]=1 DO

BEGIN A[i]：=0; i：=i-1;END;

END;

A[i]：=1;

END Inc;

【东南大学1998 三 (8分) 1994 二(15分)】

22. 阅读下列算法，指出算法A的功能和时间复杂性

PROCEDURE A (h,g:pointer);

(h,g分别为单循环链表(single linked circular list)中两个结点指针)

PROCEDURE B(s,q:pointer);

VAR p:pointer;

BEGIN

p:=s;

WHILE p^.next<>q DO p:=p^.next;

p^.next:=s;

END;(of B)

BEGIN

B(h,g); B(g,h);

END;(of A)

【东南大学 1999 二(10分)】

23. 调用下列C函数f(n)或PASACAL函数f(n) 回答下列问题 :

(1) 试指出f(n)值的大小，并写出f(n) 值的推导过程;

(2) 假定n= 5，试指出f(5)值的大小和执行f(5)时的输出结果 。tw.wiNgwiT.coM

C函数： int f(int n)

{ int i,j，k,sum= 0;

for(i=l; i

{for(j=n;j>i-1; j--)

for(k=1;k

sum++;

printf("sum=%d\n",sum);

}

return (sum);

} 【华中理工大学 2000 六(10分)】

[1] [2] [3] [4] [5] [6] [7]