#G117. GESP level5 递归算法

GESP level5 递归算法

GESP level5 - 递归算法

  1. 下面C++代码用于求斐波那契数列,该数列第1、2项为1,以后各项均是前两项之和。函数fibo()属于( )?
int fibo(int n) {
    if (n <= 0)
        return 0;
    if (n == 1 || n == 2)
        return 1;
    int a = 1, b = 1, next;
    for (int i = 3; i <= n; i++) {
        next = a + b;
        a = b;
        b = next;
    }
    return next;
}

{{ select(1) }}

  • 枚举算法
  • 贪心算法
  • 迭代算法
  • 递归算法
  1. 下面的C++代码以递归方式实现合并排序,并假设merge(int T[], int R[], int s, int m, int t)函数将有序的T[s..m]和T[m+1..t]归并到R[s..t]中。横线处应填上代码是( )?
void mergeSort(int SList[],int TList[],int s,int t,int len) {
    if(s==t) {
        TList[s] = SList[s];
        return;
    }
    int*T2 = new int[len];//保存中间结果
    int m = (s + t) / 2;
    // 在此处填入代码
    merge(T2, SList, s, m, t);
    delete T2;
    return ;
}

{{ select(2) }}

  • mergeSort(SList, T2, s, m, len), mergeSort(SList, T2, m, t, len)
  • mergeSort(SList, T2, s, m-1, len), mergeSort(SList, T2, m+1, t, len)
  • mergeSort(SList, T2, s, m, len), mergeSort(SList, T2, m+1, t, len)
  • mergeSort(SList, T2, s, m-1, len), mergeSort(SList, T2, m-1, t, len)
  1. 阅读下面的C++代码,执行后其输出是( )?
int stepCount = 0;
int fracA(int N) {
    stepCount += 1;
    cout << stepCount <";
    int rtn = 1;
    for(int i = 1; i <= N; i++)
        rtn *= i;
    return rtn;
}
int fracB(int N) {
    stepCount += 1;
    cout << stepCount <";
    if(N == 1)
        return 1;
    return N * fracB(N - 1);
}
int main() {
    cout << fracA(5);
    cout << "";
    cout << fracB(5);
    return 0;
}

{{ select(3) }}

  • 1->120<===>2->120
  • 1->120<===>1->120
  • 1->120<===>1->2->3->4->5->120
  • 1->120<===>2->3->4->5->6->120
  1. 下面C++代码用于求斐波那契数列,该数列第1、2项为1,以后各项均是前两项之和。下面有关说法错误的是( )?
int fiboA(int N) {
    if(N == 1 || N == 2)
        return 1;
    return fiboA(N - 1) + fiboA(N - 2);
}
int fiboB(int N) {
    if (N == 1 || N == 2)
        return 1;
    int last2 = 1, last1 = 1;
    int nowVal = 0;
    for(int i = 2; i < N; i++) {
        nowVal = last1 + last2;
        last2 = last1;
        last1 = nowVal;
    }
    return nowVal;
}

{{ select(4) }}

  • fiboA() 用递归方式,fiboB() 循环方式
  • fiboA() 更加符合斐波那契数列的数学定义,直观易于理解,而fiboB() 需要将数学定义转换为计算机程序实现
  • fiboA() 不仅仅更加符合数学定义,直观易于理解,且因代码量较少执行效率更高
  • fiboB() 虽然代码量有所增加,但其执行效率更高
  1. 有关下面C++代码说法正确的是( )?
int rc;
int foo(int x, int y) {
    int r;
    if(y == 0)
        r = x;
    else
        r = foo(y, x % y);
    rc++;
    return r;
}

{{ select(5) }}

  • 如果x 小于10, rc 值也不会超过20
  • foo 可能无限递归
  • foo 可以求出 x 和 y 的最大公共质因子
  • foo 能够求出 x 和 y 的最小公倍数
  1. 下面C++代码中的isPrimeA()和isPrimeB()都用于判断参数N是否素数,有关其时间复杂度的正确说法是( )?
bool isPrimeA(int N) {
    if(N < 2)
        return false;
    for(int i = 2; i <= N / 2; i++)
        if(N % i == 0)
            return false;
    return true;
}
bool isPrimeB(int N) {
    if(N < 2)
        return false;
    for (int i = 2; i <= sqrt(N); i++)
        if(N % i == 0)
            return false;
    return true;
}

{{ select(6) }}

  • isPrimeA() 的最坏时间复杂度是O(n/2), isPrimeB() 的最坏时间复杂度是O(logN), isPrimeA()优于isPrimeB()
  • isPrimeA() 的最坏时间复杂度是O(n), isPrimeB() 的最坏时间复杂度是O(√n), isPrimeB()绝大多数情况下优于isPrimeA()
  • isPrimeA() 的最坏时间复杂度是O(√n), isPrimeB() 的最坏时间复杂度是O(n), isPrimeA()优于isPrimeB()
  • isPrimeA() 的最坏时间复杂度是O(logN), isPrimeB() 的最坏时间复杂度是O(n), isPrimeA()优于isPrimeB()
  1. 下面C++代码以递归方式实现字符串反序,横线处应填上代码是( )?
