Scheda di esercizi di Strutture dati con soluzioni

In una lista concatenata semplice, ogni nodo contiene:

1. ADati e un riferimento al nodo successivo
2. BSolo dati
3. CDati e riferimenti a tutti gli altri nodi
4. DDati e un indice

Che cos'è la radice di un albero?

1. AUn nodo senza figli
2. BUn qualsiasi nodo intermedio
3. CIl nodo più in alto, privo di genitore
4. DIl nodo con il valore più grande

Che cosa contiene ogni nodo di una lista doppiamente concatenata?

1. ADati e due puntatori, uno al nodo successivo e uno al nodo ancora dopo
2. BDue copie dei dati e un solo puntatore
3. CDati, un puntatore al nodo successivo e un puntatore al nodo precedente
4. DDati e soltanto un puntatore al nodo successivo

Un albero binario ha radice 1 con figlio sinistro 2 e figlio destro 3; il nodo 2 ha figli 4 (sinistro) e 5 (destro). Qual è la visita in postordine?

1. A5 4 3 2 1
2. B1 2 4 5 3
3. C4 5 2 3 1
4. D4 2 5 1 3

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 3
2. BAll'indice 4
3. CAll'indice 6
4. DAll'indice 0

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

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

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. BUna deque che contiene indici in ordine decrescente di valore
3. CUn min-heap ricostruito per ogni finestra
4. DUn array ordinato aggiornato con spostamenti

Perché un server potrebbe scegliere a caso la propria funzione hash da una famiglia universale?

1. APer eliminare la necessità di ridimensionare la tabella
2. BPer garantire che due chiavi non collidano mai, qualunque chiave invii un attaccante
3. CPer rendere ordinata la tabella hash
4. DPer rendere molto improbabile che un attaccante scelga molte chiavi che collidono tutte