Scheda di esercizi di Strutture dati con soluzioni

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

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

Che cos'è una deque (coda a doppia estremità)?

1. AUna struttura che permette inserimenti e rimozioni a entrambe le estremità
2. BDue code separate che condividono un array
3. CUna coda che permette rimozioni solo in fondo
4. DUna coda ordinata per priorità

In un grafo non orientato, che cos'è il grado di un vertice?

1. AIl numero di vertici del grafo
2. BLa sua posizione nella lista di adiacenza
3. CLa lunghezza del cammino più lungo che parte da esso
4. DIl numero di archi a esso collegati

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

1. AUn array dinamico
2. BUn array ordinato
3. CUna lista doppiamente concatenata
4. DUna lista concatenata semplice

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

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

In un heap binario memorizzato in un array a partire dall'indice 0, dove si trova il genitore del nodo all'indice i?

1. AAll'indice 2i + 1
2. BAll'indice ⌊i / 2⌋ + 1
3. CAll'indice i − 1
4. DAll'indice ⌊(i − 1) / 2⌋

Quanto tempo serve per cercare una chiave arbitraria in un min-heap binario di n elementi?

1. AO(log n)
2. BO(n)
3. CO(1)
4. DO(log log n)

Devi conservare i k valori più piccoli di un flusso di n numeri usando O(k) memoria. Quale approccio funziona in tempo O(n log k)?

1. AUna coda FIFO degli ultimi k valori
2. BUn array ordinato di tutti gli n valori
3. CUn max-heap di dimensione k, di cui si sostituisce la radice quando arriva un valore più piccolo
4. DUn min-heap che contiene tutti gli n valori, da cui alla fine si estraggono i k più piccoli