Pular para o conteúdo principal

Questão de Algoritmos e Estrutura de Dados — Conceitos Básicos e Algoritmos — IF Sul Rio-Grandense 2021

Algoritmos e Estrutura de DadosConceitos Básicos e Algoritmos
Código
qq658745
Banca
IF Sul Rio-Grandense
Órgão
IF Sul Rio-Grandense
Ano
2021
Nível
Superior
Cargo
Professor - Informação e Comunicação
Considerando algoritmos que podem ser usados para percorrer grafos, afirma-se que
  1. Ano algoritmo DFS, ao armazenar os vértices em uma pilha, os vértices serão explorados ao longo de um caminho, visitando um novo vértice adjacente se houver um disponível.
  2. Bno algoritmo BFS, ao armazenar os vértices em uma pilha, os vértices serão explorados ao longo de um caminho, visitando um novo vértice adjacente se houver um disponível.
  3. Cno algoritmo DFS, ao armazenar os vértices em uma fila, os vértices serão explorados ao longo de um caminho, visitando um novo vértice adjacente se houver um disponível.
  4. Dno algoritmo BFS, ao armazenar os vértices em um grafo, os vértices serão explorados ao longo de um caminho, visitando um novo vértice adjacente se houver um disponível.
Revelar gabarito e comentário

GabaritoA — no algoritmo DFS, ao armazenar os vértices em uma pilha, os vértices serão explorados ao longo de um caminho, visitando um novo vértice adjacente se houver um disponível.

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: DFS e BFS

Gabarito: letra A. O algoritmo DFS (Depth-First Search) utiliza uma estrutura de pilha (stack) para explorar os vértices ao longo de um caminho, visitando um novo vértice adjacente não visitado sempre que possível. As demais alternativas trocam a estrutura de dados ou o algoritmo.

A questão testa o conhecimento básico sobre as estruturas de dados usadas nos percursos em grafos.

Percursos em grafos
  • 1DFS (profundidade)
    • Estrutura: Pilha (LIFO)
    • Exploração: ao longo de um caminho
  • 2BFS (largura)
    • Estrutura: Fila (FIFO)
    • Exploração: nível a nível
LEVEL · soulevel.com.br

Alternativa A — ✅ Correta ⟵ GABARITO

No DFS, os vértices são armazenados em uma pilha (explícita ou implicitamente via recursão), e a exploração segue um caminho até o fim antes de retroceder. A descrição está perfeita.

Alternativa B — ❌ Incorreta

Afirma que o BFS usa pilha. Na verdade, o BFS utiliza uma fila (queue) para visitar os vértices em largura (nível a nível), não ao longo de um único caminho. Confunde BFS com DFS.

Alternativa C — ❌ Incorreta

Afirma que o DFS usa fila. O DFS usa pilha, não fila. A descrição do percurso ao longo de um caminho é correta para DFS, mas a estrutura está errada.

Alternativa D — ❌ Incorreta

Afirma que o BFS armazena vértices em um grafo (o que é a própria estrutura) e explora ao longo de um caminho. O BFS usa fila para controlar a ordem de visita e explora em largura, não ao longo de um caminho. A descrição é inconsistente.

PEGA ESSA DICA!

Para fixar, lembre-se: DFS = Deep (profundidade) → Pilha (LIFO, como uma pilha de pratos). BFS = Breadth (largura) → Fila (FIFO, como uma fila de banco). A troca da estrutura de dados é um erro clássico em provas.

Link permanente: /questoes/qq658745