Scheda di esercizi di Strutture dati con soluzioni

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

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

Come sono memorizzati in memoria gli elementi di un array?

1. ASparsi, collegati da puntatori
2. BIn un unico blocco contiguo, uno dopo l'altro
3. CIn posizioni casuali scelte da un hash
4. DIn un albero di pagine di memoria

Che cosa fa una funzione hash in una tabella hash?

1. AAssocia una chiave a un indice della tabella
2. BOrdina le chiavi della tabella
3. CConta quante chiavi sono memorizzate
4. DCifra i valori della tabella

Qual è l'altezza nel caso peggiore di un albero binario di ricerca con n nodi se le chiavi vengono inserite in ordine?

1. An (diventa una lista concatenata)
2. B1
3. C√n
4. Dlog₂ n

Come si inserisce un nuovo elemento in un heap binario?

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

Un nodo di un albero binario di ricerca ha un sottoalbero destro. Dove si trova il suo successore in ordine?

1. ANel nodo più a sinistra del suo sottoalbero destro
2. BNel nodo più a destra del suo sottoalbero sinistro
3. CNel suo figlio destro, sempre
4. DNel suo genitore, sempre

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 è esattamente log₂ n
4. DL'altezza è al massimo log₂ n + 1

Le chiavi 5, 3, 8, 1 vengono inserite in quest'ordine in un min-heap binario vuoto basato su array. Qual è l'array finale?

1. A[1, 3, 5, 8]
2. B[1, 3, 8, 5]
3. C[3, 1, 8, 5]
4. D[1, 5, 8, 3]