Scheda di esercizi di Strutture dati con soluzioni

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

1. APop
2. BPush
3. CEnqueue
4. DPeek

In un albero, che cosa sono i nodi fratelli?

1. ANodi che hanno lo stesso genitore
2. BNodi alla stessa profondità in sottoalberi diversi
3. CUn nodo e il suo genitore
4. DNodi privi di figli

Quale operazione è O(1) per un array ma O(n) per una lista concatenata semplice?

1. ALeggere il primo elemento
2. BInserire in testa
3. CAccedere all'elemento di indice i
4. DRimuovere l'elemento in testa

Una tabella hash di dimensione 7 usa h(k) = k mod 7 e la scansione lineare. Dopo aver inserito 10, dove viene memorizzato 17?

1. AAll'indice 4
2. BAll'indice 6
3. CAll'indice 0
4. DAll'indice 3

Qual è il costo di inserire un elemento al centro di un array di n elementi?

1. AO(log n), per via della ricerca binaria
2. BO(n²), perché ogni elemento si sposta n volte
3. CO(n), perché gli elementi successivi devono essere spostati
4. DO(1), perché l'indice è noto

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

1. AUn array dinamico
2. BUna lista concatenata semplice
3. CUn array ordinato
4. DUna lista doppiamente concatenata

Devi conservare i k valori più piccoli di un flusso di n numeri usando O(k) memoria. Quale approccio funziona in tempo O(n log k)?

1. AUn max-heap di dimensione k, di cui si sostituisce la radice quando arriva un valore più piccolo
2. BUn min-heap che contiene tutti gli n valori, da cui alla fine si estraggono i k più piccoli
3. CUn array ordinato di tutti gli n valori
4. DUna coda FIFO degli ultimi k valori

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

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