Balanescu Cristian - Teorie Stiva

Stiva - o lista liniara simplu inlantuita care se construieste pe principiul "ultimul intrat, primul iesit".
-are un singur capat care se numeste varful stivei, singurele operatii admise sunt adaugarea unui nod in varful stivei si extragerea unui nod din varful stivei.
O stiva stimuleaza asezarea unor obiecte unul peste celalalt (cum ar fi, de exemplu, farfurii, caramizi, etc.) si adaugarea unor noi obiecte nu se poate face decat deasupra celorlalte, iar de luat nu se pot lua obiecte decat de deasupra (pentru ca, altfel, se "darama" stiva).

Adaugarea in stiva(elem, V, n)
if v[n-1] = n-1
return "stiva plina"
v[v[n-1]] = elem
v[n-1] = v[n-1] + 1
return "succes"

Stergerea din stiva(V, n)
if v[n-1] = 0
return "stiva goala"
elem = v[v[n-1] - 1]
v[n-1] = v[n-1] + 1
return elem;

Problema: Într-o stivă ce memorează numere întregi se introduc, în ordine,următoarele numere:
1,2,3,4,5,6,7. Câte numere trebuie să eliminăm din stivă astfel ca în vârful stivei să se găsească
numărul 5?

a. 5 b. 2 c. 3 d. 4

7

6

5
4

3

2

1

Pentru a avea în vârful stivei valoarea 5 trebuie să eliminăm maxim două valori,strict două valori şi anume (7,6).

Verba Roxana - teorie

Cazuri particulare de liste:
• Coada
• Stiva

Coada- o lista liniara simplu inlantuita care se construieste pe principiul “ primul intrat, primul iesit”

Coada are doua capete :
• Prin capatul din dreapta introducem noduri in coada
• Prin capatul din stanga extragem noduri.

Coada este mult utilizata in sistemele de operare ( in rutinele de alocare a resurselor, un exemplu foarte cunoscut fiind coada de asteptare a documentelor ce asteapta la tiparit atunci cand se da comanda de tiparire la o imprimanta pentru mai multe documente) sau in programe de simulare.
O coada in care adaugarile si eliminarile de elemente se po face numai la cele doua capete ale listei se numeste coada completa. Structura statica adecvata memorarii unei cozi complete este coada rulanta.

Adaugarea in coada(elem, V, n)
v[n-2] = (v[n-2] + 1) mod (n-2)
if v[n-1] = v[n-2]
return "coada plina"
V[V[n-1]] = elem
return "succes"

Stergerea din coada(V,n)
if v[n-1] = v[n-2]
return "coada goala"
v[n-1] = (v[n-1] + 1) mod (n-2)
return V[V[n-1]]

Problema: o garnitura de tren are in componenta o locomotiva si sase vagoane. locomotiva este numerotata cu 1 si vagoanele in continuare. Sa se adauge dupa primul vagon, vagonul de dormit care se va nota cu 11.

int main ()
{struct nod { int x; nod*urm;}
*p, *u, *l, *p1, *u1;
p=new nod;
p->x=1;
p=u;
p->urm=NULL;
for(i==2;i<=7;i++) {l=new nod; l->x=i;
l1->urm=l;
u=l;
l1->urm=NULL;}

l=p;
p1=new nod;
p1=l;
p=p->urm;
u1=new nod;
u1=p;
p1->urm=u1;
p=p->urm;
l=new nod;
l->x=11;
u1->urm=l;
u1=l;
u1->urm=NULL:
u1->urm=p;}

return 0;}

Serban Cristina. Variante liste

Varianta 1


1. Se consideră o coadă în care iniţial au fost introduse, în această ordine, elementele cu valorile 1 şi 2:
. Se notează cu AD(x) operaţia prin care se adaugă elementul cu valoarea x in coada
şi cu EL operaţia prin care se elimină un element din coadă. Câte
elemente va conţine coada în urma executării secvenţei de operaţii:
AD(4);EL;EL;AD(5);EL;AD(3)?

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


Raspunsul este c.2 deoarece doar doua valori au ramas dupa eliminare.



Varianta 2

3. Se consideră o stivă în care iniţial au fost introduse, în această ordine,
elementele cu valorile 1, 2 şi 3, ca în figura alăturată. Se notează cu
AD(x) operaţia prin care se adaugă elementul cu valoarea x în vârful
stivei şi cu EL operaţia prin care se elimină elementul din vârful stivei.
Care sunt valorile ultimelor două elemente eliminate din stivă în urma
executării secvenţei de operaţii: AD(4);EL;EL;AD(5);EL;EL?

