ESONERO PARZIALE 8/11/2001 SOLUZIONI COMPITO B

ESONERO PARZIALE 8/11/2001 SOLUZIONI COMPITO B

Legenda:

c risposte errate g risposte esatte

B.A.1)

Θ(n) c Θ (n²) g Θ (nlogn) c Θ (n²logn) c

altro c

B.A.2)

E[nh(k)] = α c

E[nh(k)] = α solo se vale l’ipotesi di Hashing Semplice Uniforme g

E[nh(k)] = O(m) c

E[nh(k)] = O(m) solo se n = O(m) c

E[nh(k)] = O(m) solo se n = O(m) e vale l’ipotesi di Hashing Semplice Uniforme c B.A.3)

<6, 5, 3, 1, 4, 2>; <9> g

<6, 5, 3, 1, 2, 4>; <9> c

<5, 4, 3, 2, 1>; <6, 9> c

<5, 4, 3, 1, 2>; <6, 9> g B.A.4)

<2, 5, 8, 11, 4, 3, 6> c

<2, 5, 8, 11, 3, 4, 6> g

<2, 3, 5, 6, 11, 4, 8> c

<2, 3, 5, 8, 11, 4, 6> g B.A.5)

vengono esaminate le foglie inutilmente g

l’algoritmo non è corretto g

aumenta la complessità dell’algoritmo g c

niente c

B.B.1)

Sia MAX_INFO il massimo valore che intendiamo memorizzare nell’albero, e sia definito e inizializzato con elementi tutti nulli un array int B[MAX_INFO] in cui memorizziamo il numero di occorrenze per ogni possibile valore. Sia definito un array int A[] e le variabili intere head e tail che implementano la coda per la visita in ampiezza dell’albero.

int max_occur() {

int max=-1;

while (head<tail) {

// incrementa il contatore delle occorrenze dell’info dle nodo che si sta visitando B[A[head]->info]++;

// se esiste un figlio sinistro if (A[head]->left !=NULL)

// inserisci il figlio sinistro nella coda A[tail++]=A[head]->left;

// se esiste un figlio destro if (A[head]->right !=NULL)

// inserisci il figlio destro nella coda A[tail++]=A[head]->right;

// elimina il nodo visitato dalla coda head++;

}

// trova il massimo numero di occorrenze for(int i=0; i<MAX_INFO; i++)

if (B[i]>max) max=B[i];

return max;

}

B.B.2)

Sia definito il seguente tipo di dato:

struct elem {

char* descrizione;

int key;

struct elem *next;

}

e sia definita la funzione hash int h(struct elem *); Sia definito un array struct elem * A[n] che implementa il dizionario.

// inserimento

void insert(struct elem *i) {

struct elem *p = A[h(i->key)];

i->next=p;

A[h(i->key)]=i;

}

// ricerca

struct elem* search(int k) {

struct elem *p = A[h(key)];

while ((p!=NULL) && (p->key)) p=p->next;

if (p->key==k) return p;

else

return NULL;

}