Scheda di esercizi di Algoritmi e complessità con soluzioni

Quale notazione descrive un limite inferiore alla crescita?

1. AΩ (Omega grande)
2. BΘ (Theta grande)
3. CO (O grande)
4. Do (o piccolo)

Qual è la complessità temporale nel caso migliore dell'insertion sort, su un array già ordinato?

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

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

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

La visita in ampiezza (BFS) su un grafo non pesato trova:

1. AUn ordinamento topologico in tutti i grafi
2. BI cammini minimi in numero di archi dal nodo di partenza
3. CI cammini minimi in grafi che contengono archi con peso negativo
4. DL'albero ricoprente minimo

Quale algoritmo trova i cammini minimi da una sorgente in un grafo con pesi degli archi non negativi?

1. AVisita in profondità (DFS)
2. BBellman-Ford è necessario in tutti i casi
3. CAlgoritmo di Kruskal
4. DAlgoritmo di Dijkstra

Qual è la soluzione della ricorrenza T(n) = T(n − 1) + O(1)?

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

L'insertion sort richiede O(n) su un input ordinato. Questo contraddice il limite inferiore Ω(n log n) per l'ordinamento per confronti?

1. ASì, quindi il limite inferiore è sbagliato
2. BSì, ma solo per array più corti di 100
3. CNo, il limite inferiore si applica al caso peggiore su tutti gli input, non a ogni input
4. DNo, perché l'insertion sort non è un ordinamento per confronti

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

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