Scheda di esercizi di Strutture dati con soluzioni

Che cos'è la radice di un albero?

1. AIl nodo con il valore più grande
2. BUn qualsiasi nodo intermedio
3. CIl nodo più in alto, privo di genitore
4. DUn nodo senza figli

Quale struttura dati è più adatta per la funzione «annulla» (undo) di un editor di testo?

1. AInsieme hash (hash set)
2. BPila (stack)
3. CCoda (queue)
4. DGrafo

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

1. AIl cammino minimo verso ogni altro vertice
2. BUna lista dei suoi vertici adiacenti
3. CIl numero totale di archi del grafo
4. DUna riga di V valori booleani

Quale tipo di dato astratto usa l'algoritmo di Dijkstra per scegliere il prossimo vertice da elaborare?

1. AUna coda FIFO
2. BUna pila
3. CUn insieme senza ordinamento
4. DUna coda con priorità di minimo

Qual è la complessità temporale della ricerca di una chiave in un albero binario di ricerca bilanciato?

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

Un trie (albero dei prefissi) è particolarmente efficiente per:

1. ARicerche per prefisso, come il completamento automatico
2. BTrovare cammini minimi
3. COrdinare numeri
4. DMemorizzare matrici

La complessità temporale di decrease-key in un heap binario (nota la posizione dell'elemento) è:

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

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. BRendere la dimensione del buffer una potenza di due
3. CMemorizzare front e rear nella stessa variabile
4. DSvuotare sempre il buffer ogni volta che front è uguale a rear, così lo stato è vuoto