Scheda di esercizi di Algoritmi e complessità con soluzioni

Quanta memoria aggiuntiva usa un merge sort standard su array?

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

Quale classe di complessità cresce più rapidamente per n grande?

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

Il tempo di esecuzione di un algoritmo è O(n). Come si chiama questa crescita?

1. AQuadratica
2. BCostante
3. CLogaritmica
4. DLineare

Qual è il tempo di esecuzione del radix sort LSD su n interi con d cifre in base k?

1. AO(n²)
2. BO(n log n)
3. CO(dn log k)
4. DO(d(n + k))

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

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

Che cosa significa che un problema ha una sottostruttura ottima?

1. AIl problema si può risolvere in tempo costante
2. BOgni sottoproblema ha la stessa dimensione
3. CUna soluzione ottima può essere costruita da soluzioni ottime dei suoi sottoproblemi
4. DIl problema ha esattamente una soluzione ottima, condivisa da ogni sottoproblema

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

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

Come si classifica il problema del commesso viaggiatore?

1. ALa versione decisionale è NP-completa e la versione di ottimizzazione è NP-difficile
2. BÈ in P perché l'algoritmo di Dijkstra lo risolve visitando ogni città una sola volta
3. CÈ indecidibile
4. DLa versione decisionale è in P ma quella di ottimizzazione è NP-completa