Scheda di esercizi di Strutture dati con soluzioni

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

1. AInsieme hash (hash set)
2. BGrafo
3. CPila (stack)
4. DCoda (queue)

Che cos'è la proprietà di max-heap?

1. ALe chiavi sono ordinate da sinistra a destra
2. BLa chiave di ogni genitore è maggiore o uguale alle chiavi dei suoi figli
3. CTutte le foglie contengono la chiave massima
4. DLa chiave di ogni figlio sinistro è maggiore o uguale a quella del fratello destro

In un albero, che cos'è una foglia?

1. AUn nodo con esattamente un figlio
2. BUn nodo senza figli
3. CUn nodo senza genitore
4. DIl nodo con il valore più grande

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

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

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

1. AUno stack
2. BUna coda
3. CSolo una tabella hash
4. DUn heap

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

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

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

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

Per ogni elemento di un array vuoi il successivo elemento maggiore alla sua destra, in tempo totale O(n). Quale struttura aiuta?

1. AUn albero binario di ricerca ricostruito per ogni elemento
2. BUna coda che contiene ogni coppia di elementi
3. CUna tabella hash di tutti gli elementi
4. DUna pila che conserva gli elementi in attesa della loro risposta