Scheda di esercizi di Strutture dati con soluzioni

Dove si trova l'elemento più piccolo di un min-heap binario?

1. ANell'ultima posizione dell'array
2. BIn una foglia qualsiasi, da cercare
3. CNella radice
4. DNella foglia più a sinistra

In una lista concatenata semplice, che cosa contiene il puntatore al successivo dell'ultimo nodo?

1. AIl numero di nodi della lista
2. BNull (nessun nodo)
3. CL'indirizzo del primo nodo
4. DL'indirizzo del nodo precedente

Un grafo è composto da:

1. ASolo una radice e delle foglie
2. BVertici (nodi) collegati da archi
3. CRighe e colonne
4. DSolo chiavi e hash

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

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 sinistra del suo sottoalbero destro
2. BNel nodo più a destra del suo sottoalbero sinistro
3. CNel suo genitore, sempre
4. DNel suo figlio destro, sempre

Qual è il valore dell'espressione postfissa 3 4 + 2 * ?

1. A14
2. B11
3. C10
4. D24

Come si può rilevare se una lista concatenata semplice contiene un ciclo usando O(1) memoria aggiuntiva?

1. ASi memorizza ogni nodo visitato in un hash set
2. BSi muove un puntatore di un passo e un altro di due passi e si verifica se si incontrano
3. CSi ordina la lista e si cercano i duplicati
4. DSi contano i nodi finché il conteggio supera il campo lunghezza della lista

La struttura union-find (insiemi disgiunti) con unione per rango e compressione dei cammini ha un costo ammortizzato per operazione di:

1. AO(n²)
2. BO(α(n)), l'inversa della funzione di Ackermann, praticamente costante
3. CO(n)
4. DEsattamente O(log n)