初赛模拟卷 A（3）

第 1 题（单选）

下列关于深度优先搜索（DFS）和广度优先搜索（BFS）的描述，正确的是（）。

{{ select(1) }}

• DFS 使用队列，BFS 使用栈
• DFS 通常用于求最短路径
• BFS 一定能找到最短路径（无边权情况下）
• 两者均不能用于有向图

第 2 题（单选）

下列代码中，s1->draw(); 和 s2->draw(); 输出不同结果的主要原因是（）。 public: cout draw(); s2->draw(); delete s1; delete s2; return 0; }

{{ select(2) }}

- draw() 是普通成员函数
- Shape 中的 draw() 被声明为虚函数
- Circle 和 Rectangle 中使用了 public 继承
- 指针变量名不同

## 第 3 题（单选）

关于动态规划算法特性的描述，正确的是（）。

{{ select(3) }}

- 贪心选择性质
- 最优子结构和重叠子问题
- 分而治之
- 局部最优

## 第 4 题（单选）

下列关于动态规划与分治算法的说法，正确的是（）。

{{ select(4) }}

- 两者都要求子问题相互独立
- 动态规划适用于子问题重叠的情况，分治适用于子问题不重叠的情况
- 两者都是将大问题分解为子问题，但动态规划一定使用递归
- 分治算法一定比动态规划更优

## 第 5 题（单选）

下列关于 0-1 背包问题的动态规划解法，说法正确的是（）。

{{ select(5) }}

- 状态转移方程为 dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i])，其中 i 表示物品编号，j 表示容量
- 一维数组实现时，内层循环应从小到大遍历容量
- 完全背包问题可以用相同的一维数组解法，但内层循环同样需要从大到小
- 0-1 背包问题不能使用贪心算法求解，但动态规划一定能找到最优解

## 第 6 题（单选）

代码实现了二叉排序树的插入函数（假设没有相同数值），横线处填入（）。

Node* insert(Node* root, int val) { if (root == nullptr) return new Node(val); if (val val) root->left = insert(________, val); else root->right = insert(root->right, val); return root; }

{{ select(6) }}

- root->left
- root->right
- root
- nullptr

## 第 7 题（单选）

代码实现一个二叉排序树的插入函数（没有相同的数值），横线处应填入（）。

Node* insert(Node* root, int val) { if (root == nullptr) return new Node(val); if (val val) root->left = insert(root->left, val); else root->right = insert(________, val); return root; }

{{ select(7) }}

- root->left
- root->right
- root
- nullptr

## 第 8 题（单选）

对二叉排序树进行中序遍历得到的序列是（）。

{{ select(8) }}

- 递增序列
- 递减序列
- 先递增后递减
- 随机序列

## 第 9 题（单选）

下列排序算法中，平均时间复杂度为 O(n log n) 的是（）。

{{ select(9) }}

- 冒泡排序
- 插入排序
- 快速排序
- 选择排序

## 第 10 题（单选）

下面关于二叉排序树查找的描述，正确的是（）。

{{ select(10) }}

- 查找操作最坏情况下的时间复杂度是 O(log n)
- 查找操作最好情况下的时间复杂度是 O(1)
- 查找操作的时间复杂度与树的形状无关
- 查找操作只能递归实现

## 第 11 题（单选）

设有字符集 `{a, b, c, d, e}`，出现频率分别为 `{5, 8, 12, 15, 20}`，则字符 a 的哈夫曼编码的长度可能为（）。

{{ select(11) }}

- 1
- 2
- 3
- 4

## 第 12 题（单选）

以下不属于计算机输出设备的是（）。

{{ select(12) }}

- 麦克风
- 音箱
- 打印机
- 显示器

## 第 13 题（单选）

下列 C++ 代码关于静态成员的访问，正确的是（）。

{{ select(13) }}

- 只能通过类名访问
- 只能通过对象名访问
- 两者均可
- 静态成员不能访问

## 第 14 题（单选）

下列关于格雷编码（Gray Code）的描述，正确的是（）。

{{ select(14) }}

- 相邻两个编码只有一位不同
- 相邻编码可以有两位不同
- 格雷编码是唯一的
- 格雷编码二进制表示中所有位都不同

## 第 15 题（单选）

在 C++ 中，基类的析构函数通常应该声明为虚函数，其主要目的是（）。

{{ select(15) }}

- 提高程序运行效率
- 在通过基类指针删除派生类对象时，正确调用派生类析构函数
- 减少内存占用
- 使派生类对象能直接调用基类析构函数

## 第 16 题（单选）

在 C++ 中，派生类继承基类的方式包括 public、protected 和 private。若采用 public 继承，基类中的 private 成员在派生类中的访问权限为（）。

{{ select(16) }}

