Scheda di esercizi di Strutture dati con soluzioni

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

1. ACoda (queue)
2. BGrafo
3. CInsieme hash (hash set)
4. DPila (stack)

In una lista concatenata semplice, che cosa contiene il puntatore al successivo dell'ultimo nodo?

1. ANull (nessun nodo)
2. BL'indirizzo del nodo precedente
3. CIl numero di nodi della lista
4. DL'indirizzo del primo nodo

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

1. ATabella hash
2. BLista concatenata
3. CCoda (queue)
4. DPila (stack)

Una tabella hash di dimensione 7 usa h(k) = k mod 7 e la scansione lineare. Dopo aver inserito 10, dove viene memorizzato 17?

1. AAll'indice 0
2. BAll'indice 4
3. CAll'indice 6
4. DAll'indice 3

Qual è il valore dell'espressione postfissa 3 4 + 2 * ?

1. A24
2. B11
3. C14
4. D10

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

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

Un array dinamico raddoppia quando è pieno. Perché molte implementazioni lo riducono solo quando è pieno per un quarto, e non per metà?

1. APerché l'allocatore di memoria può liberare memoria solo a quarti di blocco
2. BPerché dimezzare a metà farebbe perdere elementi
3. CPer mantenere l'array ordinato
4. DPer evitare ridimensionamenti ripetuti quando push e pop si alternano vicino alla soglia

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