Scheda di esercizi di Strutture dati con soluzioni

Quale struttura si usa tipicamente per implementare una coda con priorità?

1. AUn heap
2. BUno stack
3. CUna stringa
4. DUna lista concatenata semplice non ordinata

Una tabella hash memorizza i dati come:

1. ACoppie chiave–valore individuate da una funzione hash
2. BSolo una lista ordinata
3. CUn albero con chiavi ordinate
4. DUna stringa di lunghezza fissa

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

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

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

1. AUn heap binario di archi
2. BUn unico array ordinato di vertici
3. CMatrice di adiacenza
4. DLista di adiacenza

In un heap binario memorizzato in un array a partire dall'indice 0, dove si trova il genitore del nodo all'indice i?

1. AAll'indice ⌊i / 2⌋ + 1
2. BAll'indice ⌊(i − 1) / 2⌋
3. CAll'indice i − 1
4. DAll'indice 2i + 1

Un buffer circolare (ring buffer) è comunemente usato per implementare:

1. AUn albero binario di ricerca
2. BUna coda di dimensione fissa
3. CUna visita di un grafo
4. DUna funzione hash

L'eliminazione di un nodo con due figli da un albero binario di ricerca avviene di solito:

1. ARimuovendo l'intero sottoalbero
2. BScambiandolo con la radice
3. CRicostruendo da zero il sottoalbero sottostante e reinserendo tutte le chiavi che conteneva
4. DSostituendolo con il suo successore in ordine (o predecessore) ed eliminando quel nodo

Un array dinamico raddoppia quando è pieno. Perché molte implementazioni lo riducono solo quando è pieno per un quarto, e non per metà?

1. APerché dimezzare a metà farebbe perdere elementi
2. BPer mantenere l'array ordinato
3. CPer evitare ridimensionamenti ripetuti quando push e pop si alternano vicino alla soglia
4. DPerché l'allocatore di memoria può liberare memoria solo a quarti di blocco