Compito AA.A.1)Q

ESONERO PARZIALE 8/11/2001 SOLUZIONI COMPITO A

Legenda:

c risposte errate g risposte esatte

Compito A

A.A.1)

Θ(n) c

Θ (n

) g Θ (n

) c Θ (n

log (a+b)) c

altro c

A.A.2)

<7, 4, 5, 1, 6, 3>; <8> c

<7, 6, 5, 1, 4, 3>; <8> g

<6, 4, 5, 1, 3>; <7, 8> g

<6, 5, 3, 1, 4>; <7, 8> c A.A.3)

<1, 3, 4, 7, 6, 5, 8> g

<1, 3, 4, 6, 7, 5, 8> g

<1, 3, 4, 6, 7, 8, 5> c

<1, 3, 4, 5, 6, 8, 7> c A.A.4)

m non sia una potenza di 2 g

m non sia un numero primo c

m non sia uguale a 2

-1, con p numero primo c g m può assumere qualsiasi valore c

A.A.5)

O(n) c

O(logn) c

O(1) g

dipende dalle informazioni memorizzate nella lista c

A.B.1)

Considerando che, dato un nodo i intermedio dell’albero, altezza(i) = 1+max(altezza(i->left), altezza(i->right)) si può scrivere la seguente funzione ricorsiva:

int altezza(struct nodo *i) {

// se i è una foglia

if ((i->left==NULL) && (i->right==NULL)) return 0;

else {

// se esiste solo il figlio destro if (i->left==NULL)

return 1+altezza(i->right);

// se esiste solo il figlio sinistro if (i->right==NULL)

return 1+altezza(i->left);

// se esistono entrambi i figli

if (altezza(i->left)>altezza(i->right)) return 1+altezza(i->left);

else

return 1+altezza(i->right);

} }

A.B.2)

Si supponga definito globale l’array q di puntatori a

che implementa la coda di priorità, e le variabili intere head e tail.

struct elem * extract_max() {

struct elem *max;

if (tail<head) exit();

max = q[head];

q[head]=q[tail];

tail--;

max_heapify(head);

}