Scheda di esercizi di Strutture dati con soluzioni

In una tabella hash, che cos'è una collisione?

1. ALa tabella esaurisce la memoria
2. BUna chiave non può essere sottoposta a hash
3. CDue chiavi uguali vengono memorizzate due volte
4. DDue chiavi diverse vengono associate allo stesso indice

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

1. APila (stack)
2. BTabella hash
3. CCoda (queue)
4. DLista concatenata

Che cos'è una deque (coda a doppia estremità)?

1. AUna coda ordinata per priorità
2. BUna coda che permette rimozioni solo in fondo
3. CDue code separate che condividono un array
4. DUna struttura che permette inserimenti e rimozioni a entrambe le estremità

Quanto dura la ricerca di una parola di lunghezza L in un trie con alfabeto fisso?

1. AO(L), indipendentemente da quante parole sono memorizzate
2. BO(n), dove n è il numero di parole
3. CO(log n), dove n è il numero di parole
4. DO(L × n)

Quale struttura dati usa un programma in esecuzione per tenere traccia delle chiamate di funzione attive e delle loro variabili locali?

1. AUna tabella hash di funzioni
2. BUn albero binario di ricerca di frame
3. CLo stack delle chiamate
4. DLa coda della memoria heap

Quale condizione di bilanciamento mantiene un albero AVL in ogni nodo?

1. ALe altezze dei sottoalberi sinistro e destro differiscono al massimo di 1
2. BOgni nodo è colorato di rosso o di nero
3. CTutte le foglie sono esattamente alla stessa profondità
4. DI due sottoalberi di ogni nodo contengono esattamente lo stesso numero di nodi

Nel BST con radice 50, sottoalbero sinistro 30 (figli 20, 40) e sottoalbero destro 70 (figli 60, 80), la radice viene eliminata usando il successore in ordine. Quale chiave diventa la nuova radice?

1. A60
2. B40
3. C80
4. D70

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(n)
2. BO(m)
3. CO(1 + α), dove α = n / m
4. DO(log n)