Scheda di esercizi di Strutture dati con soluzioni

Una tabella hash memorizza i dati come:

1. ASolo una lista ordinata
2. BUn albero con chiavi ordinate
3. CUna stringa di lunghezza fissa
4. DCoppie chiave–valore individuate da una funzione hash

Quale struttura si usa tipicamente per implementare una coda con priorità?

1. AUn heap
2. BUna lista concatenata semplice non ordinata
3. CUno stack
4. DUna stringa

In un albero, che cos'è una foglia?

1. AUn nodo con esattamente un figlio
2. BIl nodo con il valore più grande
3. CUn nodo senza genitore
4. DUn nodo senza figli

Che cosa succede quando una tabella hash esegue il rehashing dopo che il fattore di carico ha superato una soglia?

1. ALe chiavi più vecchie vengono eliminate per fare spazio
2. BLe chiavi esistenti vengono ordinate sul posto
3. CSolo le chiavi in collisione vengono spostate in una nuova lista di overflow in fondo alla tabella
4. DSi alloca una tabella più grande e ogni chiave viene reinserita

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

1. A11
2. B10
3. C24
4. D14

Un'applicazione ha bisogno di ricerche veloci, ma deve anche elencare le chiavi in ordine e rispondere a interrogazioni su intervalli. Quale struttura è la più adatta?

1. AUna tabella hash
2. BUn albero binario di ricerca bilanciato
3. CUna pila
4. DUna lista concatenata non ordinata

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

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

Che cosa fa uno splay tree dopo ogni accesso?

1. ASposta il nodo acceduto in una foglia
2. BRicolora i nodi lungo il cammino di ricerca
3. CRicostruisce l'intero albero in forma bilanciata
4. DPorta con rotazioni il nodo acceduto fino alla radice