Scheda di esercizi di Strutture dati con soluzioni

Qual è la differenza principale tra un array statico e un array dinamico?

1. AUn array dinamico memorizza gli elementi in nodi collegati così può crescere un elemento alla volta
2. BUn array statico permette un accesso per indice più lento
3. CUn array dinamico può crescere spostandosi in un blocco di memoria più grande
4. DUn array statico può memorizzare solo numeri

Come si chiama l'operazione di una coda (queue) che rimuove l'elemento in testa?

1. AInsert
2. BDequeue
3. CEnqueue
4. DPush

Che cos'è la proprietà di max-heap?

1. ALe chiavi sono ordinate da sinistra a destra
2. BTutte le foglie contengono la chiave massima
3. CLa chiave di ogni figlio sinistro è maggiore o uguale a quella del fratello destro
4. DLa chiave di ogni genitore è maggiore o uguale alle chiavi dei suoi figli

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

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

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

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

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

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

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

Inserendo una chiave in un albero AVL il sottoalbero sinistro di un nodo diventa troppo alto, e la nuova chiave è finita nel sottoalbero sinistro del suo figlio sinistro (caso sinistra-sinistra). Quale correzione si applica?

1. AUna singola rotazione a destra sul nodo sbilanciato
2. BLa ricolorazione del nodo e del figlio
3. CUna rotazione a sinistra sul figlio, poi una rotazione a destra sul nodo
4. DUna singola rotazione a sinistra sul nodo sbilanciato