Scheda di esercizi di Strutture dati con soluzioni

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

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

Un grafo è composto da:

1. ARighe e colonne
2. BSolo una radice e delle foglie
3. CVertici (nodi) collegati da archi
4. DSolo chiavi e hash

Che cos'è il fattore di carico di una tabella hash?

1. AIl tempo necessario per caricare la tabella dal disco
2. BIl numero di elementi memorizzati diviso per il numero di bucket
3. CIl numero di bucket diviso per la lunghezza media delle chiavi memorizzate
4. DIl numero di collisioni avvenute finora

In una tabella hash con indirizzamento aperto, qual è il massimo fattore di carico possibile?

1. A0,5
2. B1
3. CNon c'è un massimo
4. D2

Quanto tempo serve per verificare se l'arco (u, v) esiste usando una matrice di adiacenza?

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

Quanto dura la ricerca di una parola di lunghezza L in un trie con alfabeto fisso?

1. AO(n), dove n è il numero di parole
2. BO(log n), dove n è il numero di parole
3. CO(L), indipendentemente da quante parole sono memorizzate
4. DO(L × n)

Un array dinamico raddoppia quando è pieno. Perché molte implementazioni lo riducono solo quando è pieno per un quarto, e non per metà?

1. APer mantenere l'array ordinato
2. BPerché dimezzare a metà farebbe perdere elementi
3. CPer evitare ridimensionamenti ripetuti quando push e pop si alternano vicino alla soglia
4. DPerché l'allocatore di memoria può liberare memoria solo a quarti di blocco

La complessità temporale di decrease-key in un heap binario (nota la posizione dell'elemento) è:

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