Scheda di esercizi di Strutture dati con soluzioni

Che cos'è il fattore di carico di una tabella hash?

1. AIl numero di bucket diviso per la lunghezza media delle chiavi memorizzate
2. BIl numero di elementi memorizzati diviso per il numero di bucket
3. CIl tempo necessario per caricare la tabella dal disco
4. DIl numero di collisioni avvenute finora

Che cosa memorizza una mappa (dizionario)?

1. ACoppie di chiavi uguali
2. BSolo valori in ordine di inserimento
3. CCoppie chiave–valore con chiavi univoche
4. DValori ordinati per grandezza

Quale operazione è O(1) per un array ma O(n) per una lista concatenata semplice?

1. ALeggere il primo elemento
2. BInserire in testa
3. CRimuovere l'elemento in testa
4. DAccedere all'elemento di indice i

Quale struttura dati usa la visita in profondità (DFS) nella versione iterativa?

1. ASolo una tabella hash
2. BUno stack
3. CUna coda
4. DUn heap

Hai un riferimento a un nodo a metà di una lista. In quale lista puoi rimuoverlo in O(1)?

1. AUna lista concatenata semplice
2. BUna lista doppiamente concatenata
3. CUn array ordinato
4. DUn array dinamico

Una visita in ordine (in-order) di un albero binario di ricerca visita le chiavi in:

1. AOrdine crescente
2. BOrdine sempre decrescente
3. COrdine di inserimento
4. DOrdine per livelli

Qual è il vantaggio principale di una skip list rispetto a una lista concatenata ordinata?

1. AMemorizza le chiavi senza ordine
2. BRicerca attesa in O(log n) grazie a più livelli di puntatori in avanti
3. CNon usa memoria aggiuntiva
4. DRicerca garantita in O(1) perché ogni nodo memorizza un puntatore a tutti gli altri nodi

Un filtro di Bloom può rispondere alla domanda «questo elemento è nell'insieme?» con:

1. APossibili falsi positivi ma nessun falso negativo
2. BRisposte solo per numeri
3. CRisposte sempre esatte
4. DPossibili falsi negativi ma nessun falso positivo