Scheda di esercizi di Strutture dati con soluzioni

Che cos'è il fattore di carico di una tabella hash?

1. AIl numero di bucket diviso per la lunghezza media delle chiavi memorizzate
2. BIl numero di collisioni avvenute finora
3. CIl numero di elementi memorizzati diviso per il numero di bucket
4. DIl tempo necessario per caricare la tabella dal disco

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

1. AHeap
2. BPila (stack)
3. CCoda (queue)
4. DAlbero binario

Che cos'è la radice di un albero?

1. AUn qualsiasi nodo intermedio
2. BUn nodo senza figli
3. CIl nodo con il valore più grande
4. DIl nodo più in alto, privo di genitore

In una tabella hash con indirizzamento aperto, qual è il massimo fattore di carico possibile?

1. A2
2. B0,5
3. CNon c'è un massimo
4. D1

Una coda è implementata con due pile: push su una pila «in» e pop da una pila «out», che viene riempita da «in» quando è vuota. Qual è il costo ammortizzato per operazione?

1. AO(1)
2. BO(n)
3. CO(n²)
4. DO(log n)

Come funziona extract-min in un min-heap binario?

1. ASi rimuove l'ultimo elemento dell'array
2. BSi cercano in tutte le foglie il nuovo minimo
3. CSi sposta l'ultimo elemento nella radice e lo si fa scendere
4. DSi rimuove la radice e si spostano tutti gli elementi di una posizione a sinistra

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 evitare ridimensionamenti ripetuti quando push e pop si alternano vicino alla soglia
3. CPer mantenere l'array ordinato
4. DPerché l'allocatore di memoria può liberare memoria solo a quarti di blocco

La complessità temporale di decrease-key in un heap binario (nota la posizione dell'elemento) è:

1. AO(n)
2. BO(n log n)
3. CO(1)
4. DO(log n)