Scheda di esercizi di Algoritmi e complessità con soluzioni

Scheda di esercizi di Algoritmi e complessità gratuita e stampabile: 8 esercizi dal livello facile a quello d’esame, con le soluzioni. Stampala o salvala come PDF.

Nuova schedaEsercitati online con i suggerimenti

Per i docenti: gratuita da stampare, copiare e usare in classe. Ogni nuova scheda ha nuovi valori e le sue soluzioni. Un link a ExamProblems nella pagina del corso è molto apprezzato.

Nome: ____________________   Data: ____________

1.Facile

Un algoritmo O(n) impiega 3 secondi per n = 1 milione. Circa quanto impiega per n = 2 milioni?

  1. A6 secondi
  2. B12 secondi
  3. C3 secondi
  4. D9 secondi
2.Facile

Un algoritmo con due cicli annidati, ciascuno eseguito n volte, ha tipicamente quale complessità?

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

Quali sono i tre passi di un algoritmo divide et impera?

  1. ALeggi, calcola, scrivi
  2. BDividi, risolvi (impera), combina
  3. COrdina, cerca, restituisci
  4. DIndovina, verifica, ripeti
4.Media

Ordini una volta un array di n elementi e poi rispondi a k query di appartenenza con la ricerca binaria. Qual è il costo totale?

  1. AO(n log n + k log n)
  2. BO(n + k)
  3. CO(nk)
  4. DO(k n log n)
5.Media

Qual è il tempo di esecuzione del radix sort LSD su n interi con d cifre in base k?

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

Qual è la soluzione della ricorrenza T(n) = T(n − 1) + O(1)?

  1. AO(log n)
  2. BO(n)
  3. CO(n²)
  4. DO(2ⁿ)
7.Difficile

Quale tecnica garantisce al quicksort un tempo di esecuzione atteso O(n log n) su qualsiasi input?

  1. AUsare la ricorsione solo sul lato sinistro
  2. BOrdinare l'input prima di eseguire il quicksort
  3. CScegliere il pivot in modo uniformemente casuale
  4. DScegliere sempre il primo elemento
8.Difficile

22n è in O(2ⁿ)?

  1. ASì, perché i fattori costanti nell'esponente si ignorano sempre nell'O grande
  2. BNo, perché 22n = 4ⁿ e 4ⁿ / 2ⁿ = 2ⁿ cresce senza limite
  3. CNo, perché 22n cresce più lentamente di 2ⁿ
  4. DSì, perché sono entrambi esponenziali

Soluzioni

  1. 1. A · 6 secondi
  2. 2. A · O(n²)
  3. 3. B · Dividi, risolvi (impera), combina
  4. 4. A · O(n log n + k log n)
  5. 5. C · O(d(n + k))
  6. 6. B · O(n)
  7. 7. C · Scegliere il pivot in modo uniformemente casuale
  8. 8. B · No, perché 22n = 4ⁿ e 4ⁿ / 2ⁿ = 2ⁿ cresce senza limite

Soluzioni complete passo passo: esercitati su questo argomento su examproblems.com.