Scheda di esercizi di Strutture dati con soluzioni

Come si chiama l'operazione di una coda (queue) che rimuove l'elemento in testa?

1. AInsert
2. BEnqueue
3. CDequeue
4. DPush

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

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

In un grafo non orientato, che cos'è il grado di un vertice?

1. ALa sua posizione nella lista di adiacenza
2. BLa lunghezza del cammino più lungo che parte da esso
3. CIl numero di vertici del grafo
4. DIl numero di archi a esso collegati

Un buffer circolare (ring buffer) è comunemente usato per implementare:

1. AUna coda di dimensione fissa
2. BUna funzione hash
3. CUn albero binario di ricerca
4. DUna visita di un grafo

Quanti nodi ha un albero binario perfetto di altezza h, con l'altezza contata in archi?

1. Ah²
2. B2h + 1
3. C2^h
4. D2^h+1 − 1

Gli alberi AVL e gli alberi rosso-neri garantiscono:

1. AChe nessun nodo abbia due figli
2. BUna ricerca in tempo costante in ogni caso
3. CChe le chiavi siano memorizzate in ordine di inserimento
4. DUn'altezza O(log n) tramite il ribilanciamento

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

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

Perché una tabella hash funzioni correttamente, quale regola devono rispettare hash e uguaglianza?

1. AChiavi uguali devono avere valori hash uguali
2. BValori hash uguali implicano chiavi uguali
3. CI valori hash devono essere numeri primi
4. DChiavi diverse devono avere valori hash diversi