Scheda di esercizi di Algoritmi e complessità con soluzioni

Qual è la complessità temporale nel caso peggiore dell'insertion sort?

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

Che cosa richiede la ricerca binaria al suo input?

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

Qual è il caso base di una funzione ricorsiva?

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

Che cosa significa che un problema ha una sottostruttura ottima?

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

Una funzione esegue un ciclo di n iterazioni e poi, separatamente, un altro ciclo di n iterazioni. Qual è la sua complessità temporale?

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

In un array ordinato cerchi due elementi la cui somma sia un valore dato muovendo un puntatore da ciascuna estremità verso l'interno. Qual è la complessità temporale?

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

Perché l'algoritmo di Dijkstra può dare risultati errati quando alcuni pesi degli archi sono negativi?

1. AFunziona solo sui grafi non orientati
2. BI numeri negativi non si possono memorizzare in una coda di priorità
3. CEntra in un ciclo infinito a ogni arco negativo
4. DUn vertice viene considerato definitivo quando è estratto, ma un arco negativo successivo potrebbe ancora dargli un cammino più breve

Come si classifica il problema del commesso viaggiatore?

1. AÈ indecidibile
2. BLa versione decisionale è NP-completa e la versione di ottimizzazione è NP-difficile
3. CÈ in P perché l'algoritmo di Dijkstra lo risolve visitando ogni città una sola volta
4. DLa versione decisionale è in P ma quella di ottimizzazione è NP-completa