数据结构1800题（答案全）(3)

设k的初值等于1。

【北京邮电大学 1997二（10分）】

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

i:=0;s:=0;n:=100;

REPEAT

i:=i+1;

s:=s+10*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)时的输出结果 。

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(\；

}

return (sum);

} 【华中理工大学 2000 六（10分）】

24．设n是偶数，试计算运行下列程序段后m的值并给出该程序段的时间复杂度。

m:=0;

FOR i:=1 TO n DO

FOR j:=2*i TO n DO

m:=m+1;

【南京邮电大学 2000 一、1】

25．有下列运行时间函数：

（1）T1 (n)=1000; （2）T2(n)=n2+1000n;

分别写出相应的大O表示的运算时间。

【吉林工业大学 1999 二（12分）】

26. 试给出下面两个算法的运算时间。

（1） for i←1 to n do

x ← x+1

END

（2） for i← 1 to n do

for j←1 to n do

x← x+1

end

end

3）T3(n)=3n3+100n2+n+1; （

【中科院自动化研究所 1995 二、2 （6分）】

27. 斐波那契数列Fn定义如下

F0=0， Fl=1， Fn=Fn-1+Fn-2, n=2,3...

请就此斐波那契数列，回答下列问题。

(1) (7分) 在递归计算Fn的时候，需要对较小的Fn-1，Fn-2，?, Fl, F0精确计算多少次?

(2) (5分) 如果用大O表示法，试给出递归计算Fn时递归函数的时间复杂度录多少?

【清华大学 2000 二（12分）】

28．将下列函数，按它们在n→∝时的无穷大阶数，从小到大排序。

n, n-n3+7n5, nlogn, 2n/2, n3, logn, n1/2+logn, (3/2)n, ,n!, n2+logn

【中科院计算所 1995 】

一、选择题 1.B 2.C 3.1C 3.2B 4.B 5.D 6.C 7.C 8.D 9.D 10.A 11.C 12.D 13.D 14.A 15.C 16.A 17.C

二、判断题 1. × 2. × 3.× 4.× 5. √ 6. × 7. × 8. √ 9.× 10.× 11.× 12. √ 13. ×

三．填空题 1．数据元素结构。

数据元素间关系2．集合 线性结构树形结构 图状结构或网状