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

O que é um algoritmo de força bruta?

  1. AUm que chuta uma resposta ao acaso
  2. BUm que sempre usa recursão
  3. CUm que testa todas as soluções candidatas possíveis
  4. DUm que roda em vários processadores
2.Fácil

Qual estratégia de projeto o merge sort usa?

  1. AProgramação dinâmica
  2. BDivisão e conquista
  3. CEscolha gulosa
  4. DForça bruta
3.Fácil

O tempo de execução de um algoritmo é O(n). Como se chama esse crescimento?

  1. ALinear
  2. BLogarítmico
  3. CConstante
  4. DQuadrático
4.Média

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

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

Por que a programação dinâmica não traz ganho real de velocidade para o merge sort?

  1. AO merge sort já é O(n)
  2. BO merge sort não tem estrutura recursiva
  3. CSeus subproblemas não se sobrepõem, então não há nada para reaproveitar
  4. DA programação dinâmica só funciona em problemas de grafos, não em vetores
6.Média

Por que muitas rotinas de ordenação de bibliotecas passam para o insertion sort em subarrays muito pequenos?

  1. AO insertion sort é O(n log n) no pior caso
  2. BO insertion sort tem pouco overhead e é rápido com entradas pequenas ou quase ordenadas
  3. CO insertion sort usa menos memória que qualquer outro algoritmo de ordenação em entradas grandes
  4. DAlgoritmos recursivos não conseguem lidar com arrays de menos de 10 elementos
7.Difícil

Qual afirmação sobre P e NP está correta?

  1. ANP significa "não polinomial"
  2. BFoi provado que P ≠ NP
  3. CTodo problema em P também está em NP
  4. DSoluções de problemas NP não podem ser verificadas rapidamente
8.Difícil

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

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

Gabarito

  1. 1. C · Um que testa todas as soluções candidatas possíveis
  2. 2. B · Divisão e conquista
  3. 3. A · Linear
  4. 4. B · Caminhos mínimos entre todos os pares de vértices em O(V³)
  5. 5. C · Seus subproblemas não se sobrepõem, então não há nada para reaproveitar
  6. 6. B · O insertion sort tem pouco overhead e é rápido com entradas pequenas ou quase ordenadas
  7. 7. C · Todo problema em P também está em NP
  8. 8. C · 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.