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 da busca binária em um array ordenado?

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

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

  1. ATheta grande (Big Theta)
  2. BO grande (Big O)
  3. CÔmega grande (Big Omega)
  4. DÔmega pequeno (little omega)
3.Fácil

Um algoritmo O(n²) leva 1 segundo para n = 1000. Quanto tempo leva, aproximadamente, para n = 2000?

  1. A4 segundos
  2. B1 segundo
  3. C2 segundos
  4. D8 segundos
4.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(n)
  3. CO(log n)
  4. DO(n log n)
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(n²)
  3. CO(log n)
  4. DO(2ⁿ)
6.Média

Qual é a complexidade de tempo do algoritmo de Bellman–Ford num grafo com V vértices e E arestas?

  1. AO(E log V)
  2. BO(V × E)
  3. CO(V + E)
  4. DO(V³ × E)
7.Difícil

Tomar as duas extremidades de cada aresta de um emparelhamento maximal dá uma cobertura de vértices. Quão boa é essa cobertura?

  1. ASempre uma cobertura de vértices mínima
  2. BNo máximo o dobro do tamanho de uma cobertura de vértices mínima
  3. CDe qualidade desconhecida em relação ao ótimo
  4. DNo máximo log n vezes o mínimo
8.Difícil

Qual limite está correto para log(n!)?

  1. AΘ(n log n)
  2. BΘ(log n)
  3. CΘ(n²)
  4. DΘ(n)

Gabarito

  1. 1. B · O(log n)
  2. 2. B · O grande (Big O)
  3. 3. A · 4 segundos
  4. 4. B · O(n)
  5. 5. A · O(n)
  6. 6. B · O(V × E)
  7. 7. B · No máximo o dobro do tamanho de uma cobertura de vértices mínima
  8. 8. A · Θ(n log n)

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