Scheda di esercizi di Strutture dati con soluzioni

Quale struttura dati si usa per eseguire una visita per livelli di un albero?

1. ACoda
2. BPila
3. CTabella hash
4. DCoda con priorità

Che cos'è la proprietà di max-heap?

1. ALa chiave di ogni genitore è maggiore o uguale alle chiavi dei suoi figli
2. BLa chiave di ogni figlio sinistro è maggiore o uguale a quella del fratello destro
3. CLe chiavi sono ordinate da sinistra a destra
4. DTutte le foglie contengono la chiave massima

In una tabella hash, che cos'è una collisione?

1. AUna chiave non può essere sottoposta a hash
2. BDue chiavi diverse vengono associate allo stesso indice
3. CDue chiavi uguali vengono memorizzate due volte
4. DLa tabella esaurisce la memoria

Quanto tempo serve per verificare se l'arco (u, v) esiste usando una matrice di adiacenza?

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

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

1. A1
2. B√n
3. Clog₂ n
4. Dn (diventa una lista concatenata)

Una coda è implementata con due pile: push su una pila «in» e pop da una pila «out», che viene riempita da «in» quando è vuota. Qual è il costo ammortizzato per operazione?

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

In che modo un radix tree (trie compresso) migliora un trie semplice?

1. AFonde le catene di nodi con un solo figlio in un unico arco etichettato con una stringa
2. BOrdina i figli di ogni nodo per frequenza
3. CMemorizza ogni parola in una tabella hash alla radice invece che in nodi separati
4. DConserva solo la prima lettera di ogni parola

Un filtro di Bloom può rispondere alla domanda «questo elemento è nell'insieme?» con:

1. ARisposte sempre esatte
2. BRisposte solo per numeri
3. CPossibili falsi negativi ma nessun falso positivo
4. DPossibili falsi positivi ma nessun falso negativo