Scheda di esercizi di Strutture dati con soluzioni

Che cosa memorizza una mappa (dizionario)?

1. ASolo valori in ordine di inserimento
2. BValori ordinati per grandezza
3. CCoppie di chiavi uguali
4. DCoppie chiave–valore con chiavi univoche

Che cosa definisce un albero binario?

1. AOgni nodo ha al massimo due figli
2. BOgni nodo ha esattamente due figli
3. CL'albero ha esattamente due livelli
4. DOgni nodo memorizza un numero binario

Che cosa fa una funzione hash in una tabella hash?

1. AOrdina le chiavi della tabella
2. BCifra i valori della tabella
3. CConta quante chiavi sono memorizzate
4. DAssocia una chiave a un indice della tabella

Un'applicazione ha bisogno di ricerche veloci, ma deve anche elencare le chiavi in ordine e rispondere a interrogazioni su intervalli. Quale struttura è la più adatta?

1. AUna lista concatenata non ordinata
2. BUna pila
3. CUn albero binario di ricerca bilanciato
4. DUna tabella hash

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

1. AUno stack
2. BUn heap
3. CSolo una tabella hash
4. DUna coda

Quale struttura dati si usa per verificare se le parentesi in "{[()]}" sono bilanciate?

1. AUna tabella hash
2. BUna coda
3. CUna pila
4. DUn albero binario di ricerca

L'algoritmo di Kahn per l'ordinamento topologico rimuove ripetutamente i vertici con grado entrante 0. Quale struttura contiene questi vertici?

1. AUna pila di tutti gli archi visitati
2. BUn max-heap ordinato per grado uscente
3. CUna matrice di adiacenza che registra quali vertici sono già stati rimossi
4. DUna coda (o una collezione qualsiasi) dei vertici con grado entrante 0

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

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