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

第 1 题

文件型病毒传染的主要对象是（ ）。

{{ select(1) }}

• 文本文件
• 系统文件
• 可执行文件
• EXE 和 COM 文件

第 2 题

24 针打印机的分辨率约为 180dpi。dpi 数越大，打印精度越高。其中单位 dpi 是指（ ）。

{{ select(2) }}

• 印点/厘米
• 印点/毫米
• 印点/英寸
• 印点/寸

第 3 题

内存地址最重要的特点是（ ）。

{{ select(3) }}

• 随机性
• 唯一性
• 顺序性
• 连续性

第 4 题

多媒体计算机是指（ ）。

{{ select(4) }}

• 具有多种功能的计算机
• 具有多种外设的计算机
• 能处理多种媒体的计算机
• 能借助多种媒体操作的计算机

第 5 题

最早的计算机的用途是（ ）。

{{ select(5) }}

• 科学计算
• 自动控制
• 系统仿真
• 辅助设计

第 6 题

CPU 中（ ）相当于运算器中的一个存储单元，它的存取速度比存储器快得多。

{{ select(6) }}

• 存放器
• 辅存
• 主存
• 寄存器

第 7 题

计算机软件一般指的是（ ）。

{{ select(7) }}

• 系统软件和应用软件
• 应用软件和自由软件
• 培训软件和管理软件
• 编辑软件和科学计算软件

第 8 题

操作系统在（ ）计算机中普遍开始应用。

{{ select(8) }}

• 第一代
• 第二代
• 第三代
• 第四代

第 9 题

计算机中的数有浮点与定点两种，其中用浮点表示的数通常由（ ）组成。

{{ select(9) }}

• 指数与基数
• 尾数与小数
• 阶码与尾数
• 整数与小数

第 10 题

假设用一字节来表示整数，最高位用作符号位，其他位表示数值。例如，$00000001$ 表示 $+1$，$10000001$ 表示 $-1$。采用这种表示法的整数 $A$ 的范围应该是（ ）。

{{ select(10) }}

• $-127 \leq A \leq 127$
• $-128 \leq A \leq 128$
• $-128 \leq A < 128$
• $-127 < A < 127$

第 11 题

下列叙述中，正确的是（ ）。

{{ select(11) }}

• 线性表的线性存储结构优于链表存储结构
• 队列的操作方式是先进后出
• 栈的操作方式是先进先出
• 二维数组逻辑上可以理解为它的每个数据元素为一个线性表的线性表

第 12 题

用某种排序方法对线性表 $25,84,21,47,15,27,68,35,20$ 进行排序，节点变化如下： $(1)\ 25,84,21,47,15,27,68,35,20;$ $(2)\ 20,15,21,25,47,27,68,35,84;$ $(3)\ 15,20,21,25,35,27,47,68,84;$ $(4)\ 15,20,21,25,27,35,47,68,84.$ 那么，排序方法是（ ）。

{{ select(12) }}

• 选择排序
• 希尔排序
• 合并排序
• 快速排序

第 13 题

如果某二叉树的前序遍历序列为 STUWV，中序遍历序列为 UWTVS，那么该二叉树的后序遍历序列是（ ）。

{{ select(13) }}

• WUVTS
• UWVTS
• VWUTS
• WUTSV

第 14 题

下列关于数据结构的叙述中，正确的是（ ）。

{{ select(14) }}

• 顺序存储方式的优点是存储密度大，且插入、删除运算效率高
• 链表中的每一个节点都包含一个非空指针项
• 包含 $n$ 个节点的二叉排序树的最大检索长度为 $\log_2 n$
• 将一棵树转换为二叉树后，根节点没有右子树

第 15 题

表达式 $(1+34)*5-56/7$ 的后缀表达式为（ ）。

{{ select(15) }}

• $134 + 5 56 7 - * /$
• $- * + 1 34 5 / 56 7$
• $134 + 5 * 56 7 / -$
• $134 5 * + 56 7 /$

---

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

（1）

