Scheda di esercizi di Strutture dati con soluzioni

Quale struttura si usa tipicamente per implementare una coda con priorità?

1. AUno stack
2. BUna lista concatenata semplice non ordinata
3. CUna stringa
4. DUn heap

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

1. AAccedere all'elemento di indice i
2. BInserire in testa
3. CLeggere il primo elemento
4. DRimuovere l'elemento in testa

In un albero binario di ricerca, i valori nel sottoalbero sinistro di un nodo sono:

1. AUguali al valore del nodo
2. BMaggiori del valore del nodo
3. CIn ordine casuale
4. DMinori del valore del nodo

Una rete stradale ha 100,000 incroci, ciascuno collegato a circa altri 4. Quale rappresentazione è la più adatta?

1. AMatrice di adiacenza
2. BUn unico array ordinato di vertici
3. CUn heap binario di archi
4. DLista di adiacenza

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. A1 2 4 5 3
2. B5 4 3 2 1
3. C4 5 2 3 1
4. D4 2 5 1 3

Quanto tempo serve per verificare se l'arco (u, v) esiste usando una matrice di adiacenza?

1. AO(1)
2. BO(log V)
3. CO(E)
4. DO(V)

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

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

Quale proprietà mantiene ogni B-albero perfettamente bilanciato?

1. ATutte le foglie sono alla stessa profondità
2. BOgni nodo ha esattamente due figli
3. CLe chiavi sono memorizzate solo nella radice
4. DOgni nodo memorizza una sola chiave