Laboratorio di Algoritmi e Strutture Dati ESONERO PARZIALE 8/11/2001
(Compito A)
PARTE A: Test a risposta multipla (barrare tutte le risposte corrette)
A.A.1) Si consideri il seguente programma per il calcolo della potenza n-esima di un binomio mediante la formula (a+b)
n= Σ
k=0, …, n[n:k]a
kb
n-k.
// calcola il coefficiente binomiale [n:k]
int coeffbin(int n, int k) {
int temp1, temp2;
if ((0 <= k) && (k <= n)) if ((k==0) || (k==n))
return(1);
else {
temp1 = coeffbin(n-1, k-1);
temp2 = coeffbin(n-1, k);
return (temp1 + temp2);
}
else
return (-1) ; /* come messaggio di errore */
}
void binpower() {
int n;
float a, b, auxa, auxb, res;
int k, j;
scanf ("%d %f %f", &n, &a, &b);
if ( n < 0 ) {
printf("errore: esponente negativo");
exit(0);
} else {
res = 0.0;
for (k=0; k<=n; k++) { auxa = auxb = 1.0;
/* calcola a^k */
for (j=1; j<=k; j++) auxa = a * auxa ; /* calcola b^(n-k) */
for (j=1; j<=n-k ; j++) auxb = b * auxb ;
res = res + (coeffbin(n, k)*auxa*auxb );
}
printf ("\n\n n = %d \n a = %f \n b = %f \n res = %f ", n, a, b, res);
} }
la complessità asintotica del programma nel caso peggiore è:
Θ(n) c
Θ (n
2) c
Θ (n
3) c
Θ (n
2log (a+b)) c
altro c
A.A.2) Si consideri il seguente input per l’algoritmo heap_sort: <3, 1, 4, 7, 6, 5, 8>
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)
<7, 4, 5, 1, 6, 3>; <8> c
<7, 6, 5, 1, 4, 3>; <8> c
<6, 4, 5, 1, 3>; <7, 8> c
<6, 5, 3, 1, 4>; <7, 8> c
A.A.3) Si consideri il seguente input per l’algoritmo insertion_sort: <3, 1, 4, 7, 6, 5, 8>
Quali delle seguenti sequenze intermedie sono ottenute dall’algoritmo?
<1, 3, 4, 7, 6, 5, 8> c
<1, 3, 4, 6, 7, 5, 8> c
<1, 3, 4, 6, 7, 8, 5> c
<1, 3, 4, 5, 6, 8, 7> c
A.A.4) Sia h(k) = k %m una funzione hash su una tabella di m elementi. Perché la tabella hash presenti mediamente il minor numero di conflitti occorre che:
m non sia una potenza di 2 c
m non sia un numero primo c
m non sia uguale a 2
p-1, con p numero primo c
m può assumere qualsiasi valore c
A.A.5) Sia data una lista doppia costruita a partire dal seguente elemento base:
struct nodo { int info;
struct nodo *next;;
struct nodo *prev;
}
quante istruzioni elementari richiede nel caso peggiore l’operazione
void delete(struct nodo*)?
O(n) c
O(log n) c
O(1) c
dipende dalle informazioni memorizzate nella lista c
PARTE B: Algoritmi
A.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 come globale la variabile
struct node* root;scrivere una funzione
int height(struct node * root)che calcoli l’altezza dell’albero;
A.B.2) Si supponga definito il tipo di dato
struct elem { char *nome;
int key;
};
