Pular para o conteúdo principal

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

Algoritmos e Estrutura de DadosAlgoritmos
Código
qg685517
Banca
FUNDATEC
Órgão
IFC-SC
Ano
2026
Nível
Superior
Cargo
Professor EBTT - Computação
Sobre divisão e conquista, memoização e programação dinâmica, assinale a alternativa correta.
  1. ASempre que um algoritmo recursivo apresenta subproblemas sobrepostos, a estratégia adequada é divisão e conquista, pois a independência entre subproblemas evita recomputações.
  2. BA memoização é uma abordagem iterativa de baixo para cima: percorre todos os subproblemas em ordem crescente de tamanho, armazenando cada resultado sequencialmente em tabela antes de resolver qualquer subproblema de tamanho maior.
  3. CA tabulação resolve, de forma iterativa, apenas os subproblemas que seriam efetivamente alcançados pela versão recursiva do mesmo algoritmo, evitando computações desnecessárias com estados inatingíveis
  4. DDivisão e conquista e programação dinâmica são estratégias equivalentes: ambas subdividem o problema em partes menores, resolvem cada parte e combinam os resultados — a diferença é apenas notacional, não algorítmica.
  5. EA memoização é uma estratégia top-down: aplicada a algoritmos recursivos, armazena o resultado de cada subproblema na primeira vez que é calculado, reutilizando-o em chamadas subsequentes; a tabulação é bottom-up e preenche a tabela iterativamente em ordem crescente de tamanho de subproblema.
Revelar gabarito e comentário

GabaritoE — A memoização é uma estratégia top-down: aplicada a algoritmos recursivos, armazena o resultado de cada subproblema na primeira vez que é calculado, reutilizando-o em chamadas subsequentes; a tabulação é bottom-up e preenche a tabela iterativamente em ordem crescente de tamanho de subproblema.

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

Paradigmas de Algoritmos

Gabarito: letra E. A alternativa E descreve corretamente memoização como abordagem top-down recursiva com cache e tabulação como bottom-up iterativa, que são as técnicas centrais de programação dinâmica. As demais alternativas invertem conceitos (memoização vs tabulação) ou confundem divisão e conquista com programação dinâmica.

Programação dinâmica
  • 1Técnicas
    • Memoização
      • Top-down
      • Recursiva com cache
      • Só calcula subproblemas necessários
    • Tabulação
      • Bottom-up
      • Iterativa
      • Preenche todos os subproblemas
  • 2Característica-chave
    • Subproblemas sobrepostos
  • 3Divisão e conquista
    • Subproblemas independentes
    • Sem sobreposição
LEVEL · soulevel.com.br

Alternativa A — ❌ Incorreta

A alternativa afirma que subproblemas sobrepostos são tratados por divisão e conquista, mas o correto é que programação dinâmica lida com sobreposição. Divisão e conquista exige subproblemas independentes. O erro é trocar os paradigmas.

Alternativa B — ❌ Incorreta

A definição dada é de tabulação (bottom-up), não de memoização. Memoização é top-down: parte do problema maior e, recursivamente, resolve subproblemas, armazenando resultados. A alternativa inverte os papéis.

Alternativa C — ❌ Incorreta

Tabulação (bottom-up) resolve todos os subproblemas de tamanho crescente, mesmo que alguns não sejam alcançados na recursão. Já a memoização só calcula os efetivamente necessários. A alternativa atribui à tabulação a característica da memoização.

Alternativa D — ❌ Incorreta

Divisão e conquista e programação dinâmica não são equivalentes. A diferença fundamental é que a primeira supõe subproblemas independentes; a segunda, sobrepostos. A programação dinâmica é uma otimização sobre a recursão ingênua quando há sobreposição.

Alternativa E — ✅ Correta ⟵ GABARITO

Define com precisão:

  • Memoização: top-down, recursiva, armazena resultado na primeira computação.

  • Tabulação: bottom-up, iterativa, preenche tabela do menor subproblema ao maior.

SE LIGUE NESSA!

A programação dinâmica pode ser implementada por memoização (top-down) ou tabulação (bottom-up). Ambas evitam recomputação, mas diferem na ordem de resolução.

Gabarito: letra E — a única alternativa que descreve corretamente os conceitos de memoização e tabulação.

Link permanente: /questoes/qg685517