Scheda di esercizi di Strutture dati con soluzioni

Nella rappresentazione di un grafo con liste di adiacenza, che cosa si memorizza per ogni vertice?

1. AUna lista dei suoi vertici adiacenti
2. BUna riga di V valori booleani
3. CIl numero totale di archi del grafo
4. DIl cammino minimo verso ogni altro vertice

Che cosa memorizza una mappa (dizionario)?

1. ASolo valori in ordine di inserimento
2. BCoppie di chiavi uguali
3. CValori ordinati per grandezza
4. DCoppie chiave–valore con chiavi univoche

In un albero, che cos'è una foglia?

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

Una visita in ordine (in-order) di un albero binario di ricerca visita le chiavi in:

1. AOrdine crescente
2. BOrdine sempre decrescente
3. COrdine di inserimento
4. DOrdine per livelli

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

1. ALista di adiacenza
2. BMatrice di adiacenza
3. CUn unico array ordinato di vertici
4. DUn heap binario di archi

In un heap binario memorizzato in un array a partire dall'indice 0, dove si trova il genitore del nodo all'indice i?

1. AAll'indice ⌊(i − 1) / 2⌋
2. BAll'indice ⌊i / 2⌋ + 1
3. CAll'indice 2i + 1
4. DAll'indice i − 1

Perché una tabella hash funzioni correttamente, quale regola devono rispettare hash e uguaglianza?

1. AChiavi uguali devono avere valori hash uguali
2. BValori hash uguali implicano chiavi uguali
3. CI valori hash devono essere numeri primi
4. DChiavi diverse devono avere valori hash diversi

Quale affermazione sull'heapsort è corretta?

1. AÈ stabile e richiede O(n) memoria aggiuntiva
2. BRichiede un albero binario di ricerca come memoria aggiuntiva, quindi usa O(n) memoria extra
3. CRichiede tempo O(n) su qualsiasi input
4. DOrdina sul posto in tempo O(n log n) nel caso peggiore ma non è stabile