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

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

Quais são as três etapas de um algoritmo de divisão e conquista?

  1. ALer, calcular, escrever
  2. BDividir, conquistar, combinar
  3. CChutar, verificar, repetir
  4. DOrdenar, buscar, retornar
3.Fácil

Qual é a complexidade de tempo da busca em profundidade num grafo armazenado como listas de adjacência?

  1. AO(V + E)
  2. BO(V²)
  3. CO(V × E)
  4. DO(E log V)
4.Média

Qual é a complexidade de tempo de multiplicar duas matrizes n × n com o laço triplo padrão?

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

A busca em largura (BFS) em um grafo não ponderado encontra:

  1. AUma ordenação topológica em todos os grafos
  2. BA árvore geradora mínima
  3. CCaminhos mínimos em grafos que contêm arestas com pesos negativos
  4. DCaminhos mínimos em número de arestas a partir do nó inicial
6.Média

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

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

Um problema é NP-completo se ele:

  1. APode ser resolvido em tempo polinomial
  2. BEstá fora de NP, mas é mais difícil que todos os problemas NP, como o problema da parada
  3. CÉ impossível de resolver
  4. DEstá em NP e todo problema NP se reduz a ele em tempo polinomial

Gabarito

  1. 1. C · O(n log n)
  2. 2. B · Dividir, conquistar, combinar
  3. 3. A · O(V + E)
  4. 4. A · O(n³)
  5. 5. D · Caminhos mínimos em número de arestas a partir do nó inicial
  6. 6. A · O(n)
  7. 7. B · O((V + E) log V)
  8. 8. D · Está em NP e todo problema NP se reduz a ele em tempo polinomial

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