Valorile ultimelor doua elemente eliminate din stiva in urma executarii secventei de operatii sunt 2 si 5.


Varianta 6


Se consideră o listă liniară simplu înlănţuită
alocată dinamic, cu cel puţin două
elemente. Fiecare element al listei reţine în
câmpul urm adresa elementului următor din
listă sau NULL dacă nu există un element
următor.
while (...)
p=p->urm;
delete p->urm; free (p->urm);
p->urm=NULL;
Ştiind că variabila p reţine adresa primului element din listă, care dintre expresiile următoare
poate înlocui punctele de suspensie în secvenţa de instrucţiuni de mai sus astfel încât, în
urma executării acesteia, să fie eliminat ultimul element al listei?

a. p->urm->urm!=NULL b. p->urm!=NULL
c. p!=NULL d. p->urm->urm==NULL

Raspunsul este c pt ca p nu trebuie sa fie nul ca sa se poate executa programul.

Suciu Lorena

Liste circulare simplu inlantuite

Def : O lista circulara simplu inlantuita este o lista in care ultimul element contine campul ce adreseaza elementul urmator, adresa primului element.

O lista circulara poate fi asimetrica sau simetrica dupa cum elementele listei sunt dublete, respectiv triplete, adica contin un pointer sau doi pointeri.

Listele circulare se mai numesc si liste inchise, celelalte purtand numele de liste deschise.

La operatiile specifice listelor circulare trebuie sa tinem cont, in plus, si de legaturile existente intre ultimul nod si primul nod.

{

p=new mod;

cin>>p->info;

p=u;

u->urm=p;

l=new mod;

cin>>l->info;

u->urm=l;

u=l;

u->urm=p;

l=p;

cout<info;

while(l->urm!=p;)

{l=l->urm;

cout<info;}

cout<info;

return 0;}

Babutia Ruth

Structurii de date alocate dinamic
Structurile da date alocate dinamic sunt structuri ale caror componente se aloca in timpul executarii programului.
Tipuri de strcuturii dinamice
-liniare
-arborescente
-retea
Structurile de date liniare se numesc:
- liste: liste liniare simplu inlantuite
liste liniare dublu inlantuite
Operatiile cele mai inportante ale unei liste sunt:
- crearea unei liste
- adaugarea sau inserarea unui nod in lista
- stergerea sau eliminarea unui nod din lista
- parcurgerea unei liste.

Structura unui nod este:
struct nod
{
tip informatibila;
nod *urm;
}
*p, *l, *u;

