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 destes tempos de execução é polinomial?

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

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

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

Como se chama o crescimento O(2ⁿ)?

  1. APolinomial
  2. BExponencial
  3. CLogarítmico
  4. DLinear
4.Média

Um algoritmo guloso (greedy):

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

Qual é a complexidade de tempo do quicksort no pior caso?

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

Uma função executa um laço de n iterações e depois, separadamente, outro laço de n iterações. Qual é a sua complexidade de tempo?

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

Qual definição da classe P está correta?

  1. AProblemas que podem ser resolvidos em paralelo
  2. BProblemas de decisão solúveis por um algoritmo determinístico em tempo polinomial
  3. CProblemas que exigem tempo exponencial em qualquer computador
  4. DProblemas cujas soluções podem ser verificadas, mas nunca encontradas, em tempo polinomial
8.Difícil

Por que o algoritmo de Dijkstra pode dar resultados errados quando alguns pesos de aresta são negativos?

  1. ANúmeros negativos não podem ser armazenados numa fila de prioridade
  2. BUm vértice é finalizado ao ser extraído, mas uma aresta negativa posterior ainda poderia dar a ele um caminho mais curto
  3. CSó funciona em grafos não dirigidos
  4. DEntra num laço infinito a cada aresta negativa

Gabarito

  1. 1. B · O(n³)
  2. 2. A · O(n)
  3. 3. B · Exponencial
  4. 4. A · Faz a melhor escolha local em cada passo
  5. 5. B · O(n²)
  6. 6. B · O(n)
  7. 7. B · Problemas de decisão solúveis por um algoritmo determinístico em tempo polinomial
  8. 8. B · Um vértice é finalizado ao ser extraído, mas uma aresta negativa posterior ainda poderia dar a ele um caminho mais curto

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