生科三班杨晓寒第三单元思考题

6、根据求斐波那契数列值的递归算法，写出求 fib （5） 的计算过程， 并说明递归算法的不足。/ 函数 fib 返回第 n（n 1）个斐波那契数列的值int fib(int n) if(n=1) return(1) else if(n=2) return(2) else return(fib(n-1)+fib(n-2) 如果要求第5 个斐波那契数列的值，则只要调用fib（5）即可。递归算法在程序实现时需要使用堆栈来储存中间结果、临时变量和返回地址，需要不断地进行入栈和出栈操作，而消耗资源，因此递归程序的执行效率相对较低。8、根据算法3-18 线性表折半查找算法，如果要查找的线性表长度为16，画出相应的折半查找树。116 17 916 13 57 911 1316 1.1 3.3 5.5 7.7 9.9 11.11 13.13 1516 16.16 8 4 12 6 2 5 13 3 1 10 7 11 9 16 13 15 9、对于算法3-19 简单选择排序算法，完成SelectionMin(f ，i，n） ，即写一算法求a0n中最小值的元素的序号。/ 对表 f 进行简单选择排序，n 为元素个数int SimpleSelectionSort （*f ，n） for（i=1;i<n;i+） J=SelectionMin（f,i,n）;/ 从 in 个元素中选择最小的元素，序号为j if （i!=j) fi fj 10、设元素序列为12，5，8，3，7， 20，31，15，画出快速排序的排序过程。12,5,8,3,7,20,31,15 3,5,8,12,7,20,31,15 3,5,7,12,8,20,31,15 3,5,7,12,8,15,20,31 3,5,7,8,12,15,20,31