Scheda di esercizi di Algoritmi e complessità con soluzioni

Che cos'è la memoizzazione?

1. AMemorizzare i risultati delle chiamate di funzione così che le chiamate ripetute ottengano la risposta dalla memoria
2. BLiberare la memoria dopo il ritorno di una funzione
3. CScrivere commenti accanto a ogni riga di codice
4. DConvertire automaticamente la ricorsione in un ciclo equivalente così da non avere bisogno dello stack delle chiamate

Quanta memoria aggiuntiva usa un merge sort standard su array?

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

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

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

Perché la programmazione dinamica non dà un vero guadagno di velocità per il merge sort?

1. ALa programmazione dinamica funziona solo sui problemi su grafi, non sugli array
2. BIl merge sort è già O(n)
3. CI suoi sottoproblemi non si sovrappongono, quindi non c'è nulla da riutilizzare
4. DIl merge sort non ha una struttura ricorsiva

Che cosa significa che un problema ha una sottostruttura ottima?

1. AUna soluzione ottima può essere costruita da soluzioni ottime dei suoi sottoproblemi
2. BOgni sottoproblema ha la stessa dimensione
3. CIl problema ha esattamente una soluzione ottima, condivisa da ogni sottoproblema
4. DIl problema si può risolvere in tempo costante

Quanto spazio di stack usa una semplice funzione fattoriale ricorsiva fact(n) = n × fact(n − 1)?

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

Come rileva l'algoritmo di Bellman–Ford un ciclo di peso negativo raggiungibile dalla sorgente?

1. ADopo V − 1 turni controlla se qualche arco può ancora essere rilassato
2. BConta i cicli con una visita in profondità
3. CControlla se qualche arco ha peso negativo
4. DEsegue due volte l'algoritmo di Dijkstra e confronta i due risultati delle distanze

Quale affermazione sulla selezione del k-esimo elemento più piccolo di un array non ordinato è corretta?

1. ALa selezione è possibile solo in O(n²)
2. BLa selezione richiede sempre Ω(n log n) perché richiede un ordinamento
3. CIl quickselect richiede O(n) atteso, e la mediana delle mediane garantisce O(n) nel caso peggiore
4. DIl quickselect richiede O(log n) nel caso peggiore, perché ricorre su un solo lato del pivot