ESERCIZI DI PREPARAZIONE PER IL SECONDO 
ESONERO DI PROGRAMMAZIONE II


(1)	Data una lista L1 di interi ed un intero x, definire in C 
una funzione 
ricorsiva di coda (tail) 
che restituisce in output una nuova lista (si utilizzi la funzione newnode) 
che contiene (un duplicato 
di) tutti i nodi di L1 in posizione non multipla di x. 
Si discuta la complessita' in spazio e tempo di 
tale funzione.
							(10 punti)
Esempio:  L1:        3 -> 1 -> 3 -> 5 -> 6 -> 9 -> 8 -> 3 -> 2 -> 11 -> 10	
          x=3
	  Risultato: 3 -> 1 -> 5 -> 6 -> 8 -> 3 -> 11 -> 10            

(2)	Date tre liste L1, L2 ed L3, 
definire una funzione C ricorsiva non di coda 
(non tail) che restituisce il numero di volte in cui il contenuto 
del nodo di L3 e' 
la somma dei contenuti dei 
corrispondenti nodi di L1 ed L2 (che devono essere entrambi presenti). 
Si discuta la complessita' 
in spazio e tempo di tale funzione.

							  (9 punti) 
Esempio:   	L1:  3 -> 3 -> 4 -> 5  -> 13 -> 7  -> 2 -> 8 -> 9 -> 11	
	  	L2:  3 -> 1 -> 3 -> 9  -> 8  -> 10 -> 4 	
		L3:  3 -> 4 -> 6 -> 14 -> 4  -> 1  -> 6 -> 8 
Risultato:	3
	

(3)	Si simuli l'esecuzione della funzione ricorsiva f, utilizzando 
i record di attivazione, e 
supponendo che la funzione venga richiamata con 
L1: 3->7->4->6 e nella seguente 
situazione:										
                                                                (6 punti)
	x=2; y=24; z=0; h=0; h=f(x,y,&z,L1);

	int f(int a, int b, int * c, node *lis)
	{ if (lis == NULL) return 0;
	   else if ((lis->data * a) < b) 
		   {*c = (*c)+1; return 1+f(a+2,b,c, lis->next);}
	   else if ((lis->data * a) > b) 
		   {*c=(*c)+1; return f(a+2,b,c, lis->next);}
	  else return 0; }

 (4)	La funzione f dell'esercizio 3 e' lineare? 
        E' ricorsiva di coda? Motivare le due risposte.
								(3 punti)

(5)	Si descriva la funzione merge utilizzata nel Mergesort, e la si simuli 
(indicando i risultati dopo ogni operazione di inserimento nella lista 
prodotta 
come risultato) sulle liste:  
          L1= 2 -> 3 -> 8 -> 11 
          L2= 1 -> 5 -> 9											
			                                       (5 punti)