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

 这是┅个递归调用因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. 分析下面程序段中循环語句的执行次数。

【北京邮电大学 1998 四、1（5分）】

4 （这时i=4 s=100）  REPEAT语句先执行循环体，后判断条件直到条件为真时退出循环。

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

算法在最好情况下即二进制数的最后一位為零时，只作一次判断未执行循环体，赋值语句A[i]执行了一次；最坏情况出现在二进制数各位均为1（最高位为零因题目假设无溢出），這时循环体执行了n-1次时间复杂度是O(n)，循环体平均执行n/2次时间复杂度仍是O(n)。

【东南大学 1999 二（10分）】

该算法功能是将原单循环链表分解成兩个单循环链表：其一包括结点h到结点g的前驱结点；另一个包括结点g到结点h的前驱结点时间复杂度是O(n)。

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

第一层FOR循环判断n+1次，往下执行n次第二层FOR执行次数为(n+(n-1)+(n-2)+…+1)，第三层循环体受第一层循环和第二层循环的控制其执行次数如下表：

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

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

O(n2),m的值等于赋值语句m:=m+1的运行次数，其计算式为

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

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

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

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

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

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

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

（1）由斐波那契数列的定义可得：

设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=qBm的执行次数为前两等式第一因式系數之和，即Bm=Bm-1+Bm-2再有Bn-1=1和Bn-2=2，这也是一个斐波那契数列可以解得：

（2）时间复杂度为O(n)

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