初赛模拟卷 A（4）

第 1 题（单选）

在构建哈夫曼树时，每次应该选择（）合并。

{{ select(1) }}

• 最小权值的节点
• 最大权值的节点
• 随机节点
• 深度最深的节点

第 2 题（单选）

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

{{ select(2) }}

• 1
• 2
• 3
• 4

第 3 题（单选）

哈夫曼编码是一种（）。

{{ select(3) }}

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

第 4 题（单选）

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

{{ select(4) }}

• 每次取两个权值最大的节点合并
• 每次取两个权值最小的节点合并
• 权值小的节点离根更近
• 哈夫曼树不一定是二叉树

第 5 题（单选）

哈夫曼编码的构造过程中，每次合并后的新节点的权值是（）。

{{ select(5) }}

• 被合并的两个节点权值之和
• 被合并的两个节点权值之差
• 被合并的两个节点权值之积
• 被合并的两个节点权值最大值

第 6 题（单选）

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

{{ select(6) }}

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

第 7 题（单选）

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

{{ select(7) }}

• 2i
• 2i+1
• 2i+2
• i+1

第 8 题（单选）

对于深度为 k 的二叉树，其最多有（）个节点。

{{ select(8) }}

• 2^k
• 2^k - 1
• 2^(k+1) - 1
• 2^(k-1)

第 9 题（单选）

若采用顺序存储结构存储一棵有 n 个节点的完全二叉树，数组下标从 1 开始，则节点 i 的右孩子节点下标为（）。

{{ select(9) }}

• 2i
• 2i+1
• 2i-1
• i/2

第 10 题（单选）

对于有 n 个节点的二叉树，其空指针域的数量为（）。

{{ select(10) }}

• n+1
• n-1
• n
• 2n

第 11 题（单选）

面向对象编程的主要特征不包括（）。

{{ select(11) }}

• 封装
• 继承
• 多态
• 模块化

第 12 题（单选）

当多个类之间存在“is-a”关系时，应使用面向对象的（）特性。

{{ select(12) }}

• 封装
• 继承
• 多态
• 抽象

第 13 题（单选）

在 C++ 中，下列关于构造函数的描述正确的是（）。

{{ select(13) }}

• 构造函数可以被声明为虚函数
• 构造函数不能被声明为虚函数
• 构造函数可以有返回值
• 构造函数必须显式调用

第 14 题（单选）

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

{{ select(14) }}

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

第 15 题（单选）

若采用 public 继承，基类中的 private 成员在派生类中的访问权限为（）。

{{ select(15) }}

• public
• protected
• private
• 不可访问

第 16 题（单选）

栈的典型应用包括（）。

{{ select(16) }}

• 表达式求值
• 打印机任务调度
• 进程调度
• 消息队列

第 17 题（单选）

某文本编辑器把用户输入的字符依次压入栈 S。输入 A, B, C, D 后按两次撤销，此时栈从栈底到栈顶的内容是（）。

{{ select(17) }}

• A B
• A B C
• A B D
• B C

第 18 题（单选）

执行 stack s; queue q; 分别压入 1,2,3 后，输出 s.top() 和 q.front() 的结果是（）。

{{ select(18) }}

• 1 3
• 3 1
• 3 3
• 1 1

第 19 题（单选）

在 C++ 中使用 stack（栈）容器时，新元素通过 push 操作插入到（）。

{{ select(19) }}

• 栈底
• 栈顶
• 队列尾部
• 任意位置

第 20 题（单选）

下列关于栈和队列的说法，正确的是（）。

{{ select(20) }}

• 栈和队列都是线性结构
• 栈和队列的元素进出都在同一端
• 栈是先进先出，队列是后进先出
• 栈和队列都不允许遍历

第 21 题（单选）

在构建哈夫曼树时，每次应该选择（）合并。

{{ select(21) }}

• 最小权值的节点
• 最大权值的节点
• 随机节点
• 深度最深的节点

第 22 题（单选）

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

{{ select(22) }}

• 1
• 2
• 3
• 4

第 23 题（单选）

哈夫曼编码是一种（）。

{{ select(23) }}

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

第 24 题（单选）

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

{{ select(24) }}

• 每次取两个权值最大的节点合并
• 每次取两个权值最小的节点合并
• 权值小的节点离根更近
• 哈夫曼树不一定是二叉树

第 25 题（单选）

哈夫曼编码的构造过程中，每次合并后的新节点的权值是（）。

{{ select(25) }}

