Scheda di esercizi di Strutture dati con soluzioni

Come sono memorizzati in memoria gli elementi di un array?

1. AIn un unico blocco contiguo, uno dopo l'altro
2. BIn posizioni casuali scelte da un hash
3. CIn un albero di pagine di memoria
4. DSparsi, collegati da puntatori

Che cosa fa una funzione hash in una tabella hash?

1. AConta quante chiavi sono memorizzate
2. BOrdina le chiavi della tabella
3. CCifra i valori della tabella
4. DAssocia una chiave a un indice della tabella

Che cos'è il fattore di carico di una tabella hash?

1. AIl numero di bucket diviso per la lunghezza media delle chiavi memorizzate
2. BIl numero di collisioni avvenute finora
3. CIl tempo necessario per caricare la tabella dal disco
4. DIl numero di elementi memorizzati diviso per il numero di bucket

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

1. A5 4 3 2 1
2. B4 2 5 1 3
3. C1 2 4 5 3
4. D4 5 2 3 1

Quale metodo di risoluzione delle collisioni memorizza le chiavi in collisione in una lista nello stesso bucket?

1. AConcatenamento separato (separate chaining)
2. BScansione quadratica (quadratic probing)
3. CDoppio hashing (double hashing)
4. DScansione lineare (linear probing)

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

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

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

Un segment tree (albero dei segmenti) è tipicamente usato per:

1. ARispondere a interrogazioni su intervalli (come somme su intervalli) e aggiornamenti in O(log n)
2. BImplementare uno stack
3. CMemorizzare gli archi di un grafo
4. DOrdinare stringhe alfabeticamente memorizzando ogni prefisso in un nodo separato dell'albero