Question

数据结构第1章 绪论[6]

Answer 1

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

　　i:= ;s:= ;n:= ;

　　REPEAT

　　i:=i+ ;

　　s:=s+ *i;

　　UNTIL NOT((i <n) p="" and="" (s<n));

　　【北京邮电大学 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)时的输出结果 。tW.WinGWiT

　　C函数： int f(int n)

　　{ int i,j，k,sum= 0;

　　for(i=l; i <n+1;i++) p=""> </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分)】

lishixinzhi/Article/program/sjjg/201311/22836