Questão de Algoritmos e Estrutura de Dados — Algoritmos — IF-ES 2025
Algoritmos e Estrutura de Dados›Algoritmos
Código
qg529114
Banca
IF-ES
Órgão
IF-ES
Ano
2025
Nível
Médio
Cargo
Técnico de Laboratório / Área: Informática
Considere o código de uma árvore implementado na linguagem Javascript, descrito a seguir:class TreeNode {constructor(value) {this.value = value;this.children = [];}addChild(child) {this.children.push(child);}}class Tree {constructor(value) {this.root = new TreeNode(value);}compute(value) {if (!this.root) return null;const queue = [this.root];while (queue.length > 0) {const current = queue.shift();if (current.value === value) {return current;}for (const child of current.children) {queue.push(child);}}return null;}}O método compute do código é conhecido pelo acrônimo em inglês:
ADFS - Depth-First Search.
BBFS - Breadth-First Search.
CDAS - Directed Acyclic Search.
DMST - Minimum Spanning Tree.
EMBM - Maximum Bipartite Matching.
Revelar gabarito e comentário▾
GabaritoB — BFS - Breadth-First Search.
Comentário gerado por IA. É um apoio ao estudo, ancorado em fontes, mas pode conter imprecisões — confira sempre na fonte oficial (lei, súmula, edital e gabarito da banca). Encontrou um erro? Use “Reportar”.
Busca em Árvores: BFS vs DFS
Gabarito: letra B. O método compute implementa uma busca em largura (Breadth-First Search – BFS), pois utiliza uma fila (queue) para percorrer os nós por níveis: insere a raiz, remove o primeiro elemento, verifica o valor e adiciona todos os filhos ao final da fila. Esse comportamento é característico de BFS, ao contrário da busca em profundidade (DFS) que usaria uma pilha.
A banca testa o conhecimento sobre os algoritmos clássicos de percurso em árvores/grafos. O código JavaScript é claro:
const queue = [this.root]; // fila inicializada com a raiz
while (queue.length > 0) {
const current = queue.shift(); // remove o primeiro nó (FIFO)
if (current.value === value) return current;
for (const child of current.children) {
queue.push(child); // adiciona filhos ao final
}
}
O uso de shift() (remove do início) e push() (adiciona ao fim) garante o comportamento FIFO (First-In, First-Out), típico de BFS. Se fosse DFS, usaríamos pop() (remove do fim) – uma pilha.
Algoritmo
Estrutura de Dados
Comportamento
Acrônimo
Busca em Largura
Fila (FIFO)
Remove do início (shift) e adiciona ao fim (push)
BFS
Busca em Profundidade
Pilha (LIFO)
Remove do fim (pop) e adiciona ao fim (push)
DFS
1Inicializa fila com raiz
2Remove primeiro nó (shift)
3Verifica se é o valor buscado
4Adiciona filhos ao final (push)
5Repete até fila vazia
LEVEL · soulevel.com.br
Alternativa A — ❌ Incorreta
DFS (Depth-First Search) utiliza uma pilha (LIFO) para explorar profundamente cada ramo antes de retroceder. O código emprega fila, não pilha.
Alternativa B — ✅ Correta ⟵ GABARITO
BFS (Breadth-First Search) percorre a árvore por níveis, visitando todos os nós de uma profundidade antes de passar para a próxima. O uso de fila (shift/push) é a marca registrada desse algoritmo.
Alternativa C — ❌ Incorreta
DAS (Directed Acyclic Search) não é um acrônimo padrão para algoritmos de busca. Pode haver confusão com grafos acíclicos dirigidos, mas não se aplica ao método.
Alternativa D — ❌ Incorreta
MST (Minimum Spanning Tree) é um problema de encontrar a árvore geradora mínima em grafos ponderados, resolvido por algoritmos como Kruskal ou Prim. Não há relação com o método de busca apresentado.
Alternativa E — ❌ Incorreta
MBM (Maximum Bipartite Matching) é um problema de emparelhamento máximo em grafos bipartidos, resolvido por algoritmos como Ford-Fulkerson ou Hopcroft-Karp. Totalmente fora do contexto.
PEGA ESSA DICA!
Na prova, ao se deparar com um loop que remove do início e insere no fim de uma estrutura, lembre-se: fila → BFS. Se remover e inserir sempre no mesmo lado, pilha → DFS. Esse pequeno detalhe decide a questão.