Scheda di esercizi di Strutture dati con soluzioni

Che cosa fa l'operazione peek (o top) su una pila?

1. ARestituisce l'elemento in cima senza rimuoverlo
2. BRimuove l'elemento in cima e lo restituisce
3. CRimuove tutti gli elementi dalla pila
4. DRestituisce l'elemento in fondo alla pila

Nella rappresentazione di un grafo con liste di adiacenza, che cosa si memorizza per ogni vertice?

1. AUna lista dei suoi vertici adiacenti
2. BIl numero totale di archi del grafo
3. CUna riga di V valori booleani
4. DIl cammino minimo verso ogni altro vertice

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. CMinori del valore del nodo
4. DIn ordine casuale

Gli alberi AVL e gli alberi rosso-neri garantiscono:

1. AUn'altezza O(log n) tramite il ribilanciamento
2. BChe le chiavi siano memorizzate in ordine di inserimento
3. CChe nessun nodo abbia due figli
4. DUna ricerca in tempo costante in ogni caso

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

Un buffer circolare (ring buffer) è comunemente usato per implementare:

1. AUna coda di dimensione fissa
2. BUn albero binario di ricerca
3. CUna visita di un grafo
4. DUna funzione hash

In un buffer circolare, front == rear può significare sia vuoto sia pieno. Qual è un modo comune per distinguere i due casi?

1. AMantenere un contatore separato degli elementi, oppure lasciare sempre una posizione inutilizzata
2. BMemorizzare front e rear nella stessa variabile
3. CRendere la dimensione del buffer una potenza di due
4. DSvuotare sempre il buffer ogni volta che front è uguale a rear, così lo stato è vuoto

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