Scheda di esercizi di Algoritmi e complessità con soluzioni

Quale algoritmo di ordinamento scambia ripetutamente elementi adiacenti che sono nell'ordine sbagliato?

1. AMerge sort
2. BQuicksort
3. CHeap sort
4. DBubble sort

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

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

Il tempo di esecuzione di un algoritmo è O(n). Come si chiama questa crescita?

1. ALogaritmica
2. BLineare
3. CCostante
4. DQuadratica

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

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

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

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

Qual è la complessità temporale della moltiplicazione di due matrici n × n con il triplo ciclo standard?

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

Quale affermazione sulla selezione del k-esimo elemento più piccolo di un array non ordinato è corretta?

1. AIl quickselect richiede O(n) atteso, e la mediana delle mediane garantisce O(n) nel caso peggiore
2. BLa selezione richiede sempre Ω(n log n) perché richiede un ordinamento
3. CLa selezione è possibile solo in O(n²)
4. DIl quickselect richiede O(log n) nel caso peggiore, perché ricorre su un solo lato del pivot

Come si classifica il problema del commesso viaggiatore?

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