Scheda di esercizi di Strutture dati con soluzioni

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

1. APila (stack)
2. BCoda (queue)
3. CHeap
4. DAlbero binario

Quale operazione è O(1) per un array ma O(n) per una lista concatenata semplice?

1. AInserire in testa
2. BRimuovere l'elemento in testa
3. CLeggere il primo elemento
4. DAccedere all'elemento di indice i

In una lista concatenata semplice, ogni nodo contiene:

1. ADati e un riferimento al nodo successivo
2. BSolo dati
3. CDati e un indice
4. DDati e riferimenti a tutti gli altri nodi

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 i − 1
2. BAll'indice 2i + 1
3. CAll'indice ⌊i / 2⌋ + 1
4. DAll'indice ⌊(i − 1) / 2⌋

Qual è l'altezza nel caso peggiore di un albero binario di ricerca con n nodi se le chiavi vengono inserite in ordine?

1. Alog₂ n
2. B√n
3. Cn (diventa una lista concatenata)
4. D1

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

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

Quali sono i costi in tempo e in spazio aggiuntivo dell'inversione sul posto di una lista concatenata semplice?

1. ATempo O(n) e spazio aggiuntivo O(n)
2. BTempo O(n) e spazio aggiuntivo O(1)
3. CTempo O(1) e spazio aggiuntivo O(1)
4. DTempo O(n log n) e spazio aggiuntivo O(1)

In una tabella hash con indirizzamento aperto, perché la cancellazione avviene spesso con un marcatore «lapide» (tombstone)?

1. ALe chiavi cancellate devono essere conservate per sempre per motivi di sicurezza, quindi le posizioni non si possono mai riutilizzare
2. BLe lapidi velocizzano l'hashing
3. CRende la tabella ordinata
4. DSvuotare la posizione potrebbe interrompere la sequenza di scansione di altre chiavi