Crearea, parcurgerea, si afisarea unei liste:
int main( )
{ struct nod
{ int x;
nod *urm;} *p, *u, *l, *q;
int n, i, y;
cout<<"n=";cin>>n;
p=new nod;
cout<<" citeste o valoare:"; cin>>p->x;
u=p;
u->urm=NULL;
for(i=2;i<=n;i++) { l=new nod; cin>>l->x;
u->urm=l;
u=l;
u->urm=NULL;
l=p;
k=0;
whike( l!=NULL)
{ if(l->%2==0)
k++;
l=l->urm;}
{ cout<x<<" "; l=l->urm; }
return o;}

Adaugarea unui nod in lista:
l=new nod;
l->urm=p;
p=l;
p->x=p->urm->x;

Adăugarea la sfârşitul listei

Dacă dorim ca nodurile listei să fie parcurse după un anumit criteriu (de exemplu crescător după câmpul cuvant), trebuie ca introducerea unui nou nod în listă să se facă astfel încât să nu se strice ordinea listei (altfel spus, îl vom introduce la locul lui); pentru exemplul considerat, vom introduce noul nod înaintea primului nod cu câmpul cuvant mai mare decât câmpul său cuvant.

Adăugarea la începutul listei

Adăugarea la sfârşitul listei

Adăugarea după nodul p al listei

Ştergerea dintr-o listă simplu înlănţuită ordonată

Dacă dorim să eliminăm un nod din listă, memoria pe care acesta o ocupa va trebui eliberată, pentru a fi folosită la adăugarea de alte noduri; dacă nu o eliberăm explicit cu funcţia free, ea va rămâne marcată ca fiind ocupată pe durata execuţiei programului şi nu va putea fi folosită. De aceea, înainte de a reface legăturile pentru ca nodul de şters să fie eliminat din listă, adresa lui va fi memorată într-o varialbilă pentru a fi eliberată ulterior zona de memorie dedicată lui.

Ştergerea ultimului nod

Ştergerea nodului de după nodul p

Liste liniare simplu inlantuite.

O lista liniara este o segventa finita de n elemente (componente) de acelasi tip de nod 1,nod 2,...nod n numite si noduri aflate intr-o relatie de ordine.

In cadrul unei liste sunt puse in evidenta :
- un element numit primul element;
- un element numit ultimul element;
- cate un singur element succesor pentru fiecare element al listei (cu exceptia ultimului element, care nu are succesor);
- cate un singur element predecesor pentru fiecare element al listei (cu exceptia primului element, care nu are predecesor);


Pentru a pune in evidenta succesiunea nodurilor, o lista o putem reprezenta astfel:



Componentele listei pot fi date elementare sau date structurate.

Operatiile cele mai importante definite pe liste sunt :
- crearea unei liste;
-parcugerea unei liste;
-adaugarea (inserarea) unui nou nod in lista;
- stergerea (eliminarea) unui nod din lista;
-afisarea listei.

Stergerea unui element dintr-un anumit loc din lista presupune deplasarea elementelor finale ale listei pentru a fi ocupat locul elementului ce se elimina.

void stergere(int val)

{Nod *c,*a;

c=prim;

if(prim->info==val)

{a=prim;

prim=prim->urm;

delete a;}

else

{while(c->urm->info!=val )

c=c->urm;

a=c->urm;

c->urm=a->urm;

if(a==ultim) ultim=c;

delete a;} }

Adaugarea (inserarea) unui nod in lista se poate face:
- in fata primului nod;
- in interiorul listei;
- dupa ultimul nod din lista.

Adaugarea (inserarea) in fata primului nod:

Acesta este cazul cel mai simplu: trebuie doar alocat elementul, legat de primul element din lista si repozitionarea capului listei:


l=new nod;
l->urm=p;
p=l;
p->x=p->urm->x;


Adaugarea (inserarea) unui nod in interiorul listei:
-se parcurge lista pana ce identificam nodul din lista dupa care se fae inserarea. Cautarea nodului se poate face in functie de informatia utila, fie in functie de numarul de ordine al nodului din lista.

q=new nod;
q->urm=l->urm;
l->urm=q;
q->x=q->urm->x;

Adaugarea (inserarea) la sfarsitul listei
In acest caz trebuie intai parcursa lista si dupa aceea adaugat elementul si legat de restul listei. De asemenea, trebuie avut in vedere cazul in care lista este vida.

void InserareSfarsit(Element* &cap, Date val)
{
// Alocare si initializare nod
Element *elem = new Element;
elem->valoare = val;
elem->urmator = NULL;
// daca avem lista vida
if (cap == NULL)
// doar modificam capul listei
cap = elem;
else
{
// parcurgem lista pana la ultimul nod
Element *nod = cap;
while (nod->urmator != NULL)
nod = nod->urmator;
// adaugam elementul nou in lista
nod->urmator = elem;
}
}

Participanti

Babutia Ruth
Balanescu Cristian
Suciu Lorena
Serban Cristina
Verba Roxana

teorie grafuri orientate

GRAFURI ORIENTATE

Definitie Se numește graf orientat notat cu G o pereche ordonată de mulțimi {X,U} G= {X,U} unde X este mulțimea vârfurilor si U este multimea arcelor.

X={1,2,3,4,5}
U={(1,2);(1,3);(2,5);(4,2);(4,5)}

MATRICEA DE ADIACENTA.

Matricea de adiacenta asociata unui graf orientat este patratica si nesimetrica:
a[i][j]= 1 daca nodul i este adiacent cu nodul j;
0 daca nodul i nu este adiacent cu nodul j.
pentru graful orientat de mai sus avem urmatoarea matrice de adiacenta:
A= 0 1 1 0 0
0 0 0 0 1
0 0 0 0 0
0 1 0 0 1
0 0 0 0 0


GRAFUL UNUI NOD.

-grad extern este egal cu numarul arcelor care au extremitate initiala( numarul arcelor care ies din X)
-grad intern este egal cu numarul arcelor care au extremitate finala( numarul arcelor care intra in X).


TERMINOLOGIE.

Elementele mutimii U se numesc arce,iar multimea U se mai numeste si multimea arcelor.
Varfurile adiacente sunt orice pereche de varfuri care formeaza un arc.
Pentru arcul (x,y) spunem ca x este extremitate initiala iar y este extremitate finala.
Se numesc arce incidente doua arce care au o extremitate comuna.
Se numeste succesor al varfului X orice varf in care ajunge un arc care pleaca din varful X.
Se numeste predecesor al varfului X orice varf in care intra un arc care pleaca din varful X.
Nod sursa al grafului este nodul care are multimea succesorilor formata din toate celelalte noduri mai putin el iar multimea predecesorilo sai este vida. Nod destinatie al grafului este nodul care are multimea predecesorilor formata din toate celelalte noduri mai putin el iar multimea succesorilor sai este vida.
Se numeste nod terminal un nod care are suma gradelor egala cu 1.
Se numeste nod izolat un nod care are suma gradelor egala cu 0.


TEOREME.

1.Numarul total de grafuri orientate care se pot forma cu n noduri este
2.Intr-un graf orientat cu n varfuri suma gradelor interne ale tuturor nodurilor este egala cu suma gradelor exterioare ale tuturor nodurilor si cu numarul de arce.
3.Numarul de grafuri orientate complete care se pot construi cu n noduri este egal cu
4.Un graf cu mai mult de 2 noduri este hamiltonian daca gradul fiecarui nod este >=n/2.
5. Un graf ce nu contine grafuri izolate este eulerian daca si numai daca este conex si gradele tuturor nodurilor sunt pare.
6. Numarul de cicluri hamiltoniene dintr-un graf complet cu n noduri este
7. Orice graf turneu contine un drum elementar care trece prin toate nodurile grafului.
8. Pentru orice graf turneu, exista un nod x, astfel incat toate nodurile y!=x sunt accesibile din x pe un drum care contine un arc sau doua arce.

GRAFURI SPECIALE.

Graful G se numeste graf bipartit daca exista 2 multimi nevide de noduri A si B care au urmatoarele proprietati: AuB=X si AnB= multimea vida si orice muchie(arc) din multimea U are o extremitate in multimea de noduri A si o alta extremitate in multimea de noduri B.
Graful bipartit se numeste graf bipartit complet daca pentru orice nod xi care apartine lui A si orice nod xj care apartine lui B exista o muchie ( un arc ) formata din cele 2 noduri care apatin multumii U( [ xi, xj ]e U).


Graful GT1 este graf bipartit.
A={1,3,5}
B={2,4,6,7}

GT1

Graful GT2 este bipartit complet.
A={ 1,2}
B={3,6,7}

GT2

Numim lant hamiltonian un lant elementar ce contine toate nodurile grafului.
Lantul elementar este lantul care contine numai noduri distincte.
Numim ciclu hamiltonian un ciclu elementar ce contine toate nodurile grafului.
Un graf ce contine un ciclu hamiltonian se numeste graf hamiltonian.
Numim ciclu eulerian un ciclu ce contine toate muchiile grafului.
Un graf ce contine un ciclu eulerian se numeste graf eulerian.
Un garf orientat in care , intre oricare 2 noduri exista un singur arc si numai unul se numeste graf turneu.

Variante bac S II V 21-30

Varianta 1
1. c
2. d
4.Înălţimea arborelui este 3
Frunzele arborelui sunt: 1, 2, 3 şi 8

Varianta 2
1. b
2. c
3. Valorile ultimelor două elemente eliminate sunt 5 şi 2.
4.
s=0;
for(j=0;j{
if(a[k][2*j]%2==1)
s=s+a[k][2*j];
if(a[k][2*j+1]%2==1)
s=s+a[k][2*j+1];
}

Varianta 3
1. b
drumul (5,4), (4,2), (2,1), (1,6), (6,3) are lungimea maximă 5.
2. c
Frunzele sunt: 4, 1, 10, 11, 9
4.ideale

Varianta 4
1. b
2. a
3.2 vârf
1 bază
4.if (s[i]>=97 && s[i]<=122)
{ for(j=i;js[j]=s[j+1];
s[strlen(s)-1]=’\0’;
}
else i++;

Varianta 5
1. b
2. d
3. 14
4.c=s[i];
s[i]=s[j];
s[j]=c;
i++;
j--;

Varianta 6
1. c
2. b
3. 12
4.8 componente conexe

Varianta 7
1. a
2. b
3. 2
4. 128

Varianta 8
1. b
2. c
3.abefgh 6
4.s=p->info;
while(p)
{p=p->urm;
s=s+p->info;}
cout<
Varianta9
1. a
2. a
3.3
4.abcd123efg

Varianta 10
1. a
2.d
3.3081
4.abacde

Variante bac S II V 11-20

Problema 1
Pentru arborele cu rădăcină având următorul vector de “de taţi” tata=(2,0,2,3,2,3,4,4,3), care este rădăcina arborelui şi care sunt descendenţii
direcţi (fiii) ai nodului 3?

Raspuns : Radacina arborelui este 2, deoarece in vectorul de tati nodul 2 are valoarea 0. Descendentii directi(fiii) nodul 3 sunt nodurile 4, 6 si 9, deoarece in vectorul de tati acestia au valoarea 3, valoarea nodului.

Problema 2
Care este vectorul "de taţi" pentru arborele cu rădăcină din figura alăturată?
a. 0 0 5 7 6 5 1
b. 1 0 0 7 6 5 0
c. 7 4 5 0 4 5 4
d. 7 4 5 0 4 5 7

Raspuns: c. 7 4 5 0 4 5 4 deoarece nodul 4 este radacina, nodurile 5, 7 si 2 sunt descendenti directi ai nodului 4. Varianta d nu poate fi datorita faptului ca in vectorul tata apare ca nodul 7 are doi descendenti, respectiv nodul 1 si nodul 7.

Problema 3
Care sunt etichetele nodurilor de tip frunză ale arborelui cu rădăcină, având 7 noduri,
numerotate de la 1 la 7, şi următorul vector “de taţi”: (5,1,5,1,0,7,5)?

Raspuns : Nodurile de tip frunza ale arborelui sunt 2, 3, 4 si 6, deoarece aceste noduri nu se gasesc in vectorul tata, ele nemaiavand descendenti.

Problema 4
Câţi fraţi are nodul 1 din arborele cu rădăcină cu 7 noduri, numerotate de la 1 la 7,având următorul vector ”de taţi”: (5,1,5,1,0,7,5)?

Raspuns : Nodul 1 din arbore are 2 frati si anume nodul 3 si nodul 7, deoarece aceste noduri au acelasi tata ca si nodul 1, respectiv nodul 5.

Problema 5
Un arbore binar este un arbore cu rădăcină în care fiecare nod are cel mult 2 descendenţi direcţi (fii). Înălţimea unui arbore este reprezentată de numărul maxim de muchii ale unui lanţ elementar ce uneşte rădăcina cu un vârf terminal (frunză).
Pentru un arbore binar cu exact 8 noduri, care este înălţimea minimă posibilă şi care este numărul de noduri terminale (frunze) în acest caz?

Raspuns : Inaltimea minima posibila este 4, iar in acest caz, avem un singur nod terminal.

Problema 6
Se considera graful neorientat cu 80 d enoduri si 3160 muchii. Care este numarul de muchii care pot fi eliminate astfel incat graful partial obtinut sa devina arbore ?

Raspuns : Un arbore cu n noduri are n-1 muchii. Pentru ca graful dat sa devina arbore, trebuie sa se elimine 3160-79=3081 muchii.

Problema 7
Care este gradul maxim posibil si care este gradul minim posibil pentru un nod dintr-un graf cu n noduri, care este arbore ?

a. n-1 si 1
b. n si 1
c. n si 0
d. n-1 si 0.

Raspuns: a. Un arbore este conex, deci nu are varfuri izolate, oar gradul maxim al unui varf este n-1, daca in graf sunt n varfuri.

Problema 8
Un arbore cu rădăcină având 8 noduri, numerotate de la 1 la 8, este memorat cu ajutorul vectorului de ”taţi” t=(8,8,0,3,4,3,4,6). Scrieţi care este numărul total de descendenţi ai nodului 4?

Raspuns : 2 descendenti deoarece din vectorul de tati se observa ca nodul 5 si 7 il au ca tata pe 4.

Problema 9
Care dintre următoarele afirmaţii este adevărată pentru graful neorientat având mulţimea nodurilor X={1,2,3,4,5} şi mulţimea muchiilor U={[1,2], [1,5], [2,3], [2,4],[3,4], [4,5]}? (4p.)

a. Este graf hamiltonian, dar nu este eulerian.
b. Este graf eulerian, dar nu este hamiltonian.
c. Este şi graf hamiltonian şi graf eulerian.
d. Nu este graf hamiltonian, şi nici nu este graf eulerian.

Raspuns: a) Deoarece graful format reprezinta un cilcu Hamiltonian elemtentar care trece prin fiecare nod al grafului.

Problema 10
Un graf neorientat cu nodurile numerotate de la 1 la 4 este reprezentat prin matricea de adiacenţă alăturată. Care dintre afirmaţiile de mai jos este adevărată pentru acest graf?

a. Graful este arbore
b. Graful nu este conex
c. Graful este ciclic
d. Graful are toate gradele nodurilor numere pare.

Raspuns: a)Graful este un arbore, deoarece nodul 1 este radacina, care are ramificatie de dreapta nodul 2 si de stanga nodul 3, iar nodul 3 are ramificatied de stanga.

Problema 11
Se consideră un arbore cu 9 noduri, numerotate de la 1 la 9, şi cu vectorul “de taţi” următor: (8, 8, 8, 2, 6, 2, 9, 0, 2).
a) Enumeraţi descendenţii nodului 2.
b) Câte noduri de tip frunză are acest arbore?

