Scheda di esercizi di Strutture dati con soluzioni

In un albero, che cos'è una foglia?

1. AUn nodo con esattamente un figlio
2. BUn nodo senza figli
3. CUn nodo senza genitore
4. DIl nodo con il valore più grande

Che cos'è la radice di un albero?

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

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 riga di V valori booleani
3. CUna lista dei suoi vertici adiacenti
4. DIl numero totale di archi del grafo

Quale struttura dati si usa per verificare se le parentesi in "{[()]}" sono bilanciate?

1. AUna pila
2. BUn albero binario di ricerca
3. CUna coda
4. DUna tabella hash

Quale metodo di risoluzione delle collisioni memorizza le chiavi in collisione in una lista nello stesso bucket?

1. ADoppio hashing (double hashing)
2. BScansione lineare (linear probing)
3. CConcatenamento separato (separate chaining)
4. DScansione quadratica (quadratic probing)

In un min-heap binario memorizzato in un array (indici a partire da 0), i figli del nodo all'indice i si trovano a:

1. A2i + 1 e 2i + 2
2. B2i e 2i + 1
3. Ci/2 e i/2 + 1
4. Di + 1 e i + 2

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

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

Per ogni elemento di un array vuoi il successivo elemento maggiore alla sua destra, in tempo totale O(n). Quale struttura aiuta?

1. AUna pila che conserva gli elementi in attesa della loro risposta
2. BUna coda che contiene ogni coppia di elementi
3. CUna tabella hash di tutti gli elementi
4. DUn albero binario di ricerca ricostruito per ogni elemento