Scheda di esercizi di Algoritmi e complessità con soluzioni

Qual è la complessità temporale nel caso peggiore dell'insertion sort?

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

Che cos'è un algoritmo?

1. AUna sequenza finita di passi ben definiti che risolve un problema
2. BQualsiasi programma con un'interfaccia grafica
3. CUn linguaggio di programmazione progettato per scrivere formule matematiche
4. DUna struttura dati che memorizza numeri

Qual è la complessità temporale della visita in profondità (DFS) su un grafo memorizzato con liste di adiacenza?

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

In un array ordinato cerchi due elementi la cui somma sia un valore dato muovendo un puntatore da ciascuna estremità verso l'interno. Qual è la complessità temporale?

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

Il limite inferiore per l'ordinamento basato su confronti nel caso peggiore è:

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

Qual è la complessità temporale del calcolo dell'n-esimo numero di Fibonacci con una tabella bottom-up?

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

Quale affermazione sulla selezione del k-esimo elemento più piccolo di un array non ordinato è corretta?

1. AIl quickselect richiede O(log n) nel caso peggiore, perché ricorre su un solo lato del pivot
2. BIl quickselect richiede O(n) atteso, e la mediana delle mediane garantisce O(n) nel caso peggiore
3. CLa selezione richiede sempre Ω(n log n) perché richiede un ordinamento
4. DLa selezione è possibile solo in O(n²)

Per quale variante dello zaino la regola greedy "prendi gli oggetti in ordine di valore per peso" dà sempre una risposta ottima?

1. ALo zaino frazionario, in cui gli oggetti si possono dividere
2. BEntrambe le varianti
3. CNessuna delle due varianti
4. DLo zaino 0/1, in cui gli oggetti si devono prendere sempre interi