Scheda di esercizi di Strutture dati con soluzioni

Una tabella hash memorizza i dati come:

1. ACoppie chiave–valore individuate da una funzione hash
2. BUna stringa di lunghezza fissa
3. CUn albero con chiavi ordinate
4. DSolo una lista ordinata

Che cos'è la proprietà di max-heap?

1. ATutte le foglie contengono la chiave massima
2. BLa chiave di ogni genitore è maggiore o uguale alle chiavi dei suoi figli
3. CLa chiave di ogni figlio sinistro è maggiore o uguale a quella del fratello destro
4. DLe chiavi sono ordinate da sinistra a destra

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)

In un heap binario memorizzato in un array a partire dall'indice 0, dove si trova il genitore del nodo all'indice i?

1. AAll'indice i − 1
2. BAll'indice 2i + 1
3. CAll'indice ⌊i / 2⌋ + 1
4. DAll'indice ⌊(i − 1) / 2⌋

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 6
2. BAll'indice 0
3. CAll'indice 4
4. DAll'indice 3

Qual è l'altezza nel caso peggiore di un albero binario di ricerca con n nodi se le chiavi vengono inserite in ordine?

1. An (diventa una lista concatenata)
2. B1
3. Clog₂ n
4. D√n

In un buffer circolare, front == rear può significare sia vuoto sia pieno. Qual è un modo comune per distinguere i due casi?

1. ARendere la dimensione del buffer una potenza di due
2. BSvuotare sempre il buffer ogni volta che front è uguale a rear, così lo stato è vuoto
3. CMantenere un contatore separato degli elementi, oppure lasciare sempre una posizione inutilizzata
4. DMemorizzare front e rear nella stessa variabile

Un filtro di Bloom può rispondere alla domanda «questo elemento è nell'insieme?» con:

1. ARisposte solo per numeri
2. BPossibili falsi positivi ma nessun falso negativo
3. CRisposte sempre esatte
4. DPossibili falsi negativi ma nessun falso positivo