Lista de exercícios de Algoritmos e complexidade com respostas

Lista de exercícios de Algoritmos e complexidade grátis para imprimir: 8 exercícios do nível fácil ao nível de prova, com gabarito. Imprima ou salve como PDF.

Nova lista de exercíciosPratique on-line com dicas

Para professores: pode imprimir, copiar e usar em aula gratuitamente. Cada nova folha tem novos valores e o seu próprio gabarito. Agradecemos um link para o ExamProblems na página da sua disciplina.

Nome: ____________________   Data: ____________

1.Fácil

Um laço começa com i = 1 e dobra i a cada iteração até i > n. Quantas iterações ele executa?

  1. ACerca de n
  2. BCerca de log₂ n
  3. CCerca de n²
  4. DCerca de n / 2
2.Fácil

Qual classe de complexidade cresce mais rápido para n grande?

  1. AO(n²)
  2. BO(2ⁿ)
  3. CO(n³)
  4. DO(n log n)
3.Fácil

Qual é a complexidade de tempo da busca linear em um array não ordenado com n elementos (pior caso)?

  1. AO(n²)
  2. BO(log n)
  3. CO(1)
  4. DO(n)
4.Média

Qual é a solução da recorrência T(n) = T(n/2) + O(1)?

  1. AO(n)
  2. BO(1)
  3. CO(log n)
  4. DO(n log n)
5.Média

Qual é a solução da recorrência T(n) = 2T(n/2) + O(1)?

  1. AO(n log n)
  2. BO(log n)
  3. CO(n)
  4. DO(n²)
6.Média

Quanto espaço de pilha usa uma função fatorial recursiva simples fact(n) = n × fact(n − 1)?

  1. AO(log n)
  2. BO(n)
  3. CO(n²)
  4. DO(1)
7.Difícil

Qual técnica dá ao quicksort um tempo de execução esperado O(n log n) para qualquer entrada?

  1. ASempre escolher o primeiro elemento
  2. BOrdenar a entrada antes de executar o quicksort
  3. CEscolher o pivô de forma uniformemente aleatória
  4. DUsar recursão apenas no lado esquerdo
8.Difícil

Qual é a complexidade de tempo para construir um heap binário a partir de n elementos não ordenados com o método bottom-up?

  1. AO(log n)
  2. BO(n²)
  3. CO(n)
  4. DO(n log n)

Gabarito

  1. 1. B · Cerca de log₂ n
  2. 2. B · O(2ⁿ)
  3. 3. D · O(n)
  4. 4. C · O(log n)
  5. 5. C · O(n)
  6. 6. B · O(n)
  7. 7. C · Escolher o pivô de forma uniformemente aleatória
  8. 8. C · O(n)

Soluções completas passo a passo: pratique este tópico em examproblems.com.