一、单选题（共 15 题，每题 2 分，共计 30 分）

1. 以下哪种功能没有涉及 C++ 语言的面向对象特性支持：（ ）。

{{ select(1) }}

• C++ 中调用 printf 函数
• C++ 中调用用户定义的类成员函数
• C++ 中构造一个 class 或 struct
• C++ 中构造来源于同一基类的多个派生类

2. 有6 个元素，按照 6,5,4,3,2,1 的顺序进入栈 𝑆，请问下列哪个出栈序列是非法的（ ）。

{{ select(2) }}

• 5,4,3,6,1,2
• 4,5,3,1,2,6
• 3,4,6,5,2,1
• 2,3,4,1,5,6

3. 运行以下代码片段的行为是（ ）。

{{ select(3) }}

• 将 𝑥的值赋为 201
• 将 𝑦的值赋为 101
• 将 𝑞 指向 𝑥 的地址
• 将 𝑝指向 𝑦 的地址

4.链表和数组的区别包括（ ）。

{{ select(4) }}

• 数组不能排序，链表可以
• 链表比数组能存储更多的信息
• 数组大小固定，链表大小可动态调整
• 以上均正确

5. {{ select(5) }}

• 2
• 3
• 4
• 6

6.对表达式 a+(b-c)*d 的前缀表达式为（ ），其中 +、-、* 是运算符。 {{ select(6) }}

• *+a-bcd
• +a*-bcd
• abc-d*+
• abc-+d

7.

{{ select(7) }}

• 1
• 2
• 2或3
• 3

8.一棵有 𝑛 个结点的完全二叉树用数组进行存储与表示，已知根结点存储在数组的第 1个位置。若存储在数组第 9个位置的结点存在兄弟结点和两个子结点，则它的兄弟结点和右子结点的位置分别是（ ）。 {{ select(8) }}

• 8、18
• 10、18
• 8、19
• 10、19

9.考虑由 𝑁个顶点构成的有向连通图，采用邻接矩阵的数据结构表示时，该矩阵中至少存在（ ）个非零元素 {{ select(9) }}

• N-1
• N
• N+1
• $N^2$

10.以下对数据结构的表述不恰当的一项为：（ ）。

{{ select(10) }}

• 图的深度优先遍历算法常使用的数据结构为栈。
• .栈的访问原则后进先出，队列的访问原则是先进先出。
• 队列常常被用于广度优先搜索算法。
• 栈与队列存在本质不同，无法用栈实现队列。

11.以下哪组操作能完成在双向循环链表结点 𝑝之后插入结点 𝑠 的效果（其中，next 域为结点的直接后继，prev 域为结点的直接前驱）：（ ）。

{{ select(11) }}

• p->next->prev=s; s->prev=p; p->next=s; s->next=p->next;
• p->next->prev=s; p->next=s; s->prev=p; s->next=p->next;
• s->prev=p; s->next=p->next; p->next=s; p->next->prev=s;
• s->next=p->next; p->next->prev=s; s->prev=p; p->next=s;

12.以下排序算法的常见实现中，哪个选项的说法是错误的：（ ）。

{{ select(12) }}

• 冒泡排序算法是稳定的
• 简单选择排序是稳定的
• 简单插入排序是稳定的
• 归并排序算法是稳定的

13八进制数 32.1对应的十进制数是（ ）。

{{ select(13) }}

• 24.125
• 24.250
• 26.125
• 26.250

14.一个字符串中任意个连续的字符组成的子序列称为该字符串的子串，则字符串 𝑎𝑏𝑐𝑎𝑏 有（ ）个内容互不相同的子串。

{{ select(14) }}

• 12
• 13
• 14
• 15

15.以下对递归方法的描述中，正确的是：（ ）。

{{ select(15) }}

• 递归是允许使用多组参数调用函数的编程技术
• 递归是通过调用自身来求解问题的编程技术
• 递归是面向对象和数据而不是功能和逻辑的编程语言模型
• 递归是将用某种高级语言转换为机器代码的编程技术

二.阅读程序（判断题1.5分，选择题3分，共计40分）

假设输入的 𝑥,𝑦均是不超过 15的自然数，完成下面的判断题和单选题：

判断题

1).1. 删去第 7 行与第 13行的 unsigned，程序行为不变。

{{ select(16) }}

• √
• ×

2).1. 将第 7行与第 13*行的 short 均改为 char，程序行为不变。

{{ select(17) }}

• √
• ×

3. 程序总是输出一个整数“0”。

{{ select(18) }}

• √
• ×

4).1. 当输入为 2 2 时，输出为 10。

{{ select(19) }}

• √
• ×

5).1. 当输入为 2 2 时，输出为 59。

{{ select(20) }}

• √
• ×

单选题

