Scheda di esercizi di Strutture dati con soluzioni

In un grafo, che cos'è un ciclo?

1. AUn cammino che inizia e finisce nello stesso vertice
2. BUn vertice senza archi
3. CUn cammino che visita ogni vertice
4. DUn arco di peso zero

Come si chiama l'operazione di una pila (stack) che aggiunge un elemento in cima?

1. APeek
2. BPush
3. CPop
4. DEnqueue

Dove si trova l'elemento più piccolo di un min-heap binario?

1. ANella foglia più a sinistra
2. BNell'ultima posizione dell'array
3. CNella radice
4. DIn una foglia qualsiasi, da cercare

Quale struttura dati usa la visita in profondità (DFS) nella versione iterativa?

1. AUna coda
2. BSolo una tabella hash
3. CUn heap
4. DUno stack

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

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

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 2i + 1
2. BAll'indice i − 1
3. CAll'indice ⌊(i − 1) / 2⌋
4. DAll'indice ⌊i / 2⌋ + 1

Quale problema della scansione lineare viene ridotto principalmente dal doppio hashing?

1. AIl costo O(n) della lettura del valore di una chiave
2. BL'agglomerazione primaria (primary clustering), cioè la formazione di lunghe sequenze di posizioni occupate
3. CLa necessità di memorizzare le chiavi nella tabella
4. DLa necessità di una funzione hash

Perché in un filtro di Bloom standard non si possono semplicemente eliminare gli elementi azzerandone i bit?

1. AI bit di un filtro di Bloom non si possono modificare dopo la creazione
2. BI filtri di Bloom memorizzano gli elementi completi, che una volta sottoposti a hash non si possono più ritrovare
3. CL'eliminazione porterebbe il tasso di falsi positivi al 100%
4. DQuei bit possono appartenere anche ad altri elementi, il che causerebbe falsi negativi