#include <iostream>
using namespace std;
void hanoi(int n,char a,char b,char c) {
    if (n == 1)
        cout << n << "_" << a << "_" << c << endl;
    else {
        hanoi(n-1, a, c, b);
        cout << n << "_" << a << "_" << c << endl;
        hanoi(n-1, b, a, c);
    }
}
int main() {
    int n;
    cin >> n;
    hanoi(n, 'A', 'B', 'C');
    return 0;
}

判断题

第 16 题

当 $n >= 0$ 时，程序不会出现死循环。

{{ input(16) }}

第 17 题

输出共有 $2^n$ 行。

{{ input(17) }}

第 18 题

当 $n > 0$ 时，将第 4 行的 == 改为 <=，程序输出结果必定不变。

{{ input(18) }}

第 19 题

将第 5 行的 $n$ 改为 1，程序输出结果必定不变。

{{ input(19) }}

选择题

第 20 题

此程序的时间复杂度是（ ）。

{{ select(20) }}

• $O(n)$
• $O(n^2)$
• $O(n^3)$
• $O(2^n)$

第 21 题

若要求输出不超过 15 行，则下列 $n$ 值中（ ）是合法的。

{{ select(21) }}

• 0
• 4
• 5
• 6

（2）

#include <cstdio>
#define N 1005
using namespace std;
int num[N];
int main() {
	int a1, i, n, x;
	scanf("%d", &n);
	num[1] = 1;
	for (int i = 1; i <= n; ++i) {
		x = 0;
		for (int j = 1; j <= a1; ++j) {
			num[j] = num[j] * 5 + x;
			x = num[j] / 10;
			num[j] %= 10;
		}
		if (x > 0) num[++a1] = x;
	}
	printf("0.");
	for (int i = a1; i < n; ++i) putchar('0');
	for (int i = a1; i >= 1; i--) printf("%d", num[i]);
	putchar('\n');
	return 0;
}

判断题

第 22 题

程序输出的是 $5^n$ 的值。

{{ input(22) }}

第 23 题

程序执行到倒数第 3 行时，$i$ 的值为 1。

{{ input(23) }}

第 24 题

程序结束前，对于任意 $1 \leq i \leq a1$，都有 $0 \leq num[i] \leq 9$。

{{ input(24) }}

第 25 题

程序输出的是一个小数，且小数末尾可能有多余的 0。

{{ input(25) }}

选择题

第 26 题

此程序的时间复杂度是（ ）。

{{ select(26) }}

• $O(n)$
• $O(n^2)$
• $O(n^3)$
• $O(n\log n)$

第 27 题

若 $n = 3$，则输出为（ ）。

{{ select(27) }}

• 8
• 0.125
• 0.8
• 125

（3）

#include <iostream>
using namespace std;
int l,n,m,a[50005], ans;
bool check(int dis) {
    int count=0, last =0;
    for (int i=1; i<=n+1; i++)
        if (a[i] - last < dis) count++;
        else last = a[i];
    if (count > m) return 0;
    return 1;
}
int main() {
    // 输入保证 l,n,m,a[i] 是正整数，且 a[i] 严格递增
    cin >> l >> n >> m;
    for (int i=1; i<=n; i++) cin >> a[i];
    a[n+1] = l;
    int fl = 0, fr = l;
    while (fl <= fr) {
        int mid = (fl + fr) / 2;
        if (check(mid)) fl=mid+1, ans=mid;
        else fr=mid-1;
    }
    cout << ans << endl;
    return 0;
}

判断题

第 28 题

将 main() 函数中 while 之前的 fl = 0 改为 fl = 1，程序输出结果必定不变。

{{ input(28) }}

第 29 题

程序结束前，必有 $fl > fr$。

{{ input(29) }}

第 30 题

若主函数中执行 check(mid) 返回 1，则最终的 ans 小于或等于此时的 mid。

{{ input(30) }}

选择题

第 31 题

此程序的时间复杂度是（ ）。

{{ select(31) }}

• $O(n^2)$
• $O(nl)$
• $O(n\log l)$
• $O(n\log n)$

