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

Qual é a complexidade de tempo do insertion sort no melhor caso, com um array já ordenado?

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

O que é recursão?

  1. AUm tipo de estrutura de dados
  2. BUm laço que nunca termina
  3. CUma função que chama a si mesma com entradas menores
  4. DUm método de ordenação
3.Fácil

Quais são as três etapas de um algoritmo de divisão e conquista?

  1. AChutar, verificar, repetir
  2. BLer, calcular, escrever
  3. CDividir, conquistar, combinar
  4. DOrdenar, buscar, retornar
4.Média

Qual é a complexidade de tempo de multiplicar duas matrizes n × n com o laço triplo padrão?

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

Qual algoritmo de ordenação é estável?

  1. AMerge sort
  2. BQuicksort (versão in-place típica)
  3. CSelection sort (versão típica)
  4. DHeap sort
6.Média

O que significa um problema ter subestrutura ótima?

  1. AO problema tem exatamente uma solução ótima, compartilhada por todos os subproblemas
  2. BO problema pode ser resolvido em tempo constante
  3. CTodos os subproblemas têm o mesmo tamanho
  4. DUma solução ótima pode ser construída a partir de soluções ótimas dos seus subproblemas
7.Difícil

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

  1. AΘ(n²)
  2. BΘ(n log n)
  3. CΘ(n log² n)
  4. DΘ(n)
8.Difícil

Qual afirmação sobre P e NP está correta?

  1. ATodo problema em P também está em NP
  2. BSoluções de problemas NP não podem ser verificadas rapidamente
  3. CFoi provado que P ≠ NP
  4. DNP significa "não polinomial"

Gabarito

  1. 1. A · O(n)
  2. 2. C · Uma função que chama a si mesma com entradas menores
  3. 3. C · Dividir, conquistar, combinar
  4. 4. D · O(n³)
  5. 5. A · Merge sort
  6. 6. D · Uma solução ótima pode ser construída a partir de soluções ótimas dos seus subproblemas
  7. 7. C · Θ(n log² n)
  8. 8. A · Todo problema em P também está em NP

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