Scheda di esercizi di Strutture dati con soluzioni

Che cos'è la proprietà di max-heap?

1. ATutte le foglie contengono la chiave massima
2. BLa chiave di ogni genitore è maggiore o uguale alle chiavi dei suoi figli
3. CLa chiave di ogni figlio sinistro è maggiore o uguale a quella del fratello destro
4. DLe chiavi sono ordinate da sinistra a destra

Che cosa memorizza una mappa (dizionario)?

1. ASolo valori in ordine di inserimento
2. BValori ordinati per grandezza
3. CCoppie di chiavi uguali
4. DCoppie chiave–valore con chiavi univoche

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

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

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

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

Qual è l'altezza nel caso peggiore di un albero binario di ricerca con n nodi se le chiavi vengono inserite in ordine?

1. A√n
2. B1
3. Clog₂ n
4. Dn (diventa una lista concatenata)

Come si inserisce un nuovo elemento in un heap binario?

1. ALo si pone nella radice e lo si fa scendere
2. BLo si inserisce nella posizione ordinata spostando di un posto a destra tutti gli elementi più grandi
3. CSi ricostruisce da zero l'intero heap
4. DLo si pone alla fine dell'array e lo si fa risalire finché viola la proprietà di heap

La struttura union-find (insiemi disgiunti) con unione per rango e compressione dei cammini ha un costo ammortizzato per operazione di:

1. AEsattamente O(log n)
2. BO(n)
3. CO(n²)
4. DO(α(n)), l'inversa della funzione di Ackermann, praticamente costante

Quale affermazione sull'heapsort è corretta?

1. ARichiede un albero binario di ricerca come memoria aggiuntiva, quindi usa O(n) memoria extra
2. BRichiede tempo O(n) su qualsiasi input
3. COrdina sul posto in tempo O(n log n) nel caso peggiore ma non è stabile
4. DÈ stabile e richiede O(n) memoria aggiuntiva