这是一个递归调用，因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.4 (这时i=4， s=100) REPEAT语句先执行循环体，后判断条件，直到条件为真时退出循环。
21.算法在最好情况下，即二进制数的最后一位为零时，只作一次判断，未执行循环体，赋值语句A[i]执行了一次;最坏情况出现在二进制数各位均为1(最高位为零，因题目假设无溢出)，这时循环体执行了n-1次，时间复杂度是O(n)，循环体平均执行n/2次，时间复杂度仍是O(n)。
22.该算法功能是将原单循环链表分解成两个单循环链表：其一包括结点h到结点g的前驱结点;另一个包括结点g到结点h的前驱结点。时间复杂度是O(n)。
23.第一层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.O(n2),m的值等于赋值语句m:=m+1的运行次数，其计算式为 25.(1)O(1) (2)O(n2) (3)O(n3) 26.(1)O(n) (2)O(n2)
27.(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.从小到大排列为：logn, n1/2+logn, n, nlogn, n2+logn，n3, n-n3+7n5, 2n/2, (3/2)n, n!,(2n n).