选择题

1. （2分）以下关于计算机网络的说法错误的是：{{ select(1) }}

• 局域网覆盖范围通常在几公里以内
• 广域网使用TCP/IP协议进行通信
• 路由器工作在网络层
• 交换机可以隔离广播域

2. （2分）以下C++代码的输出结果是：

#include <iostream>
using namespace std;
int main() {
    int a = 5, b = 2;
    cout << (a++ + ++b) << endl;
    return 0;
}

{{ select(2) }}

• 7
• 8
• 9
• 10

3. （2分）以下关于栈的说法正确的是：{{ select(3) }}

• 栈是一种先进先出的数据结构
• 栈的插入和删除操作都在同一端进行
• 栈可以用链表实现但不能用数组实现
• 栈的空间复杂度总是O(1)

4. （2分）以下排序算法中，平均复杂度是$nlog(n)$最坏时间复杂度为$O(n^2)$的是：{{ select(4) }}

• 快速排序
• 归并排序
• 堆排序
• 冒泡排序

5. （2分）二叉树的前序遍历顺序是：{{ select(5) }}

• 根节点->左子树->右子树
• 左子树->根节点->右子树
• 左子树->右子树->根节点
• 右子树->左子树->根节点

6. （2分）以下关于TCP协议的说法错误的是：{{ select(6) }}

• TCP提供可靠的数据传输
• TCP是面向连接的协议
• TCP使用三次握手建立连接
• TCP不保证数据包的顺序

7. （2分）以下代码的输出结果是：

#include <iostream>
using namespace std;
int main() {
    int x = 5;
    cout << (x << 2) << endl;
    return 0;
}

{{ select(7) }}

• 5
• 10
• 20
• 40

8. （2分）以下关于哈希表的说法正确的是：{{ select(8) }}

• 哈希表的查找时间复杂度总是O(1)
• 哈希表不能处理冲突
• 哈希函数应该尽可能均匀分布键值
• 哈希表的空间复杂度总是O(n)

9. （2分）以下关于递归的说法正确的是：{{ select(9) }}

• 递归函数必须有返回值
• 递归调用次数没有限制
• 递归必须有终止条件
• 递归比迭代效率更高

10. （2分）以下关于图论的说法错误的是：{{ select(10) }}

• 无向图的邻接矩阵是对称的
• 有向图可以有欧拉回路
• 最小生成树算法包括Prim和Kruskal
• 拓扑排序可以用于有环图

11. （2分）以下关于C++的说法正确的是：{{ select(11) }}

• C++是纯面向对象语言
• C++不支持函数重载
• C++支持多重继承
• C++没有指针概念

12. （2分）以下关于操作系统的说法正确的是：{{ select(12) }}

• 操作系统只管理硬件资源
• 进程是程序的一次执行过程
• 线程是资源分配的基本单位
• 死锁只能发生在两个进程之间

13. （2分）以下关于数据库的说法正确的是：{{ select(13) }}

• 关系数据库基于网状模型
• SQL是结构化查询语言
• 主键可以包含空值
• 外键用于保证实体完整性

14. （2分）关于图论中点与边的关系描述正确的是：{{ select(14) }}

• 无向完全图的边数是n(n+1)/2
• 有向连通图至少有n条边
• n个顶点的连通无向图至少有n-1条边
• 树是边数最多的无环图

15. （2分）以下关于计算机组成的说法错误的是：{{ select(15) }}

• CPU由运算器和控制器组成
• 内存比外存访问速度慢
• 总线用于连接计算机各部件
• 缓存可以提高CPU访问速度

阅读理解1（12分）

#include <iostream>
using namespace std;
int main() {
    int n, sum = 0;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        if(n % i == 0) sum += i;
    }
    cout << sum << endl;
    return 0;
}

第16题（1.5分）

该程序的功能是计算n的所有因数之和。（ ）{{ select(16) }}

• 正确
• 错误

第17题（1.5分）

如果将第7行的条件改为if(i % n == 0)，程序的功能会改变。（ ）{{ select(17) }}

• 正确
• 错误

