选择题

ID: 6057

客观题

尝试: 0

已通过: 0

难度: (无)

上传者:

root

第 1 题

关于单链表、双链表和循环链表，下列说法正确的是()。 [cite: 1559]

在单链表中，若已知任意结点的指针，则可以在O(1)时间内删除该结点。
循环链表中一定不存在空指针。
在循环双链表中，尾结点的 next 指针一定为nullptr。
在带头结点的循环单链表中，判定链表是否为空只需判断头结点的 next 是否指向自身。

第 2 题

双向循环链表中要在结点p之前插入新结点s(均非空)，以下指针操作正确的是()。 [cite: 1565]

s->next = p; p->prev = s; q->next = s; s->prev = q;
s->prev = p; s->next = p->next; p->next->prev = s; p->next = s;
s->next = p; s->prev = p->prev; p->prev->next = s; p->prev = s;
s->next = p; s->prev = nullptr; p->prev = s;

第 3 题

下面函数用“哑结点”统一处理删除单向链表中的头结点与中间结点。横线处应填()。 [cite: 1601]

Node* eraseAll (Node* head, int x) {
    Node dummy (0);
    dummy.next = head;
    Node* cur = &dummy;
    while (cur->next){
        if (cur->next->val == x) {
            Node* del = cur->next;
            ____________________;
            delete del;
        } else cur = cur->next;
    }
    return dummy.next;
}

cur = cur->next;
cur->next = del->next;
del->next = cur->next;
cur->next = nullptr;

第 4 题

对如下代码实现的欧几里得算法(辗转相除法)，执行 gcd(48,18) 得到的调用序列为()。 [cite: 1652]

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

gcd(48,18) -> gcd(18,12) -> gcd(12,6) -> gcd(6,0)
gcd(48,18) -> gcd(30,18) -> gcd(12,18)
gcd(48,18) -> gcd(18,30) -> gcd(30,6)
gcd(48,18) -> gcd(12,18) -> gcd(6,12)

第 5 题

下面代码实现了欧拉(线性)筛，横线处应填写()。 [cite: 1668]

vector<int> euler_sieve (int n) {
    vector<bool> is_composite (n+1, false);
    vector<int> primes;
    for (int i=2; i<=n; i++) {
        if (!is_composite[i])
            primes.push_back(i);
        for (int j=0; __________ && (long long)i * primes[j] <= n; j++) {
            is_composite[i * primes[j]] = true;
            if (i % primes[j] == 0)
                break;
        }
    }
    return primes;
}

j <= n
j < sqrt(n)
j < primes.size()
j < i

第 6 题

埃氏筛中将内层循环从 j=i*i 开始而不是 j=2*i 的主要原因是()。 [cite: 1710]

因为2*i一定不是合数
i*i一定是质数
小于i*i的i的倍数已被更小质因子筛过
这样可以把时间复杂度降为O(n)

第 7 题

下面程序的运行结果为()。 [cite: 1738]

// 包含二分查找答案与 check 函数判定...
int a[] = {1, 2, 8, 4, 9};
int n = 5;
int k = 3;
std::cout << solve(n, a, k) << std::endl;

第 8 题

在升序数组中查找第一个大于等于x的位置，下面循环中横线应填()。 [cite: 1820]

int lower_Bound (const vector<int>& a, int x) {
    int l = 0, r = a.size();
    while(l < r) {
        int mid = l + (r - l) / 2;
        if(a[mid] >= x)
            _________
        else 
            l = mid + 1;
    }
    return l;
}

r = mid;
r = mid - 1;
l = mid;
l = mid + 1;

第 9 题

关于递归函数调用，下列说法错误的是()。 [cite: 1842]

递归调用层次过深时，可能会耗尽栈空间导致栈溢出
尾递归函数可以通过编译器优化来避免栈溢出
所有递归函数都可以通过循环结构来改写，从而避免栈溢出
栈溢出发生时，程序会抛出异常并可以继续执行后续代码

第 10 题

给定n根木头，第i根长度为a[i]。要切成不少于m段等长木段，求最大可能长度，则横线上应填写()。 [cite: 1849]

// ... 二分答案模板
if (check(mid)) {
    ans = mid;
    _________
} else {
    _________
}
// ...

l = mid + 1; 和 r = mid - 1;
l = mid - 1; 和 r = mid + 1;
l = mid + 1; 和 r = mid;
l = mid; 和 r = mid + 1;

第 11 题

下面代码用分治求“最大连续子段和”，其时间复杂度为()。 [cite: 1939]

int solve (vector<int>& a, int l, int r){
    if(l == r) return a[l];
    int mid = l + (r - l) / 2;
    int left = solve(a, l, mid);
    int right = solve(a, mid + 1, r);
    // ... 跨越 mid 的线性扫描 ...
    return max({left, right, lmax + rmax});
}

O(n²)
O(n log n)
O(log n)
O(n)

第 12 题

游戏大赛决赛，两组选手分别按得分从小到大排好队，现在要把他们合并成一个有序排行榜。横线处应填入()。 [cite: 1991]

while (i < A.size() && j < B.size()) {
    if(__________) {
        result.push_back(A[i++]);
    } else {
        result.push_back(B[j++]);
    }
}

A[i] >= B[j]
A[i] <= B[j]
i >= j
i <= j

第 13 题

有位同学的成绩已经从小到大排好序，现在对它执行下面这段以第一个元素为 pivot的快速排序，请问此次排序的时间复杂度是()。 [cite: 2026]

// 快速排序核心代码，选择 a[l] 为 pivot

O(n)
O(n log n)
O(n²)
O(log n)

第 14 题

下面关于排序算法的描述中，不正确的是()。 [cite: 2061]

冒泡排序和插入排序都是稳定的排序算法
快速排序和归并排序都是不稳定的排序算法
冒泡排序和插入排序最好时间复杂度均为O(n)
归并排序在最好、最坏和平均三种情况的时间复杂度均为O(n log n)

第 15 题

下面代码实现两个整数除法，其中被除数为一个“大整数”，用字符串表示，除数是一个小整数，用int表示，则横线处应该填写()。 [cite: 2067]

for(int i=0; i < a.size(); i++){
    rem = rem * 10 + a[i];
    int q = rem / b;
    c.push_back(q);
    __________;
}

rem /= b;
rem %= b;
rem = b;
rem = q;

#GESP202603C5T1. 选择题