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

Quanto é log₂ 1024?

  1. A32
  2. B512
  3. C10
  4. D12
2.Fácil

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

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

O que significa uma operação rodar em tempo O(1)?

  1. ASó pode ser executada uma vez
  2. BSempre leva exatamente um segundo
  3. CProcessa exatamente um elemento por segundo de tempo de execução
  4. DSeu tempo de execução não cresce com o tamanho da entrada
4.Média

Qual é a complexidade de tempo de: for i = 1 to n: (j = 1; while j < n: j = j × 2)?

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

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

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

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

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

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

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

Como o algoritmo de Bellman–Ford detecta um ciclo de peso negativo alcançável a partir da origem?

  1. AApós V − 1 rodadas, verifica se alguma aresta ainda pode ser relaxada
  2. BConta os ciclos com busca em profundidade
  3. CExecuta o algoritmo de Dijkstra duas vezes e compara os dois resultados de distância
  4. DVerifica se alguma aresta tem peso negativo

Gabarito

  1. 1. C · 10
  2. 2. D · O grande (Big O)
  3. 3. D · Seu tempo de execução não cresce com o tamanho da entrada
  4. 4. D · O(n log n)
  5. 5. B · O(n)
  6. 6. B · O(n²)
  7. 7. C · Problemas de decisão solúveis por um algoritmo determinístico em tempo polinomial
  8. 8. A · Após V − 1 rodadas, verifica se alguma aresta ainda pode ser relaxada

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