Scheda di esercizi di Strutture dati con soluzioni

In un albero, che cos'è una foglia?

1. AUn nodo senza figli
2. BUn nodo senza genitore
3. CIl nodo con il valore più grande
4. DUn nodo con esattamente un figlio

Come sono memorizzati in memoria gli elementi di un array?

1. ASparsi, collegati da puntatori
2. BIn posizioni casuali scelte da un hash
3. CIn un albero di pagine di memoria
4. DIn un unico blocco contiguo, uno dopo l'altro

Quanti archi ha un albero con n nodi?

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

Quanto tempo serve per verificare se l'arco (u, v) esiste usando una matrice di adiacenza?

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

Che cosa succede quando una tabella hash esegue il rehashing dopo che il fattore di carico ha superato una soglia?

1. ALe chiavi più vecchie vengono eliminate per fare spazio
2. BLe chiavi esistenti vengono ordinate sul posto
3. CSolo le chiavi in collisione vengono spostate in una nuova lista di overflow in fondo alla tabella
4. DSi alloca una tabella più grande e ogni chiave viene reinserita

Quale struttura dati usa la visita in profondità (DFS) nella versione iterativa?

1. AUn heap
2. BUno stack
3. CUna coda
4. DSolo una tabella hash

Un oggetto è memorizzato come chiave in una hash map, e poi viene modificato un campo usato dalla sua funzione hash. Qual è il risultato probabile?

1. ALa mappa sposta automaticamente la chiave nel nuovo bucket
2. BLa mappa solleva un errore nel momento in cui il campo cambia
3. CLa ricerca dell'oggetto può fallire perché si trova nel bucket corrispondente al vecchio hash
4. DNon cambia nulla, perché l'hash di una chiave si calcola una sola volta all'avvio del programma

L'algoritmo di Kahn per l'ordinamento topologico rimuove ripetutamente i vertici con grado entrante 0. Quale struttura contiene questi vertici?

1. AUna coda (o una collezione qualsiasi) dei vertici con grado entrante 0
2. BUna matrice di adiacenza che registra quali vertici sono già stati rimossi
3. CUna pila di tutti gli archi visitati
4. DUn max-heap ordinato per grado uscente