一、单项选择（共15题，每题2分，共计30分；每题有且仅有一个正确选项）

1. 下列不属于算法基本特征的是（）
   {{ select(1) }}

• 有穷性
• 确定性
• 可行性
• 美观性

2. 下列哪个选项的代码能够正确赋值（）
   {{ select(2) }}

• int x = 3.14;
• double y = 5;
• string str = 'abc';
• int a[10] = 5;

3. 若某满二叉树的节点数为127（根节点深度为1），则其深度为（）
   {{ select(3) }}

• 6
• 7
• 8
• 9

4. 快速排序在最坏情况下的时间复杂度为（）
   {{ select(4) }}

• $O(n)$
• $O(n²)$
• $O(nlogn)$
• $O(logn)$

5. 设栈的初始状态为空，元素a、b、c、d、e依次入栈，以下哪个出栈序列是不可能的？（） {{ select(5) }}

• e d c b a
• a b c d e
• d c e a b
• b a d c e

6. 已知二进制数10110101，其对应的十进制数为（） {{ select(6) }}

• 181
• 179
• 165
• 193

7. 下列关于图的遍历说法错误的是（） {{ select(7) }}

• 深度优先遍历需要使用栈或递归
• 广度优先遍历需要使用队列
• 无向图中可以存在环
• 从一个顶点出发进行遍历一定可以到达图中所有点

8. 若用邻接矩阵存储一个有n个顶点的图，矩阵大小为（） {{ select(8) }}

• $n×n$
• $n×(n-1)$
• $(n-1)×n$
• $(n+1)×(n+1)$

9. 下列哪个协议用于电子邮件的发送？（） {{ select(9) }}

• SMTP
• HTTP
• FTP
• POP3

10. 已知int a[5] = {1, 2, 3, 4, 5};，下列访问数组元素错误的是（） {{ select(10) }}

• a[0]
• a[5]
• *(a+2)
• *(a+4)

11. 下列关于二叉树的说法正确的是（） {{ select(11) }}

• 完全二叉树一定是满二叉树
• 深度为$k$的满二叉树的节点数一定为$2^k - 1$
• 二叉树的左右子树可以任意交换，交换后的树和原树相同
• 深度为$k$的二叉树最多有$2^k$个节点

12. 以下代码的时间复杂度是（）

int func(int n) {
    int count = 0;
    for (int i = 1; i <= n; i *= 2) {
        for (int j = 0; j < i; j++) {
            count++;
        }
    }
    return count;
}

{{ select(12) }}

• $O(n)$
• $O(nlogn)$
• $O(logn)$
• $O(n²)$

13. 已知递归函数定义为：

int f(int n) {
    if(n <= 1) return 1;
    else return f(n-1) + f(n-2);
}

则f(6)的返回值为（） {{ select(13) }}

• 8
• 13
• 21
• 34

14. 用哈希表存储元素时，解决冲突的方法不包括（） {{ select(14) }}

• 开放定址法
• 链地址法
• 再哈希法
• 二分查找法

15. 下列关于操作系统的说法错误的是（） {{ select(15) }}

• 操作系统是硬件与应用程序的接口
• Windows和Linux都是常见的操作系统
• 进程是操作系统中资源分配的基本单位
• 操作系统不能管理计算机的网络连接

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题选正误；除特殊说明外，判断题每题2分，选择题每题3分，共40分）

(1)

#include <iostream>
using namespace std;

int main() {
    int n, sum = 0;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        if (i % 3 == 0 || i % 5 == 0) {
            sum += i;
        }
    }
    cout << sum << endl;
    return 0;
}

判断题

16. 当输入n=10时，程序输出的结果为33。（） {{ select(16) }}

• 正确
• 错误

单选题

17. 当输入n=20时，程序输出的结果为（） {{ select(17) }}

• 98
• 105
• 115
• 120

18. （4分）输出答案在[100, 200]之间的对应合法输入有（）种 {{ select(18) }}

• 8
• 9
• 10
• 11
• 12
• 13

(2)

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

