Scheda di esercizi di Algoritmi e complessità con soluzioni

Quale algoritmo di ordinamento scambia ripetutamente elementi adiacenti che sono nell'ordine sbagliato?

1. ABubble sort
2. BHeap sort
3. CQuicksort
4. DMerge sort

Che cos'è la memoizzazione?

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

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

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

La ricorrenza T(n) = 2T(n/2) + O(n) ha come soluzione:

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

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

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

Perché molte routine di ordinamento delle librerie passano all'insertion sort per sottoarray molto piccoli?

1. AGli algoritmi ricorsivi non gestiscono array con meno di 10 elementi
2. BL'insertion sort usa meno memoria di qualsiasi altro algoritmo di ordinamento per input grandi
3. CL'insertion sort è O(n log n) nel caso peggiore
4. DL'insertion sort ha poco overhead ed è veloce su input piccoli o quasi ordinati

Un problema è NP-completo se:

1. AAppartiene a NP e ogni problema NP si riduce a esso in tempo polinomiale
2. BÈ impossibile da risolvere
3. CÈ risolvibile in tempo polinomiale
4. DÈ al di fuori di NP ma più difficile di tutti i problemi NP, come il problema della fermata

Qual è il tempo di esecuzione dell'algoritmo di Dijkstra con uno heap binario su un grafo con V vertici ed E archi?

1. AO((V + E) log V)
2. BO(V + E)
3. CO(V³)
4. DO(V × E)