Subiect nr. 1:
I(4p)
1.A(20x2),B(2x15),C(15x40),D(40x2)
Care este nr minim de operatii pr A*B*C*D
a.2400
b.1340
c.1200
d.320

2.Algoritmul prezentat în cele ce urmează ar trebui să 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] =min{dist[x]}x V\S		
		S = S {u}
	 	for all v V\S 
		{
		         if ***********
			{
			dist[v] = dist[u] + C[u,v]
			pred[v] = u
			} 
		}
	} 
	return (dist, pred)
	}
Cu ce trebuie inlocuit sirul *******  pentru a obține algoritmul lui 
Dijkstra ?

a.dist[v] < dist[u] + C[u,v]
b.dist[u]>dist[v]+c[u,v]
c.dist[v] > dist[u] + C[u,v]
d.dist[u]<dist[v]+c[u,v]

3.2.	Fie D = (V, E) un digraf reprezentat prin listele de 
adiacență următoare:
      -----    -----------    -----------
    1 |  ?|?|  2   |   ?|?|  3   | 0  |
      -----    -----------    -----------
    2 |  |?|3   | 0  |
      -----    -----------   
    3 | 0 ?|
      -----    -----------    -----------
    4 |  ?|?|  1   |   ?|?|  5   | 0  |
      -----    -----------    -----------
    5 |  ?|?|  2   | 0  |
      -----    -----------
Obs.: 0 este pointerul NULL.

Gradul interior este ?

a.0	
b.1
c.2
d.3

4.  Algoritmul următor sortează crescător o secvență 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 numește stabil daca cheile egale ramân 
dupa sortare în aceeași ordine relativa. Astfel daca înainte de 
sortare A[i]=A[j]=a, i<j iar dupa sortare cheia a de pe poziția i (A
[i]) ajunge pe poziția k iar cheia a de pe poziția j  (A[j]) va fi 
plasata pe poziția 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 metodă de sortare folosește algoritmul prezentat anterior ? 
Algoritmul este stabil ?

a.Metoda bulelor, este stabil
b.Metoda inserției, este stabil
c.Metoda bulelor, nu este stabil
d.Metoda inserției, nu este stabil

II(2p).Se consideră următorul mesaj M = „vacanta de vara“. Scrieți o 
codificare Huffman a caracterelor care compun mesajul, care să 
minimizeze lungimea lui M. Precizați  metoda de proiectare utilizată 
la construcția algoritmului.

III.(2p)Se numeste "triungi" intr-un graf G un ciclu de lingimn 3.Sa 
se scrie un algoritm care verifica daca in graful G exista 
un "triunghi".Precizati metoda folosita

subiect numarul 2:
I(4 pct)
1:se da un digraf D=(V,E) prin listele de adiacenta :
|1 |->|2 |
|2 |->|3 |
|3 |->|5 |
|4 |0
|5 |->|2 |
spuneti daca este arbore:
a.este arbore cu radacina in 1
b.listele de adiacenta de mai sus nu reprezinta un arbore
c.este arbore cu radacina in 4
d.este arbore cu radacina in 2
 
2.se da algoritmul de cautare a unui nod intr-un arbore binar de cautare:
(il aveti in curs  :P)
pt un arbore cu n noduri stiind ca si radacina si fiecare nod interior are un singur descendent care este complexitatea timp:
a.O(n2)
b.O(log n)
c.O(n)
d.O(nlogn)
 
3.se da secventa W="abracadabra" cate cifre de 1 si 0 sunt necesare pt o codificare huffman optima.
a.23
b.34
c.28
d.20
 
4.se da algoritmul quick_sort(si asta este in curs de aia nu-l mai scriu aici)
care este complexitatea de memorie stiva utilizata:
a.O(n)
b.O(nlogn)
c.O(log n)
d.O(n3)
 
 
II(2pct)
 
se da un graf neorientatcu nodurile(A B C D E F) ponderat (SE DAU PONDERILE PE FIECARE MUCHIE nu le mai tin minte pe toate acu) de la C la E exista 3 drumuri minime.care din ele este dat in urma aplicarii alg dijkstra argumentati raspunsul.
 
III(2 pct)
 
se dau 6 culori: alb galben verde rosu albastru negru .sa se scrie un algoritm care coloreaza un steag cu 4 culori in toate posibilitatile stiind ca:
 culorile din mijloc adica 2 si 3 trebuie sa fie rosu sau verde sau galben
si nu pot fi doua culori la fel
precizati metoda aplicata