Scheda di esercizi di Strutture dati con soluzioni

Che cosa fa una funzione hash in una tabella hash?

1. AConta quante chiavi sono memorizzate
2. BCifra i valori della tabella
3. CAssocia una chiave a un indice della tabella
4. DOrdina le chiavi della tabella

In quale ordine una visita in postordine (postorder) di un albero binario visita i nodi?

1. ASottoalbero sinistro, poi sottoalbero destro, poi nodo
2. BNodo, poi sottoalbero sinistro, poi sottoalbero destro
3. CSottoalbero sinistro, poi nodo, poi sottoalbero destro
4. DSottoalbero destro, poi nodo, poi sottoalbero sinistro

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

1. APila
2. BCoda con priorità
3. CCoda
4. DTabella hash

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

1. Ah²
2. B2^h
3. C2^h+1 − 1
4. D2h + 1

Gli alberi AVL e gli alberi rosso-neri garantiscono:

1. AUn'altezza O(log n) tramite il ribilanciamento
2. BChe nessun nodo abbia due figli
3. CUna ricerca in tempo costante in ogni caso
4. DChe le chiavi siano memorizzate in ordine di inserimento

Qual è il valore dell'espressione postfissa 3 4 + 2 * ?

1. A10
2. B14
3. C24
4. D11

Quale problema della scansione lineare viene ridotto principalmente dal doppio hashing?

1. ALa necessità di una funzione hash
2. BL'agglomerazione primaria (primary clustering), cioè la formazione di lunghe sequenze di posizioni occupate
3. CIl costo O(n) della lettura del valore di una chiave
4. DLa necessità di memorizzare le chiavi nella tabella

Quale coppia di visite determina sempre un unico albero binario con chiavi distinte?

1. APreordine e ordine simmetrico (inorder)
2. BIl solo preordine
3. CLa sola visita per livelli
4. DPreordine e postordine