一.单选题(每题2分，共30分)

1. ⾯向对象编程(OOP)是⼀种特殊的程序设计⽅法。下⾯( )不是重要的OOP特性。

{{ select(1) }}

• 抽象
• 封装
• 继承
• 模块化

2. 以下关于C++中类的说法，哪⼀项是正确的？

{{ select(2) }}

• 类中定义的所有成员变量和成员函数默认是public 访问权限。
• 类的构造函数必须显式声明返回类型为void 。
• 在C++中，类的数据⼀般设置为私有，其公有成员函数提供访问私有数据的唯⼀途径。
• 同⼀个类的实例有各⾃的成员数据和成员函数。

3. 以下C++代码段中存在语法错误或逻辑错误，（ ）是正确的。

#include <iostream>
using namespace std;
class MyClass {
	public:
		MyClass() {
			cout << "Constructor called!" << endl;
		}
		void display() {
			cout << "Display function called!" << endl;
		}
};
int main() {
	MyClass* obj = NULL;
	obj->display();
	return 0;
}

{{ select(3) }}

• NULL 在C++中⽆法⽤于指针初始化，应使⽤ nullptr 。
• obj 的定义应该是 MyClass obj; ⽽不是指针类型。
• obj->display() 语句存在空指针访问错误， obj 应该初始化为⼀个有效的对象。
• obj->display() 语句会调⽤ display() 函数，但它没有输出任何内容。

4. 阅读以下代码，下⾯哪⼀项是正确的？

   void processData() {
   	stack<int> s;
   	queue<int> q;
   	for (int i = 1; i <= 5; ++i) {
   		s.push(i);
   		q.push(i);
   	}
   	while (!s.empty()) {
   		cout << "Stack pop: " << s.top() << endl;
   		s.pop();
   	}
    	while (!q.empty()) {
    		cout << "Queue pop: " << q.front() << endl;
    		q.pop();
    	}
   }
   

{{ select(4) }}

• 栈s的输出顺序是1 2 3 4 5，队列q的输出顺序是5 4 3 2 1。
• 栈s的输出顺序是5 4 3 2 1，队列q的输出顺序是1 2 3 4 5。
• 栈s的输出顺序是1 2 3 4 5，队列q的输出顺序是1 2 3 4 5。
• 栈s 的输出顺序是1 2 3 4 5，队列q的输出顺序是 1 2 3 4 5，程序不会正常执⾏。

5. N个节点的双向循环链，在其中查找某个节点的平均时间复杂度是( )。

{{ select(5) }}

• O(1)
• O(N)
• O(logN)
• $O(N^3)$

6. 以下关于树的说法，（ ）是正确的。

{{ select(6) }}

• 在⼀棵⼆叉树中，叶⼦结点的度⼀定是2。
• 满⼆叉树中每⼀层的结点数等于$O(2^{层数-1})$
• 在⼀棵树中，所有结点的度之和等于所有叶⼦结点的度之和。
• ⼀棵⼆叉树的先序遍历结果和中序遍历结果⼀定相同。

7. 已知字符集 {A, B, C, D} 的出现频率如下表所⽰：

   

   根据哈夫曼编码法，下⾯（ ）是正确的哈夫曼树。

{{ select(7) }}

• 

• 

• 

• 

8. 上⼀题中各字符的哈夫曼编码是（ ）。

{{ select(8) }}

• A: 0, B: 10, C: 110, D: 111
• A: 0, B: 10, C: 11, D: 10
• A: 0, B: 101, C: 100, D: 11
• A: 11, B: 10, C: 01, D: 00

9. ( )是位格雷编码。

{{ select(9) }}

• 000 001 011 010 110 111 101 100
• 000 001 010 011 100 101 110 111
• 000 001 100 101 011 010 111 110
• 000 010 001 011 100 110 101 111

10. 根据下⾯⼆叉树和给定的代码，

     #include <iostream>
     using namespace std;
     struct TreeNode {
        int val;
        TreeNode* left;
        TreeNode* right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     };
     TreeNode* search(TreeNode* root, int val) {
        cout << root->val << " ";
        if (root == NULL || root->val == val) return root;
        if (val < root->val)
            return search(root->left, val);
        else
            return search(root->right, val);
     }
    

给定以下⼆叉搜索树，调⽤函数 search(root,7) 时，输出的结果是（ ）。

{{ select(10) }}

• 5 3 7
• 5 7
• 2 3 4 5 6 7
• 8 7

11. 阅读以下⼆叉树的深度优先搜索算法，横线上应填写

     void dfs(TreeNode* root) {
        if (root == nullptr)
            return;
         
        stack<TreeNode*> s;
          s.push(root);
        while (!s.empty()) {
            ———————————————————————— // 在此处填入代码
            cout << node->value << " ";
            
            if (node->right) s.push(node->right);
            if (node->left) s.push(node->left);
        }
     }
    

