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

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
2.Fácil

Como se chama o crescimento O(2ⁿ)?

  1. APolinomial
  2. BExponencial
  3. CLinear
  4. DLogarítmico
3.Fácil

O que é um algoritmo?

  1. AUma sequência finita de passos bem definidos que resolve um problema
  2. BUma estrutura de dados que armazena números
  3. CQualquer programa de computador com interface gráfica
  4. DUma linguagem de programação criada para escrever fórmulas matemáticas
4.Média

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

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

Qual é o tempo de execução do radix sort LSD para n inteiros com d dígitos na base k?

  1. AO(n²)
  2. BO(d(n + k))
  3. CO(dn log k)
  4. DO(n log n)
6.Média

Qual é a complexidade de tempo do quicksort no pior caso?

  1. AO(n log n)
  2. BO(n²)
  3. CO(log n)
  4. DO(n)
7.Difícil

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

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

Qual é a complexidade de tempo de: for i = 1 to n: for (j = i; j ≤ n; j = j + i) faça trabalho O(1)?

  1. AO(n log n)
  2. BO(n²)
  3. CO(n)
  4. DO(n √n)

Gabarito

  1. 1. B · A quantidade de memória que um algoritmo precisa à medida que a entrada cresce
  2. 2. B · Exponencial
  3. 3. A · Uma sequência finita de passos bem definidos que resolve um problema
  4. 4. D · O(n³)
  5. 5. B · O(d(n + k))
  6. 6. B · O(n²)
  7. 7. C · Chegar ao elemento do meio leva O(n) passos, pois não há acesso direto por índice
  8. 8. A · O(n log n)

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