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 a busca binária exige da sua entrada?

  1. AO array não pode ter mais de 1000 elementos
  2. BO array deve estar ordenado
  3. CO tamanho do array deve ser uma potência de dois
  4. DO array deve conter só números positivos
2.Fácil

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

  1. AÔmega pequeno (little omega)
  2. BTheta grande (Big Theta)
  3. CO grande (Big O)
  4. DÔmega grande (Big Omega)
3.Fácil

Qual destes tempos de execução é polinomial?

  1. AO(n³)
  2. BO(n!)
  3. CO(2ⁿ)
  4. DO(nⁿ)
4.Média

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

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

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

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

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

  1. AO(log n)
  2. BO(n)
  3. CO(n²)
  4. DO(n log n)
7.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Θ(n2)
  2. BΘ(n² log n)
  3. CΘ(nlog₂ 7), cerca de n2,81
  4. DΘ(n³)
8.Difícil

Quais são os custos de tempo e espaço de calcular o n-ésimo número de Fibonacci com um laço que guarda só os dois últimos valores?

  1. ATempo O(log n) e espaço O(n)
  2. BTempo O(n) e espaço O(n)
  3. CTempo O(2ⁿ) e espaço O(1)
  4. DTempo O(n) e espaço O(1)

Gabarito

  1. 1. B · O array deve estar ordenado
  2. 2. C · O grande (Big O)
  3. 3. A · O(n³)
  4. 4. C · O(d(n + k))
  5. 5. D · O(n²)
  6. 6. C · O(n²)
  7. 7. C · Θ(nlog₂ 7), cerca de n2,81
  8. 8. D · Tempo O(n) e espaço O(1)

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