#G117. GESP level5 递归算法
GESP level5 递归算法
GESP level5 - 递归算法
- 下面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) }}
- 枚举算法
- 贪心算法
- 迭代算法
- 递归算法
- 下面的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)
- 阅读下面的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
- 下面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() 虽然代码量有所增加,但其执行效率更高
- 有关下面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 的最小公倍数
- 下面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()
- 下面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]
- 印度古老的汉诺塔传说:创世时有三根金刚柱,其中一柱从下往上按照大小顺序摞着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)
- 下面代码中的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()
- 下面代码执行后的输出是( )?
#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
- 下面关于递归的说法,错误的是( )?
{{ select(11) }}
- 递归函数必须有终止条件
- 递归函数每次调用自身时,参数应向终止条件靠拢
- 递归的空间复杂度一定比迭代高
- 所有递归函数都可以用迭代方式实现
- 快速排序算法不可以用迭代方式实现
- 对下面两个函数,说法错误的是( )?
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²)
- 给定如下函数:
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
- 给定如下函数(函数功能同上题,增加输出打印):
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
- 递归函数在调用自身时,必须满足( ),以避免无限递归?
{{ select(15) }}
- 有终止条件
- 函数参数递减(或递增)
- 函数返回值固定
- 以上都对