- public
- protected
- private
- 不可访问

## 第 17 题（单选）

在 C++ 中，关于 this 指针的说法正确的是（）。

{{ select(17) }}

- 在非静态成员函数中均可使用
- 在静态成员函数中也可使用
- this 指针存储的是当前对象的地址
- this 指针的值可以修改

## 第 18 题（单选）

如果树中的节点 A 是节点 B 的祖先，则节点 A 和节点 B 之间的关系是（）。

{{ select(18) }}

- A 在 B 的上方
- B 在 A 的子树中
- A 是 B 的父节点
- A 和 B 位于同一层

## 第 19 题（单选）

在 C++ 中，关于重写（override）的说法正确的是（）。

{{ select(19) }}

- 被重写的函数必须是虚函数
- 重写函数与基类函数可以有不同的参数列表
- 重写函数与基类函数可以有不同的返回类型
- 只有 public 继承才能重写

## 第 20 题（单选）

哈夫曼编码是一种（）。

{{ select(20) }}

- 变长前缀编码
- 定长编码
- 等长编码
- 后缀编码

## 第 21 题（单选）

关于 C++ 中类的描述，正确的是（）。

{{ select(21) }}

- 如果类没有用户声明的构造函数，编译器会隐式声明一个默认构造函数
- 类的析构函数可以被重载，一个类可以有多个析构函数
- 类中的所有成员都必须声明为 public
- 类和结构体在 C++ 中没有区别，包括默认访问权限也相同

## 第 22 题（单选）

在二叉搜索树（BST）中，若中序遍历序列为 `{1, 2, 3, 4, 5}`，且先序遍历的第一个元素为 3，下列说法正确的是（）。

{{ select(22) }}

- 3 是根节点，2 是 3 的左子节点，4 是 3 的右子节点
- 该 BST 是平衡的
- 3 是根节点，1 是 3 的左子树中的最左节点
- 5 是 3 的右子节点

## 第 23 题（单选）

格雷编码中，3 位格雷编码 101 之后的下一个编码不可能是（）。

{{ select(23) }}

- 100
- 111
- 001
- 000

## 第 24 题（单选）

在 C++ 中，如果一个类没有定义任何构造函数，编译器（）。

{{ select(24) }}

- 会生成一个默认的无参构造函数
- 不会生成任何构造函数
- 只生成拷贝构造函数
- 会生成一个带参构造函数

## 第 25 题（单选）

关于树的遍历说法，正确的是（）。

{{ select(25) }}

- 前序遍历结果是根节点在最后
- 中序遍历结果一定是升序
- 后序遍历的最后一个是根节点
- 层序遍历必须使用递归

## 第 26 题（单选）

下列关于 C++ 中多态的说法，正确的是（）。

{{ select(26) }}

- 只有通过指针或引用调用虚函数才能体现运行时多态
- 通过对象直接调用虚函数也能体现多态
- 多态只能通过继承实现
- 虚函数必须用 override 关键字

## 第 27 题（单选）

下列关于哈夫曼树的说法，正确的是（）。

{{ select(27) }}

- 哈夫曼树是带权路径长度（WPL）最小的二叉树
- 哈夫曼树一定是完全二叉树
- 哈夫曼树中可能存在度为1的节点
- 哈夫曼树中权值较大的节点离根较远

## 第 28 题（单选）

下面关于 C++ 类继承的说法，正确的是（）。

{{ select(28) }}

- C++ 只支持单继承
- C++ 只支持多继承
- C++ 同时支持单继承和多继承
- C++ 不支持继承

## 第 29 题（单选）

已知 3 位格雷编码的顺序是从 000 到 100，按照此顺序，001 和 011 之间相差（）位不同。

{{ select(29) }}

- 1
- 2
- 3
- 4

## 第 30 题（单选）

在 C++ 中，对类的成员变量进行“数据隐藏”通常是通过（）实现。

{{ select(30) }}

- public
- private
- virtual
- static

## 第 31 题（多选）

关于循环队列，下列哪些说法是正确的？（）

{{ multiselect(31) }}

- 循环队列解决了顺序队列的“假溢出”问题
- 循环队列通常使用一个空闲位置来区分队空和队满
- 循环队列的入队和出队操作时间复杂度为 O(1)
- 循环队列只能使用数组实现

## 第 32 题（多选）

关于二叉树的顺序存储，下列哪些说法是正确的？（）

{{ multiselect(32) }}

- 适用于完全二叉树
- 使用数组存储
- 对于不完全二叉树，存储时会浪费空间
- 可以快速找到某个节点的父节点和子节点

## 第 33 题（多选）

关于完全二叉树，下列哪些说法是正确的？（）

{{ multiselect(33) }}

