Numele si Prenumele 
Grupa :
 
Proiectarea Algoritmilor
Nr. 2.

 

I (4p)

 

1. Care este numarul minim de operatii necesare pentru realizarea produsului  A10´4 , B4´5, C5´20, D20´4 

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.       600

b.      440

c.       1680

d.      640     

Raspuns : d

 

2.  Se considera functia de cautare într-un arbore binar de cautare in care radacina si fiecare nod interior are un singur fiu:

search(r,x)

{

        p=r;

        while( p ¹ NULL)

                        {

                          if ( x < data(p) ) p=lchild(p);

                          else       if ( x > data(p) ) p=rchild(p);

                                        else return(p);

                        }

        return(p);               // return null

}

 

Complexitatea timp pentru cazul cel mai defavorabil este:

a.                    O(n)                    

b.                   O(nlog n)               

c.                    O(n2)        

d.                   O(logn)

Raspuns : a 

 

3. Fie cuvantul W= ‘’hasta la vista’’. Care este numarul de cifre (0 si 1) ale codificarii binare a lui W, de lungime minima,  realizata prin metoda arborilor Huffman:

a.        23

b.       35

c.        40

d.       20

Raspuns : c ( nu erau ordinea asta dar sigur mi-a dat 40 )

          

4. Se considera urmatoarea varianta a algoritmului de sortare rapida:

 

        Quick_Sort(A, low, high)

{

        if(high > low) then

        {

                        k = Partition(A, low, high)   // partitionare

                        Quick_Sort (A, low, k-1)

                        Quick_Sort (A, k+1, high)

        }

}

Partition(A, low, high)

{ 

                l= low; h= high;

                x= A[l];

                while (l < h)

                                {

                                  while (A[l] £ x and  l £  high) l=l+1;

                                  while (A[h] > x and h ³  low) h=h-1-;

                                  if (l <h)  interchange (A[l], A[h]) ;

                                }

                interchange (A[h], A[low])

                return(h);

}

Care este ordinul de complexitate a memoriei stiva consumate de algoritmul de mai sus:

a.        O(n)

b.       O(nlogn)

c.        O(logn)

d.       O(n2)

Raspuns : a

II (2 p)

Fie G=(V,E) un graf orientat  ponderat (peste E este definita o functie w:E®N). Se considera V=(A,B,C,D,E,F)..Graful G este reprezentat astfel:

 

        A. B(4),F(2)

        B: A(2), C(3), D(4)

        C: A(6), B(3), D(7)

        D: A(6), E(2)

        E: D(5)

        F: D(2), E(3)

 

Obs: A: B(4) Û w(AB)=4 etc.

Între C si  E exista doua drumuri de lungime minima. Care din acestea este obtinut prin algoritmul lui Dijkstra? Justificati raspunsul.

          Am scris C B D E . dar nu stiu dak e corekt, rog pe cei care au scris bine sa posteze varianta corecta.          

 

III   (2p) 

Un instructor are la dispozitie n perechi de schiuri care trebuie repartizate la n elevi incepatori. Sa se scrie un algoritm care sa determine repartizarea astfel incat suma diferentelor absolute dintre inaltimea elevului si lungimea schiurilor atribuite sa fie minima. Sa se precizeze metoda de proiectare folosita.

Sortare crescatoare a ambilor vectori  plus corespon dentza h(n) - l(n) , unde h-vectorul inaltimilor si l - vectorul lungimilor schiurilor.

 


Baza 2p