Scheda di esercizi di Strutture dati con soluzioni

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

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

Nella rappresentazione di un grafo con liste di adiacenza, che cosa si memorizza per ogni vertice?

1. AUna riga di V valori booleani
2. BIl cammino minimo verso ogni altro vertice
3. CIl numero totale di archi del grafo
4. DUna lista dei suoi vertici adiacenti

Che cos'è il fattore di carico di una tabella hash?

1. AIl numero di collisioni avvenute finora
2. BIl tempo necessario per caricare la tabella dal disco
3. CIl numero di elementi memorizzati diviso per il numero di bucket
4. DIl numero di bucket diviso per la lunghezza media delle chiavi memorizzate

Quanto dura la ricerca di una parola di lunghezza L in un trie con alfabeto fisso?

1. AO(n), dove n è il numero di parole
2. BO(log n), dove n è il numero di parole
3. CO(L), indipendentemente da quante parole sono memorizzate
4. DO(L × n)

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 4 5 3
2. B4 2 5 1 3
3. C1 2 3 4 5
4. D4 5 2 3 1

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

1. A2i + 1
2. Bi + 1
3. C(i + 1) mod n
4. D(i − 1) mod n

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

Qual è il tempo di esecuzione della visita in ampiezza (BFS) su un grafo con V vertici memorizzato come matrice di adiacenza?

1. AO(V + E)
2. BO(V²)
3. CO(E log V)
4. DO(V)