ESONERO PARZIALE 8/11/2001 SOLUZIONI COMPITO C

ESONERO PARZIALE 8/11/2001 SOLUZIONI COMPITO C

Legenda:

c risposte errate g risposte esatte

C.A.1)

Θ(n) c

Θ (n²) g

Θ (nlogn) c

Θ (n²logn) c

altro c

C.A.2)

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

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

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

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

<1, 2, 6, 3, 8, 4, 9> g c

<1, 2, 3, 6, 4, 8, 9> c

<1, 2, 3, 4, 8, 6, 9> c

<1, 2, 6, 3, 8, 4, 9> g c

(la sequenza iniziale può essere considerata giusta).

C.A.4)

O(n) g

O(logn) c

O(nlogn) c

O(n²) c

altro c

C.A.5)

Θ(1+α) g

Θ(1+α) solo se l’elemento esiste c Θ(1+α) solo se l’elemento non esiste c

Θ (α) c

altro g c

(la complessità è Θ(1+α) se vale l’ipotesi di hashing semplice uniforme).

C.B.1) Sia definito globale l’array int A[n] da ordinare.

void insertion_sort_rec(int i) {

// un singolo elemento è banalmente ordinato if (i=0)

return;

// ordina l’array con i-1 elementi insertion_sort_rec(i-1);

int j=i-1;

while ((i>=0) && (A[i]<A[j])) {

swap(i, j);

i--;

j--;

} return;

}

C.B.2) Siano definiti gli m array c_1, …, c_m e sia data la funzione build_max_heap(struct elem **).

struct persona* the_best() {

struct persona *maxp;

int max=0;

// costruisci le code di priorità build_max_heap(c_1);

…

build_max_heap(c_m);

// cerca l’elemento massimo if (c_1[0]->voto > max) {

max = c_1[0]->voto;

maxp = c_1[0];

}

…

if (c_m[0]->voto > max) {

max = c_m[0]->voto;

maxp = c_m[0];

}

return maxp;

}