Scheda di esercizi di Strutture dati con soluzioni

Qual è la caratteristica distintiva di un insieme (set) come tipo di dato astratto?

1. AMemorizza coppie chiave–valore
2. BMemorizza elementi in ordine
3. CPermette l'accesso solo a un'estremità
4. DMemorizza elementi senza duplicati

In quale ordine una visita in preordine (preorder) di un albero binario visita i nodi?

1. ASottoalbero sinistro, poi nodo, poi sottoalbero destro
2. BSottoalbero sinistro, poi sottoalbero destro, poi nodo
3. CNodo, poi sottoalbero sinistro, poi sottoalbero destro
4. DLivello per livello a partire dall'alto

Che cosa memorizza una mappa (dizionario)?

1. ACoppie chiave–valore con chiavi univoche
2. BSolo valori in ordine di inserimento
3. CCoppie di chiavi uguali
4. DValori ordinati per grandezza

Una visita in ordine (in-order) di un albero binario di ricerca visita le chiavi in:

1. AOrdine di inserimento
2. BOrdine crescente
3. COrdine sempre decrescente
4. DOrdine per livelli

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

1. AUn heap
2. BUna coda
3. CSolo una tabella hash
4. DUno stack

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

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

Che cosa fa uno splay tree dopo ogni accesso?

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

Devi conservare i k valori più piccoli di un flusso di n numeri usando O(k) memoria. Quale approccio funziona in tempo O(n log k)?

1. AUn max-heap di dimensione k, di cui si sostituisce la radice quando arriva un valore più piccolo
2. BUna coda FIFO degli ultimi k valori
3. CUn array ordinato di tutti gli n valori
4. DUn min-heap che contiene tutti gli n valori, da cui alla fine si estraggono i k più piccoli