Scheda di esercizi di Strutture dati con soluzioni

Quale operazione è lenta in un array ma veloce in testa a una lista concatenata?

1. ALeggere l'ultimo elemento tramite indice
2. BOttenere la lunghezza di un array di dimensione fissa
3. CAccedere al 5° elemento
4. DInserire all'inizio

In quale ordine una visita in postordine (postorder) di un albero binario visita i nodi?

1. ASottoalbero sinistro, poi nodo, poi sottoalbero destro
2. BSottoalbero destro, poi nodo, poi sottoalbero sinistro
3. CNodo, poi sottoalbero sinistro, poi sottoalbero destro
4. DSottoalbero sinistro, poi sottoalbero destro, poi nodo

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

1. AIl cammino minimo verso ogni altro vertice
2. BIl numero totale di archi del grafo
3. CUna lista dei suoi vertici adiacenti
4. DUna riga di V valori booleani

Come si inserisce un nuovo elemento in un heap binario?

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

Una tabella hash di dimensione 7 usa h(k) = k mod 7 e la scansione lineare. Dopo aver inserito 10, dove viene memorizzato 17?

1. AAll'indice 6
2. BAll'indice 0
3. CAll'indice 3
4. DAll'indice 4

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 − 1) / 2⌋
2. BAll'indice 2i + 1
3. CAll'indice ⌊i / 2⌋ + 1
4. DAll'indice i − 1

Quale struttura permette di calcolare il massimo di ogni finestra di dimensione k di un array in tempo totale O(n)?

1. AUna lista concatenata semplice degli elementi della finestra
2. BUn min-heap ricostruito per ogni finestra
3. CUn array ordinato aggiornato con spostamenti
4. DUna deque che contiene indici in ordine decrescente di valore

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 min-heap che contiene tutti gli n valori, da cui alla fine si estraggono i k più piccoli
2. BUn array ordinato di tutti gli n valori
3. CUn max-heap di dimensione k, di cui si sostituisce la radice quando arriva un valore più piccolo
4. DUna coda FIFO degli ultimi k valori