第 32 题

若输入如下，则输出为（ ）。

25 5 2
2 11 14 17 21

{{ select(32) }}

• 3
• 4
• 5
• 6

---

三、完善程序（单选题，每小题 3 分，共计 30 分）

（1）

Dijkstra 算法是由荷兰计算机科学家 Dijkstra 于 1959 年提出的，是从图中一个顶点到其余各顶点的最短路径算法，解决的是有向图中的最短路问题。Dijkstra 算法的主要特点是以源点为中心向外扩展，直到扩展到终点为止。

#include <iostream>
using namespace std;
int main() {
    int edges;
    int points;
    int dis[10];
    int flag[10];
    int infinity=99999999;
    cin >> points >> edges;
    int edg[10][10];
    for (int i=1; i<=points; i++) {
        for (int j=1; j<=points; j++) {
            if (i == j)
                edg[i][j]=①;
            else {
                edg[i][j]=②;
            }
        }
    }
    int point1, point2, quanzhi;
    for (int i=1;i<=edges; i++) {
        cin >> point1 >> point2 >> quanzhi;
        edg[point1][point2] =③;
    }
    for (int i=1; i<=points; i++) dis[i] = edg[1][i];
    for (int i=1; i<=points; i++) flag[i]=0;
    flag[1]=1;
    int min,u;
    for (int i=1; i<=points-1; i++) {
        // 源点到源点不用比较，因此总的次数少一次
        min = infinity;
        for (int j=1;j<points; j++) {
            if (flag[j]==0 && dis[j]<min) {
                // 核心思想：依次比较出离源点最近的点
                min =④;
                u=j;
            }
        }
        flag[u] = 1;
        for (int v=1; v<=points; v++) {
            // 找出离源点最近之后，更新 dis 里面的源点到各个点的值是否最小
            if (edg[u][v] < infinity) {
                if (dis[v] > dis[u] + edg[u][v]) {
                    dis[v] =⑤;
                }
            }
        }
    }
    for (int i=1; i<=points; i++) cout << dis[i]<<" ";
    cout << endl;
    return 0;
}

第 33 题

①处应填（ ）。

{{ select(33) }}

• infinity
• dis[i]
• 0
• 1

第 34 题

②处应填（ ）。

{{ select(34) }}

• infinity
• dis[i]
• 0
• 1

第 35 题

③处应填（ ）。

{{ select(35) }}

• quanzhi
• 0
• infinity
• 1

第 36 题

④处应填（ ）。

{{ select(36) }}

• j
• dis[j]
• flag[j]
• i

第 37 题

⑤处应填（ ）。

{{ select(37) }}

• dis[u]
• edg[u][v]
• dis[u] + edg[u][v]
• infinity

（2）

（完全背包问题）有一个容量为 10 的背包，另有 5 种物品，每种物品数量无限，其重量分别为 5,4,3,2,1，价值分别为 1,2,3,4,5。设计算法，实现背包内物品价值最大。代码如下（输出 50）。

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    int total_weight=10;
    int w[6] = {0,5,4,3,2,1};
    int v[6] = {0,1,2,3,4,5};
    int dp[11] = {①};
    for (int i=1; i<=②; i++)
        for (int j=w[i]; j<=③; j++)
            dp[j] =④;
    cout << ⑤ << endl;
    return 0;
}

第 38 题

①处应填（ ）。

{{ select(38) }}

• 0
• 5
• 10
• 15

第 39 题

②处应填（ ）。

{{ select(39) }}

• 5
• 6
• 10
• 15

第 40 题

③处应填（ ）。

{{ select(40) }}

• 5
• 6
• 10
• 15

第 41 题

④处应填（ ）。

{{ select(41) }}

• dp[j] + v[i]
• dp[j-w[i]] + v[i]
• min(dp[j], dp[j-w[i]] + v[i])
• max(dp[j], dp[j-w[i]] + v[i])

第 42 题

⑤处应填（ ）。

{{ select(42) }}

• v[10]
• dp[10]
• w[10]
• total_weight