Raspuns: a) descendentii nodului 2 sunt: 4,6,9,5,7;
b) exista 3 noduri de tip frunza : 4,5,7;

Variante bac S II V 1-10

Varianta 1

2.Câte grafuri neorientate, distincte, cu 4 vârfuri, se pot construi? Două grafuri se consideră distincte dacă matricele lor de adiacenţă sunt diferite.
Raspuns : d - teoreme - nr total de grafuri neorientate cu n noduri este

4. Prin înălţimea unui arbore cu rădăcină înţelegem numărul de muchii ale celui mai lung lanţ format din noduri distincte care are una dintre extremităţi în rădăcina arborelui. Scrieţi care este înălţimea şi care sunt frunzele arborelui descris prin următorul vector ”de taţi”:(6,6,5,0,6,4,4,7).
Raspuns : Înălţimea arborelui este 3

Frunzele arborelui sunt 1,2,3, si 8



Varianta 2
1. 1. Câte grafuri orientate, distincte, cu 4 vârfuri se pot construi? Două grafuri se consideră distincte dacă matricele lor de adiacenţă sunt diferite.
Raspuns : b - teorema : nr total de grafuri orientate care se pot forma cu n noduri este

Varianta 3

2.Câte frunze are arborele cu rădăcină descris prin următorul vector ”de taţi”:
(6,5,5,2,0,3,3,3,8,7,7)?
Raspuns : c - Frunzele sunt: 4, 1, 10, 11, 9

