Scheda di esercizi di Algoritmi e complessità con soluzioni

Che cos'è la ricorsione?

1. AUna funzione che chiama se stessa su input più piccoli
2. BUn ciclo che non termina mai
3. CUn metodo di ordinamento
4. DUn tipo di struttura dati

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

Quale di queste cresce più lentamente quando n diventa grande?

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

In un array ordinato cerchi due elementi la cui somma sia un valore dato muovendo un puntatore da ciascuna estremità verso l'interno. Qual è la complessità temporale?

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

Nel problema della selezione di attività, quale regola greedy dà sempre il numero massimo di attività non sovrapposte?

1. AScegliere per prima l'attività con meno sovrapposizioni, poi ripetere con quelle compatibili
2. BScegliere l'attività che inizia prima
3. CScegliere per prima l'attività più breve
4. DScegliere l'attività che termina prima, poi ripetere con quelle compatibili

La programmazione dinamica è utile quando un problema presenta:

1. ANessun sottoproblema, quindi si risolve in un solo passo
2. BUn unico ciclo
3. CSolo input casuali
4. DSottoproblemi sovrapposti e sottostruttura ottima

Perché una ricerca in una tabella hash è in media O(1) ma nel caso peggiore O(n)?

1. AGli array hanno accesso O(n)
2. BLe funzioni hash sono lente
3. CMolte chiavi possono collidere nello stesso bucket
4. DLe chiavi devono prima essere ordinate

L'algoritmo di Strassen moltiplica matrici usando 7 invece di 8 moltiplicazioni ricorsive di blocchi di metà dimensione. Qual è il suo tempo di esecuzione?

1. AΘ(n² log n)
2. BΘ(n^{log₂ 7}), circa n^2,81
3. CΘ(n³)
4. DΘ(n²)