• 被合并的两个节点权值之和
• 被合并的两个节点权值之差
• 被合并的两个节点权值之积
• 被合并的两个节点权值最大值

第 26 题（单选）

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

{{ select(26) }}

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

第 27 题（单选）

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

{{ select(27) }}

• 2i
• 2i+1
• 2i+2
• i+1

第 28 题（单选）

对于深度为 k 的二叉树，其最多有（）个节点。

{{ select(28) }}

• 2^k
• 2^k - 1
• 2^(k+1) - 1
• 2^(k-1)

第 29 题（单选）

若采用顺序存储结构存储一棵有 n 个节点的完全二叉树，数组下标从 1 开始，则节点 i 的右孩子节点下标为（）。

{{ select(29) }}

• 2i
• 2i+1
• 2i-1
• i/2

第 30 题（单选）

对于有 n 个节点的二叉树，其空指针域的数量为（）。

{{ select(30) }}

• n+1
• n-1
• n
• 2n

第 31 题（多选）

关于 C++ 中类的继承，下列哪些说法是正确的？

{{ multiselect(31) }}

• 子类可以继承父类的 public 成员
• 子类不能访问父类的 private 成员
• 子类可以重写父类的虚函数
• C++ 支持多继承

第 32 题（多选）

在 C++ 中，关于静态成员，下列哪些说法是正确的？

{{ multiselect(32) }}

• 静态成员变量属于类，不属于某个具体对象
• 静态成员函数不能访问非静态成员变量
• 静态成员变量必须在类外进行初始化
• 静态成员函数可以使用 this 指针

第 33 题（多选）

下列哪些是 C++ 面向对象编程的三大特性？

{{ multiselect(33) }}

• 封装
• 继承
• 多态
• 抽象

第 34 题（多选）

关于 C++ 中的虚函数，下列哪些说法是正确的？

{{ multiselect(34) }}

• 基类指针可以调用派生类的虚函数
• 虚函数用于实现运行时多态
• 构造函数可以是虚函数
• 析构函数可以是虚函数

第 35 题（多选）

在 C++ 中，关于构造函数的初始化列表，下列哪些说法是正确的？

{{ multiselect(35) }}

• 可以初始化 const 成员变量
• 可以初始化引用成员变量
• 执行顺序由成员在类中的声明顺序决定
• 执行顺序由初始化列表中的顺序决定

第 36 题（多选）

下列哪些是树的遍历方式？

{{ multiselect(36) }}

• 前序遍历
• 中序遍历
• 层序遍历
• 后序遍历

第 37 题（多选）

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

{{ multiselect(37) }}

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

第 38 题（多选）

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

{{ multiselect(38) }}

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

第 39 题（多选）

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

{{ multiselect(39) }}

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

第 40 题（多选）

关于二叉树的性质，下列哪些说法是正确的？

{{ multiselect(40) }}

• 第 i 层最多有 2^(i-1) 个节点
• 深度为 k 的二叉树最多有 2^k - 1 个节点
• 叶子节点数 = 度为 2 的节点数 + 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 题（单选）

在一个循环队列中，front 指向队头元素的位置，rear 指向队尾元素的下一个位置。初始化时，front 和 rear 的值应为（）。

{{ select(43) }}

• 0 和 0
• 0 和 1
• 1 和 0
• 1 和 1

第 44 题（单选）

在一个循环队列中，队列的最大容量为 5，采用“空一格判满”的策略。执行入队 1,2,3,4，出队两次，再入队 5,6 后，队列状态是（）。

{{ select(44) }}

• 已满，rear = 1
• 未满，rear = 1
• 已满，rear = 2
• 未满，rear = 4

第 45 题（单选）

以下场景中，最适合使用循环队列的是（）。

{{ select(45) }}

• 函数调用过程中，保存局部变量和返回地址
• 表达式求值中的运算符优先级处理
• 生产者和消费者问题中的共享缓冲区
• 操作系统中的进程优先级调度

第 46 题（单选）

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

{{ select(46) }}

• 栈
• 队列
• 数组
• 链表

第 47 题（单选）

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

{{ select(47) }}

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

第 48 题（单选）

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

{{ select(48) }}

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

第 49 题（单选）

在对二叉树进行层序遍历时，通常使用的辅助数据结构是（）。

{{ select(49) }}

• 栈
• 队列
• 优先队列
• 数组

第 50 题（单选）

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

{{ select(50) }}

• O(1)
• O(n)
• O(n²)
• O(log n)