数据结构各章作业题目及答案 数据结构第一章 绪论答案[3]

数据结构第一章 绪论答案[3]  

　　这是一个递归调用 因k的初值为 由语句( )知 每次调用k增 故第( )语句执行n次 ( )是FOR循环语句 在满足( )的条件下执行 该语句进入循环体( )n次 加上最后一次判断出界 故执行了n+ 次 ( )也是循环语句 当k= 时判断n+ 次(进入循环体( )n次) k= 时判断n次 最后一次k=n 时判断 次 故执行次数是(n+ )+n+…+ =(n+ )(n )/ 次 语句( )是( )的循环体 每次比( )少一次判断 故执行次数是n+(n )+…+ =(n+ )(n )/ 次 注意分析时 不要把( )分析成n次 更不是 次

　　 (这时i= s= ) REPEAT语句先执行循环体 后判断条件 直到条件为真时退出循环

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

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

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

　　i= … n

　　j=n n n n … n

　　j=n n n n …

　　… … … …

　　j=

　　j=

　　j=

　　执行次数为( + +…+n)+( + +…+n)+…+n=n*n(n+ )/ n(n )/ 在n= 时 f( )= 执行过程中 输出结果为 sum= sum= sum= sum= sum= (每个sum= 占一行 为节省篇幅 这里省去换行)

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

　　 ( )由斐波那契数列的定义可得

　　Fn=Fn +Fn

　　= Fn +Fn

　　= Fn + Fn

　　= Fn + Fn

　　= Fn + Fn

　　……

　　=pF +qF

　　设Fm的执行次数为Bm(m= … n ) 由以上等式可知 Fn 被执行一次 即Bn = ;Fn 被执行两次 即Bn = ;直至F 被执行p次 F 被执行q次 即B =p B =q Bm的执行次数为前两等式第一因式系数之和 即Bm=Bm +Bm 再有Bn = 和Bn = 这也是一个斐波那契数列 可以解得

　　Bm= [( )n m+ ( )n m+ ] (m= … n )

　　( )时间复杂度为O(n)

　　 从小到大排列为 logn n / +logn n nlogn n +logn n n n + n n/ ( / )n n! ( n n)