PROCEDURE    perm  ( a: ar; k, n: integer);
     VAR   x: datatype;     i:integer;
     BEGIN
       （1）IF k=n
            THEN BEGIN
                （2）FOR  i:=1  TO  n DO
                （3）write (a[i]);
                     writeln;
                 END
             ELSE BEGIN
                （4） FOR   i:=k  TO  n  DO
                （5）a[i]:=a[i]+i*i;
                （6） perm (a, k+1, n);
                  END;
         END;
设k的初值等于1。
【北京邮电大学 1997二（10分）】
(1)n   (2)n+1  (3)n  (4)(n+4)(n-1)/2  (5)(n+2)(n-1)/2  (6)n-1
 这是一个递归调用，因k的初值为1，由语句（6）知，每次调用k增1，故第(1)语句执行n次。（2）是FOR循环语句，在满足(1)的条件下执行，该语句进入循环体(3)n次，加上最后一次判断出界，故执行了n+1次。(4)也是循环语句，当k=1时判断n+1次（进入循环体(5)n次），k=2时判断n次，最后一次k=n-1时判断3次，故执行次数是（n+1）+n+…+3=(n+4)(n-1)/2次。语句(5)是(4)的循环体，每次比(4)少一次判断，故执行次数是n+(n-1)+…+2=(n+2)(n-1)/2次。注意分析时，不要把(2)分析成n次，更不是1次。

20. 分析下面程序段中循环语句的执行次数。
i:=0;s:=0;n:=100;
REPEAT
   i:=i+1;
   s:=s+10*i;
UNTIL  NOT((i<n) AND (s<n));
【北京邮电大学 1998 四、1（5分）】
4 （这时i=4， s=100）  REPEAT语句先执行循环体，后判断条件，直到条件为真时退出循环。
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分）】
算法在最好情况下，即二进制数的最后一位为零时，只作一次判断，未执行循环体，赋值语句A[i]执行了一次；最坏情况出现在二进制数各位均为1（最高位为零，因题目假设无溢出），这时循环体执行了n-1次，时间复杂度是O(n)，循环体平均执行n/2次，时间复杂度仍是O(n)。
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分）】

该算法功能是将原单循环链表分解成两个单循环链表：其一包括结点h到结点g的前驱结点；另一个包括结点g到结点h的前驱结点。时间复杂度是O(n)。
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<n+1;i++)
               {for(j=n;j>i-1; j--)
                 for(k=1;k<j+1;k++ )
 sum++;
                 printf("sum=%d\n",sum)；
}
              return (sum);
}  【华中理工大学 2000 六（10分）】
第一层FOR循环判断n+1次，往下执行n次，第二层FOR执行次数为(n+(n-1)+(n-2)+…+1)，第三层循环体受第一层循环和第二层循环的控制，其执行次数如下表：
          i=     1    2    3    …   n  
         j=n     n    n    n    …   n
         j=n-1   n-1  n-1  n-1  …
          …     …   …   …
j=3     3    3
j=2     2    2
j=1     1
执行次数为(1+2+…+n)+(2+3+…+n)+…+n=n*n(n+1)/2-n(n2-1)/6。在n=5时，f(5)=55，执行过程中，输出结果为：sum=15,sum=29,sum=41,sum=50,sum=55（每个sum= 占一行,为节省篇幅，这里省去换行）。

24．设n是偶数，试计算运行下列程序段后m的值并给出该程序段的时间复杂度。
m:=0;
FOR  i:=1  TO  n  DO
  FOR  j:=2*i  TO  n  DO
      m:=m+1;
【南京邮电大学 2000 一、1】
O(n2),m的值等于赋值语句m:=m+1的运行次数，其计算式为

25．有下列运行时间函数：
（1）T1 (n)=1000;    （2）T2(n)=n2+1000n;     （3）T3(n)=3n3+100n2+n+1;
分别写出相应的大O表示的运算时间。
(1)O(1)  (2)O(n2)  (3)O(n3)
【吉林工业大学 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
【中科院自动化研究所 1995 二、2 （6分）】
(1)O(n)   (2)O(n2)
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分）】
（1）由斐波那契数列的定义可得：
Fn=Fn-1+Fn-2
  =2Fn-2+Fn-3
  =3Fn-3+2Fn-4
  =5Fn-4+3Fn-5
  =8Fn-5+5Fn-6
     ……
  =pF1+qF0
设Fm的执行次数为Bm(m=0、1、2、…、n-1)，由以上等式可知，Fn-1被执行一次，即Bn-1=1；Fn-2被执行两次，即Bn-2=2；直至F1被执行p次、F0被执行q次，即B1=p，B0=q。Bm的执行次数为前两等式第一因式系数之和，即Bm=Bm-1+Bm-2，再有Bn-1=1和Bn-2=2，这也是一个斐波那契数列。可以解得：
Bm= [( )n-m+2-( )n-m+2]      (m=0,1,2,…,n-1)
（2）时间复杂度为O(n)

28．将下列函数，按它们在n→∝时的无穷大阶数，从小到大排序。
    n, n-n3+7n5, nlogn, 2n/2, n3, logn, n1/2+logn, (3/2)n,  ,n!, n2+logn
【中科院计算所 1995 080385】
从小到大排列为：logn, n1/2+logn, n, nlogn, n2+logn，n3,  n-n3+7n5, 2n/2, (3/2)n, n!,