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 classe de complexidade cresce mais rápido para n grande?

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

O que descreve o tempo de execução de um algoritmo no pior caso?

  1. AO tempo máximo que ele leva entre todas as entradas de tamanho n
  2. BO tempo que leva num computador lento
  3. CO tempo que leva com a menor entrada
  4. DO tempo esperado que leva com uma entrada aleatória de tamanho n
3.Fácil

Quanto é log₂ 1024?

  1. A10
  2. B512
  3. C32
  4. D12
4.Média

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

  1. AMerge sort
  2. BHeap sort
  3. CSelection sort (versão típica)
  4. DQuicksort (versão in-place típica)
5.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(n)
  2. BO(2ⁿ)
  3. CO(log n)
  4. DO(n²)
6.Média

O limite inferior para ordenação baseada em comparações no pior caso é:

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

Qual é o tempo de execução do algoritmo de Dijkstra com um heap binário num grafo com V vértices e E arestas?

  1. AO((V + E) log V)
  2. BO(V + E)
  3. CO(V × E)
  4. DO(V³)
8.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. ANenhuma das variantes
  2. BA mochila fracionária, em que os itens podem ser divididos
  3. CA mochila 0/1, em que os itens devem ser sempre levados inteiros
  4. DAs duas variantes

Gabarito

  1. 1. D · O(2ⁿ)
  2. 2. A · O tempo máximo que ele leva entre todas as entradas de tamanho n
  3. 3. A · 10
  4. 4. A · Merge sort
  5. 5. A · O(n)
  6. 6. C · Ω(n log n)
  7. 7. A · O((V + E) log V)
  8. 8. B · A mochila fracionária, em que os itens podem ser divididos

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