GESP 五级 · 2023 真题

下面 C++ 代码用于求斐波那契数列，该数列第 $1$、$2$ 项为 $1$，以后各项均是前两项之和。下面有关说法错误的是（ ）。

01int fiboA(int N)
02{
03    if (N == 1 || N == 2)
04        return 1;
05    return fiboA(N - 1) + fiboA(N - 2);
06}
07int fiboB(int N)
08{
09    if (N == 1 || N == 2)
10        return 1;
11    int last2 = 1, last1 = 1;
12    int nowVal = 0;
13    for (int i = 2; i < N; i++)
14    {
15        nowVal = last1 + last2;
16        last2 = last1;
17        last1 = nowVal;
18    }
19    return nowVal;
20}

下面 C++ 代码以递归方式实现合并排序，并假设 merge(int T[], int R[], int s, int m, int t) 函数将有序（同样排序规则）的 T[s..m] 和 T[m+1..t] 归并到 R[s..t] 中。横线处应填上代码是（ ）。

01void mergeSort(int SList[], int TList[], int s, int t, int len)
02{
03    if (s == t) {
04        TList[s] = SList[s];
05        return;
06    }
07    int *T2 = new int[len]; // 保存中间结果
08    int m = (s + t) / 2;
09    ____________;
10    merge(T2, SList, s, m, t);
11    delete T2;
12    return ;
13}

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

01int stepCount = 0;
02int fracA(int N)
03{
04    stepCount += 1;
05    cout << stepCount << "->";
06    int rtn = 1;
07    for (int i = 1; i <= N; i++)
08        rtn *= i;
09    return rtn;
10}
11int fracB(int N)
12{
13    stepCount += 1;
14    cout << stepCount << "->";
15    if (N == 1)
16        return 1;
17    return N * fracB(N - 1);
18}
19int main()
20{
21    cout << fracA(5);
22    cout << "<====>";
23    cout << fracB(5);
24    return 0;
25}

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

01bool isEven(int N)
02{
03    return N % 2 == 0;
04}
05
06void swap(int &a, int &b)
07{
08    int t;
09    t=a,a=b,b=t;
10    return;
11}
12
13void sortA(int lstA[], int n)
14{
15    int i, j, t;
16    for (i = n-1; i > 0; i--)
17        for(j = 0; j < i; j++)
18            if(____________)
19                swap(lstA[j], lstA[j+1]);
20
21    return;
22}

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

01typedef struct Node{
02    string str;
03    int ref;
04    struct Node *next, *prev;
05}Node;
06Node * Insert(Node *pHead, string s)
07{
08    Node *p = pHead->next;
09    Node *q;
10    while(p) {
11        if(p->str == s) {
12            p->ref++;
13            p->next->prev = p->prev;
14            p->prev->next = p->next;
15            break;
16        }
17        p=p->next;
18    }
19    if(!p) {
20        p = new Node;
21        p->str = s;
22        p->ref=0;
23        p->next = p->prev = NULL;
24    }
25    ____________
26    pHead->next = p, p->prev = pHead;
27    return pHead;
28}

有关下面 C++ 代码说法正确的是（ ）。

01int rc;
02int foo(int x, int y)
03{
04    int r;
05    if(y == 0)
06        r = x;
07    else {
08        r = foo(y, x % y);
09        rc++;
10    }
11    return r;
12}

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

01vector<int> operator + (vector<int>lA, vector<int>lB)
02{
03    vector<int>lst;
04
05    for (int i = 1; i < lA.size(); i++)
06        lst.push_back(lA[i]);
07    for (int i = 1; i < lB.size(); i++)
08        lst.push_back(lB[i]);
09
10    return lst;
11}
12vector<int> qSort(vector<int>lst)
13{
14    if (lst.size() < 2)
15        return lst;
16    int pivot = lst[0];
17    vector<int> less, greater;
18    for (int i = 1; i < lst.size(); i++)
19        if (lst[i] <= pivot) less.push_back(lst[i]);
20        else greater.push_back(lst[i]);
21    for (int i = 1; i < lst.size(); i++)
22        if (lst[i] <= pivot) less.push_back(lst[i]);
23        else greater.push_back(lst[i]);
24
25    return ____________;
26}

下面 C++ 代码中的 isPrimeA() 和 isPrimeB() 都用于判断参数 N 是否素数，有关其时间复杂度的正确说法是（ ）。

