Scheda di esercizi di Strutture dati con soluzioni

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

1. ALe chiavi sono ordinate da sinistra a destra
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. DTutte le foglie contengono la chiave massima

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

1. AInsieme hash (hash set)
2. BCoda (queue)
3. CGrafo
4. DPila (stack)

In quale ordine una visita in preordine (preorder) di un albero binario visita i nodi?

1. ASottoalbero sinistro, poi nodo, poi sottoalbero destro
2. BLivello per livello a partire dall'alto
3. CSottoalbero sinistro, poi sottoalbero destro, poi nodo
4. DNodo, poi sottoalbero sinistro, poi sottoalbero destro

Un albero binario ha radice 1 con figlio sinistro 2 e figlio destro 3; il nodo 2 ha figli 4 (sinistro) e 5 (destro). Qual è la visita in postordine?

1. A1 2 4 5 3
2. B4 5 2 3 1
3. C5 4 3 2 1
4. D4 2 5 1 3

Le chiavi 50, 30, 70, 20, 40 vengono inserite in quest'ordine in un albero binario di ricerca vuoto. Qual è il figlio sinistro di 30?

1. A70
2. B50
3. C40
4. D20

In una coda circolare memorizzata in un array di capacità n, come si calcola la posizione successiva all'indice i?

1. A(i − 1) mod n
2. B(i + 1) mod n
3. Ci + 1
4. D2i + 1

Un oggetto è memorizzato come chiave in una hash map, e poi viene modificato un campo usato dalla sua funzione hash. Qual è il risultato probabile?

1. ANon cambia nulla, perché l'hash di una chiave si calcola una sola volta all'avvio del programma
2. BLa mappa solleva un errore nel momento in cui il campo cambia
3. CLa mappa sposta automaticamente la chiave nel nuovo bucket
4. DLa ricerca dell'oggetto può fallire perché si trova nel bucket corrispondente al vecchio hash

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

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