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

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

Qual classe de complexidade cresce mais rápido para n grande?

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

Qual é a complexidade de tempo da busca binária em um array ordenado?

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

Qual algoritmo encontra os caminhos mínimos a partir de uma origem em um grafo com pesos de arestas não negativos?

  1. AAlgoritmo de Kruskal
  2. BBellman-Ford é necessário em todos os casos
  3. CBusca em profundidade (DFS)
  4. DAlgoritmo de Dijkstra
5.Média

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

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

A programação dinâmica é útil quando um problema tem:

  1. ANenhum subproblema, de modo que pode ser resolvido em um único passo
  2. BSubproblemas sobrepostos e subestrutura ótima
  3. CApenas entradas aleatórias
  4. DUm único laço
7.Difícil

O problema da parada mostra que:

  1. ANenhum algoritmo consegue decidir, para todo programa e toda entrada, se o programa para
  2. BAlguns programas rodam mais rápido em computadores mais rápidos, então a parada depende do hardware
  3. CTodo programa acaba parando
  4. DLaços devem ser evitados
8.Difícil

Qual afirmação sobre a notação o pequeno está correta?

  1. A2n = o(n), porque 2n cresce devagar
  2. Bn = o(n²), mas n não é o(n)
  3. Cn² = o(n)
  4. Dn = o(n), já que toda função é o pequeno de si mesma

Gabarito

  1. 1. B · O(n²)
  2. 2. D · O(2ⁿ)
  3. 3. C · O(log n)
  4. 4. D · Algoritmo de Dijkstra
  5. 5. C · O(2ⁿ)
  6. 6. B · Subproblemas sobrepostos e subestrutura ótima
  7. 7. A · Nenhum algoritmo consegue decidir, para todo programa e toda entrada, se o programa para
  8. 8. B · n = o(n²), mas n não é o(n)

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