单选题

1. 下列哪一项不是面向对象编程（OOP）的基本特征？

   {{ select(1) }}

• 继承 (Inheritance)
• 封装 (Encapsulation)
• 多态 (Polymorphism)
• 链接 (Linking)

2. 为了让 Dog 类的构造函数能正确地调用其父类 Animal 的构造方法，横线处应填入（ ）。

{{ select(2) }}

• 

• 

• 

• 

3. 代码同上一题，代码 animal.speak() 执行后输出结果是（ ）。

   {{ select(3) }}

• 输出 Animal speaks
• 输出 Dog barks
• 编译错误
• 程序崩溃

4. 以下Python代码执行后其输出是（ ）。

   from collections import deque
   stack = []
   queue = deque()
   
   # 元素入栈/入队 (1, 2, 3)
   for i in range(1, 4):
       stack.append(i)
       queue.append(i)
   print(f"{stack[-1]} {queue[0]})")
   

   {{ select(4) }}

• 13
• 31
• 33
• 11

5. 在一个使用列表实现的循环队列中，front 表示从头元素的位置（索引），rear 表示队尾元素的下一个插入位置（索引），队列的最大容量为 maxSize。那么判断队列已满的条件是（ ）。

   {{ select(5) }}

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

6. 在二叉树中，只有最底层的节点未被填满，且最底层节点尽量靠近填充的是（ ）。

   {{ select(6) }}

• 完美二叉树
• 完全二叉树
• 完满二叉树
• 平衡二叉树

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

   {{ select(7) }}

• ((i-1)/2)
• ( i+1)
• ( i*2)
• ( 2*i+1 )

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

   {{ select(8) }}

• ADFGEHMZ
• ADFGHMEZ
• AFDGEMZH
• AFDHZMEG

9. 设有字符集 ({a, b, c, d, e})，其出现频率分别为 ({5, 8, 12, 15, 20})，得到的哈夫曼编码为（ ）。

   {{ select(9) }}

• 1 a: 010 
  2 b: 011 
  3 c: 00 
  4 d: 10 
  5 e: 11 
  

• 1 a: 00 
  2 b: 10 
  3 c: 011 
  4 d: 100 
  5 e: 111 
  

• 1 a: 10 
  2 b: 01 
  3 c: 011 
  4 d: 100 
  5 e: 111 
  

• 1 a: 100 
  2 b: 01 
  3 c: 011 
  4 d: 100 
  5 e: 00 
  

10. 3位格雷编码中，编码101之后的下一个编码是（ ）。

    {{ select(10) }}

• 100
• 110
• 001

11. 请将下列Python实现的深度优先搜索（DFS）代码补充完整，横线处应填入（ ）。

{{ select(11) }}

• result.append(root.val)
  dfs_preorder(root.left, result)
  dfs_preorder(root.right, result)
  

• result.append(root.val)
  dfs_preorder(root.left, result)
  

• result.append(root.val)
  dfs_preorder(root.right, result)
  

• dfs_preorder(root.left, result)
  dfs_preorder(root.right, result)
  

12. 给定一个二叉树，返回每一层中最大的节点值，结果以数组形式返回，横线处应填入（ ）。

    

    {{ select(12) }}

• 1  node = queue.popright()
  2  max_val = max(max_val, node.val)
  

• 1  node = queue.popleft()
  

• 1  max_val = max(max_val, node.val)
  

• 1  node = queue.popleft()
  2  max_val = max(max_val, node.val)
  

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

{{ select(13) }}

• 1  if key < root.val:
  2      root.left = insert(root.left, key)
  3  elif key > root.val:
  4      root.right = insert(root.right, key)
  

• 1  if key > root.val:
  2      root.left = insert(root.left, key)
  3  elif key > root.val:
  4      root.right = insert(root.right, key)
  

• 1  if key < root.val:
  2      root.left = insert(root.left, key)
  3  elif key >= root.val:
  4      root.right = insert(root.left, key)
  