Varianta 4
1.Se consideră un graf orientat cu 6 noduri numerotate de la 1 la 6 şi cu mulţimea arcelor formată doar din arcele:
- de la fiecare nod numerotat cu un număr neprim i (i>1) la toate nodurile numerotate cu numere ce aparţin mulţimii divizorilor proprii ai lui i (divizori diferiţi de 1 şi de i)
- de la nodul numerotat cu 1 la nodul numerotat cu 6
- de la fiecare nod numerotat cu un număr prim i la nodul numerotat cu i-1
Pentru graful dat, care este lungimea celui mai mare drum, format doar din noduri distincte, ce uneşte nodul 6 cu nodul 1?
Raspuns : b

2.Câte frunze are arborele cu rădăcină, cu 8 noduri, numerotate de la 1 la 8, descris prin următorul vector ”de taţi”: (6,5,5,2,0,3,3,3)?
Raspuns : a

3.Se consideră o stivă în care iniţial au fost introduse, în această ordine, elementele cu valorile 1, 2 şi 3, ca în figura alăturată. Se notează cu AD(x) operaţia prin care se adaugă elementul cu valoarea x în vârful stivei şi cu EL operaţia prin care se elimină elementul din vârful stivei. Reprezentaţi, după modelul alăturat, conţinutul stivei, rezultat în urma executării secvenţei de operaţii: AD(4);EL;EL;AD(5);EL.
Raspuns : 2 vârf
1 bază


