[exameneac] subiecte PA 23.06.2005 

    
NR 1

1.        Care este numarul minim de operatii necesare pentru realizarea produsului  A10´2 , B2´25, C25´20, D20´2 

Obs. Pentru a realiza produsul A´B unde A este o matrice de dimensiune m´n iar B este o matrice de dimensiune n´p, sunt necesare m´n´p operatii.

a.       2400

b.      1120 corect

c.       1500

d.      1240

 

2.     Algoritmul prezentat în cele ce urmeaza ar trebui sa calculeaze drumurile minime într-un graf G=(V,E) de la nodul s  la toate celelalte n noduri.

 

                         short_path( G, C, s, n )

                         {

                         // G = ( V, E )  ,  V = {1,2,...,n}

                         // C - matrice de cost C[i,j] = 
                         // folosim vectorii dist[1..n] si pred[1..n]

                         // S - multimea nodurilor atinse

                         S = {s}

                         for  i=1,2,…,n

                         {

                                      dist[i] = C[s,i]

                                      pred[i] = s

                         }    

                         for  k=2,3,…,n-1   

                         {

                                      fie u a.î. dist[u] = *******                                

                                      S = S {u}

                                     for all v V\S 

                                      {

                                         if (dist[v] > dist[u] + C[u,v] 

                                                {

                                                                dist[v] = dist[u] + C[u,v]

                                                                pred[v] = u

                                                } 

                                      }

                         } 

                         return (dist, pred)

                         }

Cu ce trebuie inlocuit sirul *******  pentru a obtine algoritmul lui Dijkstra ?

 

a.        min{dist[x]}

       x S

b.        min{dist[x]} corect

       x V\S

c.        min{dist[x]}

       x V

d.        min{dist[x]}

       x S\V

 

2.        Fie D = (V, E) un digraf reprezentat prin listele de adiacenta urmatoare:

      -----    -----------    -----------

    1 |  -|®|  2   |   -|®|  3   | 0  |

      -----    -----------    -----------

    2 | 0 |

      -----    -----------   

    3 |  -|®|  4   | 0  |

      -----    -----------    -----------

    4 |  -|®|  1   |   -|®|  5   | 0  |

      -----    -----------    -----------

    5 |  -|®|  2   | 0  |

      -----    -----------

Obs.: 0 este pointerul NULL.

 

Digraful D contine circuite ?

 

a.        Da corect

b.        Nu

c.        Listele de adiacenta de mai sus nu reprezinta un digraf.

 

4.  Algoritmul urmator sorteaza crescator o secventa de n chei numerice de sortare memorate într-un tablou A de dimensiune n.

 

Sort(A,n)

flag=1; k=n;

while (flag ą 0 and k >= 1) do

k=k-1; flag=0;

for  i=1 to k do

                      if ( A[i] > A[i+1] ) then

                                        interchange ( A[i], A[i+1] ); flag=1;

                      end_if

      end_for

end_while

end{Sort}

 

Un algoritm de sortare se numeste stabil daca cheile egale ramân dupa sortare în aceeasi ordine relativa. Astfel daca înainte de sortare A[i]=A[j]=a, i<j iar dupa sortare cheia a de pe pozitia i (A[i]) ajunge pe pozitia k iar cheia a de pe pozitia j  (A[j]) va fi plasata pe pozitia l, atunci k<l. Exemplu : înainte de sortare A=(4,1,2a,5,6,2b,3) iar dupa sortare A=(1,2a,2b,3,4,5,6). 

Ce metoda de sortare foloseste algoritmul prezentat anterior ? Algoritmul este stabil ?

a.        Metoda bulelor, este stabil  corect

b.        Metoda insertiei, este stabil

c.        Metoda bulelor, nu este stabil

d.        Metoda insertiei, nu este stabil

 

II    (2p)

Se considera urmatorul mesaj M = „mare si tare“. Scrieti o codificare Huffman a caracterelor care compun mesajul, care sa minimizeze lungimea lui M. Precizati  metoda de proiectare utilizata la constructia algoritmului.

 

III (3p)
Se considera un graf G=(V,E) cu V={1,2,....,n} si m culori numerotate 1,2,...,m. O colorare a grafului este o functie C: V->{1,2,......,m} cu proprietatea ca oricare muchie are extremitatile colorate diferit Sa se scrie un algoritm care sa genereze toate colorarile posibile. Sa se precizeze metoda de proiectare folosita.