{{ select(11) }}

• TreeNode* node = s.top();
• TreeNode* node = s.top(); s.pop();
• TreeNode* node = s.front();
• TreeNode* node = s.front(); s.pop();

12. 阅读以下⼆叉树的⼴度优先搜索的代码，横线上应填写

     #include <queue>
     void bfs(TreeNode* root) {
        if (root == NULL) return;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            ———————————————————————— // 在此处填入代码
            cout << node->val << " ";
            if (node->left) {
                q.push(node->left);
            }
            if (node->right) {
                q.push(node->right);
            }
        }
     }
    

{{ select(12) }}

• TreeNode* node = q.top();
• TreeNode* node = q.top(); q.pop();
• TreeNode* node = q.front();
• TreeNode* node = q.front(); q.pop();

13. 使⽤上题中的宽度优先搜索算法遍历以下这棵树，可能的输出是( )。

![1](./3621/file/7.png)

{{ select(13) }}

• 1 2 8 9 4 5 3 6 7
• 1 2 3 4 5 6 6 8 9
• 1 2 3 8 9 6 4 5 7
• 8 4 5 9 2 1 3 6 7

14. 以下关于动态规划的描述，（ ）是正确的。

{{ select(14) }}

• 动态规划适⽤于没有重叠⼦问题的优化问题。
• 动态规划要求问题具有最优⼦结构和⽆后效性。
• 动态规划通常通过递归来实现。
• 动态规划与贪⼼算法不同，贪⼼算法不适⽤于有重叠⼦问题的问题。

15. 假设背包的最⼤容量W=8kg，共有有4个物品可供选择，4个物品的重量分别为weights=[2,3,5,7]，对应 的价值分别为values=[30,40,60,80] ，则该0/1背包问题中，背包的最⼤价值为（ ）。

{{ select(15) }}

• $70$
• $90$
• $100$
• $120$

二.判断题(每题2分，共20分)

16. 构造函数是⼀种特殊的类成员函数，构造函数的名称和类名相同。但通过函数重载，可以创建多个同名的构 造函数，条件是每个构造函数的参数列表不同。 {{ select(16) }}

• 正确
• 错误

17. 类的静态成员函数既能访问类的静态数据成员，也能访问⾮静态数据成员。 {{ select(17) }}

• 正确
• 错误

18. 栈中元素的插⼊和删除操作都在栈的顶端进⾏，所以⽅便⽤单向链表实现。

    {{ select(18) }}

• 正确
• 错误

19. 下⾯代码构建的树⼀定是完全⼆叉树：

    struct TreeNode {
        int value;
        TreeNode* left;
        TreeNode* right;
     };
     TreeNode* buildCompleteBinaryTree() {
        TreeNode* root = new TreeNode{1};
        root->left = new TreeNode{2};
        root->right = new TreeNode{3};
        root->left->left = new TreeNode{4};
        root->left->right = new TreeNode{5};
        root->right->left = new TreeNode{6};
        return root;
     }
    

{{ select(19) }}

• 正确
• 错误

20. 在⼆叉排序树中，左⼦树所有节点的值都⼤于根节点的值，右⼦树所有节点的值都⼩于根节点的值。

    {{ select(20) }}

• 正确

• 错误

21. 在⽣成⼀个派⽣类的对象时，只调⽤派⽣类的构造函数。

    {{ select(21) }}

• 正确
• 错误

22. 下⾯的代码实现了⼆叉树的前序遍历，它通过递归⽅法访问每个节点并打印节点值。

```cpp
 void preorder(TreeNode* root) {
 	if (root == NULL) return;
 	cout << root->val << " ";
	preorder(root->left);
 	preorder(root->right);
 }
```

{{ select(22) }}

• 正确
• 错误

23. 宽度优先搜索算法（BFS）保证了每个节点在最短路径的情况下被访问。

    {{ select(23) }}

• 正确
• 错误

24. 在解决简单背包问题时，动态规划的状态转移⽅程如下：

```
dp[i][w] = max(dp[i-1][w], dp[i-1][w - weights[i-1]] + values[i-1]);
```

该⽅程表⽰：在考虑第  i 个物品时，当前背包容量为 w，如果不放物品 i，则最⼤价值是  放⼊物品 i，则最⼤价值是  `dp[i-1][w] `；如果 `dp[i-1][w - weights[i-1]] + values[i-1]` ，其中数组 weights 和 values 分 别表⽰所有物品的重量和价值，数组下标从0开始。

{{ select(24) }}

• 正确
• 错误

25. 栈中元素的插⼊和删除操作都在栈的顶端进⾏，所以⽅便⽤双向链表⽐单向链表更合适表实现。 {{ select(25) }}

• 正确

• 错误