Scheda di esercizi di Strutture dati con soluzioni

Nella rappresentazione di un grafo con liste di adiacenza, che cosa si memorizza per ogni vertice?

1. AUna riga di V valori booleani
2. BUna lista dei suoi vertici adiacenti
3. CIl cammino minimo verso ogni altro vertice
4. DIl numero totale di archi del grafo

In un albero, che cosa sono i nodi fratelli?

1. AUn nodo e il suo genitore
2. BNodi privi di figli
3. CNodi che hanno lo stesso genitore
4. DNodi alla stessa profondità in sottoalberi diversi

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

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

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

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

Quale struttura dati usa un programma in esecuzione per tenere traccia delle chiamate di funzione attive e delle loro variabili locali?

1. ALo stack delle chiamate
2. BUna tabella hash di funzioni
3. CUn albero binario di ricerca di frame
4. DLa coda della memoria heap

Un nodo di un albero binario di ricerca ha un sottoalbero destro. Dove si trova il suo successore in ordine?

1. ANel suo figlio destro, sempre
2. BNel nodo più a sinistra del suo sottoalbero destro
3. CNel nodo più a destra del suo sottoalbero sinistro
4. DNel suo genitore, sempre

Quale struttura dati permette una cache LRU (least recently used) con get e put in O(1)?

1. AUn singolo array ordinato
2. BUna hash map combinata con una lista doppiamente concatenata
3. CSolo un albero binario di ricerca
4. DSolo uno stack

Le chiavi 5, 3, 8, 1 vengono inserite in quest'ordine in un min-heap binario vuoto basato su array. Qual è l'array finale?

1. A[1, 3, 5, 8]
2. B[1, 5, 8, 3]
3. C[3, 1, 8, 5]
4. D[1, 3, 8, 5]