Laboratorio di Algoritmi e Strutture Dati ESONERO PARZIALE 8/11/2001 (Compito B)

Laboratorio di Algoritmi e Strutture Dati ESONERO PARZIALE 8/11/2001

(Compito B)

PARTE A: Test a risposta multipla (barrare tutte le risposte corrette) B.A.1) Si consideri il seguente programma per l’ordinamento di un array:

void swap(int &a, int &b) { int temp;

temp = a;

a = b;

b = temp;

}

void selection_sort(int *A, int n) { int max=-∞, maxind;

if (n==0) exit();

for (int i=0; i<n; i++) if (A[i] > max) {

maxind=i;

max=A[i];

}

swap(A[n], A[i]);

selection_sort(A, n-1);

}

Qual è la complessità della funzione

nel caso peggiore?

Θ (n) c

Θ (n

) c

Θ (nlogn) c

Θ (n

logn) c

altro c

B.A.2) Consideriamo una tabella hash in cui i conflitti sono risolti mediante concatenazione. Il valore atteso del numero di elementi in ogni posizione della tabella è:

E[n

] = α c

E[n

] = α solo se vale l’ipotesi di Hashing Semplice Uniforme c

E[n

] = O(m) c

E[n

] = O(m) solo se n = O(m) c

E[n

] = O(m) solo se n = O(m) e vale l’ipotesi di Hashing Semplice Uniforme c

B.A.3) Si consideri il seguente input per l’algoritmo heap_sort: <2, 4, 3, 1, 5, 6, 9>

Dopo aver costruito l’heap, quali delle seguenti sequenze parziali sono ottenute dall’algoritmo? (la prima sequenza rappresenta l’heap, la seconda rappresenta l’array parziale ordinato)

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

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

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

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

B.A.4) Si consideri il seguente input per l’algoritmo insertion_sort: <5, 8, 11, 2, 3, 4, 6>

Quali delle seguenti sequenze intermedie sono ottenute dall’algoritmo?

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

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

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

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

B.A.5) Che succede se nella costruzione di un max heap si effettua sull’array un ciclo for da 0 a n-1 anziché da

n/2-1 a 0?

vengono esaminate le foglie inutilmente c

l’algoritmo non è corretto c

aumenta la complessità dell’algoritmo c

niente c

PARTE B: Algoritmi

B.B.1) Si supponga definito il tipo di dato

struct nodo { int info;

struct nodo* left;

struct nodo* right;

};

come tipo elementare per l’implementazione di un albero binario. Si supponga inoltre definita globale la variabile

Scrivere una funzione

che, eseguendo una ricerca in ampiezza, trovi il numero più occorrente nell’albero

[SUGGERIMENTO: si utilizzi una coda per memorizzare i figli di uno stesso nodo].

B.B.2) Per l’archiviazione del materiale inventariabile della facoltà di Scienze si utilizza un dizionario in cui ogni elemento inventariabile è descritto con una stringa di caratteri ed è rintracciabile attraverso una chiave numerica. Si scrivano le necessarie procedure di inserimento e ricerca di un elemento.

PARTE C: Domande aperte

B.C.1) Si descriva il metodo della moltiplicazione per la costruzione di tabelle hash illustrando i particolari della implementazione della funzione di hashing e le prestazioni dal punto di vista della distribuzione delle chiavi.

B.C.2) Si illustri il funzionamento dell’algoritmo heap_sort e si discuta la sua complessità computazionale nel

caso peggiore.