2026 华为OD机试真题 7月12日华为OD上机新系统考试真题 100 分题型

点击查看华为 OD 机试真题完整目录：2026最新华为OD机试新系统卷 + 双机位C卷 真题题库目录｜全覆盖题库 + 逐点算法考点详解

题目描述

在软件构建中，模块之间存在复杂的依赖关系。请基于给定的依赖规则和项目的直接依赖列表，按照依赖解析规则展开完整的依赖树，按 BFS 顺序输出所有依赖组件及其版本号。

2026 华为OD机试真题 7月12日华为OD上机新系统考试真题 100 分题型

数据格式

• 直接依赖 directDeps：项目所直接依赖的组件列表。每条格式为 name:version[:exclusions]，多个组件用英文逗号分隔，多个排除项用逗号分隔。例如 ["A:1.0","B:2.0:C,D"]。
• 依赖规则 depRules：每个组件的子依赖列表。每条格式为 name:depname:depversion[:exclusions]，表示 name 依赖 depname（版本 depversion），若附带排除项则 name 的依赖传递中排除这些名字。

解析规则

1. 从直接依赖出发，依次展开每个组件的子依赖，形成依赖树。
2. 使用 BFS（广度优先）遍历组件，同一层中按声明顺序处理父组件，父优先。
3. 同一组件只保留首次出现的位置，后续重复依赖需要去重。
4. 排除项沿路径向下传递：被排除的组件及其整个子树都不会被加入。
5. 子规则的 exclusions 与路径上的父级 exclusions 做集合并集后继续下传。

输出

按 BFS 顺序输出所有依赖组件（去重后），每个组件输出为 name:version。

输入描述

• 参数1：directDeps（字符串数组）：项目直接依赖列表。
• 参数2：depRules（字符串数组）：依赖规则列表。

输出描述

按解析后 BFS 顺序输出每个依赖项，格式为 name:version，用逗号分隔，整体用方括号包围，例：["A:1.0","B:1.0","C:1.0"]。

示例1

输入

["A:1.0"]
["A:B:1.0","A:C:1.0"]

输出

["A:1.0","B:1.0","C:1.0"]

说明

• 项目直接依赖 A:1.0。
• A 声明依赖 B:1.0 和 C:1.0。
• BFS 顺序：A → B → C。

示例2

输入

["A:1.0:EXCL"]
["A:B:1.0","B:C:1.0"]

输出

["A:1.0"]

说明

• 项目直接依赖 A:1.0，并排除 EXCL。
• A 规则依赖 B，但在 A 路径上没有任何名为 EXCL 的子依赖，因此该排除集合不影响 B。
• 但当 A 处理完直接依赖即终止，不引入 B，因此输出仅 A:1.0。

解题思路

核心思想

依赖树展开本质是广度优先搜索（BFS）：从直接依赖出发，逐层展开所有子依赖，同时维护已访问集合用于去重，使用排除集合沿路径传递来剪枝。

算法步骤

1. 解析规则：将 depRules 解析为 name → [(depname, depversion, excl_set), ...] 的映射，保持声明顺序。
2. 初始化队列：将每条直接依赖 (name, version, excl) 加入队列。
3. BFS 遍历：
   • 取出队首 (name, version, excl)，若已访问则跳过。
   • 加入答案 name:version，标记已访问。
   • 遍历该组件的子依赖规则：若 depname 被当前 excl 排除则跳过；否则将 (depname, depversion, excl | child_excl) 加入队列。
4. 返回结果列表。

复杂度分析

• 时间复杂度：O(N + M)，N 为依赖组件数，M 为规则数。每个组件最多入队一次。
• 空间复杂度：O(N + M)，用于规则表、队列、答案和已访