Scheda di esercizi di Algoritmi e complessità con soluzioni

Accedere a un elemento di un array tramite indice richiede:

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

Qual è la complessità temporale nel caso migliore dell'insertion sort, su un array già ordinato?

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

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

1. AOrdina, cerca, restituisci
2. BDividi, risolvi (impera), combina
3. CLeggi, calcola, scrivi
4. DIndovina, verifica, ripeti

Un algoritmo greedy (goloso):

1. AProva ogni soluzione possibile
2. BCompie la scelta localmente migliore a ogni passo
3. CUsa solo la ricorsione
4. DFornisce sempre la soluzione ottima

Quale affermazione su una funzione ricorsiva senza un caso base raggiungibile è corretta?

1. ARestituisce automaticamente 0
2. BIl compilatore la trasforma sempre in un ciclo che termina in modo sicuro
3. CViene eseguita in tempo O(1)
4. DContinua a chiamare se stessa finché lo stack delle chiamate va in overflow

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

1. ALineare
2. BCostante
3. CLogaritmica
4. DEsponenziale

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₂ 7}), circa n^2,81
2. BΘ(n²)
3. CΘ(n² log n)
4. DΘ(n³)

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. BScegliere il pivot in modo uniformemente casuale
3. COrdinare l'input prima di eseguire il quicksort
4. DScegliere sempre il primo elemento