2005 – 5

Cosa stampa il seguente programma?

#include 

int funzione1(int arr[]) 
{
   int i=1;
   while(arr[i] != -1)
      i=i*2;
   return i;
}

int funzione2(int arr[], int f, int k) 
{
   int i=0;
   int m;
   while(i <= f)
   {
      m=(i+f)/2;
      if(arr[m] == k) 
         return m;
      if((arr[m] == -1) || (arr[m] > k)) 
         f=m-1;
      else 
         i=m+1;
   }
    return -1;
}

main() 
{
   int arr[10]={1,2,4,8,-1,-1,-1,-1,-1,-1};
   int f=funzione1(arr);
   int a=funzione2(arr, f, 4);
   int b=funzione2(arr, f, 7);
   printf("a=%d,b=%d\n", a, b); 
}

Risposte:

1. a=2,b=4
2. a=2,b=-1
3. a=-1,b=4
4. a=-1,b=-1

Soluzione: b (a=2,b=-1)

La funzione funzione1() restituisce 4, l’indice del primo valore -1.

La funzione funzione2() effettua una ricerca binaria in arr[], dall’indice 0 all’indice f, del valore 4 (restituisce 2) e del valore 7 (restituisce -1).