Varianta 5
1.Într-un graf neorientat cu 20 muchii, fiecare nod al grafului are gradul un număr nenul. Doar patru dintre noduri au gradul un număr par, restul nodurilor având gradele numere impare. Care este numărul maxim de noduri pe care poate să le aibă graful?
Raspuns : b

2.Variabila d, declarată alăturat, memorează în câmpurile a şi b lăţimea şi, respectiv, lungimea unui dreptunghi. Care dintre următoarele instrucţiuni atribuie câmpului aria al variabilei d valoarea ariei dreptunghiului respectiv?
Raspuns : d

3.Se consideră un arbore cu rădăcină în care doar 13 dintre nodurile sale au exact 2
descendenţi direcţi (fii), restul nodurilor având cel mult un descendent direct (fiu). Care este numărul frunzelor arborelui?
Raspuns : 14

4.Fie s o variabilă ce memorează un şir de caractere, c o variabilă de tip char, iar i şi j două variabile de tip int. Scrieţi instrucţiunile ce pot înlocui punctele de suspensie din secvenţa de program alăturată astfel încât executarea ei să determine
modificarea conţinutul şirului s prin interschimbarea caracterelor aflate pe poziţii simetrice faţă de mijlocul şirului (primului caracter cu ultimul, al doilea cu penultimul, etc).
Raspuns : c=s[i];
s[i]=s[j];
s[j]=c;
i++;
j--;


