Pular para o conteúdo principal

Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — CONSULPAM 2026

Algoritmos e Estrutura de DadosEstrutura de Dados
Código
qg660561
Banca
CONSULPAM
Órgão
GHC-RS
Ano
2026
Nível
Médio
Cargo
Programador
Grafos caracterizam uma das estruturas de dados mais poderosas da computação, sendo empregados em diversos processos de negócio. Acerca do tema, analise as sentenças a seguir:I- Em grafos não ponderados, uma busca em largura iniciada em um vértice de origem é adequada para determinar um caminho com o menor número de arestas para cada vértice alcançável.PORQUEII- A BFS explora os vértices em camadas de distância crescente a partir da origem, utilizando uma estrutura do tipo fila para processar primeiro os vértices descobertos mais cedo.Analisadas as sentenças, assinale a alternativa CORRETA:
  1. AAs duas sentenças são verdadeiras, e a segunda é uma justificativa correta da primeira.
  2. BAs duas sentenças são verdadeiras, mas a segunda não é uma justificativa correta da primeira.
  3. CA primeira sentença é verdadeira, e a segunda, falsa.
  4. DA primeira sentença é falsa, e a segunda, verdadeira.
  5. ETanto a primeira sentença quanto a segunda sentença são falsas.
Revelar gabarito e comentário

GabaritoA — As duas sentenças são verdadeiras, e a segunda é uma justificativa correta da primeira.

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”.

Grafos e Busca em Largura (BFS)

Gabarito: letra A. Ambas as sentenças são verdadeiras, e a segunda justifica corretamente a primeira. A BFS, por explorar vértices em camadas de distância crescente usando uma fila, garante encontrar o caminho de menor número de arestas em grafos não ponderados.

Análise das sentenças

I – Verdadeira. Em grafos não ponderados, a busca em largura (BFS) a partir de um vértice fonte determina, para cada vértice alcançável, um caminho com o menor número de arestas. Essa é uma propriedade clássica da BFS, pois ela visita vértices em ordem crescente de distância do vértice inicial.

II – Verdadeira. A BFS explora os vértices em camadas: primeiro os vizinhos diretos (distância 1), depois os vizinhos dos vizinhos (distância 2), e assim sucessivamente. Para isso, utiliza uma estrutura de dados do tipo fila (FIFO), garantindo que os vértices descobertos mais cedo sejam processados primeiro. Essa descrição corresponde exatamente ao algoritmo padrão da BFS.

Relação entre as sentenças

A sentença II explica o porquê da sentença I ser verdadeira. O uso da fila e a exploração por camadas de distância crescente é a razão pela qual a BFS encontra o caminho mínimo em número de arestas. Portanto, a segunda é uma justificativa correta da primeira.

1Estrutura
Fila (FIFO)
Explora por camadas
2Propriedade
Caminho mínimo em arestas
Grafos não ponderados
3Contraste com DFS
Pilha (LIFO)
Não garante caminho mínimo
Busca em Largura (BFS)
LEVELsoulevel.com.br
Busca em Largura (BFS): Estrutura (Fila (FIFO), Explora por camadas); Propriedade (Caminho mínimo em arestas, Grafos não ponderados); Contraste com DFS (Pilha (LIFO), Não garante caminho mínimo)
NÃO CAIA NESSA!

A banca pode tentar confundir a BFS com a busca em profundidade (DFS). Enquanto a BFS usa fila e garante caminhos mínimos em grafos não ponderados, a DFS usa pilha e não oferece essa garantia. Lembre-se: BFS → fila → camadas → caminho mínimo.

Conclusão: Alternativa A – ambas verdadeiras e a segunda justifica a primeira.

Gabarito: letra A

Link permanente: /questoes/qg660561