Scheda di esercizi di Algoritmi e complessità con soluzioni

Che cos'è un algoritmo a forza bruta?

1. AUn algoritmo che gira su molti processori
2. BUn algoritmo che tira a indovinare una risposta a caso
3. CUn algoritmo che usa sempre la ricorsione
4. DUn algoritmo che prova tutte le possibili soluzioni candidate

Come funziona il selection sort?

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

Quanta memoria aggiuntiva usa un merge sort standard su array?

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

Con monete da 1, 3 e 4 e un importo di 6, quante monete usa il metodo greedy "prima la moneta più grande", rispetto all'ottimo?

1. AIl greedy usa 3 monete; l'ottimo è 3
2. BIl greedy usa 2 monete; l'ottimo è 2
3. CIl greedy usa 3 monete; l'ottimo è 2
4. DIl greedy usa 4 monete; l'ottimo è 3

Ordini una volta un array di n elementi e poi rispondi a k query di appartenenza con la ricerca binaria. Qual è il costo totale?

1. AO(k n log n)
2. BO(nk)
3. CO(n + k)
4. DO(n log n + k log n)

Qual è la complessità temporale dell'algoritmo standard di programmazione dinamica per la sottosequenza comune più lunga di stringhe di lunghezze m e n?

1. AO(m + n)
2. BO(2^m+n)
3. CO(mn)
4. DO(mn log n)

Qual è la soluzione della ricorrenza T(n) = 2T(n/2) + n log n?

1. AΘ(n log n)
2. BΘ(n)
3. CΘ(n log² n)
4. DΘ(n²)

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

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