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

Il tempo di esecuzione di un algoritmo è O(n). Come si chiama questa crescita?

  1. ALogaritmica
  2. BQuadratica
  3. CLineare
  4. DCostante
2.Facile

La complessità spaziale misura:

  1. ALe dimensioni fisiche del computer
  2. BIl numero di righe di codice
  3. CLa quantità di memoria di cui un algoritmo ha bisogno al crescere dell'input
  4. DLo spazio su disco del file del programma una volta compilato
3.Facile

Un ciclo parte con i = 1 e raddoppia i a ogni iterazione finché i > n. Quante iterazioni esegue?

  1. ACirca n
  2. BCirca n²
  3. CCirca log₂ n
  4. DCirca n / 2
4.Media

Quale algoritmo di ordinamento è stabile?

  1. AMerge sort
  2. BQuicksort (tipica versione in loco)
  3. CSelection sort (versione tipica)
  4. DHeap sort
5.Media

Come costruisce l'algoritmo di Prim un albero ricoprente minimo?

  1. AOrdina tutti gli archi per peso e aggiunge ciascuno di essi a meno che non formi un ciclo nella foresta
  2. BRimuove l'arco più costoso finché non restano cicli
  3. CFa crescere un unico albero da un vertice iniziale, aggiungendo l'arco più economico che esce dall'albero
  4. DEsegue una visita in ampiezza e conserva l'albero BFS
6.Media

La complessità temporale del Fibonacci ricorsivo ingenuo (fib(n) = fib(n−1) + fib(n−2)) è:

  1. AEsponenziale
  2. BLineare
  3. CLogaritmica
  4. DCostante
7.Difficile

Per quale variante dello zaino la regola greedy "prendi gli oggetti in ordine di valore per peso" dà sempre una risposta ottima?

  1. ALo zaino frazionario, in cui gli oggetti si possono dividere
  2. BLo zaino 0/1, in cui gli oggetti si devono prendere sempre interi
  3. CEntrambe le varianti
  4. DNessuna delle due varianti
8.Difficile

Qual è il costo ammortizzato dell'incremento di un contatore binario, dato che un incremento può invertire molti bit?

  1. AO(log n) per incremento
  2. BO(n) per incremento
  3. CO(n log n) per incremento
  4. DO(1) per incremento

Soluzioni

  1. 1. C · Lineare
  2. 2. C · La quantità di memoria di cui un algoritmo ha bisogno al crescere dell'input
  3. 3. C · Circa log₂ n
  4. 4. A · Merge sort
  5. 5. C · Fa crescere un unico albero da un vertice iniziale, aggiungendo l'arco più economico che esce dall'albero
  6. 6. A · Esponenziale
  7. 7. A · Lo zaino frazionario, in cui gli oggetti si possono dividere
  8. 8. D · O(1) per incremento

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