Scheda di esercizi di Strutture dati con soluzioni

In un albero binario di ricerca, i valori nel sottoalbero sinistro di un nodo sono:

1. AUguali al valore del nodo
2. BMinori del valore del nodo
3. CMaggiori del valore del nodo
4. DIn ordine casuale

In una lista concatenata semplice, ogni nodo contiene:

1. ADati e riferimenti a tutti gli altri nodi
2. BDati e un indice
3. CDati e un riferimento al nodo successivo
4. DSolo dati

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

1. ALivello per livello a partire dall'alto
2. BSottoalbero sinistro, poi nodo, poi sottoalbero destro
3. CNodo, poi sottoalbero sinistro, poi sottoalbero destro
4. DSottoalbero sinistro, poi sottoalbero destro, poi nodo

Hai un riferimento a un nodo a metà di una lista. In quale lista puoi rimuoverlo in O(1)?

1. AUn array ordinato
2. BUn array dinamico
3. CUna lista doppiamente concatenata
4. DUna lista concatenata semplice

Una rete stradale ha 100,000 incroci, ciascuno collegato a circa altri 4. Quale rappresentazione è la più adatta?

1. ALista di adiacenza
2. BUn heap binario di archi
3. CMatrice di adiacenza
4. DUn unico array ordinato di vertici

Quanto dura la ricerca di una parola di lunghezza L in un trie con alfabeto fisso?

1. AO(L), indipendentemente da quante parole sono memorizzate
2. BO(log n), dove n è il numero di parole
3. CO(n), dove n è il numero di parole
4. DO(L × n)

In che modo un radix tree (trie compresso) migliora un trie semplice?

1. AOrdina i figli di ogni nodo per frequenza
2. BConserva solo la prima lettera di ogni parola
3. CFonde le catene di nodi con un solo figlio in un unico arco etichettato con una stringa
4. DMemorizza ogni parola in una tabella hash alla radice invece che in nodi separati

Quale proprietà mantiene ogni B-albero perfettamente bilanciato?

1. ATutte le foglie sono alla stessa profondità
2. BOgni nodo memorizza una sola chiave
3. CLe chiavi sono memorizzate solo nella radice
4. DOgni nodo ha esattamente due figli