单选题

1. 以下（ ）没有涉及Python语言的面向对象特性支持。

   {{ select(1) }}

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

2. 关于Python中面向对象的类的继承，下面说法错误的是（ ）

   {{ select(2) }}

• 子类可以通过继承不能访问到父类的所有属性
• 多个子类可以继承同一个父类
• 子类和子类产生的对象都可以通过句的方式拿到父类
• python中支持多继承

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. 采用如下代码实现检查输入的字符串括号是否匹配，横线上应填入的代码为（ ）。

{{ select(4) }}

• s.push(symbol)
• s.pop(symbol)
• s.push(index)
• s.pop(index)

5. 下面代码判断队列的第一个元素是否等于a，并删除该元素，横向上应填写（ ）。

{{ select(5) }}

• not q.empty() and q.queue[0] != a:
• not q.empty() and q.queue[0] == a:
• q.empty() and q.queue[0] == a:
• q.empty() and q.queue[0] != a:

6. 假设字母表{a,b,c,d,e}在字符串出现的频率分别为10%、15%、30%、16%、29%。若使用哈夫曼编码方式对字母进行二进制编码，则字符abcdef分别对应的一组哈夫曼编码的长度分别为（ ）。

   {{ select(6) }}

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

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

   def generate_gray_code(n):
       if n <= 0:
           return []
       if n == 1:
           return [0, 1]
       gray_code = generate_gray_code(n - 1)
       inverted_gray_code = [int(('1' * n + bin(x)[2:])[-n:], 2) for x in gray_code]
       return gray_code + inverted_gray_code
   

   {{ select(7) }}

• inverted_gray_code = [int(('0' * n + bin(x)[2:])[-n:], 2)
• inverted_gray_code = [int(('1' * n + bin(x)[2:])[-n:], 2)
• inverted_gray_code = [int(('1' * n + bin(x)[1:])[-n:], 2)
• inverted_gray_code = [int(('1' * n + bin(x)[2:])[n:], 2)

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

   {{ select(8) }}

• EDBGFCA
• EDGBFCA
• DEBGFCA
• DBEGFCA

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

   {{ select(9) }}

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

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

{{ select(10) }}

• return max(left_depth, right_depth)
• return min(left_depth, right_depth) + 1
• return max(left_depth, right_depth) + 1
• return max(left_depth, right_depth) - 1

11. 以下基于二叉树的搜索实现的深度计算函数中横线上应填写（ ）。

    def height(root):
        if root is None:
            return 0
        else:
            left_height = height(root.left)
            right_height = height(root.right)
            ______
    

    {{ select(11) }}

• return max(left_height, right_height) + 1
• return min(left_height, right_height) - 1
• return min(left_height, right_height) + 1
• return max(left_height, right_height) - 1

12. 二叉搜索树中的每个结点，其左子树的所有结点值都小于该结点值，右子树的所有结点值都大于该结点值。以下代码对给定的整数数组(假设数组中没有数值相等的元素)，构造一个对应的二叉搜索树，横线上应填写（ ）：

    class Solution:
        def isValidBST(self, root: TreeNode) -> bool:
            def helper(node, min_val, max_val):
                if not node:
                    return True
                if ______:
                    return False
                return helper(node.left, min_val, node.val) and helper(node.right, node.val, max_val)
            return helper(root, float('-inf'), float('inf'))
    

    {{ select(12) }}

• if node.val <= min_val or node.val >= max_val:
• if node.val >= min_val or node.val >= max_val:
• if node.val <= min_val or node.val <= max_val:
• if node.val >= min_val or node.val <= max_val:

13. 对上题中的二叉搜索树，当输入数组为[5,3,7,2,4,6,8]时，构建二叉搜索树，并采用如下代码实现的遍历方式，得到的输出是（ ）。

    def traversal(root):
        if root is None:
            return
        traversal(root.left)
        print(root.val, end=" ")
        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，则函数的输出为（ ）。

    def knapsack(capacity, weights, values):
        dp = [[0 for _ in range(capacity + 1)] for _ in range(len(weights) + 1)]
        for i in range(1, len(weights) + 1):
            for j in range(1, capacity + 1):
                if weights[i - 1] <= j:
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1])
                else:
                    dp[i][j] = dp[i - 1][j]
        return dp[-1][-1]
    

    {{ select(15) }}

• 90
• 100
• 110
• 140

判断题

1. C++、Python和JAVA等都是面向对象的编程语言。

   {{ select(16) }}

• 对
• 错

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

   {{ select(17) }}

• 对
• 错

3. 栈和队列均可通过数组或链表来实现，其中数组实现支持随机访问、占用内存较少、但插入和删除元素效率低；链表实现的元素插入与删除效率高，但元素访问效率低、占用内存较多。

   {{ select(18) }}

• 对
• 错

4. 运行以下Python代码，屏幕将输出“derived class”。

   class BaseClass:
       def my_method(self):
           print("base class")
   
   class DerivedClass(BaseClass):
       def my_method(self):
           print("derived class")
   
   derived_instance = DerivedClass()
   derived_instance.my_method()
   

   {{ select(19) }}

• 对
• 错

5. 如下列代码所示的基类（base）及其派生类（derived），则生成一个派生类的对象时，只调用派生类的构造函数。

   class Base:
       def __init__(self):
           print("Base.__init__ called")
   
   class Derived(Base):
       def __init__(self):
           print("Derived.__init__ called")
           super().__init__()
   
   d = Derived()
   

   {{ select(20) }}

• 对
• 错

6. 哈夫曼编码本质上是一种贪心策略。

   {{ select(21) }}

• 对
• 错

7. 如果根结点的深度记为1，则一棵恰有2个叶结点的二叉树的深度最少是2。

   {{ select(22) }}

• 对
• 错

8. 在非递归实现的树的广度优先搜索中，通常使用栈来辅助实现。

   {{ select(23) }}

• 对
• 错

9. 状态转移方程是动态规划的核心，可以通过递推方式表示问题状态的变化。

   {{ select(24) }}

• 对
• 错

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

    {{ select(25) }}

• 对
• 错