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

Como funciona o selection sort?

  1. ADivide o array em metades e as intercala
  2. BEncontra repetidamente o mínimo da parte não ordenada e o troca para a frente
  3. CInsere cada elemento numa parte ordenada crescente por deslocamento
  4. DTroca repetidamente elementos vizinhos que estão na ordem errada
2.Fácil

A complexidade de espaço mede:

  1. AO tamanho físico do computador
  2. BA quantidade de memória que um algoritmo precisa à medida que a entrada cresce
  3. CO espaço em disco do arquivo do programa depois de compilado
  4. DO número de linhas de código
3.Fácil

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

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

É correto dizer que um algoritmo O(n²) também é O(n³)?

  1. ANão, porque n³ é menor que n² para n grande
  2. BNão, porque o O grande deve sempre dar a taxa de crescimento exata da função
  3. CSim, porque o O grande é um limite superior e n² não cresce mais rápido que n³
  4. DSim, mas só se n for menor que 100
5.Média

Uma função executa um laço de n iterações e depois, separadamente, outro laço de n iterações. Qual é a sua complexidade de tempo?

  1. AO(log n)
  2. BO(2ⁿ)
  3. CO(n)
  4. DO(n²)
6.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. BCaminhos mínimos em grafos que contêm arestas com pesos negativos
  3. CCaminhos mínimos em número de arestas a partir do nó inicial
  4. DA árvore geradora mínima
7.Difícil

O problema da mochila 0/1 resolvido com programação dinâmica leva tempo O(nW). Por que isso é chamado de pseudopolinomial?

  1. APorque só funciona para W = 0
  2. BW é um número, então o tempo é exponencial no número de bits usados para escrever W
  3. CPorque o algoritmo é aleatorizado e seu tempo de execução varia a cada entrada
  4. DPorque n é sempre pequeno
8.Difícil

O algoritmo de Strassen multiplica matrizes usando 7, em vez de 8, multiplicações recursivas de blocos de metade do tamanho. Qual é o seu tempo de execução?

  1. AΘ(n² log n)
  2. BΘ(n³)
  3. CΘ(nlog₂ 7), cerca de n2,81
  4. DΘ(n2)

Gabarito

  1. 1. B · Encontra repetidamente o mínimo da parte não ordenada e o troca para a frente
  2. 2. B · A quantidade de memória que um algoritmo precisa à medida que a entrada cresce
  3. 3. A · O(log n)
  4. 4. C · Sim, porque o O grande é um limite superior e n² não cresce mais rápido que n³
  5. 5. C · O(n)
  6. 6. C · Caminhos mínimos em número de arestas a partir do nó inicial
  7. 7. B · W é um número, então o tempo é exponencial no número de bits usados para escrever W
  8. 8. C · Θ(nlog₂ 7), cerca de n2,81

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