Scheda di esercizi di Algoritmi e complessità con soluzioni

Come funziona il selection sort?

1. ADivide l'array a metà e le fonde
2. BScambia ripetutamente elementi adiacenti che sono nell'ordine sbagliato
3. CInserisce ogni elemento in una parte ordinata crescente spostando gli altri
4. DTrova ripetutamente il minimo della parte non ordinata e lo scambia portandolo in testa

Qual è l'O grande di 3n² + 5n + 2?

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

Quale notazione descrive un limite inferiore alla crescita?

1. AΘ (Theta grande)
2. BO (O grande)
3. CΩ (Omega grande)
4. Do (o piccolo)

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 4 monete; l'ottimo è 3
4. DIl greedy usa 3 monete; l'ottimo è 3

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

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

Nel problema della selezione di attività, quale regola greedy dà sempre il numero massimo di attività non sovrapposte?

1. AScegliere l'attività che termina prima, poi ripetere con quelle compatibili
2. BScegliere l'attività che inizia prima
3. CScegliere per prima l'attività con meno sovrapposizioni, poi ripetere con quelle compatibili
4. DScegliere per prima l'attività più breve

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

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

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

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