2023-12-Level-5

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

int fibroA(int N)
{
    if (N == 1 || N == 2)
    {
        return 1;
        return fibroA(N - 1) + fibroA(N - 2);
    }
    int fibroB(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 << 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 << "< $\leq$$\geq$>";
    cout << fracB(5);
    return 0;
}

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

下面的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<int> operator +(vector<int>lA,vector<int>lB)
{
    vector<int>lst;

    for (int i = 1; i < lA.size(); i++)
    {
        lst.push_back(lA[i]);
        for (int i = 1; i < lB.size(); i++)
        {
            lst.push_back(lB[i]);
            return lst;
        }
    }

    vector<int>qSort(vector<int>lst)
{
    if (lst.size() < 2)
    {
        return lst;
    }
    int pivot = lst[0];
    vector<int>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<int>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[Mid])
    {
        return _binarySearch(lst, Low, Mid - 1, Target);
    }
    else
    {
        return _binarySearch(lst, Mid + 1, High, Target);
    }
}

int bSearch(vector<int>lst, int Val)
{
    return _binarySearch(lst, 0, lst.size(), Val);
}

在上题的 _binarySearch_ 算法中，如果 lst 中有 N 个元素，其时间复杂度是（ ）。

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

vector<int> operator + (vector<int> a, vector<int> b)
{
    vector<int> 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++ 代码的说法正确的是（）。

class Node
{
public:
    int Value;
    Node* Prev;
    Node* Next;
    Node(int Val, Node* Prv = NULL, Node* Nxt = NULL);
};

Node::Node(int Val, Node* Prv, Node* Nxt)
{
    this->Value = Val;
    this->Prev = Prv;
    this->Next = Nxt;
}

int main()
{
    Node firstNode = Node(10);
    firstNode.Next = new Node(100, &firstNode);
    firstNode.Next->Next = new Node(111, firstNode.Next);
}

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

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

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

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

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

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

int Fibo(int N)
{
    if (N == 1 || N == 2)
        return 1;
    else
    {
        int m = fiboA(N - 1);
        int n = fiboB(N - 2);
        return m + n;
    }
}

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

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

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

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

char s[10];
int main()
{
    int N;
    cin >> N;
    string rst = "";
    while (N != 0)
    {
        s[0] = N & 8 + '0';
        rst += string(s);
        N /= 8;
    }
    cout << rst << endl;
    return 0;
}

对数组 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次的循环就能够算出来了。（）

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