1. 数据结构：二叉树遍历的非递归实现

问题：写出二叉树先序遍历的非递归算法，并分析其时间复杂度。
考点：栈的应用、遍历算法的灵活实现。

回答：

def preorderTraversal(root):
    stack, result = [], []
    if root:
        stack.append(root)
    while stack:
        node = stack.pop()
        result.append(node.val)
        if node.right:  # 右子节点先入栈
            stack.append(node.right)
        if node.left:   # 左子节点后入栈
            stack.append(node.left)
    return result

时间复杂度：O(n)，其中n为节点数。每个节点入栈出栈各一次。

2. 算法设计与分析：动态规划

问题：给定一组物品的重量和价值，如何用动态规划求解0-1背包问题？写出状态转移方程并解释其含义。
考点：动态规划思想、最优子结构分析。

回答：定义状态 𝑑𝑝[𝑖][𝑗] 表示前i个物品在容量j下的最大价值。状态转移方程为：
𝑑𝑝[𝑖][𝑗]=max⁡(𝑑𝑝[𝑖−1][𝑗],𝑑𝑝[𝑖−1][𝑗−𝑤𝑖]+𝑣𝑖))
解释：

不选第i个物品：𝑑𝑝[𝑖−1][𝑗]
选第i个物品：𝑑𝑝[𝑖−1][𝑗−𝑤𝑖]+𝑣𝑖）

3. 操作系统：虚拟内存管理

问题：解释页面置换算法中的LRU（最近最少使用）策略，并说明其实现难点及优化方法。
考点：虚拟内存机制、硬件支持（如TLB）、算法效率。

回答：

4. 计算机网络：TCP与UDP协议对比

问题：TCP的三次握手过程为何能保证可靠连接？UDP适用于哪些场景？
考点：协议设计原理、可靠传输与实时性权衡。

5. 计算机组成原理：流水线冲突处理

问题：CPU流水线中的结构冲突、数据冲突和控制冲突分别如何解决？举例说明。
考点：流水线优化技术（如转发、分支预测）。

6. 数据库系统：事务与锁机制

问题：什么是事务的ACID特性？共享锁（S锁）和排他锁（X锁）的区别是什么？
考点：并发控制、隔离级别与锁粒度。

7. 编译原理：词法分析与正则表达式

问题：设计一个正则表达式，用于匹配C语言中的浮点数常量（如3.14e-5），并画出对应的NFA。
考点：形式语言理论、自动机转换。

8. 软件工程：白盒测试与黑盒测试

问题：比较白盒测试中的条件覆盖和路径覆盖的优缺点，并给出测试用例设计示例。
考点：测试策略选择、代码覆盖率分析。

9. 离散数学：图论应用

问题：证明一个无向连通图的边数至少为顶点数减一（即 𝑚≥𝑛−1m≥n−1），并说明等号成立的条件。
考点：树的性质、数学归纳法。

10. 算法应用题：哈夫曼编码

问题：给定字符集频率表 {A:5, B:9, C:12, D:13, E:16, F:45}，构造哈夫曼树并计算其带权路径长度（WPL）。
考点：贪心算法、优先级队列实现。

[𝑗]: