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

1. 以下（ ） 没有涉及 C++ 语⾔的⾯向对象特性⽀持。

{{ select(1) }}

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

2. 关于以下C++代码， （ ） ⾏代码会引起编译错误。

   #include <iostream>
   using namespace std;
   
   class Base {
   private:
   	int a;
   protected:
   	int b;
   public:
   	int c;
   	Base() : a(1), b(2), c(3) {}
   };
   
   class Derived : public Base {
   public:
   	void show() {
   		cout << a << endl; // Line 1
   		cout << b << endl; // Line 2
   		cout << c << endl; // Line 3
   	}
   };
   

{{ select(2) }}

• Line 1
• Line 2
• Line 3
• 没有编译错误

3. 有6个元素， 按照 6,5,4,3,2,1 的顺序进⼊栈S， 下列（ ） 的出栈序列是不能出现的（ ） 。

{{ select(3) }}

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

4. 采⽤如下代码实现检查输⼊的字符串括号是否匹配， 横线上应填⼊的代码为

   #include <iostream>
   #include <stack>
   #include <string>
   
   using namespace std;
   
   bool is_valid(string s) {
   	stack<char> st;
   	char top;
       
   	for (char& ch : s) {
   		if (ch == '(' || ch == '{' || ch == '[') {
   		st.push(ch); // 左括号入栈
   		}
       	else
   		{
   			if (st.empty())
   				return false;
   			———————————————————————— // 在此处填入代码
   			if ((ch == ')' && top != '(') ||
   				(ch == '}' && top != '{') ||
   				(ch == ']' && top != '[')) {
   					return false;
   			}
   		}
   	} 
       
   	return st.empty(); // 栈为空则说明所有括号匹配成功
   }
   

{{ select(4) }}

• top = st.top(); st.pop();
• st.pop(); top = st.top();
• st.pop(); top = st.front();
• top = st.front(); st.pop();

5. 下⾯代码判断队列的第⼀个元素是否等于 ， 并删除该元素， 横向上应填写

   #include <iostream>
   #include <queue>
   using namespace std;
   bool is_front_equal(std::queue<int>& q, int a) {
   	bool is_equal = false;
   	if (!q.empty()) {
   		———————————————————————— // 在此处填入代码
   	}
   	return is_equal;
   }
   

{{ select(5) }}

• is_equal = (q.front() == a);
• is_equal = (q.front() == a);
• q.pop(); is_equal = (q.front() == a);
• q.pop(); is_equal = (q.front() == a);

6. 假设字母表 {a,b,c,d,e} 在字符串出现的频率分别为 10%， 15%， 30%， 16%， 29%。 若使⽤哈夫曼编码⽅ 式对字母进⾏⼆进制编码， 则字符 abcdef 分别对应的⼀组哈夫曼编码的长度分别为

{{ select(6) }}

• 4, 4, 1, 3, 2
• 4, 4, 1, 3, 2
• 3, 3, 1, 2, 1
• 4, 4, 1, 2, 2

7. 以下C++代码实现 位的格雷码， 则横线上应填写 （ ）。

   #include <iostream>
   #include <vector>
   #include <string>
   using namespace std;
   // 生成 n 位的格雷码
   vector<string> generate_graycode(int n) {
   	vector<string> graycode_list;
   	if (n <= 0) {
   		return graycode_list;
   	} 
       	
   	// 初始1位格雷码
   	graycode_list.push_back("0");
   	graycode_list.push_back("1");
       
   	// 迭代生成 n 位的格雷码
   	for (int i = 2; i <= n; i++) {
   		int current_size = graycode_list.size();
           
   		for (int j = current_size - 1; j >= 0; j--) {
   			graycode_list.push_back("1" + graycode_list[j]);
   		}
           
   		for (int j = 0; j < current_size; j++) {
      		 ———————————————————————— // 在此处填入代码
   		}
   	} 
       
   	return graycode_list;
   }
   

{{ select(7) }}

• graycode_list.push_back("0" + graycode_list[j]);

• graycode_list[j] = "0" + graycode_list[j];

• graycode_list.push_back("1" + graycode_list[j])

• graycode_list[j] = "1" + graycode_list[j];

