Scheda di esercizi di Strutture dati con soluzioni

Che cosa contiene ogni nodo di una lista doppiamente concatenata?

1. ADati, un puntatore al nodo successivo e un puntatore al nodo precedente
2. BDue copie dei dati e un solo puntatore
3. CDati e soltanto un puntatore al nodo successivo
4. DDati e due puntatori, uno al nodo successivo e uno al nodo ancora dopo

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

1. AL'indirizzo del primo nodo
2. BNull (nessun nodo)
3. CL'indirizzo del nodo precedente
4. DIl numero di nodi della lista

Che cosa fa una funzione hash in una tabella hash?

1. ACifra i valori della tabella
2. BAssocia una chiave a un indice della tabella
3. CConta quante chiavi sono memorizzate
4. DOrdina le chiavi della tabella

Una rete stradale ha 100,000 incroci, ciascuno collegato a circa altri 4. Quale rappresentazione è la più adatta?

1. AUn unico array ordinato di vertici
2. BLista di adiacenza
3. CUn heap binario di archi
4. DMatrice di adiacenza

Perché un heap binario si può memorizzare in un array senza puntatori?

1. AGli heap non contengono mai più di 100 elementi
2. BGli array mantengono automaticamente le chiavi in ordine, quindi non servono puntatori
3. CÈ un albero binario completo, quindi le posizioni seguono semplici formule sugli indici
4. DTutte le chiavi di un heap sono uguali

Quale tipo di dato astratto usa l'algoritmo di Dijkstra per scegliere il prossimo vertice da elaborare?

1. AUn insieme senza ordinamento
2. BUna coda FIFO
3. CUna coda con priorità di minimo
4. DUna pila

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

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

Quanto tempo serve per cercare una chiave arbitraria in un min-heap binario di n elementi?

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