Varianta 96 (Subiectul II)
1. Care este numărul maxim de valori egale care pot să apară într-un vector cu legături „de tip tată” asociat unui arbore cu rădăcină care conţine 10 noduri?
a. cel mult b. 10 c. nu pot să apară valori egale într-un vector cu legături de tip tată d. 29
Raspunsul corect este b.
Arborele are o radacina care contine 10 noduri.
Varianta 97 (Subiectul II)
1.Se considera un graf neorientat cu 5 noduri si 3 muchii.Care este numarul maxim de noduri cu grad 1 care pot exista in graf?
a.2 b.3 c.4 d.5
Raspunsul corect este c.
Nodurile 1,2,3 si 4 din graful neorientat din imagine au gradul 1,rezulta numarul maxim de noduri cu grad 1 care pot exista intr-un graf neorientat cu 5 noduri si 3 muchii este 4.
2. Se consideră un arbore cu rădăcină memorat cu ajutorul vectorului de ”taţi” T=(2,0,1,1,1,2). Stabiliţi care dintre nodurile arborelui sunt situate pe nivelul 3, dacă rădăcina este situată pe nivelul 1?
2. Se consideră un arbore cu rădăcină memorat cu ajutorul vectorului de ”taţi” T=(2,0,1,1,1,2). Stabiliţi care dintre nodurile arborelui sunt situate pe nivelul 3, dacă rădăcina este situată pe nivelul 1? a.3 4 5 b.1 c. 2 6 d.1 2 6
Raspunsul corect este a.
Conform desenului rezulta foarte evident ca nodurile 3,4 si 5 sunt situate pe nivelul 3 al arborelui.
Varianta 98 (Subiectul II)
1.Fie graful orientat G cu 5 vârfuri, numerotate cu 1,2,3,4,5, şi arcele (1,2), (1,3), (1,4),(2,3), (4,2), (4,5), (5,2), (2,4). Care dintre următoarele vârfuri au gradul extern egal cu gradul intern?
a. 2 şi 4 b. 4 şi 5 c. 1 şi 2 d. 3 şi 4
a. 2 şi 4 b. 4 şi 5 c. 1 şi 2 d. 3 şi 4
Raspunsul corect este b. d+(1)=3 d-(1)=0
d+(2)=2 d-(2)=3
d+(3)=0 d-(3)=2
d+(4)=2 d-(4)=2
d+(5)=1 d-(5)=1 d+(3)=0 d-(3)=2
d+(4)=2 d-(4)=2
rezulta varfurile 4 si 5 au gradul extern egal cu gradul intern.
Varianta 99 (Subiectul II)
1.Considerăm un graf orientat cu 7 noduri, numerotate de la 1 la 7, şi arcele: (1,6), (2,1),(3,1), (3,4), (3,5), (6,2), (7,3). Care este lungimea maximă a unui circuitelementar care se poate obţine în graf prin adăugarea unui singur arc? Lungimea unui circuit reprezintă numărul arcelor ce unesc nodurile circuitului. Un circuit este elementar dacă este format doar din noduri distincte, cu excepţia primului nod, care coincide cu ultimul.
a. 6 b. 4 c. 3 d. 5 Raspunsul corect este d.
Prin adaugarea arcului (2,7) se obtine circuitul de lungime 5:(2,7,3,1,6,2) Varianta 100 (Subiectul II)
1. Un graf neorientat este complet dacă oricare două noduri distincte ale sale sunt adiacente.Care este numărul minim de muchii care trebuie eliminate dintr-un graf neorientat complet cu 100 de noduri astfel încât graful parţial obţinut să fie eulerian?
a. 4851 b. 0 c. 100 d. 50
Variante bac
-liste-
Varianta 76 (Subiectul II)
2. Într-o listă simplu înlănţuită fiecare element reţine în câmpul urm adresa elementului următor din listă, iar în câmpul inf un număr întreg. Adresa primului element al listei este memorată în variabila prim,variabila p este de acelaşi tip cu prim, iar variabila x este de tip întreg. Iniţial, în listă sunt memorate, în această ordine, numerele de mai jos,. Care este conţinutul listei în urma executării secvenţei de instrucţiuni scrise alăturat? (4p.)
p=prim;
while(p->urm!=NULL)
{x=p->inf;
p->inf=p->urm->inf;
p->urm->inf=x;
p=p->urm;}
a. 2 3 4 5 6 1
b. 6 5 4 3 2 1
c. 2 1 4 3 6 5
d. 1 2 3 4 5 6
Raspunsul corect este d, deoarece primul numar este 1 iar urmatoarele elemente (p->urm->inf=2) sunt in ordine consecutiva .
Varianta 77 (Subiectul II)
2.Într-o listă simplu înlănţuită fiecare element reţine în câmpul urm adresa elementului următor din listă, iar în câmpul inf un număr întreg. Adresa primului element al listei este memorată în variabila prim, iar variabilele p şi q sunt de acelaşi tip cu prim. Iniţial, în listă sunt memorate, în această ordine, numerele de mai jos. Care va fi conţinutul listei după executarea secvenţei alăturate? (4p.)
p=prim->urm;
q=p->urm;
p->urm=q->urm;
prim->urm=q;
q->urm=p;
a. 1 3 2 4 5 6
b. 6 5 4 3 2 1
c. 1 2 4 3 5 6
d. 2 1 3 4 5 6
Raspunsul corect este a,deoarece p=q=3 este elementul urmatorul dupa prim iar restul nodurilor isi pastreaza ordinea .
Varianta 100 (Subiectul II)
2.Fiecare element al unei liste simplu înlănţuite memorează în câmpul urm adresa următorului element din listă, iar variabilele k1, k2 şi k3, reţin adresele a 3 elemente succesive în listă, ca în figură. Cu ce instrucţiune se pot înlocui punctele de suspensie din secvenţa de mai jos astfel încât aceasta să determine interschimbarea corectă a poziţiilor în listă a elementelor de la adresele k2 şi k3? (4p.)
k1->urm=k3; ... k3->urm=k2;
a. k2->urm=k3->urm; b. k2->urm=k3;
c. k2->urm=k1->urm; d. k2=k3->urm;
Teorie liste
LISTE CIRCULARE SIMPLU INLANTUITE:
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 duble respectiv triple,adica contin un pointer sau doi pointeri.
Listele circulare se mai numesc si liste inchise.
In cazul listelor circulare,la operatiile specifice trebuie sa tinem cont si de legaturile existente intre ultimul nod si primul nod .
Crearea unei liste circulare se realizeaza in mod asemanator cu o lista liniara simplu inlantuita, cu deosebirea ca ultimul element adaugat in lista nu va mai avea in campul de adresa valoarea NULL, ci adresa primului element adaugat.
Creare:
Vom crea mai intai primul element al listei.
Vom utiliza pointerii : p– contine adresa primului element adaugat in lista; u – contine adresa ultimului element adaugat in lista; l – contine adresa elementului ce se adauga.
p=new nod;
cin>>p->info;
u=p;
u->urm=p;
l=new nod;
cin>>l->info;
u->urm=l;
u=l;
u->urm=p;
Afisare:
l=p;
cout<
while(l->urm!=p)
{l=l->urm;
cout<
cout<
Reprezentarea grafica pentru o lista circulara simplu inlantuita este urmatoarea:
