Pular para o conteúdo principal

Questão de Algoritmos e Estrutura de Dados — Algoritmos — CEPS-UFPA 2022

Algoritmos e Estrutura de DadosAlgoritmos
Código
gp036801
Banca
CEPS-UFPA
Órgão
UFPA
Ano
2022
Cargo
CEPS - - Analista de Tecnologia da Informação / Área: Desenvolvimento
Considere o programa a seguir escrito em linguagem C.#include <stdio.h>int TAM(int n) {int x;if (n == 1) {return(1 + n);}x = TAM(n/2) + TAM(n/2);return(x);}int main() {int n = 16;printf("%d ", TAM(n));}Após a execução do programa, o resultado é
  1. A16
  2. B32
  3. C256
  4. D272
  5. E1.024
Revelar gabarito e comentário

GabaritoB — 32

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

Recursão em C: análise da função TAM

Gabarito: letra B (32). A função TAM(n) é recursiva e, para n=1, retorna 1+n = 2. Para n>1, retorna a soma de duas chamadas a TAM(n/2). Portanto, cada chamada dobra o valor da subchamada, formando uma sequência que para n=16 resulta em 32.

A banca testa a capacidade de rastrear chamadas recursivas. Vamos executar manualmente:

TAM(16) = TAM(8) + TAM(8)
  TAM(8) = TAM(4) + TAM(4)
    TAM(4) = TAM(2) + TAM(2)
      TAM(2) = TAM(1) + TAM(1)
        TAM(1) = 2
      → TAM(2) = 2+2 = 4
    → TAM(4) = 4+4 = 8
  → TAM(8) = 8+8 = 16
→ TAM(16) = 16+16 = 32

Outra forma: A recorrência é T(1)=2T(1)=2, T(n)=2⋅T(n/2)T(n)=2\cdot T(n/2). Resolvendo, T(16)=2⋅T(8)=22⋅T(4)=23⋅T(2)=24⋅T(1)=16⋅2=32T(16)=2\cdot T(8)=2^2\cdot T(4)=2^3\cdot T(2)=2^4\cdot T(1)=16\cdot 2 = 32.

  1. 1TAM(1) = 2
  2. 2TAM(2) = 2+2 = 4
  3. 3TAM(4) = 4+4 = 8
  4. 4TAM(8) = 8+8 = 16
  5. 5TAM(16) = 16+16 = 32
LEVEL · soulevel.com.br

Alternativa A — ❌ Incorreta

Valor 16. Corresponde a T(8)T(8) ou a um único ramo da árvore.

Alternativa B — ✅ Correta ⟵ GABARITO

Valor 32, conforme demonstrado.

Alternativa C — ❌ Incorreta

Valor 256. Equivale a 16216^2 ou 282^8, mas não ao resultado da recursão.

Alternativa D — ❌ Incorreta

Valor 272. Provável confusão com soma de potências ou contagem incorreta de chamadas.

Alternativa E — ❌ Incorreta

Valor 1024. Corresponde a 2102^{10}, mas não à saída do programa.

PEGA ESSA DICA!

Para funções recursivas que chamam a si mesmas duas vezes com metade do argumento, monte a árvore de recursão ou escreva a recorrência. A cada nível o tamanho do problema se reduz pela metade e o valor dobra até a base.

Gabarito: letra B.

Link permanente: /questoes/gp036801