Scheda di esercizi di Algoritmi e complessità con soluzioni

Qual è la complessità temporale nel caso migliore dell'insertion sort, su un array già ordinato?

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

Che cosa richiede la ricerca binaria al suo input?

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

Come funziona il selection sort?

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

Come costruisce l'algoritmo di Prim un albero ricoprente minimo?

1. AOrdina tutti gli archi per peso e aggiunge ciascuno di essi a meno che non formi un ciclo nella foresta
2. BRimuove l'arco più costoso finché non restano cicli
3. CEsegue una visita in ampiezza e conserva l'albero BFS
4. DFa crescere un unico albero da un vertice iniziale, aggiungendo l'arco più economico che esce dall'albero

Quale algoritmo trova i cammini minimi da una sorgente in un grafo con pesi degli archi non negativi?

1. AVisita in profondità (DFS)
2. BAlgoritmo di Kruskal
3. CBellman-Ford è necessario in tutti i casi
4. DAlgoritmo di Dijkstra

La complessità temporale del Fibonacci ricorsivo ingenuo (fib(n) = fib(n−1) + fib(n−2)) è:

1. AEsponenziale
2. BCostante
3. CLogaritmica
4. DLineare

Il problema dello zaino 0/1 risolto con la programmazione dinamica richiede tempo O(nW). Perché si dice pseudo-polinomiale?

1. APerché n è sempre piccolo
2. BPerché funziona solo per W = 0
3. CPerché l'algoritmo è randomizzato e il suo tempo di esecuzione varia a ogni input
4. DW è un numero, quindi il tempo è esponenziale nel numero di bit usati per scrivere W

Quale affermazione su P e NP è corretta?

1. ANP significa «non polinomiale»
2. BLe soluzioni dei problemi NP non possono essere verificate rapidamente
3. CÈ stato dimostrato che P ≠ NP
4. DOgni problema in P appartiene anche a NP