- 只有最后一层节点可能不满
- 最后一层节点尽量靠左排列
- 可以用数组进行顺序存储
- 所有叶子节点都在同一层

## 第 34 题（多选）

关于队列的基本操作，下列哪些是正确的？（）

{{ multiselect(34) }}

- enqueue（入队）
- dequeue（出队）
- isEmpty（判空）
- getSize（获取大小）

## 第 35 题（多选）

关于二叉树的链式存储结构，下列哪些说法是正确的？（）

{{ multiselect(35) }}

- 每个节点包含两个指针域
- 可以方便地进行各种遍历
- 存储 n 个节点需要 2n 个指针域
- 空指针域的数量为 n+1

## 第 36 题（多选）

关于二叉排序树（BST），下列哪些说法是正确的？（）

{{ multiselect(36) }}

- 左子树中所有节点的值均小于根节点的值
- 中序遍历 BST 可以得到一个升序序列
- BST 的查找效率与树的高度有关
- 删除 BST 中的节点时，如果被删除节点有左右子树，可以用左子树的最大节点来替换

## 第 37 题（多选）

关于二叉排序树的查找，下列说法正确的有（）。

{{ multiselect(37) }}

- 平均查找长度与树的形状有关
- 最坏情况下查找效率退化为 O(n)
- 二叉排序树查找效率一定高于顺序查找
- 插入和删除操作会改变树的形状

## 第 38 题（多选）

下列哪些是动态规划的特点？（）

{{ multiselect(38) }}

- 最优子结构
- 贪心选择
- 重叠子问题
- 自底向上或自顶向下求解

## 第 39 题（多选）

下列哪些算法可以用动态规划求解？（）

{{ multiselect(39) }}

- 背包问题
- 最长公共子序列
- 最短路径（Dijkstra 算法）
- 斐波那契数列

## 第 40 题（多选）

下列哪些问题是典型的动态规划问题？（）

{{ multiselect(40) }}

- 爬楼梯问题
- 最长上升子序列
- 最短路径（无权图）
- 0-1 背包问题

## 第 41 题（单选）

在队列中，元素的添加和删除是按照（）原则进行的。

{{ select(41) }}

- 先进先出
- 先进后出
- 最小值先出
- 随机进出

## 第 42 题（单选）

循环队列中，队列最大容量为 maxSize，front指向队头，rear指向队尾。判断队列已满的条件是（）。

{{ select(42) }}

- rear == front
- (rear + 1) % maxSize == front
- (rear - 1 + maxSize) % maxSize == front
- (rear - 1) == front

## 第 43 题（单选）

以下关于完全二叉树的描述，正确的是（）。

{{ select(43) }}

- 所有叶子节点都在同一层
- 只有最底层的节点未被填满，且最底层节点尽量靠左填充
- 每个节点都有两个子节点
- 所有节点度数均为2

## 第 44 题（单选）

在使用数组表示完全二叉树时，如果一个节点的索引为 i（从 0 开始计数），那么其左子节点的索引通常是（）。

{{ select(44) }}

- 2i
- 2i+1
- 2i+2
- i+1

## 第 45 题（单选）

已知一棵二叉树的前序遍历序列为 GDAFEMHZ，中序遍历序列为 ADFGEHMZ，则其后序遍历序列为（）。

{{ select(45) }}

- AGH ZEMFD
- AGH Z E M F D
- A G H Z E M F D
- AFGHEMZD

## 第 46 题（单选）

使用深度优先搜索（DFS）遍历一个图时，通常使用的辅助数据结构是（）。

{{ select(46) }}

- 栈
- 队列
- 数组
- 链表

## 第 47 题（单选）

以下关于广度优先搜索（BFS）的描述，错误的是（）。

{{ select(47) }}

- BFS 通常借助队列来实现
- BFS 常用于在无权图中寻找最短路径
- BFS 适合搜索所有解空间（通常由深度优先搜索承担）
- 在无权图中，BFS 第一次访问到目标节点时，所经路径一定最短

## 第 48 题（单选）

下列关于树的深度优先搜索（DFS）的说法，正确的是（）。

{{ select(48) }}

- DFS 一定会访问所有节点
- DFS 使用队列作为辅助数据结构
- DFS 在二叉树中通常用递归或栈实现
- DFS 无法处理有环图

## 第 49 题（单选）

对于一个有 n 个节点和 n-1 条边的连通图，下列说法正确的是（）。

{{ select(49) }}

- 它一定是一棵树
- 它一定不是树
- 它可能存在环
- 它可能不连通

## 第 50 题（单选）

使用二维数组存储图时，为了判断两个顶点之间是否有边，时间复杂度为（）。

{{ select(50) }}

- O(1)
- O(n)
- O(n²)
- O(log n)