Scheda di esercizi di Algoritmi e complessità con soluzioni

Qual è la complessità temporale della visita in profondità (DFS) su un grafo memorizzato con liste di adiacenza?

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

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

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

Un problema si dice di solito trattabile se:

1. APuò essere risolto in tempo costante
2. BNon ha soluzione
3. CPuò essere risolto in tempo polinomiale
4. DPuò essere risolto solo provando ogni possibilità

Con monete da 1, 3 e 4 e un importo di 6, quante monete usa il metodo greedy "prima la moneta più grande", rispetto all'ottimo?

1. AIl greedy usa 2 monete; l'ottimo è 2
2. BIl greedy usa 3 monete; l'ottimo è 2
3. CIl greedy usa 3 monete; l'ottimo è 3
4. DIl greedy usa 4 monete; l'ottimo è 3

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

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

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

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

Perché una ricerca in una tabella hash è in media O(1) ma nel caso peggiore O(n)?

1. ALe funzioni hash sono lente
2. BLe chiavi devono prima essere ordinate
3. CGli array hanno accesso O(n)
4. DMolte chiavi possono collidere nello stesso bucket

Quali sono i costi in tempo e spazio del calcolo dell'n-esimo numero di Fibonacci con un ciclo che conserva solo gli ultimi due valori?

1. ATempo O(n) e spazio O(1)
2. BTempo O(2ⁿ) e spazio O(1)
3. CTempo O(n) e spazio O(n)
4. DTempo O(log n) e spazio O(n)