Scheda di esercizi di Strutture dati con soluzioni

Che cosa contiene ogni nodo di una lista doppiamente concatenata?

1. ADati e soltanto un puntatore al nodo successivo
2. BDue copie dei dati e un solo puntatore
3. CDati, un puntatore al nodo successivo e un puntatore al nodo precedente
4. DDati e due puntatori, uno al nodo successivo e uno al nodo ancora dopo

Come si chiama l'operazione di una pila (stack) che aggiunge un elemento in cima?

1. AEnqueue
2. BPop
3. CPeek
4. DPush

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

1. ACoda (queue)
2. BInsieme hash (hash set)
3. CGrafo
4. DPila (stack)

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

1. A4 2 5 1 3
2. B1 2 4 5 3
3. C5 4 3 2 1
4. D4 5 2 3 1

Qual è l'altezza nel caso peggiore di un albero binario di ricerca con n nodi se le chiavi vengono inserite in ordine?

1. Alog₂ n
2. Bn (diventa una lista concatenata)
3. C1
4. D√n

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. CLo stack delle chiamate
4. DUn albero binario di ricerca di frame

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

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

Un segment tree (albero dei segmenti) è tipicamente usato per:

1. ARispondere a interrogazioni su intervalli (come somme su intervalli) e aggiornamenti in O(log n)
2. BImplementare uno stack
3. COrdinare stringhe alfabeticamente memorizzando ogni prefisso in un nodo separato dell'albero
4. DMemorizzare gli archi di un grafo