Scheda di esercizi di Strutture dati con soluzioni

In una lista concatenata semplice, che cosa contiene il puntatore al successivo dell'ultimo nodo?

1. ANull (nessun nodo)
2. BIl numero di nodi della lista
3. CL'indirizzo del nodo precedente
4. DL'indirizzo del primo nodo

Quale operazione è lenta in un array ma veloce in testa a una lista concatenata?

1. AOttenere la lunghezza di un array di dimensione fissa
2. BInserire all'inizio
3. CLeggere l'ultimo elemento tramite indice
4. DAccedere al 5° elemento

Che cos'è la radice di un albero?

1. AUn nodo senza figli
2. BIl nodo con il valore più grande
3. CIl nodo più in alto, privo di genitore
4. DUn qualsiasi nodo intermedio

Qual è il costo di inserire un elemento al centro di un array di n elementi?

1. AO(n²), perché ogni elemento si sposta n volte
2. BO(n), perché gli elementi successivi devono essere spostati
3. CO(1), perché l'indice è noto
4. DO(log n), per via della ricerca binaria

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

1. AUn albero binario di ricerca di frame
2. BUna tabella hash di funzioni
3. CLa coda della memoria heap
4. DLo stack delle chiamate

Quanta memoria usa una lista di adiacenza per un grafo con V vertici ed E archi?

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

Perché una tabella hash funzioni correttamente, quale regola devono rispettare hash e uguaglianza?

1. AChiavi diverse devono avere valori hash diversi
2. BValori hash uguali implicano chiavi uguali
3. CChiavi uguali devono avere valori hash uguali
4. DI valori hash devono essere numeri primi

Perché un server potrebbe scegliere a caso la propria funzione hash da una famiglia universale?

1. APer rendere ordinata la tabella hash
2. BPer rendere molto improbabile che un attaccante scelga molte chiavi che collidono tutte
3. CPer eliminare la necessità di ridimensionare la tabella
4. DPer garantire che due chiavi non collidano mai, qualunque chiave invii un attaccante