Scheda di esercizi di Strutture dati con soluzioni

Che cos'è la radice di un albero?

1. AIl nodo con il valore più grande
2. BUn qualsiasi nodo intermedio
3. CUn nodo senza figli
4. DIl nodo più in alto, privo di genitore

La profondità di un nodo in un albero è:

1. AIl numero di nodi del suo sottoalbero
2. BIl numero di archi dalla radice a quel nodo
3. CIl numero di figli di quel nodo
4. DIl numero di archi da quel nodo alla foglia più profonda

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

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

Gli alberi AVL e gli alberi rosso-neri garantiscono:

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

Un nodo di un albero binario di ricerca ha un sottoalbero destro. Dove si trova il suo successore in ordine?

1. ANel nodo più a sinistra del suo sottoalbero destro
2. BNel suo figlio destro, sempre
3. CNel suo genitore, sempre
4. DNel nodo più a destra del suo sottoalbero sinistro

In una coda circolare memorizzata in un array di capacità n, come si calcola la posizione successiva all'indice i?

1. Ai + 1
2. B2i + 1
3. C(i + 1) mod n
4. D(i − 1) mod n

La complessità temporale di decrease-key in un heap binario (nota la posizione dell'elemento) è:

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

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

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