Scheda di esercizi di Strutture dati con soluzioni

Una tabella hash memorizza i dati come:

1. AUna stringa di lunghezza fissa
2. BSolo una lista ordinata
3. CCoppie chiave–valore individuate da una funzione hash
4. DUn albero con chiavi ordinate

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

1. ASottoalbero sinistro, poi nodo, poi sottoalbero destro
2. BNodo, poi sottoalbero sinistro, poi sottoalbero destro
3. CLivello per livello a partire dall'alto
4. DSottoalbero sinistro, poi sottoalbero destro, poi nodo

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

1. ATabella hash
2. BCoda
3. CPila
4. DCoda con priorità

Quale struttura dati usa un programma in esecuzione per tenere traccia delle chiamate di funzione attive e delle loro variabili locali?

1. AUna tabella hash di funzioni
2. BLo stack delle chiamate
3. CLa coda della memoria heap
4. DUn albero binario di ricerca di frame

Una tabella hash di dimensione 7 usa h(k) = k mod 7 e la scansione lineare. Dopo aver inserito 10, dove viene memorizzato 17?

1. AAll'indice 6
2. BAll'indice 0
3. CAll'indice 3
4. DAll'indice 4

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

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

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

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

Nell'ipotesi di hashing uniforme semplice, qual è il tempo atteso di una ricerca in una tabella hash con concatenamento, n chiavi e m bucket?

1. AO(m)
2. BO(log n)
3. CO(n)
4. DO(1 + α), dove α = n / m