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 merge sort no pior caso?

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

Qual notação descreve um limite superior de crescimento?

  1. AÔmega pequeno (little omega)
  2. BTheta grande (Big Theta)
  3. CÔmega grande (Big Omega)
  4. DO grande (Big O)
3.Fácil

Quanta memória extra usa um merge sort padrão baseado em arrays?

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

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

  1. AO(n²)
  2. BO(n log n)
  3. CO(n)
  4. DO(2ⁿ)
5.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(log n)
  3. CO(n log n)
  4. DO(n²)
6.Média

Um quicksort usa sempre o primeiro elemento como pivô. Com qual entrada ele apresenta o comportamento de pior caso?

  1. AUm array de tamanho 2
  2. BUm array com todos os elementos diferentes
  3. CUm array em ordem aleatória
  4. DUm array que já está ordenado
7.Difícil

O algoritmo de programação dinâmica de Held–Karp resolve o problema do caixeiro-viajante de forma exata. Qual é o seu tempo de execução para n cidades?

  1. AO(n!)
  2. BO(n² 2ⁿ)
  3. CO(2n²)
  4. DO(n³)
8.Difícil

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

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

Gabarito

  1. 1. A · O(n log n)
  2. 2. D · O grande (Big O)
  3. 3. D · O(n)
  4. 4. A · O(n²)
  5. 5. A · O(n)
  6. 6. D · Um array que já está ordenado
  7. 7. B · O(n² 2ⁿ)
  8. 8. A · 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.