bool isPalindrome(string s) {
    int left = 0, right = s.length() - 1;
    while (left != right) {
        if (s[left] != s[right]) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

int main() {
    string str;
    cin >> str;
    if (isPalindrome(str)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

判断题

19.输入字符串"level"时，程序输出"Yes"。（） {{ select(19) }}

• 正确
• 错误

20. 对于任意长度为1的小写字母构成的字符串，程序均会输出"No"。（） {{ select(20) }}

• 正确
• 错误

21. 将函数的返回值类型由bool改成int，程序仍然可以正常运行，且执行结果和之前并无变化。（） {{ select(21) }}

• 正确
• 错误

单选题

22. 选出下列字符串中执行结果和其他不同的一项（） {{ select(22) }}

• AaA
• d
• ABBA
• 00000

（3） 下列程序接收第一行一个整数n，第二行n个正整数stone[i]。其中保证$1 \le n, stone[i] \le 300$。

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 305;
const int INF = 0x3f3f3f3f;
int n, stone[MAXN], sum[MAXN];
int dp[MAXN][MAXN];  
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> stone[i];
        sum[i] = sum[i - 1] + stone[i]; 
    }
    memset(dp, 0x3f, sizeof(dp));
    for (int i = 1; i <= n; i++) {
        dp[i][i] = 0;  
    }
    for (int len = 2; len <= n; len++) {
        for (int i = 1; i + len - 1 <= n; i++) {
            int j = i + len - 1;  
            for (int k = i; k < j; k++) {
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + sum[j] - sum[i-1]);
            }
        }
    }  
    cout << dp[1][n] << endl;
    return 0;
}

判断题

23.若给出下列输入，程序运行的结果为3（）

2
1 2

{{ select(23) }}

• 正确
• 错误

24. 在给定数据范围下，程序不可能输出0。（） {{ select(24) }}

• 正确
• 错误

25.程序的复杂度是$O(n^3)$。（） {{ select(25) }}

• 正确
• 错误

单选题

26. （4分）一共可以构造（）种不同的合法输入，使得程序运行的结果为5。 {{ select(26) }}

• 3
• 4
• 5
• 6
• 8

27. 下列输入的正确结果是（）

4
2 5 7 1

{{ select(27) }}

• 30
• 28
• 15
• 14

(4) 阅读以下C++程序，该程序使用深度优先搜索（DFS）求解连通块问题，统计网格图中不同连通块的数量，其中连通块定义为四连通（上下左右相邻）且值为1的区域。分析代码逻辑后回答问题。 保证输入的$1\le n, m \le 100$，网格图中只有0和1。

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

const int MAXN = 105;
int n, m;
int grid[MAXN][MAXN];
bool visited[MAXN][MAXN];
int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

void dfs(int x, int y) {
    visited[x][y] = true; 
    for (int i = 0; i < 4; i++) { 
        int nx = x + dir[i][0];
        int ny = y + dir[i][1];
        if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny] && grid[nx][ny] == 1) {
            dfs(nx, ny);
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
        }
    }
    memset(visited, false, sizeof(visited));  
    int count = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == 1 && !visited[i][j]) {  
                dfs(i, j);
                count++;  
            }
        }
    }
    cout << count << endl;
    return 0;
}

判断题 28. 若将dir数组改为{{-1, -1}, {-1, 0}, {-1, 1}, {0, 1}}，程序将从四连通改为八连通判断。（） {{ select(28) }}

• 正确
• 错误

单选题 29. 对于下列输入，程序的输出结果是（）

3 3
1 0 1
0 1 0
1 0 1

{{ select(29) }}

• 1
• 3
• 5
• 9

