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

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

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

O que descreve o tempo de execução de um algoritmo no pior caso?

  1. AO tempo que leva com a menor entrada
  2. BO tempo esperado que leva com uma entrada aleatória de tamanho n
  3. CO tempo que leva num computador lento
  4. DO tempo máximo que ele leva entre todas as entradas de tamanho n
3.Fácil

Qual notação descreve um limite inferior de crescimento?

  1. AΩ (Ômega grande)
  2. BO (O grande)
  3. CΘ (Theta grande)
  4. Do (o pequeno)
4.Média

Qual é a complexidade de tempo de calcular o n-ésimo número de Fibonacci com uma tabela bottom-up?

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

Aproximadamente quantas comparações a busca binária precisa no pior caso num array ordenado de 1,000,000 de elementos?

  1. ACerca de 100
  2. BCerca de 1,000
  3. CCerca de 20
  4. DCerca de 500,000
7.Difícil

Qual é o custo amortizado de incrementar um contador binário, sabendo que um incremento pode inverter muitos bits?

  1. AO(1) por incremento
  2. BO(log n) por incremento
  3. CO(n log n) por incremento
  4. DO(n) por incremento
8.Difícil

A ordenação topológica só é possível para:

  1. AGrafos completos
  2. BGrafos não dirigidos
  3. CGrafos acíclicos dirigidos (DAG)
  4. DGrafos com pesos negativos

Gabarito

  1. 1. A · Dividir, conquistar, combinar
  2. 2. D · O tempo máximo que ele leva entre todas as entradas de tamanho n
  3. 3. A · Ω (Ômega grande)
  4. 4. A · O(n)
  5. 5. D · Caminhos mínimos em número de arestas a partir do nó inicial
  6. 6. C · Cerca de 20
  7. 7. A · O(1) por incremento
  8. 8. C · Grafos acíclicos dirigidos (DAG)

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