Scheda di esercizi di Strutture dati con soluzioni

Nella rappresentazione di un grafo con liste di adiacenza, che cosa si memorizza per ogni vertice?

1. AUna riga di V valori booleani
2. BUna lista dei suoi vertici adiacenti
3. CIl cammino minimo verso ogni altro vertice
4. DIl numero totale di archi del grafo

Quale struttura dati funziona secondo il principio «ultimo a entrare, primo a uscire» (LIFO)?

1. ACoda (queue)
2. BLista concatenata
3. CPila (stack)
4. DTabella hash

In un albero binario di ricerca, i valori nel sottoalbero sinistro di un nodo sono:

1. AIn ordine casuale
2. BMinori del valore del nodo
3. CUguali al valore del nodo
4. DMaggiori del valore del nodo

Come si trova la chiave minima in un albero binario di ricerca?

1. ASi guarda solo la radice
2. BSi seguono i figli sinistri dalla radice finché non c'è più un figlio sinistro
3. CSi seguono i figli destri dalla radice finché non c'è più un figlio destro
4. DSi visitano tutte le foglie e le si confronta

Un trie (albero dei prefissi) è particolarmente efficiente per:

1. AOrdinare numeri
2. BTrovare cammini minimi
3. CMemorizzare matrici
4. DRicerche per prefisso, come il completamento automatico

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

Le chiavi 5, 3, 8, 1 vengono inserite in quest'ordine in un min-heap binario vuoto basato su array. Qual è l'array finale?

1. A[1, 3, 8, 5]
2. B[1, 3, 5, 8]
3. C[3, 1, 8, 5]
4. D[1, 5, 8, 3]

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

1. AI valori hash devono essere numeri primi
2. BChiavi uguali devono avere valori hash uguali
3. CChiavi diverse devono avere valori hash diversi
4. DValori hash uguali implicano chiavi uguali