第18题（1.5分）

该程序的时间复杂度是O(n)。（ ）{{ select(18) }}

• 正确
• 错误

第19题（1.5分）

当n为质数时，程序的输出结果为n+1。（ ）{{ select(19) }}

• 正确
• 错误

第20题（3分）

当输入为12时，程序的输出是（ ）。{{ select(20) }}

• 16
• 18
• 28
• 36

第21题（3分）

该程序的空间复杂度是（ ）。{{ select(21) }}

• O(1)
• O(n)
• O(n^2)
• O(log n)

阅读理解2（12分）

#include <iostream>
#include <vector>
using namespace std;

int binarySearch(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while(left <= right) {
        int mid = left + (right - left) / 2;
        if(nums[mid] == target) return mid;
        else if(nums[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

int main() {
    vector<int> nums = {1,3,5,7,9,11,13,15};
    int target;
    cin >> target;
    cout << binarySearch(nums, target) << endl;
    return 0;
}

第22题（1.5分）

该程序实现了二分查找算法。（ ）{{ select(22) }}

• 正确
• 错误

第23题（1.5分）

如果将第7行的条件改为while(left < right)，程序的功能会改变。（ ）{{ select(23) }}

• 正确
• 错误

第24题（1.5分）

该程序的时间复杂度是O(log n)。（ ）{{ select(24) }}

• 正确
• 错误

第25题（1.5分）

当输入为7时，程序的输出结果是3。（ ）{{ select(25) }}

• 正确
• 错误

第26题（3分）

当输入为10时，程序的输出是（ ）。{{ select(26) }}

• -1
• 3
• 4
• 5

第27题（3分）

当输入为5时，while的循环次数是（ ）。{{ select(27) }}

• 2
• 3
• 4
• 5

阅读理解3（12分）

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<int> bfs(vector<vector<int>>& graph, int start) {
    vector<int> visited(graph.size(), 0);
    vector<int> result;
    queue<int> q;
    q.push(start);
    visited[start] = 1;
    
    while(!q.empty()) {
        int node = q.front();
        q.pop();
        result.push_back(node);
        
        for(int neighbor : graph[node]) {
            if(!visited[neighbor]) {
                visited[neighbor] = 1;
                q.push(neighbor);
            }
        }
    }
    return result;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> graph(n);
    for(int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);       // 33题所描述的代码
    }
    
    vector<int> traversal = bfs(graph, 0);
    for(int node : traversal) {
        cout << node << " ";
    }
    return 0;
}

第28题（1.5分）

该程序实现了图的深度优先搜索算法。（ ）{{ select(28) }}

• 正确
• 错误

第29题（1.5分）

如果将第12行的visited[start] = 1改为visited[start] = 0，程序会陷入死循环。（ ）{{ select(29) }}

• 正确
• 错误

第30题（3分）

该程序的时间复杂度是（ ）。{{ select(30) }}

• O(n)
• O(m)
• O(n + m)
• O(n^2)

第31题（3分）

该程序的空间复杂度是（ ）。{{ select(31) }}

• O(n)
• O(m)
• O(n + m)
• O(n^2)

第32题（3分）

对于以下输入，程序的输出是（ ）。 输入： 4 4 0 1 0 2 1 3 2 3 {{ select(32) }}

• 0 1 2 3
• 0 1 3 2
• 0 2 1 3
• 3 2 1 0

第33题（3分）

如果将第22行的graph[v].push_back(u)删除，程序的功能会（ ）。{{ select(33) }}

• 完全不变
• 仅对无向图有效
• 仅对有向图有效
• 无法正常运行

编程填空1（15分）

（带限制条件的最大子数组和）给定一个整数数组和一个整数k，找出长度不超过k的连续子数组的最大和。

样例1： 输入：[1,3,-1,-3,5,3,6,7], k=3 输出：16 解释：子数组 [5,3,6,7] 的和最大，为 21，但长度超过k=3； 长度不超过3的最大子数组是 [6,7]，和为13

样例2： 输入：[-2,-1,-3,-4,-1], k=2 输出：-1 解释：子数组 [-1] 的和最大，为 -1

int maxSubarraySumWithLengthLimit(vector<int>& nums, int k) {
    int n = nums.size();
    if (n == 0 || k <= 0) return 0;
    vector<int> pre(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        ①;
    }
    deque<int> dq;
    int res = INT_MIN;
    for (int m = 0; m <= n; ++m) {
        while (!dq.empty() && ②) {
            dq.pop_front();
        }
        if (m >= 1) {
            if (!dq.empty()) {
                res = max(res, ③);
            }
        }
        while (!dq.empty() && ④) {
            ⑤ 
        }
        dq.push_back(m);
    }
    return res;
}

int main() {
    int n,k;
    cin >> n >> k;
    vector<int> nums(n);
    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
    }
    cout << maxSubarraySumWithLengthLimit(nums, k) << endl;
    return 0;
}

第34题（3分）①处应填（ ）{{ select(34) }}

• pre[i + 1] = pre[i] + nums[i];
• nums[i + 1] = nums[i] + pre[i];
• pre[i + 1] = pre[i] + pre[i-1];
• nums[i + 1] = nums[i] + nums[i-1];

第35题（3分）②处应填（ ）{{ select(35) }}

• dq.front() < m
• dq.front() < k
• dq.front() < m - k
• dq.front() < m + k

第36题（3分）③处应填（ ）{{ select(36) }}

• pre[m] - pre[dq.front()]
• pre[m] - pre[dq.back()]
• pre[k] - pre[dq.front()]
• pre[k] - pre[dq.back()]

第37题（3分）④处应填（ ）{{ select(37) }}

• pre[dq.back()] <= pre[m]
• pre[dq.front()] <= pre[m]
• pre[dq.back()] >= pre[m]
• pre[dq.front()] >= pre[m]

第38题（3分）⑤处应填（ ）{{ select(38) }}

• dq.pop_front();
• dq.pop_back();
• pre.pop_front();
• m++;

编程填空2（15分）

（带权最小编辑距离）给定两个字符串word1和word2，以及插入、删除、替换三种操作的不同代价，计算将word1转换成word2所需的最小代价。

样例1：

输入："horse", "ros", 1, 1, 1
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

样例2：

输入："intention", "execution", 1, 1, 1
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int minDistance(string word1, string word2, int ins_cost, int del_cost, int rep_cost) {
    int m = word1.size(), n = word2.size();
    vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
    for(int i = 0; i <= m; i++) dp[i][0] = ①;
    for(int j = 0; j <= n; j++) dp[0][j] = ②;
    
    for(int i = 1; i <= m; i++) {
        for(int j = 1; j <= n; j++) {
            int del = ③;
            int ins = ④;
            int rep = dp[i-1][j-1] + ((word1[i-1] == word2[j-1]) ? 0 : rep_cost);
            dp[i][j] = ⑤;
        }
    }
    return dp[m][n];
}

int main() {
    string word1, word2;
    int ins, del, rep;
    cin >> word1 >> word2 >> ins >> del >> rep;
    cout << minDistance(word1, word2, ins, del, rep) << endl;
    return 0;
}

第39题（3分）①处应填（ ）{{ select(39) }}

• i * del_cost
• j * del_cost
• i * ins_cost
• j * ins_cost

第40题（3分）②处应填（ ）{{ select(40) }}

• i * del_cost
• j * del_cost
• i * ins_cost
• j * ins_cost

第41题（3分）③处应填（ ）{{ select(41) }}

• dp[i-1][j] + del_cost
• dp[i][j-1] + del_cost
• dp[i-1][j] + ins_cost
• dp[i][j-1] + ins_cost

第42题（3分）④处应填（ ）{{ select(42) }}

• dp[i-1][j] + ins_cost
• dp[i][j-1] + ins_cost
• dp[i-1][j] + del_cost
• dp[i][j-1] + del_cost

第43题（3分）⑤处应填（ ）{{ select(43) }}

• min({del, ins, rep})
• min(del, ins)
• min(ins, rep)
• min(del, rep)