C 语言斐波那契数列 MCQ 练习题 2

说明

• 正确答案是选项“b”。构成斐波那契数列的数字都是前面两个数字之和。数列中的每个新数字都是通过将前面两个数字相加确定的，从 0 和 1 开始。这是斐波那契数列的正式定义
  F(0) = 0
  F(1) = 1
  F(n) = F(n-1) + F(n-2) 对于 n ≥ 2

说明

• 正确答案是选项“c”。斐波那契数列的递归定义需要基本情况来终止递归并提供初始值。基本情况是
• F(0) = 0 表示零的斐波那契数。
• 第一个斐波那契数 F(1) = 1 的定义。
• 如果没有这些基本情况，递归函数将无法终止递归。

说明

• 正确答案是选项“c”。对于大于 1 的任何 n 值，函数在朴素递归方法中会调用自身两次，导致调用的次数呈指数级增长。因此，需要反复解决许多重叠的子问题。
• 例如，F(n)=F(n−1) + F (n−2) 是 F(n) 的朴素递归计算。
• 因此，会产生一个递归调用的二叉树，当 n 增大时，调用的次数呈指数级增长。这棵递归树的高度为 n，时间复杂度为 O(2^n)，因为树的每一层都会使调用次数加倍。

说明

• 正确答案是选项“c”。使用朴素递归方法生成斐波那契数的时间复杂度很高。这是由于涉及大量冗余计算。由于每次计算每个斐波那契数都会进行大量计算，因此函数调用次数呈指数级增长。具体来说，由于时间复杂度为O(2^n)，因此该方法对于较大的 n 值非常低效。

说明

• 正确答案是选项“a”。要确定 fib(5) 中 fib(2) 被调用的次数。

fib(5) 调用 fib(4) 和 fib(3)

fib(4) 调用 fib(3) 和 fib(2)

fib(3) 调用 fib(2) 和 fib(1)

计算 fib(2) 的调用次数。

fib(5) 导致 fib(4) -> fib(3) -> fib(2) (第 1 次调用)

fib(4) 直接调用 fib(2) (第 2 次调用)

fib(3) 直接调用 fib(2) (第 3 次调用)

因此，使用朴素递归方法，计算 fib(5) 会调用 fib(2) 三次。

说明

• 正确答案是选项“d”。与简单的递归方法相比，生成斐波那契数的迭代方法具有以下优点：它只需要几个变量来存储前一个和当前的斐波那契数，并且使用恒定的空间，即O(1)。

说明

• 正确答案是选项“b”。斐波那契数列中的每个数字都定义为它之前的两个数字之和，通常以 0 和 1 开头。顺序从 0 开始；1, 1, 2, 3, 5, 8, 13, 21, 34,...
• 前十个斐波那契数的总和可以通过 F0=0, F1=1, F2=1, F3=2, F4=3, F5=5, F6=8, F7=13, F8=21, F9=34 来找到。

将这些数字加在一起

0+1+1+2+3+5+8+13+21+34

前 10 个斐波那契数的和是 88。