6).当输入为 13 8 时，输出为（ ）。

{{ select(21) }}

• 0
• 209
• 197
• 226

假设输入的n、m均是不超过100 的正整数，完成下面的判断题和单选题：

判断题

1).1. 当输入为 7 3 时，第 19行用来取最小值的 min 函数执行了 449 次。 {{ select(22) }}

• √
• ×

2).输出的两行整数总是相同的。 {{ select(23) }}

• √
• ×

3).1. 当 𝑚为 1 时，输出的第一行总为 𝑛。 {{ select(24) }}

• √
• ×

单选题

4).4. 算法 𝑔(𝑛,𝑚)最为准确的时间复杂度分析结果为（ ）。 {{ select(25) }}

• 
• 𝑂(𝑛𝑚)
• $𝑂(𝑛^2𝑚)$
• $𝑂(𝑛𝑚^2)$

5)当输入为 20 2 时，输出的第一行为（ ）。 {{ select(26) }}

• 4
• 5
• 6
• 20

6)(4分)当输入 100 100 时，输出的第一行为（ ） {{ select(27) }}

• 6
• 7
• 8
• 9

假设 int 为32位有符号整数类型，输入的 n 是不超过47000的自然数、k 是不超过 int 表示范围的自然数，完成下面的判断题和单选题：

判断题

1. 该算法最准确的时间复杂度分析结果为 𝑂(log⁡𝑛+𝑘) {{ select(28) }}

• √
• ×

2).当输入为 9801 1 时，输出的第一个数为 99。 {{ select(29) }}

• √
• ×

3).对于任意输入的 𝑛，随着所输入 𝑘的增大，输出的第二个数会变成 1。 {{ select(30) }}

• √
• ×

4).1. 该程序有存在缺陷。当输入的 𝑛 过大时，第 12行的乘法有可能溢出，因此应当将 mid 强制转换为 64位整数再计算。

{{ select(31) }}

• √
• ×

单选题

5).5. 当输入为 2 1 时，输出的第一个数最接近（ ）。

{{ select(32) }}

• 1
• 1.414
• 1.5
• 2

6).当输入为 3 10 时，输出的第一个数最接近（ ）。

{{ select(33) }}

• 1.7
• 1.732
• 1.75
• 2

7). 当输入为 256 11 时，输出的第一个数（ ）。 {{ select(34) }}

• 等于 16
• 接近但小于 16
• 接近但大于 16
• 前三种情况都有可能

三、完善程序

（1）（枚举因数）从小到大打印正整数 𝑛 的所有正因数。 试补全枚举程序。

1).①处应填（ ）。 {{ select(35) }}

• n % i == 0
• n % i == 1
• n % (i-1) == 0
• n % (i-1) == 1

2).②处应填（ ）。 {{ select(36) }}

• n / fac[k]
• fac[k]
• fac[k]-1
• n / (fac[k]-1)

3).③处应填（ ）。 {{ select(37) }}

• (i-1)*(i-1)== n
• (i-1)*i == n
• i*i == n
• i*(i-1) == n

4).④处应填（ ）。 {{ select(38) }}

• n-i
• n-i+1
• i-1
• i

5).⑤处应填（ ）。 {{ select(39) }}

• n / fac[k]
• fac[k]
• fac[k]-1
• n / (fac[k]-1)

2.（洪水填充）

现有用字符标记像素颜色的 8×8 图像。颜色填充的操作描述如下：给定起始像素的位置待填充的颜色，将起始像素和所有可达的像素（可达的定义：经过一次或多次的向上、下、左、右四个方向移动所能到达且终点和路径上所有像素的颜色都与起始像素颜色相同），替换为给定的颜色。

试补全程序。

1).①处应填（ ）。 {{ select(40) }}

• image[r][c] == prev_color
• image[r][c] != prev\_color
• image[r][c] == new_color
• image[r][c] != new_color

2).②处应填（ ）。 {{ select(41) }}

• image[cur.r+1][cur.c] = new_color
• image[cur.r][cur.c] = new_color
• image[cur.r][cur.c+1] = new_color
• image[cur.r][cur.c] = prev_color

3).③处应填（ ）。 {{ select(42) }}

• Point(pt.r, pt.c)
• Point(pt.r, pt.c+1)
• Point(pt.r+1, pt.c)
• Point(pt.r+1, pt.c+1)

4).④处应填（ ）。

{{ select(43) }}

• prev_color = image[p.r][p.c]
• new_color = image[p.r][p.c]
• image[p.r][p.c] = prev_color
• image[p.r][p.c] = new_color

5).⑤处应填（ ）。

{{ select(44) }}

• queue.push(p)
• queue. push (pt)
• queue.push(cur)
• queue. push(Point (ROWS, COLS))