Scheda di esercizi di Algoritmi e complessità con soluzioni

Quale di queste cresce più lentamente quando n diventa grande?

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

Accedere a un elemento di un array tramite indice richiede:

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

Quale algoritmo di ordinamento scambia ripetutamente elementi adiacenti che sono nell'ordine sbagliato?

1. AHeap sort
2. BMerge sort
3. CBubble sort
4. DQuicksort

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

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

Che cosa misura l'analisi ammortizzata?

1. AIl costo atteso su input casuali
2. BIl costo di un algoritmo sull'input migliore
3. CIl costo della singola operazione più costosa in un punto qualsiasi della sequenza
4. DIl costo medio per operazione su una sequenza di operazioni nel caso peggiore

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

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

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

1. ANo, perché l'insertion sort non è un ordinamento per confronti
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. DSì, quindi il limite inferiore è sbagliato

Quale definizione della classe P è corretta?

1. AProblemi le cui soluzioni si possono verificare ma mai trovare in tempo polinomiale
2. BProblemi decisionali risolvibili da un algoritmo deterministico in tempo polinomiale
3. CProblemi che richiedono tempo esponenziale su ogni computer
4. DProblemi che si possono risolvere in parallelo