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. AInsertion sort
2. BBubble sort
3. CQuicksort
4. DMerge sort

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

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

Quanta memoria aggiuntiva usa un merge sort standard su array?

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

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

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

Qual è la complessità temporale della moltiplicazione di due matrici n × n con il triplo ciclo standard?

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

Che cosa significa che un problema ha una sottostruttura ottima?

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

Quale tecnica garantisce al quicksort un tempo di esecuzione atteso O(n log n) su qualsiasi input?

1. AUsare la ricorsione solo sul lato sinistro
2. BScegliere il pivot in modo uniformemente casuale
3. CScegliere sempre il primo elemento
4. DOrdinare l'input prima di eseguire il quicksort

Perché qualsiasi ricerca basata su confronti in un array ordinato richiede Ω(log n) confronti nel caso peggiore?

1. AUn albero di decisione con n esiti possibili deve avere profondità almeno log₂ n
2. BOgni elemento deve essere confrontato almeno una volta
3. CLa ricerca binaria è l'unico algoritmo possibile e richiede log₂ n confronti
4. DOgni confronto richiede un tempo logaritmico