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 algoritmo de ordenação troca repetidamente elementos adjacentes que estão na ordem errada?

  1. AMerge sort (ordenação por intercalação)
  2. BBubble sort (ordenação por bolha)
  3. CQuicksort
  4. DHeap sort
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(n log n)
  3. CO(n)
  4. DO(log n)
3.Fácil

Qual é a complexidade de tempo do insertion sort no pior caso?

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

Qual é a complexidade de tempo amortizada de adicionar ao final de um array dinâmico que dobra sua capacidade quando fica cheio?

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

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

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

Com moedas de 1, 3 e 4 e um valor de 6, quantas moedas o método guloso "maior moeda primeiro" usa, em comparação com o ótimo?

  1. AO guloso usa 3 moedas; o ótimo é 2
  2. BO guloso usa 3 moedas; o ótimo é 3
  3. CO guloso usa 4 moedas; o ótimo é 3
  4. DO guloso usa 2 moedas; o ótimo é 2
7.Difícil

Por que a busca binária não dá tempo O(log n) numa lista simplesmente encadeada?

  1. AChegar ao elemento do meio leva O(n) passos, pois não há acesso direto por índice
  2. BAs comparações entre nós de lista encadeada são mais lentas
  3. CA busca binária precisa de pelo menos o dobro da memória
  4. DListas encadeadas não podem ser ordenadas
8.Difícil

Qual algoritmo encontra uma árvore geradora mínima adicionando repetidamente a aresta mais barata que não forma um ciclo?

  1. AAlgoritmo de Prim a partir de um nó
  2. BAlgoritmo de Kruskal
  3. CAlgoritmo de Dijkstra
  4. DFloyd-Warshall

Gabarito

  1. 1. B · Bubble sort (ordenação por bolha)
  2. 2. C · O(n)
  3. 3. C · O(n²)
  4. 4. A · O(1)
  5. 5. B · O(2ⁿ)
  6. 6. A · O guloso usa 3 moedas; o ótimo é 2
  7. 7. A · Chegar ao elemento do meio leva O(n) passos, pois não há acesso direto por índice
  8. 8. B · Algoritmo de Kruskal

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