Domanda 1 :

Per ordinare il  vettore, di Fig 1, con l'algoritmo selection sort, in ordine crescente al crescere dei suoi indici, quanti confronti occorrono :

Fig.1

 12 confronti

 4 confronti

 10 confronti

 15 confronti

Domanda 2 :

Volendo ordinare il vettore in Fig. 2, in senso crescente al crescere degli indici del vettore, con l'algoritmo selection-sort , al secondo  passo  della seconda iterazione, quale vettore semi-ordinato avremo. 

Fig. 2 

Domanda 3 :

Il seguente programma cosa fa all'array VET ?

#include<stdio.h>

#define N  10

main( )

{

int VET[N] = {2,  5,  6,  34,  11,  44,  33,  89,  68,  36 };

  int  i, k, vecchio;

  for (i=0; i<DIM; i++)

   printf (“\n%d”, VET[i] );

     for (k=1; k<N ; k++) 

     for (i=0;i<=N -1 ; i++)  

      if (VET[i] >VET[i+1] )   

      {                                   

       vecchio = VET[i];   

       VET[i] = VET[i+1];

        VET[i+1] = vecchio;

       }

return 0;

}

lo ordina in senso decrescente,solo parzialmente, con il bubble-sort 

lo ordina in senso crescente utilizzando il bubble-sort

lo ordina in senso decrescente utilizzando la selection-sort

lo ordina in senso crescente utilizzando la selection-sort

Domanda 4 :

La funzione seguente cosa fa all'array A passatole come parametro essendo n il numero di elementi dell'array A ?

void selection_sort(int A[ ], int n)

{

 int i, j, i_minimo;

 for ( i=0;i<n-1; i++) /*iterazione*/

  {

   /*ricerca della componente minima fra A[i] e A[n]*/

   i_minimo=i;

   for(j=i+1;j<n;j++)   /*passi*/

    if(A[j]<A[i_minimo]) /*confronto*/

      scambia(A[j],A[i_minimo] );

  }

}

  non riesce ad ordinarlo in senso crescente poiche' manca l'istruzione  i_minimo= j; dopo il confronto.

  lo ordina in senso crescente correttamente

  non riesce ad ordinarlo in senso crescente poiche' il confronto dovrebbe essere if( A[j]>=A[i_minimo] )

  lo ordina in senso decrescente correttamente

Domanda 5 

Volendo ordinare il vettore in Fig. 3, in senso crescente al crescere degli indici del vettore, con l'algoritmo bubble-sort , al secondo  passo  della seconda iterazione quale vettore semi-ordinato avremo. 

Fig. 3 

Domanda  6 :

Avendo un array  di (2^20 +1) interi, ordinato in senso decrescente al crescere degli indici, quanti confronti occorrono nel caso peggiore, con la ricerca binaria (adattata a tale caso) per trovare un elemento, che sappiamo essere in esso presente.

  almeno 50 confronti

  al massimo 15 confronti

  21 confronti

  51 confronti 

Domanda  7 :

A quale compito assolve la seguente funzione funz:

int funz (int elemento[ ], int cont, int chiave)

{

register int k; 

for(k=0; k<cont; k++)

  if(chiave==elemento[k] )    return(k); 

 else return( -1); }

 restituisce l'indice dell'array in cui e' contenuto l'intero cercato con la ricerca sequenziale oppure -1 se non trova l'intero richiesto

 restituisce l'elemento dell'array in cui e' contenuto l'intero cercato, con la ricerca sequenziale, oppure -1 se non trova l'intero richiesto

 restituisce l'indice dell'array in cui e' contenuto l'intero cercato con la ricerca binaria oppure -1 se non trova l'intero richiesto

 restituisce l'elemento dell'array in cui e' contenuto l'intero cercato, con la ricerca binaria, oppure -1 se non trova l'intero richiesto

Domanda  8 :

Volendo cercare l'elemento 14 in un array, a, cosi ordinato come in Fig. 4, dopo quanti passi, della istruzione while  della ricerca binaria, lo riusciamo ad individuare essendo noti i parametri della funzione di ricerca binaria a,x,n :

_____________________________________________________

return to lesson 16 

_____________________________________________________