设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．集合 线性结构树形结构 图状结构或网状