• 1  if key < root.val:
  2      root.left = insert(root.right, key)
  3  elif key > root.val:
  4      root.right = insert(root.left, key)
  

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

    {{ select(14) }}

• 子问题相互独立，不重叠
• 问题包含重叠子问题和最优子结构
• 只能从底至顶迭代求解
• 必须使用递归实现，不能使用迭代

15. 给定个物品和一个最大承重为的背包，每个物品有一个重量和价值，每个物品只能选择放或不放。目标是选择若干个物品放入背包，使得总价值最大，且总重量不超过。关于下面代码，说法正确的是（ ）。

    def knapsack1D(W: int, wt: list[int], val: list[int], n: int) -> int:
        dp = [0] * (W + 1)
        for i in range(n):
            for w in range(W, wt[i] - 1, -1):
                dp[w] = max(dp[w], dp[w - wt[i]] + val[i])
        return dp[W]
    

    {{ select(15) }}

• 该算法不能处理背包容量为 0 的情况
• 外层循环 i 遍历背包容量，内层遍历物品
• 从大到小遍历 w 是为了避免重复使用同一物品
• 这段代码计算的是最小重量而非最大价值

判断题

1. 构造函数只能自动不可以被手动调用。（ ）

   {{ select(16) }}

• 对
• 错

2. 给定一组字符及其出现的频率，构造出的哈夫曼树是唯一的。（ ）

   {{ select(17) }}

• 对
• 错

3. 为了实现一个队列，使其出队操作（pop）的时间复杂度为(O(1))并且避免数组删除首元素的(O(n))问题。一种常见且有效的方法是使用环形数组，通过调整队首和队尾指针来实现。（ ）

   {{ select(18) }}

• 对
• 错

4. 对一棵从小到大的一叉排序树进行中序遍历，可以得到一个递增的有序序列。（ ）

   {{ select(19) }}

• 对
• 错

5. 如果二叉搜索树在连续的插入和删除操作后，所有节点都偏向一侧，导致其退化为类似于链表的结构，这时其查找、插入、删除操作的时间复杂度会从理想情况下的(O(logn))退化到(O(nlogn))。（ ）

   {{ select(20) }}

• 对
• 错

6. 执行下列代码，my_dog.name 的最终值是 Charlie。（ ）

   class Dog:
       def __init__(self, name):
           self.name = name
   
   if __name__ == "__main__":
       my_dog = Dog("Buddy")
       my_dog.name = "Charlie"
   

   {{ select(21) }}

• 对
• 错

7. 下列python代码可以成功执行，并且子类 Child 的实例能通过其成员函数访问父类 Parent 的属性 value。（ ）

   class Parent:
       def __init__(self):
           self._value = 100
   
   class Child(Parent):
       def get_protected_val(self):
           return self._value
   

   {{ select(22) }}

• 对
• 错

8. 下列代码中的 tree 列表，表示的是一棵完全二叉树（-1 代表空节点)按照层序遍历的结果。（ ）

   tree = [1, 2, 3, 4, -1, 6, 7]
   

   {{ select(23) }}

• 对
• 错

9. 在树的深度优先搜索（DFS）中，可以使用栈作为辅助数据结构以实现“先进后出”的访问顺序。（ ）

   {{ select(24) }}

• 对
• 错

10. 下面代码采用动态规划求解零线兑换问题：给定n种硬币，第i种硬币的面值为 (coins[i - 1])，目标金额为 (amt)，每种硬币可以重复选取，求能够发出目标金额的最少硬币数量；如果不能发出目标金额，返回 -1。（ ）

    def coinChangeDPComp(coins: list[int], ant: int) -> int:
        n = len(coins)
        MAX = ant + 1
        dp = [MAX] * (ant + 1)
        dp[0] = 0
        for i in range(1, n + 1):
            for a in range(1, ant + 1):
                if coins[i - 1] > a:
                    dp[a] = dp[a]
                else:
                    dp[a] = min(dp[a], dp[a - coins[i - 1]] + 1)
        return dp[amt] if dp[amt] != MAX else -1
    

    {{ select(25) }}

• 对
• 错