一、单项选择题(共 15 题，每题 2 分，共计 30 分;每题有且仅有一个正确选项)

1.以下哪种功能没有涉及C++语言的面向对象特性支持:( )。 {{ select(1) }}

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

2. 有 6 个元素，按照 6、5、4、3、2、1 的顺序进入栈 S，请问下列哪个出栈序列是非法的 ( )。 {{ 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. 运行以下代码片段的行为是( )。

int x = 101;
int y = 201;
int *p = &x;
int *q = &y;
p = q;

{{ select(3) }}

• 将x的值赋为201
• 将y的值赋为101
• 将q指向x的地址
• 将p指向y的地址

4. 链表和数组的区别包括( )。 {{ select(4) }}

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

5. 对假设栈 S 和队列 Q 的初始状态为空。存在 e1~e6 六个互不相同的数据，每个数据按照 进栈 S、出栈 S、进队列 Q、出队列 Q 的顺序操作，不同数据间的操作可能会交错。已知 栈 S 中依次有数据 e1、e2、e3、e4、e5 和 e6 进栈，队列 Q 依次有数据 e2、e4、e3、 e6、e5和e1出队列。则栈S的容量至少是( )个数据。 {{ select(5) }}

• 2
• 3
• 4
• 6

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

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

7. 假设字母表 {a, b, c, d, e} 在字符串出现的频率分别为 10%, 15%, 30%, 16%, 29%。若使用哈夫曼编码方式对字母进行不定长的二进制编码，字母 d 的编码长度为 ( )位。 {{ select(7) }}

• 1
• 2
• 2或3
• 3

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

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

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

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

10.以下对数据结构的表述不恰当的一项为:( )。 {{ select(10) }}

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

11. 以下哪组操作能完成在双向循环链表结点 p 之后插入结点 s 的效果(其中，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. 一个字符串中任意个连续的字符组成的子序列称为该字符串的子串，则字符串 abcab 有 ( )个内容互不相同的子串。 {{ select(14) }}

• 12
• 13
• 14
• 15

15. 以下对递归方法的描述中，正确的是:( ) {{ select(15) }}

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

二、阅读程序(程序输入不超过数组或字符串定义的范围;判断题正确填√，错误填×;除特 殊说明外，判断题 1.5 分，选择题 3 分，共计 40 分)

(1)

01 #include <iostream>
02
03 using namespace std;
04
05 int main()
06 {
07 unsigned short x, y;
08 cin>>x>>y;
09 x = (x | x << 2) & 0x33;
10 x = (x | x << 1) & 0x55;
11 y = (y | y << 2) & 0x33;
12 y = (y | y << 1) & 0x55;
13 unsigned short z = x| y << 1;
14 cout << z << endl;
15 return 0;
16 }

假设输入的 x、y 均是不超过 15 的自然数，完成下面的判断题和单选题:

判断题

16. 删去第7行与第13行的unsigned，程序行为不变。( ) {{ select(16) }}

• 正确
• 错误

17. 将第7行与第13行的short均改为char，程序行为不变。( ) {{ select(17) }}

• 正确
• 错误

18. 程序总是输出一个整数“0”。( ) {{ select(18) }}

• 正确
• 错误

19. 当输入为“2 2”时，输出为“10”。( ) {{ select(19) }}

• 正确
• 错误

20. 当输入为“2 2”时，输出为“59”。( ) {{ select(20) }}

• 正确
• 错误

单选题

21. 当输入为“13 8”时，输出为( )。 {{ select(21) }}

• “0”
• “209”
• “197”
• “226”

(2)

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

判断题

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

• 正确
• 错误

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

• 正确
• 错误

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

• 正确
• 错误

25.算法g(n,m)最为准确的时间复杂度分析结果为( )。 {{ select(25) }}

• $O\left(n^{3 / 2} m\right)$
• $O(mn)$
• $O(n^2m)$
• $O(nm^2)$

26.当输入为“20 2”时，输出的第一行为( )。 {{ select(26) }}

• “4”
• “5”
• “6”
• “20”

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

• “6”
• “7”
• “8”
• “9”

(3)

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

判断题

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

• 正确
• 错误

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

• 正确
• 错误

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

• 正确
• 错误

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

• 正确
• 错误

单选题

32.当输入为“2 1”时，输出的第一个数最接近( )。 {{ select(32) }}

• 1
• 1.414
• 1.5
• 2

33.当输入为“3 10”时，输出的第一个数最接近( )。 {{ select(33) }}

• 1.7
• 1.732
• 1.75
• 2

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

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

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

(1)(枚举因数)从小到大打印正整数 n 的所有正因数。

试补全枚举程序。

35.1处应填( ) {{ select(35) }}

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

36.2处应填( ) {{ select(36) }}

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

37.3处应填( ) {{ select(37) }}

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

38.4处应填( ) {{ select(38) }}

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

39.5处应填( ) {{ select(39) }}

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

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

试补全程序。

40.1处应填( ) {{ select(40) }}

• image[r][c] == prev_color
• image[r][c] != prev_color
• image[r][c] == new_color
• image[r][c] != new_color

41.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

42.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)

43.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

44.5处应填( ) {{ select(44) }}

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