Scheda di esercizi di Strutture dati con soluzioni

Che cosa memorizza una mappa (dizionario)?

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

In un grafo non orientato, che cos'è il grado di un vertice?

1. ALa sua posizione nella lista di adiacenza
2. BIl numero di archi a esso collegati
3. CLa lunghezza del cammino più lungo che parte da esso
4. DIl numero di vertici del grafo

Che cos'è un grafo orientato?

1. AUn grafo i cui archi hanno una direzione da un vertice a un altro
2. BUn grafo i cui archi hanno tutti un peso
3. CUn grafo privo di cicli
4. DUn grafo in cui ogni coppia di vertici distinti è collegata da un arco

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

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. B4 2 5 1 3
3. C4 5 2 3 1
4. D1 2 4 5 3

Quale metodo di risoluzione delle collisioni memorizza le chiavi in collisione in una lista nello stesso bucket?

1. AConcatenamento separato (separate chaining)
2. BScansione quadratica (quadratic probing)
3. CDoppio hashing (double hashing)
4. DScansione lineare (linear probing)

Un segment tree (albero dei segmenti) è tipicamente usato per:

1. AMemorizzare gli archi di un grafo
2. BRispondere a interrogazioni su intervalli (come somme su intervalli) e aggiornamenti in O(log n)
3. CImplementare uno stack
4. DOrdinare stringhe alfabeticamente memorizzando ogni prefisso in un nodo separato dell'albero

Perché i B-alberi (B-tree) sono usati nei database e nei file system?

1. AIl loro elevato fattore di ramificazione mantiene l'albero poco profondo, riducendo le lente letture da disco
2. BUsano meno memoria di qualsiasi array, quindi l'intero indice sta sempre nella memoria centrale
3. CMemorizzano i dati in modo non ordinato
4. DNon richiedono ribilanciamento