Scheda di esercizi di Strutture dati con soluzioni

In un albero, che cosa sono i nodi fratelli?

1. ANodi alla stessa profondità in sottoalberi diversi
2. BNodi privi di figli
3. CNodi che hanno lo stesso genitore
4. DUn nodo e il suo genitore

Quale struttura dati funziona secondo il principio «ultimo a entrare, primo a uscire» (LIFO)?

1. APila (stack)
2. BCoda (queue)
3. CTabella hash
4. DLista concatenata

Dove si trova l'elemento più piccolo di un min-heap binario?

1. ANella radice
2. BNella foglia più a sinistra
3. CIn una foglia qualsiasi, da cercare
4. DNell'ultima posizione dell'array

Che cosa è vero per la matrice di adiacenza di un grafo non orientato?

1. ALa sua diagonale principale contiene sempre degli uno
2. BÈ sempre triangolare superiore
3. COgni riga contiene esattamente un 1
4. DÈ simmetrica rispetto alla diagonale principale

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

Un buffer circolare (ring buffer) è comunemente usato per implementare:

1. AUna visita di un grafo
2. BUna coda di dimensione fissa
3. CUn albero binario di ricerca
4. DUna funzione hash

Quale problema della scansione lineare viene ridotto principalmente dal doppio hashing?

1. AIl costo O(n) della lettura del valore di una chiave
2. BLa necessità di una funzione hash
3. CL'agglomerazione primaria (primary clustering), cioè la formazione di lunghe sequenze di posizioni occupate
4. DLa necessità di memorizzare le chiavi nella tabella

Nell'ipotesi di hashing uniforme semplice, qual è il tempo atteso di una ricerca in una tabella hash con concatenamento, n chiavi e m bucket?

1. AO(m)
2. BO(n)
3. CO(1 + α), dove α = n / m
4. DO(log n)