Scheda di esercizi di Strutture dati con soluzioni

Come sono memorizzati in memoria gli elementi di un array?

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

Quale struttura dati funziona secondo il principio «primo a entrare, primo a uscire» (FIFO)?

1. AAlbero binario
2. BCoda (queue)
3. CHeap
4. DPila (stack)

In quale ordine una visita in preordine (preorder) di un albero binario visita i nodi?

1. ANodo, poi sottoalbero sinistro, poi sottoalbero destro
2. BSottoalbero sinistro, poi nodo, poi sottoalbero destro
3. CSottoalbero sinistro, poi sottoalbero destro, poi nodo
4. DLivello per livello a partire dall'alto

Quanto dura la ricerca di una parola di lunghezza L in un trie con alfabeto fisso?

1. AO(L), indipendentemente da quante parole sono memorizzate
2. BO(n), dove n è il numero di parole
3. CO(L × n)
4. DO(log n), dove n è il numero di parole

Quanti nodi ha un albero binario perfetto di altezza h, con l'altezza contata in archi?

1. A2^h
2. B2^h+1 − 1
3. Ch²
4. D2h + 1

Che cosa succede quando una tabella hash esegue il rehashing dopo che il fattore di carico ha superato una soglia?

1. ASolo le chiavi in collisione vengono spostate in una nuova lista di overflow in fondo alla tabella
2. BSi alloca una tabella più grande e ogni chiave viene reinserita
3. CLe chiavi esistenti vengono ordinate sul posto
4. DLe chiavi più vecchie vengono eliminate per fare spazio

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[3, 1, 8, 5]
2. B[1, 5, 8, 3]
3. C[1, 3, 5, 8]
4. D[1, 3, 8, 5]

Quale struttura permette di calcolare il massimo di ogni finestra di dimensione k di un array in tempo totale O(n)?

1. AUn array ordinato aggiornato con spostamenti
2. BUna deque che contiene indici in ordine decrescente di valore
3. CUn min-heap ricostruito per ogni finestra
4. DUna lista concatenata semplice degli elementi della finestra