Scheda di esercizi di Algoritmi e complessità con soluzioni

Quale algoritmo di ordinamento sceglie un pivot e partiziona l'array in elementi minori e maggiori?

1. AQuicksort
2. BBubble sort
3. CInsertion sort
4. DMerge sort

Qual è la complessità temporale del merge sort nel caso peggiore?

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

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

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

Come costruisce l'algoritmo di Prim un albero ricoprente minimo?

1. ARimuove l'arco più costoso finché non restano cicli
2. BEsegue una visita in ampiezza e conserva l'albero BFS
3. COrdina tutti gli archi per peso e aggiunge ciascuno di essi a meno che non formi un ciclo nella foresta
4. DFa crescere un unico albero da un vertice iniziale, aggiungendo l'arco più economico che esce dall'albero

Qual è la complessità temporale ammortizzata dell'aggiunta in coda a un array dinamico che raddoppia la capacità quando è pieno?

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

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

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

Quale limite è corretto per log(n!)?

1. AΘ(n²)
2. BΘ(n)
3. CΘ(log n)
4. DΘ(n log 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. BLa selezione è possibile solo in O(n²)
3. CIl quickselect richiede O(log n) nel caso peggiore, perché ricorre su un solo lato del pivot
4. DIl quickselect richiede O(n) atteso, e la mediana delle mediane garantisce O(n) nel caso peggiore