Scheda di esercizi di Strutture dati con soluzioni

In un grafo non orientato, che cos'è il grado di un vertice?

1. ALa sua posizione nella lista di adiacenza
2. BLa lunghezza del cammino più lungo che parte da esso
3. CIl numero di archi a esso collegati
4. DIl numero di vertici del grafo

Quale operazione è O(1) per un array ma O(n) per una lista concatenata semplice?

1. ARimuovere l'elemento in testa
2. BAccedere all'elemento di indice i
3. CInserire in testa
4. DLeggere il primo elemento

Quale struttura dati è più adatta per la funzione «annulla» (undo) di un editor di testo?

1. APila (stack)
2. BInsieme hash (hash set)
3. CGrafo
4. DCoda (queue)

Come si inserisce un nuovo elemento in un heap binario?

1. ALo si pone nella radice e lo si fa scendere
2. BSi ricostruisce da zero l'intero heap
3. CLo si pone alla fine dell'array e lo si fa risalire finché viola la proprietà di heap
4. DLo si inserisce nella posizione ordinata spostando di un posto a destra tutti gli elementi più grandi

Quanti nodi ha un albero binario perfetto di altezza h, con l'altezza contata in archi?

1. Ah²
2. B2h + 1
3. C2^h+1 − 1
4. D2^h

Un albero binario ha radice 1 con figlio sinistro 2 e figlio destro 3; il nodo 2 ha figli 4 (sinistro) e 5 (destro). Qual è la visita in preordine?

1. A4 5 2 3 1
2. B1 2 3 4 5
3. C4 2 5 1 3
4. D1 2 4 5 3

Quale garanzia danno le regole degli alberi rosso-neri sull'altezza di un albero con n chiavi?

1. AL'altezza è al massimo n / 2
2. BL'altezza è al massimo 2 log₂(n + 1)
3. CL'altezza è al massimo log₂ n + 1
4. DL'altezza è esattamente log₂ n

Quale affermazione sull'heapsort è corretta?

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