8. 给定⼀棵⼆叉树， 其前序遍历结果为： ABDECFG,中序遍历结果为： DEBACFG， 则这棵树的正确后序遍历 结果是

{{ select(8) }}

• EDBGFCA
• EDGBFCA
• DEBGFCA
• DBEGFCA

9. ⼀棵有个结点的完全⼆叉树⽤数组进⾏存储与表⽰， 已知根结点存储在数组的第1个位置。 若存储在数组第9个位置的结点存在兄弟结点和两个⼦结点， 则它的兄弟结点和右⼦结点的位置分别是

{{ select(9) }}

• 8, 18
• 10, 18
• 8, 19
• 10, 19

10. ⼆叉树的深度定义为从根结点到叶结点的最长路径上的结点数， 则以下基于⼆叉树的深度优先搜索实现的 深度计算函数中横线上应填写

    // 定义二叉树的结点结构
    struct tree_node {
    	int val;
    	tree_node* left;
    	tree_node* right;
        
    	tree_node(int x) : val(x), left(nullptr), right(nullptr) {}
    };
    
    // 计算二叉树的深度
    int max_depth(tree_node* root) {
    	if (root == nullptr) {
    		return 0; // 如果根结点为空， 则深度为 0
    	} 
        
    	int left_depth = max_depth(root->left);
    	int right_depth = max_depth(root->right);
        
    	 ———————————————————————— // 在此处填入代码
    }
    

{{ select(10) }}

• return left_depth + right_depth;
• return max(left_depth, right_depth);
• return max(left_depth, right_depth);
• return left_depth + right_depth + 1;

11. 上⼀题的⼆叉树深度计算还可以采⽤⼆叉树的⼴度优先搜索来实现。 以下基于⼆叉树的⼴度优先搜索实现 的深度计算函数中横线上应填写

    #include <queue>
    
    int max_depth_bfs(tree_node* root) {
    	if (root == nullptr) {
    		return 0; // 如果树为空， 深度为 0
    	} 
        
    	queue <tree_node*> q;
    	q.push(root);
    	int depth = 0;
        
    	// 使用队列进行层序遍历
    	while (!q.empty()) {
    		———————————————————————— // 在此处填入代码
    		for (int i = 0; i < level_size; ++i) {
    			tree_node* node = q.front();
    			q.pop();
                
    			if (node->left) {
    				q.push(node->left);
    			}
    			if (node->right) {
    				q.push(node->right);
    			}
    		}
    	} 
        
    	return depth;
    }
    

{{ select(11) }}

• int level_size = q.size(); depth++;
• int level_size = 2; depth++;
• int level_size = q.size(); depth += level_size;
• int level_size = 2; depth += level_size;

12. ⼆叉搜索树中的每个结点， 其左⼦树的所有结点值都⼩于该结点值， 右⼦树的所有结点值都⼤于该结点值。 以下代码对给定的整数数组(假设数组中没有数值相等的元素)， 构造⼀个对应的⼆叉搜索树， 横线上应填写

    / 定义二叉树的结点结构
    struct tree_node {
    	int val;
    	tree_node* left;
    	tree_node* right;
        
    	tree_node(int x) : val(x), left(nullptr), right(nullptr) {}
    };
    
    // 插入结点到二叉搜索树中
    tree_node* insert(tree_node* root, int val) {
    	if (root == nullptr) {
    		return new tree_node(val);
    	} 
        
        ———————————————————————— // 在此处填入代码
            
    	return root;
    } 
    
    // 根据给定数组构造二叉搜索树
    tree_node* constructBST(const int arr[], int size) {
    	tree_node* root = nullptr;
        
    	for (int i = 0; i < size; ++i) {
    		root = insert(root, arr[i]);
    	} 
    	return root;
    }
    

{{ select(12) }}

• if (val < root->val)
  	root->left = insert(root->left, val);
  else
  	root->right = insert(root->right, val);
  

• if (val > root->val)
  	root->left = insert(root->left, val);
  else
  	root->right = insert(root->right, val);
  

• if (val < root->val)
  	root->left = insert(root, val);
  else
  	root->right = insert(root, val);
  

