Scheda di esercizi di Algoritmi e complessità con soluzioni

Qual è il caso base di una funzione ricorsiva?

1. AIl caso con l'input più grande, che viene gestito prima di qualsiasi chiamata ricorsiva
2. BUn caso a cui si risponde direttamente senza un'altra chiamata ricorsiva
3. CLa prima riga della funzione
4. DLa chiamata che usa più memoria

Qual è la complessità temporale della ricerca lineare in un array non ordinato di n elementi (caso peggiore)?

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

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

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

Circa quanti confronti richiede nel caso peggiore la ricerca binaria su un array ordinato di 1,000,000 di elementi?

1. ACirca 100
2. BCirca 20
3. CCirca 1,000
4. DCirca 500,000

Perché la programmazione dinamica non dà un vero guadagno di velocità per il merge sort?

1. AI suoi sottoproblemi non si sovrappongono, quindi non c'è nulla da riutilizzare
2. BIl merge sort non ha una struttura ricorsiva
3. CIl merge sort è già O(n)
4. DLa programmazione dinamica funziona solo sui problemi su grafi, non sugli array

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(log n)
4. DO(1)

Per dimostrare che un nuovo problema X è NP-difficile, che cosa devi fare?

1. ADimostrare che X non ha un algoritmo polinomiale per input piccoli
2. BDimostrare che X si può verificare in tempo polinomiale
3. CRidurre in tempo polinomiale X a un problema NP-difficile noto
4. DRidurre in tempo polinomiale un problema NP-difficile noto a X

Qual è la soluzione della ricorrenza T(n) = 2T(n/2) + n log n?

1. AΘ(n)
2. BΘ(n log n)
3. CΘ(n²)
4. DΘ(n log² n)