Varianta 6
1.Care dintre următoarele expresii reprezintă un element al tabloului
bidimensional a, declarat alăturat?
Raspuns : c
2.Se consideră o listă liniară simplu înlănţuită alocată dinamic, cu cel puţin două
elemente. Fiecare element al listei reţine în câmpul urm adresa elementului următor din listă sau NULL dacă nu există un element următor.Ştiind că variabila p reţine adresa primului element din listă, care dintre expresiile următoare
poate înlocui punctele de suspensie în secvenţa de instrucţiuni de mai sus astfel încât, în urma executării acesteia, să fie eliminat ultimul element al listei?
Raspuns : b

3.Se consideră un arbore cu 11 muchii. Care este numărul de noduri ale arborelui?
Raspuns : 12

4.Se consideră un graf neorientat G cu 12 noduri si 7 muchii. Care este numărul maxim de componente conexe din care poate fi format graful G?
Raspuns : 8 componente conexe

Varianta 7
1.Care dintre variantele de mai jos reprezintă declararea eficientă şi corectă a unui tablou bidimensional cu exact 20 de elemente, numere întregi cu cel mult 4 cifre fiecare?
Raspuns : a
2.O listă liniară simplu înlănţuită cu cel puţin două elemente, alocată dinamic, reţine în câmpul info al fiecărui element câte un număr natural de maximum 4 cifre, iar în câmpul urm adresa elementului următor din listă sau NULL dacă nu există un element următor.Dacă variabila p reţine adresa primului element al listei atunci, în urma executării secvenţei de program de mai sus se afişează întotdeauna:
Raspuns : b

3.Se consideră graful neorientat definit prin mulţimea vârfurilor {1,2,3,4,5,6} şi mulţimea muchiilor {[1,2],[2,3],[3,4],[3,5],[4,5],[1,3],[2,6],[2,4],[4,6]}.
Care este numărul minim de muchii ce pot fi eliminate astfel încât graful parţial obţinut să nu mai fie conex?
Raspuns : 2
4.Se consideră graful orientat cu 6 noduri reprezentat prin matricea de adiacenţă alăturată. Care este numărul tuturor grafurilor parţiale distincte ale grafului dat? Doua grafuri parţiale sunt distincte dacă matricele lor de adiacenţă sunt diferite. Raspuns : 128


Varianta 8

1.Se consideră graful orientat reprezentat prin listele de adiacenţă alăturate. Câte noduri au gradul extern mai mare decât gradul intern?
Raspuns : b

2.Se consideră un graf neorientat cu 50 noduri şi 32 muchii. Care este numărul maxim de vârfuri cu gradul 0 pe care le poate avea graful?
Raspuns : c

3.Ce se afişează în urma executării secvenţei de program alăturate dacă variabila s memorează şirul de caractere abcdefgh?
Raspuns : abefgh 6

4.Într-o listă liniară simplu înlănţuită cu cel puţin 4 elemente, fiecare element reţine în câmpul urm adresa elementului următor sau NULL dacă nu există un element următor, iar în câmpul info o valoare întreagă. Ştiind că variabila p reţine adresa primului element din listă, înlocuiţi punctele de suspensie cu expresiile corespunzătoare, astfel încât secvenţa alăturată să calculeze în variabila s suma tuturor valorilor elementelor listei.
Raspuns : s=p->info;
while(p)
{p=p->urm;
s=s+p->info;}
cout<

Varianta9
1.Considerând declararea alăturată, care dintre următoarele secvenţe realizează în mod corect citirea de la tastatură a valorilor celor două câmpuri ale variabilei x? Raspuns : a

2.Într-o listă liniară simplu înlănţuită fiecare element reţine în câmpul info o valoare întreagă, iar în câmpul urm adresa elementului următor din listă sau NULL dacă nu există un element următor. Variabila p reţine adresa primului element din listă. Lista conţine, în această ordine, pornind de la primul element, valorile: 2, 3, 4, 5, 6, 7, 8. Ce se va afişa în urma executării secvenţei de instrucţiuni alăturată?
Raspuns : a

3.Se consideră un graf orientat cu 6 noduri care are următoarele proprietăti:
- suma gradelor externe ale tuturor vârfurilor grafului este egală cu 6
- sunt numai 3 vârfuri care au gradul intern egal cu 1
Care este valoarea maximă pe care o poate avea gradul extern al unui vârf din graful dat?
Raspuns : 3

4.Se consideră declararea de mai jos: char s[50], x[50]; Ce se afişează în urma executării secvenţei de program scrisă alăturat dacă variabila s memorează şirul abcdefg?
Raspuns : abcd123efg


