Scheda di esercizi di Algoritmi e complessità con soluzioni

Che cosa richiede la ricerca binaria al suo input?

1. AL'array deve contenere solo numeri positivi
2. BL'array non deve avere più di 1000 elementi
3. CLa lunghezza dell'array deve essere una potenza di due
4. DL'array deve essere ordinato

Qual è la complessità temporale per trovare il valore massimo in un array non ordinato di n numeri?

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

Che cos'è un algoritmo a forza bruta?

1. AUn algoritmo che usa sempre la ricorsione
2. BUn algoritmo che prova tutte le possibili soluzioni candidate
3. CUn algoritmo che tira a indovinare una risposta a caso
4. DUn algoritmo che gira su molti processori

Quale affermazione su una funzione ricorsiva senza un caso base raggiungibile è corretta?

1. ARestituisce automaticamente 0
2. BIl compilatore la trasforma sempre in un ciclo che termina in modo sicuro
3. CContinua a chiamare se stessa finché lo stack delle chiamate va in overflow
4. DViene eseguita in tempo O(1)

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

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

Qual è la complessità temporale dell'algoritmo standard di programmazione dinamica per la sottosequenza comune più lunga di stringhe di lunghezze m e n?

1. AO(2^m+n)
2. BO(m + n)
3. CO(mn)
4. DO(mn log n)

Per quale variante dello zaino la regola greedy "prendi gli oggetti in ordine di valore per peso" dà sempre una risposta ottima?

1. ALo zaino 0/1, in cui gli oggetti si devono prendere sempre interi
2. BNessuna delle due varianti
3. CEntrambe le varianti
4. DLo zaino frazionario, in cui gli oggetti si possono dividere

Come rileva l'algoritmo di Bellman–Ford un ciclo di peso negativo raggiungibile dalla sorgente?

1. AControlla se qualche arco ha peso negativo
2. BEsegue due volte l'algoritmo di Dijkstra e confronta i due risultati delle distanze
3. CDopo V − 1 turni controlla se qualche arco può ancora essere rilassato
4. DConta i cicli con una visita in profondità