Scheda di esercizi di Strutture dati con soluzioni

Che cos'è un grafo pesato?

1. AUn grafo con più archi che vertici
2. BUn grafo in cui ogni arco ha un valore numerico, come un costo o una distanza
3. CUn grafo in cui alcuni vertici sono più pesanti di altri perché hanno più archi
4. DUn grafo memorizzato su disco

Quale struttura dati funziona secondo il principio «ultimo a entrare, primo a uscire» (LIFO)?

1. APila (stack)
2. BCoda (queue)
3. CTabella hash
4. DLista concatenata

Che cosa fa una funzione hash in una tabella hash?

1. AConta quante chiavi sono memorizzate
2. BAssocia una chiave a un indice della tabella
3. COrdina le chiavi della tabella
4. DCifra i valori della tabella

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

1. ASolo una tabella hash
2. BUna coda
3. CUn heap
4. DUno stack

Quanto dura la ricerca di una parola di lunghezza L in un trie con alfabeto fisso?

1. AO(L × n)
2. BO(log n), dove n è il numero di parole
3. CO(L), indipendentemente da quante parole sono memorizzate
4. DO(n), dove n è il numero di parole

Una rete stradale ha 100,000 incroci, ciascuno collegato a circa altri 4. Quale rappresentazione è la più adatta?

1. AUn unico array ordinato di vertici
2. BUn heap binario di archi
3. CMatrice di adiacenza
4. DLista di adiacenza

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

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

Che cosa fa uno splay tree dopo ogni accesso?

1. ARicostruisce l'intero albero in forma bilanciata
2. BRicolora i nodi lungo il cammino di ricerca
3. CPorta con rotazioni il nodo acceduto fino alla radice
4. DSposta il nodo acceduto in una foglia