Scheda di esercizi di Strutture dati con soluzioni

In quale ordine una visita in postordine (postorder) di un albero binario visita i nodi?

1. ANodo, poi sottoalbero sinistro, poi sottoalbero destro
2. BSottoalbero sinistro, poi nodo, poi sottoalbero destro
3. CSottoalbero destro, poi nodo, poi sottoalbero sinistro
4. DSottoalbero sinistro, poi sottoalbero destro, poi nodo

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

1. ANella radice
2. BNell'ultima posizione dell'array
3. CNella foglia più a sinistra
4. DIn una foglia qualsiasi, da cercare

In un grafo non orientato, che cos'è il grado di un vertice?

1. AIl numero di vertici del grafo
2. BIl numero di archi a esso collegati
3. CLa lunghezza del cammino più lungo che parte da esso
4. DLa sua posizione nella lista di adiacenza

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(V)
4. DO(E)

Gli alberi AVL e gli alberi rosso-neri garantiscono:

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

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 preordine?

1. A1 2 4 5 3
2. B1 2 3 4 5
3. C4 2 5 1 3
4. D4 5 2 3 1

L'eliminazione di un nodo con due figli da un albero binario di ricerca avviene di solito:

1. ASostituendolo con il suo successore in ordine (o predecessore) ed eliminando quel nodo
2. BScambiandolo con la radice
3. CRicostruendo da zero il sottoalbero sottostante e reinserendo tutte le chiavi che conteneva
4. DRimuovendo l'intero sottoalbero

Quale proprietà deve soddisfare un albero rosso-nero?

1. AOgni cammino da un nodo alle sue foglie discendenti contiene lo stesso numero di nodi neri
2. BOgni nodo deve essere rosso
3. CLa radice deve essere rossa
4. DOgni nodo rosso deve avere figli rossi, quindi i nodi rossi formano sempre catene ininterrotte fino alle foglie