30. (4分） 对于一个n = 2, m = 3大小的网格图，使得输出结果为1的合法的不同输入有（）种。 {{ select(30) }}

• 20
• 35
• 32
• 12
• 18
• 40

完善程序

（1）小明的花店新开张，为了吸引顾客，他想在花店的门口摆上一排花，共 $m$ 盆。通过调查顾客的喜好，小明列出了顾客最喜欢的 $n$ 种花，从 $1$ 到 $n$ 标号。为了在门口展出更多种花，规定第 $i$ 种花不能超过 $a_i$ 盆，摆花时同一种花放在一起，且不同种类的花需按标号的从小到大的顺序依次摆列。试编程计算，一共有多少种不同的摆花方案。方案数对$1e6+7$取模。

#include <iostream>
using namespace std;
const int mod = 1e6 + 7;
int ans[105][105], a[105];
int n, m;

int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; ++i) cin >> a[i];
    for(int i = 0; i <= n; ++i) ans[0][i] = ___31___;
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= m; ++j) { 
            ans[j][i] = ___32___;
            for(int k = 0; k <= a[i]; ++k) {
                if(___33___) continue;
                ans[j][i] += ___34___;
                ans[j][i] %= mod;
            }
        }
    }
    
    // 空5：输出最终结果
    cout << ___35___ << endl;
    return 0;
}

31.31处应填入（）
{{ select(31) }}

• 0
• 1
• i
• a[i]

32. 32处应填入（） {{ select(32) }}

• ans[j][i-1]
• ans[j-1][i]
• 0
• 1

33. 33处应填入（） {{ select(33) }}

• i - 1 < 0
• j + k > m
• k > a[i]
• j - k < 0

34. 34处应填入（） {{ select(34) }}

• ans[j - k][i - 1]
• ans[j + k][i - 1]
• ans[j - 1][i - k]
• ans[j - 1][i + k]

35. 35处应填入（）
    {{ select(35) }}

• ans[m][n]
• ans[n][m]
• ans[m][m]
• ans[n][n]

(2)对于一张有向图，给定起点s，要求计算起点到其他点的距离并输出。对于无法到达的点，输出$10^9$。请补全下列程序。

#include <bits/stdc++.h>
const int MaxN = 100010, MaxM = 500010, inf = 1e9;

struct edge {
    int to, dis, next;
};

edge e[MaxM];
int head[MaxN], dis[MaxN], cnt;
bool vis[MaxN];
int n, m, s;

inline void add_edge(int u, int v, int d)
{
    cnt++;
    e[cnt].dis = d;
    e[cnt].to = v;
    e[cnt].next = ___36___;
    head[u] = cnt;
}

struct node
{
    int dis;
    int pos;
    bool operator<(const node &x) const
    {
        return ___37___ < dis;
    }
};

std::priority_queue<node> q;

inline void dijkstra()
{
    dis[s] = ___38___;
    q.push((node){0, s});
    while (!q.empty())
    {
        node tmp = q.top();
        q.pop();
        int x = tmp.pos, d = tmp.dis;
        if (vis[x])
            continue;
        vis[x] = 1;
        for (int i = head[x]; i; i = e[i].next)
        {
            int y = e[i].to;
            if (dis[y] > ___39___)
            {
                dis[y] = dis[x] + e[i].dis;
                if (!vis[y])
                {
                    q.push((node){dis[y], y});
                }
            }
        }
    }
}

int main()
{
    scanf("%d%d%d", &n, &m, &s);
    
    for (int i = 1; i <= n; ++i)
        dis[i] = ___40___;
    for (int i = 0; i < m; ++i)
    {
        int u, v, d;
        scanf("%d%d%d", &u, &v, &d);
        add_edge(u, v, d);
    }
    dijkstra();
    for (int i = 1; i <= n; i++)
        printf("%d ", dis[i]);
    return 0;
}

36. 36处应填入（） {{ select(36) }}

• head[v]
• head[u]
• cnt
• i

37. 37处应填入（） {{ select(37) }}

• x.dis
• dis
• x.pos
• pos

38. 38处应填入（） {{ select(38) }}

• inf
• 0
• 1
• n

39. 39处应填入（） {{ select(39) }}

• dis[x] + e[i].dis
• dis[y] + e[i].dis
• dis[x] - e[i].dis
• dis[y] - e[i].dis

40. 40处应填入（） {{ select(40) }}

• 0
• 1
• n
• inf