GESP 5级客观题｜算法复杂度分析｜课后作业

考试频率：高频。本卷共 6 题。

1. 现在⽤如下代码来计算 $x^n$（$n$ 个 $x$相乘），其时间复杂度为（ ）。

double quick_power(double x, unsigned n) {
    if (n == 0) return 1;
    if (n == 1) return x;
    return quick_power(x, n / 2) * quick_power(x, n / 2) * ((n & 1) ? x : 1);
}

{{ select(1) }}

• $O(n)$
• $O(n^2)$
• $O(log n)$
• $O(n log n)$

2. 假设快速排序算法的输⼊是⼀个长度为 的已排序数组，且该快速排序算法在分治过程总是选择第⼀个元素作为基准元素。下⾯选项（ ）描述的是在这种情况下的快速排序⾏为。

   {{ select(2) }}

• 快速排序对于此类输⼊的表现最好，因为数组已经排序。
• 快速排序对于此类输⼊的时间复杂度是 $O(n log n)$。
• 快速排序对于此类输⼊的时间复杂度是 $O(n^2)$。
• 快速排序⽆法对此类数组进⾏排序，因为数组已经排序。

3. 关于分治算法，以下哪个说法正确？

   {{ select(3) }}

• 分治算法将问题分成⼦问题，然后分别解决⼦问题，最后合并结果。
• 归并排序不是分治算法的应⽤。
• 分治算法通常⽤于解决⼩规模问题。
• 分治算法的时间复杂度总是优于$O(n log (n))$。

4. 快速排序和归并排序的平均时间复杂度均为$O(nlogn)$ ，且都是稳定排序。

   {{ select(4) }}

• 对
• 错

5. 下面关于链表和数组的描述，错误的是（ ）。

   {{ select(5) }}

• 当数据数量不确定时，为了应对各种可能的情况，需要申请一个较大的数组，可能浪费空间；此时用链表比较合适，大小可动态调整。
• 在链表中访问节点的效率较低，时间复杂度为 $O(n)$。
• 链表插入和删除元素效率较低，时间复杂度为 $O(n)$。
• 链表的节点在内存中是分散存储的，通过指针连在一起。

6. 对下面两个函数，说法错误的是（ ）。

int fibA(int n)
{
    if (n <= 1)
        return n;

    int f1 = 0, f2 = 1;
    for (int i = 2; i <= n; ++i)
    {
        int temp = f2;
        f2 = f1 + f2;
        f1 = temp;
    }
    return f2;
}

int fibB(int n)
{
    if (n <= 1)
        return n;
    return fibB(n - 1) + fibB(n - 2);
}

{{ select(6) }}

• 两个函数的实现的功能相同。
• fibA采用递推方式。
• fibB采用的是递归方式。
• fibA时间复杂度为 $O(n)$，fibB的时间复杂度为 $O(n^2)$ 。