Scheda di esercizi di Algoritmi e complessità con soluzioni

Che cosa significa che un'operazione ha tempo O(1)?

1. ARichiede sempre esattamente un secondo
2. BElabora esattamente un elemento per ogni secondo di tempo di esecuzione
3. CPuò essere eseguita una sola volta
4. DIl suo tempo di esecuzione non cresce con la dimensione dell'input

Che cosa descrive il tempo di esecuzione nel caso peggiore di un algoritmo?

1. AIl tempo massimo impiegato su tutti gli input di dimensione n
2. BIl tempo atteso su un input casuale di dimensione n
3. CIl tempo impiegato sull'input più piccolo
4. DIl tempo impiegato su un computer lento

La complessità spaziale misura:

1. ALo spazio su disco del file del programma una volta compilato
2. BLe dimensioni fisiche del computer
3. CIl numero di righe di codice
4. DLa quantità di memoria di cui un algoritmo ha bisogno al crescere dell'input

Qual è la complessità temporale dell'algoritmo di Bellman–Ford su un grafo con V vertici ed E archi?

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

La complessità temporale del Fibonacci ricorsivo ingenuo (fib(n) = fib(n−1) + fib(n−2)) è:

1. ALineare
2. BLogaritmica
3. CCostante
4. DEsponenziale

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

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

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

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

Quale algoritmo trova un albero ricoprente minimo aggiungendo ripetutamente l'arco più economico che non forma un ciclo?

1. AAlgoritmo di Dijkstra
2. BAlgoritmo di Prim a partire da un nodo
3. CFloyd-Warshall
4. DAlgoritmo di Kruskal