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. C12
  4. D10
2.Fácil

Qual é a complexidade de tempo para encontrar o maior valor num array não ordenado de n números?

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

Um algoritmo O(n) leva 3 segundos para n = 1 milhão. Quanto tempo leva, aproximadamente, para n = 2 milhões?

  1. A6 segundos
  2. B9 segundos
  3. C12 segundos
  4. D3 segundos
4.Média

O que o algoritmo de Floyd–Warshall calcula, e com que rapidez?

  1. ACaminhos mínimos entre todos os pares de vértices em O(V³)
  2. BCaminhos mínimos de um vértice de origem para todos os outros em O(V + E)
  3. CUma ordenação topológica em O(V²)
  4. DUma árvore geradora mínima em O(E log V)
5.Média

Qual é a complexidade de tempo de: for i = 1 to n: for j = 1 to i: faça trabalho O(1)?

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

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

  1. AO(n²)
  2. BO(2ⁿ)
  3. CO(n)
  4. DO(log n)
7.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
8.Difícil

Qual é a solução da recorrência T(n) = 2T(n/2) + n log n?

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

Gabarito

  1. 1. D · 10
  2. 2. C · O(n)
  3. 3. A · 6 segundos
  4. 4. A · Caminhos mínimos entre todos os pares de vértices em O(V³)
  5. 5. C · O(n²)
  6. 6. C · O(n)
  7. 7. A · Após V − 1 rodadas, verifica se alguma aresta ainda pode ser relaxada
  8. 8. A · Θ(n log² n)

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