Scheda di esercizi di Algoritmi e complessità con soluzioni

Quanta memoria aggiuntiva usa un merge sort standard su array?

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

Che cos'è la memoizzazione?

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

Come funziona il selection sort?

1. AScambia ripetutamente elementi adiacenti che sono nell'ordine sbagliato
2. BTrova ripetutamente il minimo della parte non ordinata e lo scambia portandolo in testa
3. CInserisce ogni elemento in una parte ordinata crescente spostando gli altri
4. DDivide l'array a metà e le fonde

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

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

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

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

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

Perché l'algoritmo di Dijkstra può dare risultati errati quando alcuni pesi degli archi sono negativi?

1. AEntra in un ciclo infinito a ogni arco negativo
2. BFunziona solo sui grafi non orientati
3. CI numeri negativi non si possono memorizzare in una coda di priorità
4. DUn vertice viene considerato definitivo quando è estratto, ma un arco negativo successivo potrebbe ancora dargli un cammino più breve

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

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