Scheda di esercizi di Strutture dati con soluzioni

Che cos'è un grafo orientato?

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

In quale ordine una visita in preordine (preorder) di un albero binario visita i nodi?

1. ASottoalbero sinistro, poi sottoalbero destro, poi nodo
2. BNodo, poi sottoalbero sinistro, poi sottoalbero destro
3. CSottoalbero sinistro, poi nodo, poi sottoalbero destro
4. DLivello per livello a partire dall'alto

Come si chiama l'operazione di una pila (stack) che aggiunge un elemento in cima?

1. AEnqueue
2. BPop
3. CPush
4. DPeek

Un nodo di un albero binario di ricerca ha un sottoalbero destro. Dove si trova il suo successore in ordine?

1. ANel nodo più a destra del suo sottoalbero sinistro
2. BNel suo genitore, sempre
3. CNel suo figlio destro, sempre
4. DNel nodo più a sinistra del suo sottoalbero destro

Quale struttura dati usa un programma in esecuzione per tenere traccia delle chiamate di funzione attive e delle loro variabili locali?

1. AUna tabella hash di funzioni
2. BLa coda della memoria heap
3. CUn albero binario di ricerca di frame
4. DLo stack delle chiamate

Perché un heap binario si può memorizzare in un array senza puntatori?

1. AGli heap non contengono mai più di 100 elementi
2. BÈ un albero binario completo, quindi le posizioni seguono semplici formule sugli indici
3. CGli array mantengono automaticamente le chiavi in ordine, quindi non servono puntatori
4. DTutte le chiavi di un heap sono uguali

Un oggetto è memorizzato come chiave in una hash map, e poi viene modificato un campo usato dalla sua funzione hash. Qual è il risultato probabile?

1. ALa mappa solleva un errore nel momento in cui il campo cambia
2. BNon cambia nulla, perché l'hash di una chiave si calcola una sola volta all'avvio del programma
3. CLa ricerca dell'oggetto può fallire perché si trova nel bucket corrispondente al vecchio hash
4. DLa mappa sposta automaticamente la chiave nel nuovo bucket

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

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