Scheda di esercizi di Strutture dati con soluzioni

Quale struttura si usa tipicamente per implementare una coda con priorità?

1. AUn heap
2. BUno stack
3. CUna lista concatenata semplice non ordinata
4. DUna stringa

Quanti archi ha un albero con n nodi?

1. An − 1
2. Bn + 1
3. C2n
4. Dn

Che cos'è una deque (coda a doppia estremità)?

1. AUna coda che permette rimozioni solo in fondo
2. BDue code separate che condividono un array
3. CUna struttura che permette inserimenti e rimozioni a entrambe le estremità
4. DUna coda ordinata per priorità

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

1. A√n
2. Bn (diventa una lista concatenata)
3. Clog₂ n
4. D1

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

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

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 3 4 5
2. B4 2 5 1 3
3. C1 2 4 5 3
4. D4 5 2 3 1

Quanto tempo serve per cercare una chiave arbitraria in un min-heap binario di n elementi?

1. AO(n)
2. BO(log log n)
3. CO(log n)
4. DO(1)

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

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