Day3.5 STL 深度阅读程序

判断题请选择“正确/错误”。题目考查对所有合法输入的性质、修改影响、边界与复杂度，不能只靠运行一组数据判断。

程序一：排序去重函数

int normalize(vector<int>& a) {
    sort(a.begin(), a.end());
    auto newEnd = unique(a.begin(), a.end());
    int removed = a.end() - newEnd;
    a.erase(newEnd, a.end());
    return removed;
}

第 1 题

对任意输入vector，函数结束后 a 中不存在重复元素。（ ）

{{ select(1) }}

• 正确
• 错误

第 2 题

函数结束后，a 中的元素按照非递减顺序排列。（ ）

{{ select(2) }}

• 正确
• 错误

第 3 题

若原长度为 n、不同元素个数为 d，返回值为 n-d。（ ）

{{ select(3) }}

• 正确
• 错误

第 4 题

删除 sort 一行后，函数仍能对所有输入完成整体去重。（ ）

{{ select(4) }}

• 正确
• 错误

第 5 题

若保留 unique 但删除 erase，a.size() 仍保持原长度。（ ）

{{ select(5) }}

• 正确
• 错误

第 6 题

设原长度为 n，该函数的总体时间复杂度是（ ）。

{{ select(6) }}

• $O(1)$
• $O(\log n)$
• $O(n)$
• $O(n\log n)$

---

程序二：最高词频

string mostFrequent(const vector<string>& words) {
    map<string, int> cnt;
    for (const string& s : words) cnt[s]++;

    string ans = "";
    int best = -1;
    for (const auto& p : cnt) {
        if (p.second > best) {
            best = p.second;
            ans = p.first;
        }
    }
    return ans;
}

第 7 题

若有多个单词并列最高频，函数返回字典序最小者。（ ）

{{ select(7) }}

• 正确
• 错误

第 8 题

若 words 长度为 n，所有 cnt 中的计数之和等于 n。（ ）

{{ select(8) }}

• 正确
• 错误

第 9 题

若 words 中有 k 个不同单词，则 cnt.size() 等于 k。（ ）

{{ select(9) }}

• 正确
• 错误

第 10 题

把 map 换成 unordered_map，函数对并列最高频情况仍必然返回相同单词。（ ）

{{ select(10) }}

• 正确
• 错误

第 11 题

若对不存在的键执行 cnt[key]，可能使 cnt 的 size 增加。（ ）

{{ select(11) }}

• 正确
• 错误

第 12 题

若有 n 个单词、k 个不同单词，使用 map 统计的常见时间复杂度是（ ）。

{{ select(12) }}

• $O(1)$
• $O(n)$固定
• $O(n\log k)$
• $O(2^n)$

---

程序三：有序区间计数

int countInRange(const vector<int>& a, int L, int R) {
    auto left = lower_bound(a.begin(), a.end(), L);
    auto right = upper_bound(a.begin(), a.end(), R);
    return right - left;
}

第 13 题

在 a 已升序且 L<=R 的前提下，函数统计闭区间 [L,R] 内的元素个数。（ ）

{{ select(13) }}

• 正确
• 错误

第 14 题

若 a 无序，函数结果仍对所有输入正确。（ ）

{{ select(14) }}

• 正确
• 错误

第 15 题

若 a 中没有元素落在 [L,R]，函数返回 0。（ ）

{{ select(15) }}

• 正确
• 错误

第 16 题

当 LRx 时，函数返回 x 在 a 中的出现次数。（ ）

{{ select(16) }}

• 正确
• 错误

第 17 题

若把 upper_bound(...,R) 改为 lower_bound(...,R)，统计范围变为 [L,R)。（ ）

{{ select(17) }}

• 正确
• 错误

第 18 题

设 a 长度为 n，函数的时间复杂度是（ ）。

{{ select(18) }}

• $O(1)$
• $O(\log n)$
• $O(n)$
• $O(n\log n)$

---