Scheda di esercizi di Strutture dati con soluzioni

Che cosa memorizza una mappa (dizionario)?

1. ASolo valori in ordine di inserimento
2. BCoppie di chiavi uguali
3. CValori ordinati per grandezza
4. DCoppie chiave–valore con chiavi univoche

In una lista concatenata semplice, che cosa contiene il puntatore al successivo dell'ultimo nodo?

1. AL'indirizzo del nodo precedente
2. BNull (nessun nodo)
3. CIl numero di nodi della lista
4. DL'indirizzo del primo nodo

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

1. AGrafo
2. BPila (stack)
3. CInsieme hash (hash set)
4. DCoda (queue)

Hai un riferimento a un nodo a metà di una lista. In quale lista puoi rimuoverlo in O(1)?

1. AUna lista doppiamente concatenata
2. BUn array dinamico
3. CUn array ordinato
4. DUna lista concatenata semplice

Perché in pratica percorrere un array è spesso molto più veloce che percorrere una lista concatenata della stessa lunghezza?

1. ALe liste concatenate memorizzano sempre gli elementi su disco
2. BLa visita di un array è O(1) in totale, mentre quella di una lista concatenata è O(n)
3. CGli elementi dell'array sono contigui, quindi sfruttano bene la cache della CPU
4. DGli array usano meno istruzioni per confrontare i valori

A che cosa serve un nodo sentinella (fittizio) in una lista concatenata?

1. AA impedire che la lista cresca oltre un numero massimo fisso di nodi
2. BA rendere la lista ordinata
3. CA semplificare il codice eliminando i casi particolari in testa o in coda
4. DA memorizzare il numero di elementi

Nell'ipotesi di hashing uniforme semplice, qual è il tempo atteso di una ricerca in una tabella hash con concatenamento, n chiavi e m bucket?

1. AO(log n)
2. BO(m)
3. CO(n)
4. DO(1 + α), dove α = n / m

Nell'algoritmo di Kruskal per l'albero ricoprente minimo, a che cosa serve la struttura union-find?

1. AA ordinare gli archi per peso
2. BA scegliere il vertice di partenza
3. CA memorizzare la distanza corrente di ogni vertice dalla sorgente durante la visita
4. DA verificare se i due estremi di un arco sono già collegati