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

Che cosa descrive il tempo di esecuzione nel caso peggiore di un algoritmo?

  1. AIl tempo impiegato sull'input più piccolo
  2. BIl tempo massimo impiegato su tutti gli input di dimensione n
  3. CIl tempo impiegato su un computer lento
  4. DIl tempo atteso su un input casuale di dimensione n
2.Facile

Che cos'è un algoritmo?

  1. AQualsiasi programma con un'interfaccia grafica
  2. BUna struttura dati che memorizza numeri
  3. CUna sequenza finita di passi ben definiti che risolve un problema
  4. DUn linguaggio di programmazione progettato per scrivere formule matematiche
3.Facile

Che cosa significa che un'operazione ha tempo O(1)?

  1. AElabora esattamente un elemento per ogni secondo di tempo di esecuzione
  2. BPuò essere eseguita una sola volta
  3. CRichiede sempre esattamente un secondo
  4. DIl suo tempo di esecuzione non cresce con la dimensione dell'input
4.Media

Che cosa significa che un problema ha una sottostruttura ottima?

  1. AOgni sottoproblema ha la stessa dimensione
  2. BIl problema ha esattamente una soluzione ottima, condivisa da ogni sottoproblema
  3. CIl problema si può risolvere in tempo costante
  4. DUna soluzione ottima può essere costruita da soluzioni ottime dei suoi sottoproblemi
5.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(k n log n)
  2. BO(nk)
  3. CO(n + k)
  4. DO(n log n + k log n)
6.Media

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

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

Perché la ricerca binaria non dà tempo O(log n) su una lista concatenata semplice?

  1. ARaggiungere l'elemento centrale richiede O(n) passi, perché non c'è accesso diretto tramite indice
  2. BLe liste concatenate non si possono ordinare
  3. CLa ricerca binaria richiede almeno il doppio della memoria
  4. DI confronti sui nodi di una lista concatenata sono più lenti
8.Difficile

Qual è la complessità temporale di: for i = 1 to n: for (j = i; j ≤ n; j = j + i) lavoro O(1)?

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

Soluzioni

  1. 1. B · Il tempo massimo impiegato su tutti gli input di dimensione n
  2. 2. C · Una sequenza finita di passi ben definiti che risolve un problema
  3. 3. D · Il suo tempo di esecuzione non cresce con la dimensione dell'input
  4. 4. D · Una soluzione ottima può essere costruita da soluzioni ottime dei suoi sottoproblemi
  5. 5. D · O(n log n + k log n)
  6. 6. B · O(n²)
  7. 7. A · Raggiungere l'elemento centrale richiede O(n) passi, perché non c'è accesso diretto tramite indice
  8. 8. B · O(n log n)

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