Scheda di esercizi di Strutture dati con soluzioni

Un grafo è composto da:

1. ARighe e colonne
2. BSolo una radice e delle foglie
3. CVertici (nodi) collegati da archi
4. DSolo chiavi e hash

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

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

In una lista concatenata semplice, ogni nodo contiene:

1. ADati e un riferimento al nodo successivo
2. BDati e riferimenti a tutti gli altri nodi
3. CSolo dati
4. DDati e un indice

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 preordine?

1. A4 5 2 3 1
2. B1 2 3 4 5
3. C4 2 5 1 3
4. D1 2 4 5 3

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. BLo stack delle chiamate
3. CUn albero binario di ricerca di frame
4. DLa coda della memoria heap

Qual è la complessità temporale della ricerca di una chiave in un albero binario di ricerca bilanciato?

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

In una tabella hash con indirizzamento aperto, perché la cancellazione avviene spesso con un marcatore «lapide» (tombstone)?

1. ARende la tabella ordinata
2. BLe chiavi cancellate devono essere conservate per sempre per motivi di sicurezza, quindi le posizioni non si possono mai riutilizzare
3. CLe lapidi velocizzano l'hashing
4. DSvuotare la posizione potrebbe interrompere la sequenza di scansione di altre chiavi

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

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