• if (val > root->val)
  	root->left = insert(root, val);
  else
  	root->right = insert(root, val);
  
  

13. 对上题中的⼆叉搜素树， 当输⼊数组为 时， 构建⼆叉搜索树， 并采⽤如下代码实现的遍历⽅式， 得到 的输出是

```cpp
#
include <iostream>
using namespace std;
// 遍历二叉搜索树， 输出结点值
void traversal(tree_node* root) {
	if (root == nullptr) {
		return;
	} 
	traversal(root->left);
	cout << root->val << " ";
	traversal(root->right);
}

{{ select(13) }}

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

14. 动态规划通常⽤于解决

{{ select(14) }}

• ⽆法分解的问题
• 可以分解成相互依赖的⼦问题的问题
• 可以通过贪⼼算法解决的问题
• 只能通过递归解决的问题

15. 阅读以下⽤动态规划解决的0-1背包问题的函数， 假设背包的W容量 是10kg， 假设输⼊4个物品的重量weights分别为1,3,4,6 （单位为kg） ， 每个物品对应的价值values分别为20,30,50,60 ， 则函数的输出为

    #include <iostream>
    #include <vector>
    using namespace std;
    // 0/1背包问题
    int knapsack(int W, const vector<int>& weights, const vector<int>& values, int n) {
    	vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
    	for (int i = 1; i <= n; ++i) {
    		for (int w = 0; w <= W; ++w) {
    			if (weights[i - 1] <= w) {
    				dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] +values[i - 					1]);
    			}
    			else
    			{
    				dp[i][w] = dp[i - 1][w];
    			}
    		}
    	} 
    	return dp[n][W];
    }
    

{{ select(15) }}

• $90$
• $100$
• $110$
• $140$

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

16. C++、 Python和JAVA等都是⾯向对象的编程语⾔。

{{ select(16) }}

• 正确
• 错误

17. 在C++中， 类的静态成员变量只能被该类对象的成员函数访问。

{{ select(17) }}

• 正确
• 错误

18. 栈是⼀种线性结构， 可通过数组或链表来实现。 ⼆者相⽐， 数组实现占⽤的内存较少， 链表实现的⼊队和出队操作的时间复杂度较低。

    {{ select(18) }}

• 正确
• 错误

19. 运⾏以下C++代码， 屏幕将输出“derived class”。

    #include <iostream>
    using namespace std;
    
    class base {
    	public:
    	virtual void show() {
    		cout << "base class" << endl;
    	}
    };
    
    class derived : public base {
    	public:
    		void show() override {
    			cout << "derived class" << endl;
    		}
    };
    
    int main() {
    	base* b;
    	derived d;
    	b = &d;
        b->show();
    	return 0;
    }
    

{{ select(19) }}

• 正确
• 错误

20. 如下列代码所⽰的基类（base） 及其派⽣类（derived） ， 则⽣成⼀个派⽣类的对象时， 只调⽤派⽣类的构造函数

    #include <iostream>
    using namespace std;
    
    class base {
    	public:
    	base() {
    		cout << "base constructor" << endl;
    	}
    	~base() {
    		cout << "base destructor" << endl;
    	}
    };
    
    class derived : public base {
    	public:
    		derived() {
    			cout << "derived constructor" << endl;
    		}
    		~derived() {
    			cout << "derived destructor" << endl;
    		}
    };
    

    {{ select(20) }}

• 正确

• 错误

21. 哈夫曼编码本质上是⼀种贪⼼策略。

    {{ select(21) }}

• 正确
• 错误

22. 如果根结点的深度记为1， 则⼀棵恰有2024个叶结点的⼆叉树的深度最少是12 。

{{ select(22) }}

• 正确
• 错误

23. 在⾮递归实现的树的⼴度优先搜索中， 通常使⽤栈来辅助实现。

    {{ select(23) }}

• 正确
• 错误

24. 状态转移⽅程是动态规划的核⼼， 可以通过递推⽅式表⽰问题状态的变化。

{{ select(24) }}

• 正确
• 错误

25. 应⽤动态规划算法时， 识别并存储重叠⼦问题的解是必须的。

{{ select(25) }}

• 正确

• 错误