Scheda di esercizi di Strutture dati con soluzioni

L'altezza di un albero è comunemente definita come:

1. AIl numero di figli della radice
2. BIl numero di foglie dell'albero
3. CIl numero di archi del cammino più lungo dalla radice a una foglia
4. DIl numero totale di nodi dell'albero, contando la radice e ogni foglia

Una tabella hash memorizza i dati come:

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

Quanti archi ha un albero con n nodi?

1. An
2. B2n
3. Cn − 1
4. Dn + 1

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

1. ALa coda della memoria heap
2. BUn albero binario di ricerca di frame
3. CUna tabella hash di funzioni
4. DLo stack delle chiamate

Come funziona extract-min in un min-heap binario?

1. ASi sposta l'ultimo elemento nella radice e lo si fa scendere
2. BSi rimuove l'ultimo elemento dell'array
3. CSi cercano in tutte le foglie il nuovo minimo
4. DSi rimuove la radice e si spostano tutti gli elementi di una posizione a sinistra

Un albero binario ha radice 1 con figlio sinistro 2 e figlio destro 3; il nodo 2 ha figli 4 (sinistro) e 5 (destro). Qual è la visita in preordine?

1. A1 2 3 4 5
2. B4 5 2 3 1
3. C1 2 4 5 3
4. D4 2 5 1 3

Perché i B-alberi (B-tree) sono usati nei database e nei file system?

1. ANon richiedono ribilanciamento
2. BMemorizzano i dati in modo non ordinato
3. CUsano meno memoria di qualsiasi array, quindi l'intero indice sta sempre nella memoria centrale
4. DIl loro elevato fattore di ramificazione mantiene l'albero poco profondo, riducendo le lente letture da disco

Per ogni elemento di un array vuoi il successivo elemento maggiore alla sua destra, in tempo totale O(n). Quale struttura aiuta?

1. AUn albero binario di ricerca ricostruito per ogni elemento
2. BUna pila che conserva gli elementi in attesa della loro risposta
3. CUna coda che contiene ogni coppia di elementi
4. DUna tabella hash di tutti gli elementi