01bool isPrimeA(int N)
02{
03    if (N < 2)
04        return false;
05    for (int i = 2; i <= N / 2; i++)
06        if (N % i == 0)
07            return false;
08    return true;
09}
10bool isPrimeB(int N)
11{
12    if (N < 2)
13        return false;
14    for (int i = 2; i <= sqrt(N); i++)
15        if (N % i == 0)
16            return false;
17    return true;
18}

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

01int _binarySearch(vector<int>lst, int Low, int High, int Target)
02{
03    if (Low > High)
04        return -1;
05    int Mid = (Low + High) / 2;
06    if (Target == lst[Mid])
07        return Mid;
08    else if (Target < lst[Mid])
09        return _binarySearch(lst, Low, Mid - 1, Target);
10    else
11        return _binarySearch(lst, Mid + 1, High, Target);
12}
13int bSearch(vector<int>lst, int Val)
14{
15    return _binarySearch(lst, 0, lst.size(), Val);
16}

在二分查找算法中，如果有序列表中有 N 个元素，其时间复杂度是（ ）。

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

01vector<int> operator + (vector<int> a, vector<int> b)
02{
03    vector<int> c;
04    int t = 0;
05
06    for(int i = 0; i < a.size() || i < b.size(); i ++ )
07    {
08        if(i < a.size()) t = t + a[i];
09        if(i < b.size()) t = t + b[i];
10        ____________
11    }
12
13    if(t) c.push_back(t);
14
15    return c;
16}

有关下面 C++ 代码的说法正确的是（ ）。

01class Node
02{
03public:
04    int Value;
05    Node* Prev;
06    Node* Next;
07    Node(int Val, Node* Prv = NULL, Node* Nxt = NULL);
08};
09
10Node::Node(int Val, Node*Prv, Node* Nxt)
11{
12    this->Value = Val;
13    this->Prev = Prv;
14    this->Next = Nxt;
15}
16
17int main()
18{
19    Node firstNode = Node(10);
20    firstNode.Next = new Node(100, &firstNode);
21    firstNode.Next->Next = new Node(111, firstNode.Next);
22}

通讯卫星在通信网络系统中主要起到（ ）的作用。

小杨想编写一个判断任意输入的整数 N 是否为素数的程序，下面哪个方法不合适？（ ）

下面的排序算法都要处理多趟数据，哪种排序算法不能保证在下一趟处理时从待处理数据中选出最大或最小的数据？（ ）

归并排序的时间复杂度是 $O(N \log N)$。

小杨在生日聚会时拿一块 H*W 的巧克力招待来的 K 个小朋友，保证每位小朋友至少能获得一块相同大小的巧克力。那么小杨想分出来最大边长的巧克力可以使用二分法。

以下 C++ 代码能以递归方式实现斐波那契数列，该数列第 $1$、$2$ 项为 $1$，以后各项均是前两项之和。

01int Fibo(int N)
02{
03    if (N == 1 || N == 2)
04        return 1;
05    else
06    {
07        int m = fiboA(N - 1);
08        int n = fiboB(N - 2);
09        return m + n;
10    }
11}

贪心算法可以达到局部最优，但可能不是全局最优解。

小杨设计了一个拆数程序，它能够将任意的非质数自然数 N 转换成若干个质数的乘积，这个程序是可以设计出来的。

插入排序有时比快速排序时间复杂度更低。

下面的 C++ 代码能实现十进制正整数 N 转换为八进制并输出。

01char s[10];
02int main()
03{
04    int N;
05    cin >> N;
06    string rst = "";
07    while (N != 0)
08    {
09        s[0]=N % 8 + '0';
10        rst += string(s);
11        N /= 8;
12    }
13    cout << rst << endl;
14
15    return 0;
16}

对数组 int arr[] = {2, 6, 3, 5, 4, 8, 1, 0, 9, 10} 执行 sort(arr, arr+10)，则执行后 arr 中的数据调整为 {0, 1, 2, 3, 4, 5, 6, 8, 9, 10}。

小杨想写一个程序来算出正整数 N 有多少个因数，经过思考他写出了一个重复没有超过 N/2 次的循环就能够算出来了。

同样的整数序列分别保存在单链表和双向链中，这两种链表上的简单冒泡排序的复杂度相同。