GESP C++ 5级 2023.12

下面 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;
}

下面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;
}

阅读下面的C++代码，执行后其输出是

int stepCount = 0;

int fracA(int N) {
 stepCount += 1;
 cout ";
 int rtn = 1;
 for(int i = 1; i ";
 if(N == 1) {
 return 1;
 }
 return N * fracB(N - 1);
}

int main() {
 cout ";
 cout << fracB(5);
 return 0;
}

下面的C++代码使用数组模拟整数加法，可以处理超出大整数范围的加法运算。横线处应填入代码是

vector operator +(vector a, vector b) {
 vector c;
 int t = 0;
 for(int i = 0; i < a.size() || i < b.size(); i++) {
 if(i < a.size()) t = t + a[i];
 if(i < b.size()) t = t + b[i];
 ________________________
 }
 if(t) c.push_back(t);
 return c;
}

下面的C++用于对 lstA 排序，使得偶数在前奇数在后，横线处应填入

bool isEven(int N) {
 return N % 2 == 0;
}

void swap(int &a, int &b) {
 int t;
 t = a, a = b, b = t;
 return;
}

void sortA(int lstA[], int n) {
 int i, j, t;
 for( i = n-1; i > 0; i--) {
 for(j = 0; j < i; j++) {
 if(_______________) {
 swap(lstA[j], lstA[j+1]);
 }
 }
 }
 return;
}

下面的C++代码用于将字符串保存到带头节点的双向链表中，并对重复的串计数，然后将最新访问的串的节点放在链头便于查找。横线处应填入代码是

typedef struct Node {
 string str;
 int ref;
 struct Node *next, *prev;
} Node;

Node * Insert(Node *pHead, string s) {
 Node *p = pHead->next;
 Node *q;
 while(p) {
 if(p->str == s) {
 p->ref++;
 p->next->prev = p->prev;
 p->prev->next = p->next;
 break;
 }
 p = p->next;
 }
 if (!p) {
 p = new Node;
 p->str = s;
 p->ref = 0;
 p->next = p->prev = NULL;
 
 }
 ________________________________
 pHead->next = p, p->prev = pHead;
 return pHead;
}

有关下面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;
}

下面的C++代码实现对list的快速排序，有关说法，错误的是

vector operator+(vector lA, vector lB) {
 vector lst;
 for(int i = 1; i qSort(vector lst) {
 if(lst.size() less, greater;
 for (int i = 1; i < lst.size(); i++) {
 if (lst[i] <= pivot) {
 less.push_back(lst[i]);
 } else {
 greater.push_back(lst[i]);
 }
 }
 for (int i = 1; i < lst.size(); i++) {
 if (lst[i] <= pivot) {
 less.push_back(lst[i]);
 } else {
 greater.push_back(lst[i]);
 }
 }
 return______________________________;
}

下面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;
}

下面C++代码用于有序 list 的二分查找，有关说法错误的是

int _binarySearch(vector lst, int Low, int High, int Target) {
 if (Low > High) {
 return -1;
 }
 int Mid = (Low + High) / 2;
 if (Target == lst[Mid]) {
 return Mid;
 } else if (Target lst, int Val) {
 return _binarySearch(lst, 0, lst.size() - 1, Val);
}