//字符串反序
#include 
#include 
using namespace std;
string sReverse(string sIn) {
    if(sIn.length() > sIn;
    cout << sReverse(sIn) << endl;
    return 0;
}

{{ select(7) }}

  • sIn[sIn.length() - 1] + sReverse(sIn.substr(0, sIn.length() - 1))
  • sIn[0] + sReverse(sIn.substr(1, sIn.length() - 1))
  • sReverse(sIn.substr(0, sIn.length() - 1)) + sIn[sIn.length() - 1]
  • sReverse(sIn.substr(1, sIn.length() - 1)) + sIn[sIn.length() - 1]
  1. 印度古老的汉诺塔传说:创世时有三根金刚柱,其中一柱从下往上按照大小顺序摞着64片黄金圆盘,当圆盘逐一从一柱借助另外一柱全部移动到另外一柱时,宇宙毁灭。移动规则:在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。下面的C++代码以递归方式实现汉诺塔,横线处应填入代码是( )?
#include 
using namespace std;
//递归实现汉诺塔,将N个圆盘从A通过B移动C
//圆盘从底到顶,半径必须从大到小
void Hanoi(string A, string B, string C, int N) {
    if(N == 1) {
        cout << A <" << C << endl;
    } else {
        Hanoi(A, C, B, N - 1);
        cout << A <" << C << endl;
        // 在此处填入代码
    }
}
int main() {
    Hanoi("甲", "乙", "丙", 3);
    return 0;
}

{{ select(8) }}

  • Hanoi(B, C, A, N - 2)
  • Hanoi(B, A, C, N - 1)
  • Hanoi(A, B, C, N - 2)
  • Hanoi(C, B, A, N - 1)
  1. 下面代码中的isPrimeA()和isPrimeB()都用于判断参数N是否素数,有关其时间复杂度的正确说法是( )?
#include 
#include 
using namespace std;
bool isPrimeA(int N) {
    if(N < 2)
        return false;
    for(int i = 2; i < N; i++)
        if(N % i == 0)
            return false;
    return true;
}
bool isPrimeB(int N) {
    if(N < 2)
        return false;
    int endNum = int(sqrt(N));
    for(int i = 2; i <= endNum; i++)
        if(N % i == 0)
            return false;
    return true;
}
int main() {
    cout << boolalpha;
    cout << isPrimeA(13) << " " << isPrimeB(13) << endl;
    return 0;
}

{{ select(9) }}

  • isPrimeA() 的最坏时间复杂度是O(N), isPrimeB() 的最坏时间复杂度是O(log N), isPrimeB()优于isPrimeA()
  • isPrimeA() 的最坏时间复杂度是O(N), isPrimeB() 的最坏时间复杂度是O(√N), isPrimeB()优于isPrimeA()
  • isPrimeA() 的最坏时间复杂度是O(√N), isPrimeB() 的最坏时间复杂度是O(N), isPrimeA()优于isPrimeB()
  • isPrimeA() 的最坏时间复杂度是O(log N), isPrimeB() 的最坏时间复杂度是O(N), isPrimeA()优于isPrimeB()
  1. 下面代码执行后的输出是( )?
#include 
using namespace std;
int jumpFloor(int N) {
    cout << N << "#";
    if(N == 1 || N == 2) {
        return N;
    } else {
        return jumpFloor(N - 1) + jumpFloor(N - 2);
    }
}
int main() {
    cout << jumpFloor(4) << endl;
    return 0;
}

{{ select(10) }}

  • 4#3#2#2#4
  • 4#3#2#2#1#5
  • 4#3#2#1#2#4
  • 4#3#2#1#2#5
  1. 下面关于递归的说法,错误的是( )?

{{ select(11) }}

  • 递归函数必须有终止条件
  • 递归函数每次调用自身时,参数应向终止条件靠拢
  • 递归的空间复杂度一定比迭代高
  • 所有递归函数都可以用迭代方式实现
  • 快速排序算法不可以用迭代方式实现
  1. 对下面两个函数,说法错误的是( )?
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(12) }}

  • 两个函数的实现的功能相同
  • fibA采用递推方式
  • fibB采用的是递归方式
  • fibA时间复杂度为O(n),fibB的时间复杂度为O(n²)
  1. 给定如下函数:
int fun(int n) {
    if (n == 1)
        return 1;
    if (n == 2)
        return 2;
    return fun(n - 2) - fun(n - 1);
}

则当n=7时,函数返回值为( )? {{ select(13) }}

  • 0
  • 1
  • 21
  • -11
  1. 给定如下函数(函数功能同上题,增加输出打印):
int fun(int n) {
    cout << n << " ";
    if (n == 1)
        return 1;
    if (n == 2)
        return 2;
    return fun(n - 2) - fun(n - 1);
}

则当n=4时,屏幕上输出序列为( )? {{ select(14) }}

  • 4 3 2 1
  • 1 2 3 4
  • 4 2 3 1 2
  • 4 2 3 2 1
  1. 递归函数在调用自身时,必须满足( ),以避免无限递归?

{{ select(15) }}

  • 有终止条件
  • 函数参数递减(或递增)
  • 函数返回值固定
  • 以上都对