Scheda di esercizi di Strutture dati con soluzioni

Che cosa definisce un albero binario?

1. AOgni nodo ha esattamente due figli
2. BOgni nodo ha al massimo due figli
3. COgni nodo memorizza un numero binario
4. DL'albero ha esattamente due livelli

Un grafo è composto da:

1. ARighe e colonne
2. BSolo una radice e delle foglie
3. CVertici (nodi) collegati da archi
4. DSolo chiavi e hash

Qual è la caratteristica distintiva di un insieme (set) come tipo di dato astratto?

1. AMemorizza elementi senza duplicati
2. BPermette l'accesso solo a un'estremità
3. CMemorizza elementi in ordine
4. DMemorizza coppie chiave–valore

Qual è la complessità temporale della ricerca di una chiave in un albero binario di ricerca bilanciato?

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

In una tabella hash con indirizzamento aperto, qual è il massimo fattore di carico possibile?

1. A1
2. B2
3. C0,5
4. DNon c'è un massimo

Come funziona extract-min in un min-heap binario?

1. ASi rimuove la radice e si spostano tutti gli elementi di una posizione a sinistra
2. BSi rimuove l'ultimo elemento dell'array
3. CSi cercano in tutte le foglie il nuovo minimo
4. DSi sposta l'ultimo elemento nella radice e lo si fa scendere

Qual è il tempo di esecuzione della visita in ampiezza (BFS) su un grafo con V vertici memorizzato come matrice di adiacenza?

1. AO(V + E)
2. BO(E log V)
3. CO(V)
4. DO(V²)

Quale affermazione sull'heapsort è corretta?

1. AOrdina sul posto in tempo O(n log n) nel caso peggiore ma non è stabile
2. BRichiede tempo O(n) su qualsiasi input
3. CRichiede un albero binario di ricerca come memoria aggiuntiva, quindi usa O(n) memoria extra
4. DÈ stabile e richiede O(n) memoria aggiuntiva