Varianta 10
1.Considerând declararea alăturată, care dintre următoarele secvenţe de instrucţiuni afişează valorile memorate în cele două câmpuri ale variabilei x, separate printr-un spaţiu?
Raspuns : a

2.Într-o listă liniară simplu înlănţuită fiecare element reţine în câmpul info o valoare întreagă, iar în câmpul urm adresa elementului următor din listă sau NULL dacă nu există un element următor. Variabila p reţine adresa primului element din listă. Lista conţine, începând de la primul element, în această ordine, valorile: 2, 3, 4, 5, 6, 7, 8. Ce se va afişa în urma executării secvenţei de instrucţiuni alăturate?
Raspuns : d

3.Se consideră un graf neorientat cu 80 de noduri şi 3560 muchii. Care este numărul de muchii ce pot fi eliminate astfel astfel încât graful parţial obţinut să fie arbore?
Raspuns : 3081

4.Ce se va afişa în urma executării secvenţei de instrucţiuni alăturate dacă variabila s memorează şirul de caractere abbacdde, iar variabila i este de tip întreg?
Raspuns : abacde

Teorie Grafuri Neorientate

Definitie : Se numeste graf neorientat G o pereche de multimi (X,), unde X este
o multime finita si nevida de elemente, iar U o multime de perechi cu elemente distincte din multimea X.

Terminologie:

Elementele multimii X se numesc noduri sau varfuri. Multimea X se mai numeste si multimea nodurilor sau varfurilor.

Ordinul grafului reprezinta numarul de noduri ale grafului.

Elementele multimii U se numesc muchii. Multimea U se mai numeste si multimea muchiilor.

Numim noduri adiacente orice pereche de noduri care formeaza o muchie. Fiecare din cele doua noduri spunem, ca sunt incidente cu muchia pe care o formeaza.

Se numesc muchii incidente doua muchii care au o extremitate comuna.


In memoria calculatorului un graf neorientat se reprezinta cu ajutorul matricii de adiacenta notata cu A(i,j).









Matricea de adiacenta este o matrice patratica si simetrica fata de diagonala principala.
Exemplu de matrice patratica:

Definitie: Gradul unui nod x al grafului G este egal cu numarul muchiilor incidente cu nodul si se noteaza cu d(x).
Terminologie:
Se numeste nod terminal un nod care are gradul egal cu 1.
Se numeste nod izolat un nod care are gradul 0.



X={1,2,3,4,5,6}
U={(1,2),(1,6),(2,6),(3,5)}
nodurile 1 si 2 sunt nodurile vecine nodului 6;
nodurile 5 si 3 sunt noduri terminale;
nodul 4 este nod izolat.








Teoreme:

Numarul total de grafuri cu n noduri este:

2.Suma gradelor tuturor nodurilor unui graf neorientat este egala cu dublul numarului de muchii.
3.Daca graful G neorientat are n noduri, n>2, atunci cel putin 2 noduri au acelasi grad.
4.Pentru orice grad neorientat numarul nodurilor de grad impar este par.
5.Numarul minim de muchii pe care trebuie sa le aiba un graf neorientat cu n noduri, ca sa nu existe noduri izolate este:

Se numeste lant intr-un graf neorientat o succesiune de varfuri cu proprietatea ca intre oricare doua varfuri(noduri) alaturate exista o muchie.
Numim lant elementar o succesiune de varfuri care respecta proprietatea de lant si-n care oricare doua varfuri sunt distincte. In caz contrar lantul se numeste neelementar.
Lanturile sunt:
-simple: o succesiune de varfuri cu proprietatea ca fiecare muchie este vizitata o singura data.
-compuse: in care o muchie este vizitata de doua ori.
Se numeste ciclu intr-un lant neorientat o succesiune de varfuri cu proprietatea ca primul nod coincide cu ultimul.

Se numeste graf partial notat cu Gp=(x,v), cu proprietatea ca multimea v de perechi de varfuri este inclusa in multimea x.



imaginea 2

imaginea 1



Imaginea 1 prezinta un graf oarecare iar imaginea 2 prezinta graful partial al primului prin eliminarea muchilor (1,2) si (2,4).



Se numeste subgraf al unui graf G(X,U) , un graf Gs=(y,v) cu proprietatea ca multimea y<=X si v<=U si v este formata din valori distincte ale multimii y.


Am transformat din graf in subgraf eliminand un nod:


Matricea si graful dupa eliminarea nodului:






Grafuri speciale:
-graful nul: graful care are multimea U=0;
-graful complet cu noduri: graful care are intre oricare doua noduri adiacente o muchie.


Exemplu de graf complet: