Scheda di esercizi di Strutture dati con soluzioni

L'altezza di un albero è comunemente definita come:

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

Che cosa fa l'operazione peek (o top) su una pila?

1. ARestituisce l'elemento in cima senza rimuoverlo
2. BRimuove l'elemento in cima e lo restituisce
3. CRimuove tutti gli elementi dalla pila
4. DRestituisce l'elemento in fondo alla pila

Quale struttura si usa tipicamente per implementare una coda con priorità?

1. AUna stringa
2. BUna lista concatenata semplice non ordinata
3. CUno stack
4. DUn heap

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

1. A14
2. B24
3. C10
4. D11

In una tabella hash con indirizzamento aperto, qual è il massimo fattore di carico possibile?

1. A1
2. B0,5
3. C2
4. DNon c'è un massimo

Un trie (albero dei prefissi) è particolarmente efficiente per:

1. ATrovare cammini minimi
2. BRicerche per prefisso, come il completamento automatico
3. CMemorizzare matrici
4. DOrdinare numeri

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(n)
2. BO(1 + α), dove α = n / m
3. CO(m)
4. DO(log n)

Che cosa fa uno splay tree dopo ogni accesso?

1. ASposta il nodo acceduto in una foglia
2. BRicostruisce l'intero albero in forma bilanciata
3. CRicolora i nodi lungo il cammino di ricerca
4. DPorta con rotazioni il nodo acceduto fino alla radice