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 algoritmo com dois laços aninhados, cada um executado n vezes, normalmente tem qual complexidade?

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

A complexidade de espaço mede:

  1. AO número de linhas de código
  2. BO espaço em disco do arquivo do programa depois de compilado
  3. CO tamanho físico do computador
  4. DA quantidade de memória que um algoritmo precisa à medida que a entrada cresce
3.Fácil

Qual estratégia de projeto o merge sort usa?

  1. AEscolha gulosa
  2. BDivisão e conquista
  3. CProgramação dinâmica
  4. DForça bruta
4.Média

Um algoritmo guloso (greedy):

  1. ATesta todas as soluções possíveis
  2. BSempre fornece a solução ótima
  3. CFaz a melhor escolha local em cada passo
  4. DUsa apenas recursão
5.Média

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

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

Num array ordenado, você procura dois elementos cuja soma seja um alvo movendo um ponteiro de cada extremidade para dentro. Qual é a complexidade de tempo?

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

Para qual variante da mochila a regra gulosa "pegar os itens em ordem de valor por peso" sempre dá uma resposta ótima?

  1. AA mochila fracionária, em que os itens podem ser divididos
  2. BA mochila 0/1, em que os itens devem ser sempre levados inteiros
  3. CNenhuma das variantes
  4. DAs duas variantes
8.Difícil

Qual limite está correto para log(n!)?

  1. AΘ(n log n)
  2. BΘ(log n)
  3. CΘ(n²)
  4. DΘ(n)

Gabarito

  1. 1. C · O(n²)
  2. 2. D · A quantidade de memória que um algoritmo precisa à medida que a entrada cresce
  3. 3. B · Divisão e conquista
  4. 4. C · Faz a melhor escolha local em cada passo
  5. 5. C · O(n)
  6. 6. A · O(n)
  7. 7. A · A mochila fracionária, em que os itens podem ser divididos
  8. 8. A · Θ(n log n)

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