bac 2008- s2

Ministerul Educaiei, Cercetrii i Tineretului Centrul Naional pentru Curriculum i Evaluare n nvmntul Preuniversitar

BACALAUREAT 2008 - INFORMATIC, limbajul Pascal Subiectul II Specializarea Matematic-informatic intensiv informatic

Subiectul II (30 de puncte) - Varianta 001

Pentru fiecare dintre itemii 1 i 2 scriei pe foaia de examen litera care corespunde rspunsului corect. 1. Se consider o coad n care iniial au fost introduse, n aceast ordine, elementele cu

valorile 1 i 2: 1 2

. Se noteaz cu AD(x) operaia prin care se adaug elementul cu valoarea x n coad i cu EL operaia prin care se elimin un element din coad. Cte elemente va conine coada n urma executrii secvenei de operaii: AD(4);EL;EL;AD(5);EL;AD(3)? (4p.)

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

2. Cte grafuri neorientate, distincte, cu 4 vrfuri se pot construi? Dou grafuri se consider distincte dac matricele lor de adiacen sunt diferite. (4p.)

a. 24 b. 4 c. 46 d. 26 Scriei pe foaia de examen rspunsul pentru fiecare dintre cerinele urmtoare. 3. n declararea alturat, cmpurile x i y ale nregistrrii pot

memora coordonatele carteziene ale unui punct din planul xOy. Scriei o secven de instruciuni prin executarea creia se memoreaz n variabila C coordonatele mijlocului segmentului cu capetele n punctele ale cror coordonate sunt memorate n variabilele A i B. (6p.)

type punct=record x,y:real end; var A,B,C:punct;

4. Prin nlimea unui arbore cu rdcin nelegem numrul de muchii ale celui mai lung lan format din noduri distincte care are una dintre extremiti n rdcina arborelui. Scriei care este nlimea i care sunt frunzele arborelui descris prin urmtorul vector de tai: (6,6,5,0,6,4,4,7). (6p.)

Scriei un program Pascal care citete de la tastatur dou numere naturale nenule n i m (2m10, 2n10) i care construiete n memorie i apoi afieaz o matrice A cu n linii (numerotate de la 1 la n) i m coloane (numerotate de la 1 la m) cu proprietatea c fiecare element Aij memoreaz cea mai mic dintre valorile indicilor i i j (1in, 1jm). Matricea se va afia pe ecran, cte o linie a matricei pe cte o linie a ecranului, elementele fiecrei linii fiind separate prin cte un spaiu.

5.

Exemplu: pentru n=4 i m=5 se va afia matricea alturat. (10p.)

1 1 1 1 1 1 2 2 2 2 1 2 3 3 3 1 2 3 4 4




Pentru fiecare dintre itemii 1 i 2 scriei pe foaia de examen litera care corespunde rspunsului corect.

1. Cte grafuri orientate, distincte, cu 4 vrfuri se pot construi? Dou grafuri se consider distincte dac matricele lor de adiacen sunt diferite. (4p.)

a. 46 b. 26 c. 64 d. 4

2. Variabila d, declarat alturat, memoreaz n cmpurile a i b limea i, respectiv, lungimea unui dreptunghi. Care dintre urmtoarele instruciuni atribuie cmpului p al variabilei d valoarea perimetrului dreptunghiului respectiv? (4p.)

type dreptunghi=record a,b,p:real end; var d:dreptunghi;

a. p.d:=2*(d.a+d.b); b. p.d:=2*a.d+2*b.d; c. d.p:=2*d.a+2*d.b; d. d.p=2*d.a+2*d.b;

Scriei pe foaia de examen rspunsul pentru fiecare dintre cerinele urmtoare. 3. Se consider o stiv n care iniial au fost introduse, n aceast ordine,

elementele cu valorile 1, 2 i 3, ca n figura alturat. Se noteaz cu AD(x) operaia prin care se adaug elementul cu valoarea x n vrful stivei i cu EL operaia prin care se elimin elementul din vrful stivei. Care sunt valorile ultimelor dou elemente eliminate din stiv n urma executrii secvenei de operaii: AD(4);EL;EL;AD(5);EL;EL? (6p.)

1

2

3 vrf

baza

4. n secvena alturat, variabila a memoreaz o matrice cu n linii i n coloane (numerotate de la 1 la n) cu elemente numere ntregi, iar toate celelalte variabile sunt ntregi. tiind c n este un numr natural par, nenul, scriei instruciunile ce pot pot nlocui punctele de suspensie din secvena de program alturat astfel nct, n urma executrii acesteia, s se afieze suma elementelor numere naturale impare de pe linia k a matricei a. (6p.)

s:=0; for j:=1 to n div 2 dobegin .............

end;

writeln(s);

5. S se scrie un program Pascal care citete de la tastatur un cuvnt format din cel mult 20 de caractere, doar litere mici ale alfabetului englez. Programul determin transformarea cuvntului citit prin nlocuirea fiecrei vocale a cuvntului, cu litera mare corespunztoare, restul literelor nemodificndu-se, ca n exemplu. Programul afieaz pe ecran cuvntul obinut, pe o singur linie. Se consider vocale literele din mulimea {a,e,i,o,u}. Exemplu: pentru cuvntul bacalaureat se va afia pe ecran: bAcAlAUrEAt (10p.)





1. Se consider un graf orientat cu 6 noduri numerotate de la 1 la 6 i cu mulimea arcelor format doar din arcele: - de la fiecare nod numerotat cu un numr neprim i (i>1) la toate nodurile numerotate cu numere ce aparin mulimii divizorilor proprii ai lui i (divizori diferii de 1 i de i) - de la nodul numerotat cu 1 la nodul numerotat cu 6 - de la fiecare nod numerotat cu un numr prim i la nodul numerotat cu i-1 Pentru graful dat, care este lungimea celui mai mare drum, format doar din noduri distincte? (4p.)

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

2. Cte frunze are arborele cu rdcin descris prin urmtorul vector de tai: (6,5,5,2,0,3,3,3,8,7,7)? (4p.)

a. 1 b. 2 c. 5 d. 4 Scriei pe foaia de examen rspunsul pentru fiecare dintre cerinele urmtoare. 3. n declararea alturat, cmpurile x i y ale nregistrrii pot

memora numrtorul, respectiv numitorul unei fracii. Scriei secvena de instruciuni prin executarea creia se construiete n variabila f o fracie obinut prin nsumarea fraciilor memorate n variabilele f1 i f2. (6p.)

type fractie =record x,y:integer

end; var f,f1,f2:fractie;

n secvena de instruciuni de mai jos, variabila s memoreaz un ir de caractere format doar din litere ale alfabetului englez, iar variabila i este de tip integer.

4.

tiind c n urma executrii secvenei s-a afiat succesiunea de caractere eied*eael* scriei care este irul de caractere memorat de variabila s. (6p.)

for i:=1 to length(s) do

if s[i]=e then write(*) else write(e,s[i]);

5. Scriei un program Pascal care citete de la tastatur un numr natural n (2n24) i construiete n memorie o matrice cu n linii i n coloane ale crei elemente vor primi valori dup cum urmeaz: - elementele aflate pe diagonala principal a matricei vor primi valoarea 0 - elementele de pe prima coloan, cu excepia celui aflat pe diagonala principal vor primi valoarea n - elementele de pe a doua coloan, cu excepia celui aflat pe diagonala principal vor primi valoarea n-1 ... - elementele de pe ultima coloan, cu excepia celui aflat pe diagonala principal vor primi valoarea 1

Programul va afia matricea astfel construit pe ecran, cte o linie a matricei pe cte o linie a ecranului, cu cte un spaiu ntre elementele fiecrei linii (ca n exemplu). Exemplu: pentru n=4 se va afia matricea alturat. (10p.)

0 3 2 1 4 0 2 1

4 3 0 1 4 3 2 0




Pentru fiecare dintre itemii 1 i 2 scriei pe foaia de examen litera care corespunde rspunsului corect. 1. Se consider un graf orientat cu 6 noduri numerotate de la 1 la 6 i cu mulimea arcelor

format doar din arcele: - de la fiecare nod numerotat cu un numr neprim i (i>1) la toate nodurile numerotate cu numere ce aparin mulimii divizorilor proprii ai lui i (divizori diferii de 1 i de i); - de la nodul numerotat cu 1 la nodul numerotat cu 6; - de la fiecare nod numerotat cu un numr prim i la nodul numerotat cu i-1. Pentru graful dat, care este lungimea celui mai mare drum, format doar din noduri distincte, ce unete nodul 6 cu nodul 1? (4p.)

a. 1 b. 3 c. 4 d. 6

2. Cte frunze are arborele cu rdcin, cu 8 noduri, numerotate de la 1 la 8, descris prin urmtorul vector de tai: (6,5,5,2,0,3,3,3)? (4p.)

a. 4 b. 6 c. 5 d. 3 Scriei pe foaia de examen rspunsul pentru fiecare dintre cerinele urmtoare.

3. Se consider o stiv n care iniial au fost introduse, n aceast ordine, elementele cu valorile 1, 2 i 3, ca n figura alturat. Se noteaz cu AD(x) operaia prin care se adaug elementul cu valoarea x n vrful stivei i cu EL operaia prin care se elimin elementul din vrful stivei. Reprezentai, dup modelul alturat, coninutul stivei rezultat n urma executrii secvenei de operaii: AD(4);EL;EL;AD(5);EL. (6p.)

1

2

3 vrf

baza

4. Fie s o variabil ce memoreaz un ir de caractere, format doar din litere ale alfabetului englez, i i o variabil de tip integer. Scriei instruciunile ce pot nlocui punctele de suspensie din secvena de program alturat astfel nct executarea ei s determine eliminarea tuturor literelor mici din irul s i apoi afiarea irului obinut. (6p.)

i:=1; while i





1. ntr-un graf neorientat cu 20 muchii, fiecare nod al grafului are gradul un numr nenul. Doar patru dintre noduri au gradul un numr par, restul nodurilor avnd gradele numere impare. Care este numrul maxim de noduri pe care poate s le aib graful? (4p.)

a. 32 b. 36 c. 10 d. 16

2. Variabila d, declarat alturat, memoreaz n cmpurile a i b limea i, respectiv, lungimea unui dreptunghi. Care dintre urmtoarele instruciuni atribuie cmpului aria al variabilei d valoarea ariei dreptunghiului respectiv? (4p.)

type dreptunghi=record a,b,aria:real end; var d:dreptunghi;

a. d.aria=d.a*d.b; b. aria.d:=a.d*b.d; c. aria.d:=d.a*d.b; d. d.aria:=d.a*d.b;

Scriei pe foaia de examen rspunsul pentru fiecare dintre cerinele urmtoare. 3. Se consider un arbore cu rdcin n care doar 13 dintre nodurile arborelui au exact 2

descendeni direci (fii), restul nodurilor avnd cel mult un descendent direct (fiu). Care este numrul frunzelor arborelui? (6p.)

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 integer. Scriei instruciunile ce pot nlocui punctele de suspensie din secvena de program alturat astfel nct executarea ei s determine modificarea coninutul irului s prin interschimbarea caracterelor aflate pe poziii simetrice fa de mijlocul irului (primului caracter cu ultimul, al doilea cu penultimul, etc). (6p.)

i:=1; j:=length(s); while i





1. Care dintre urmtoarele expresii reprezint un element al tabloului bidimensional a,declarat alturat? (4p.)

var a:array[1..5,1..6] of integer;

a. a[40] b. a[6,7] c. a[2,3] d. a[10*5]

2. Se consider o list liniar simplu nlnuit alocat dinamic, cu cel puin dou elemente. Fiecare element al listei reine n cmpul urm adresa elementului urmtor din list sau nil dac nu exist un element urmtor.

while ... do p:=p^.urm; dispose(p^.urm); p^.urm:=nil;

tiind c variabila p reine adresa primului element din list, care dintre expresiile urmtoare poate nlocui punctele de suspensie n secvena de instruciuni de mai sus astfel nct, n urma executrii acesteia, s fie eliminat ultimul element al listei? (4p.)

a. p^.urm^.urmnil b. p^.urmnil c. pnil d. p^.urm^.urm:=nil

Scriei pe foaia de examen rspunsul pentru fiecare dintre cerinele urmtoare.

3. Se consider un arbore cu 11 muchii. Care este numrul de noduri ale arborelui? (6p.)

4. Se consider un graf neorientat G cu 12 noduri si 7 muchii. Care este numrul maxim de componente conexe din care poate fi format graful G? (6p.)

5. Se consider un text cu maximum 255 de caractere n care cuvintele sunt separate prin unul sau mai multe spaii. Primul caracter din textul citit este o liter, iar cuvintele sunt formate numai din litere mici ale alfabetului englez. Scriei un program Pascal care citete de la tastatur textul i l transform, nlocuind prima liter a fiecrui cuvnt cu litera mare corespunztoare, restul caracterelor rmnnd nemodificate. Textul astfel transformat va fi afiat pe ecran. Exemplu: dac de la tastatur se introduce textul: mare frig rosu se va afia pe ecran: Mare Frig Rosu (10p.)




Pentru fiecare dintre itemii 1 i 2 scriei pe foaia de examen litera care corespunde rspunsului corect. 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? (4p.) a. var a:array[1..2,1..10] of integer; b. var a:array[1.. 40]of real; c. var a:array[1..2,1..10]of char; d. var a:array[1..40] of integer;

2. O list liniar simplu nlnuit cu cel puin dou elemente, alocat dinamic, reine n cmpul info al fiecrui element cte un numr natural de maximum 4 cifre, iar n cmpul urm adresa elementului urmtor din list sau nil dac nu exist un element urmtor.

while p^.urmnil do begin if p^.urm^.info < p^.info then p^.urm^.info:=p^.info; p:=p^.urm end; write(p^.info);

Dac variabila p reine adresa primului element al listei atunci, n urma executrii secvenei de program alturate se afieaz ntotdeauna: (4p.)

a. cea mai mic dintre valorile memorate de elementele din list.

b. cea mai mare dintre valorile memorate de elementele din list.

c. valoarea memorat de penultimul element din list.

d. valoarea memorat de primul element din list.

Scriei pe foaia de examen rspunsul pentru fiecare dintre cerinele urmtoare. 3. Se consider graful neorientat cu mulimea vrfurilor {1,2,3,4,5,6} i mulimea muchiilor

{[1,2],[2,3],[3,4],[3,5],[4,5],[1,3],[2,6],[2,4],[4,6]} . Care este numrul minim de muchii ce pot fi eliminate astfel nct graful parial obinut s nu mai fie conex? (6p.)

4. Se consider graful orientat cu 6 noduri, reprezentat prin matricea de adiacen alturat. Care este numrul tuturor grafurilor pariale distincte ale grafului dat? Doua grafuri partiale sunt distincte daca matricele lor de adiacen sunt diferite. (6p.)

0 1 0 1 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 0

5. Se consider un text cu maximum 255 de caractere, format din litere mici ale alfabetului englez i spaii. Textul conine cel puin o consoan. Scriei un program Pascal care citete de la tastatur textul i apoi determin transformarea acestuia, eliminnd numai ultima consoan care apare n text, ca n exemplu. Programul va afia pe ecran textul obinut. Exemplu: dac de la tastatur se introduce textul: mare frig saci pe ecran se va afia: mare frig sai (10p.)





1. Se consider graful orientat reprezentat prin listele de adiacen alturate. Cte noduri au gradul extern mai mare dect gradul intern? (4p.)

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

2. Se consider un graf neorientat cu 50 noduri i 32 muchii. Care este numrul maxim de vrfuri cu gradul 0 pe care le poate avea graful? (4p.)


3. Ce se afieaz n urma executrii secvenei alturate de program, dac variabila s memoreaz irul de caractere abcdefgh? (6p.)

delete(s,3,2); write(s, ,length(s));

4. ntr-o list liniar simplu nlnuit cu cel puin 4 elemente, fiecare element reine n cmpul urm adresa elementului urmtor sau nil dac nu exist un element urmtor, iar n cmpul info o valoare ntreag. tiind c variabila p reine adresa primului element din list, nlocuii punctele de suspensie cu expresiile corespunztoare, astfel nct secvena alturat s calculeze n variabila s suma tuturor valorilor elementelor listei. (6p.)

s:=; while do begin p:=p^.urm; s:=s+p^.info end; write(s);

5. Scriei un program Pascal care citete de la tastatur dou numere naturale n i p (2n20, 1p20) i construiete n memorie un tablou bidimensional cu n linii i p coloane. Tabloul va fi construit astfel nct, parcurgnd tabloul linie cu linie de sus n jos i fiecare linie de la stnga la dreapta, s se obin irul primelor n*p ptrate perfecte impare, ordonat strict cresctor, ca n exemplu. Tabloul astfel construit va fi afiat pe ecran, fiecare linie a tabloului pe cte o linie a ecranului, cu cte un spaiu ntre elementele fiecrei linii.

Exemplu: pentru n=2, p=3 programul va afia tabloul alturat: (10p.)

1 9 25 49 81 121




Pentru fiecare dintre itemii 1 i 2 scriei pe foaia de examen litera care corespunde rspunsului corect. 1. Considernd declararea alturat, care dintre urmtoarele

secvene de instruciuni realizeaz n mod corect citirea de la tastatur a valorilor celor dou cmpuri ale variabilei x? (4p.)

type p=record

a,b:integer

end; var x:p;

a. read(x.a,x.b) b. read(a.x,b.x) c. read(a->x,b->x) d. read(x)

2. ntr-o list liniar simplu nlnuit fiecare element reine n cmpul info o valoare ntreag, iar n cmpul urm adresa elementului urmtor din list sau nil dac nu exist un element urmtor. Variabila p reine adresa primului element din list.

while (p^.urmnil)and(pnil)do

begin

write(p^.info, );

p^.urm:=p^.urm^.urm;

p:=p^.urm end;

Lista conine, n aceast ordine, pornind de la primul element, valorile: 2, 3, 4, 5, 6, 7, 8. Ce se va afia n urma executrii secvenei de instruciuni de mai sus? (4p.)

a. 2 4 6 b. 2 4 6 8 c. 2 4 8 d. 2 5 8 Scriei pe foaia de examen rspunsul pentru fiecare dintre cerinele urmtoare. 3. Se consider un graf orientat cu 6 noduri care are urmtoarele proprietti:

- suma gradelor externe ale tuturor vrfurilor grafului este egal cu 6 - sunt numai 3 vrfuri care au gradul intern egal cu 1

Care este valoarea maxim pe care o poate avea gradul extern al unui vrf din graful dat?(6p.) 4. Se consider declararea de mai jos:

var s,x:string[50];

Ce se afieaz n urma executrii secvenei de program alturate dac variabila s memoreaz irul abcdefg? (6p.)

x:=copy(s,5,3); delete(s,5,3); s:=s+123+x; write(s);

5. Se consider tabloul bidimensional cu n linii i n coloane ce conine numere naturale cu cel mult patru cifre fiecare. Scriei programul Pascal care citete de la tastatur numrul natural n (2n23) i cele n*n elemente ale tabloului i apoi afieaz pe ecran elementele primului ptrat concentric, separate prin cte un spaiu. Ptratul este parcurs n sensul acelor de ceasornic ncepnd din colul su stnga-sus, ca n exemplu. Primul ptrat concentric este format din prima i ultima linie, prima i ultima coloan a tabloului.

Exemplu: pentru n=5 i tabloul alturat, se va afia: 1 2 3 4 5 1 6 2 7 6 5 4 3 7 2 6 (10p.)

1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7





1. Considernd declararea alturat, care dintre urmtoarele secvene de instruciuni afieaz valorile memorate n cele dou cmpuri ale variabilei x, separate printr-un spaiu? (4p.)

type p=record

a,b:integer

end; var x:p;

a. write(x.a, ,x.b); b. write(a.x, ,b.x); c. write(x); d. write(a->x, ,b->x);

ntr-o list liniar simplu nlnuit fiecare element reine n cmpul info o valoare ntreag, iar n cmpul urm adresa elementului urmtor din list sau nil dac nu exist un element urmtor. Variabila p reine adresa primului element din list.

2.

Lista conine, ncepnd de la primul element, n aceast ordine, valorile: 2, 3, 4, 5, 6, 7, 8. Ce se va afia n urma executrii secvenei de instruciuni alturate? (4p.)

while (p^.urmnil)and(pnil)do begin p^.urm:=p^.urm^.urm; p:=p^.urm; write(p^.info, ) end;

a. 2 5 8 b. 2 4 8 c. 2 4 6 8 d. 4 6 8

Scriei pe foaia de examen rspunsul pentru fiecare dintre cerinele urmtoare. 3. Se consider un graf neorientat cu 80 de noduri i 3160 muchii. Care este numrul de

muchii ce pot fi eliminate astfel astfel nct graful parial obinut s fie arbore? (6p.) 4. Ce se va afia n urma executrii secvenei de

instruciuni alturate dac variabila s memoreaz irul de caractere abbacdde, iar variabila i este de tip ntreg? (6p.)

i:=1; while i



Subiectul II (30 de puncte) - Varianta 011 Pentru fiecare dintre itemii 1 i 2 scriei pe foaia de examen litera care corespunde rspunsului corect. 1. Se consider graful orientat reprezentat prin matricea de

adiacen alturat. Care este lungimea maxim a unui drum de la vrful 4 pn la vrful 6 format din vrfuri distincte dou cte dou (lungimea unui drum este egal cu numrul de arce care compun acel drum)? (4p.)

0 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 1 0 1 1 0 0 0 1 1 0 1 0 0 0

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

2. Care este numrul de grafuri orientate cu 4 vrfuri, fr circuite de lungime 1 (bucle)? (4p.) a. 1048576 b. 16 c. 64 d. 4096

Scriei pe foaia de examen rspunsul pentru fiecare dintre cerinele urmtoare. 3. Ce se afieaz pe ecran n urma executrii secvenei de

program alturate, n care variabila s memoreaz un ir cu cel mult 12 caractere, iar i este de tip ntreg? (6p.)

s:='abracadabra'; writeln(length(s)); i:=1; while i



Subiectul II (30 de puncte) - Varianta 012 Pentru fiecare dintre itemii 1 i 2 scriei pe foaia de examen litera care corespunde rspunsului corect.

1. Un graf orientat este reprezentat prin matricea de adiacen dat alturat. Care sunt nodurile pentru care gradul interior este mai mare dect gradul exterior? (4p.)

0 1 1 0 0 0 0 0 1 1 0 1 1 1 0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 1 0

a. 2, 4, 5, 6 b. 2, 4, 5 c. 1, 4, 5 d. 1, 3, 6

ntr-o list liniar simplu nlnuit, fiecare element reine n cmpul inf un numr ntreg, iar n cmpul ref adresa urmtorului nod din list sau NIL n cazul ultimului nod al listei. Adresa primului element al listei este reinut n variabila prim, iar p este o variabil de acelai tip cu prim. Dac n list sunt memorate, n aceast ordine, numerele 1, 2, 3, 4 ca n figura de mai jos, care va fi coninutul listei n urma executrii secvenei alturate de instruciuni? (4p.)

2.

p:=prim^.ref^.ref; prim^.ref^.ref:=p^.ref; p^.ref:=prim^.ref; prim^.ref:=p;

a. 1 3 2 4 b. 1 2 4 3 c. 1 4 2 3 d. 1 4 3 2 Scriei pe foaia de examen rspunsul pentru fiecare dintre cerinele urmtoare. 3. Pentru arborele cu rdcin avnd urmtorul vector de de tai

tata=(2,0,2,3,2,3,4,4,3), care este rdcina arborelui i care sunt descendenii direci (fiii) ai nodului 3? (6p.)

4. Scriei ce se afieaz pe ecran n urma executrii secvenei de program alturate, n care variabila s memoreaz un ir de cel mult 12 caractere, iar variabila i este de tip ntreg. (6p.)

s:='abcdefghoid'; writeln(length(s)); for i:=1 to length(s) do if pos(s[i],'aeiou')>0 then s[i]:=chr(ord(s[i])-ord('a')+ord('A')); writeln(' ',s);

Scriei un program Pascal care citete de la tastatur un numr natural n (2




1. Care este vectorul "de tai" pentru arborele cu rdcin din figura alturat? (4p.)

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

2. O list liniar simplu nlnuit, alocat dinamic, memoreaz n cmpul ref al fiecrui nod adresa urmtorului nod din list sau nil n cazul n care nu exist un nod urmtor. Lista conine cel puin 5 noduri, adresa primului nod este memorat n variabila p, iar variabilele a i b sunt de acelai tip cu p. Adresa crui nod va fi memorat n variabila b, dup executarea secvenei alturate de program? (6p.)

a:=p; while a^.refnil do begin b:=a; a:=a^.ref end;

a. Nodul aflat n mijlocul listei b. Penultimul nod al listei c. Ultimul nod al listei d. Nodul al treilea din list

Scriei pe foaia de examen rspunsul pentru fiecare dintre cerinele urmtoare. 3. Scriei listele de adiacen prin care este reprezentat un graf neorientat conex, cu 6 noduri,

numerotate de la 1 la 6, care este eulerian, dar NU este hamiltonian. (4p.)

4. Scriei ce se afieaz pe ecran n urma executrii secvenei de program alturate, n care variabila s memoreaz un ir de cel mult 12 caractere, iar variabila i este de tip ntreg. (6p.)

s:='abcdefghoid'; i:=1; writeln(length(s)); while i0 then delete(s,i,1) else i:=i+1; writeln(' ',s);




Subiectul II (30 de puncte) - Varianta 014 Pentru fiecare dintre itemii 1 i 2 scriei pe foaia de examen litera care corespunde rspunsului corect. 1. Se consider un graf neorientat cu 5 noduri, etichetate cu literele a, b, c, d, e, n care orice

nod etichetat cu o vocal este adiacent cu toate nodurile etichetate cu consoane, iar orice nod etichetat cu o consoan este adiacent cu toate nodurile etichetate cu vocale. Cte muchii are acest graf? (4p.)

a. 12 b. 6 c. 4 d. 3

ntr-o list liniar simplu nlnuit, alocat dinamic, fiecare element reine n cmpul inf un numr ntreg, iar n cmpul ref adresa urmtorului nod din list sau NIL n cazul ultimului element al listei.

2.

Adresa primului element al listei este reinut n variabila prim, iar variabila p este de acelai tip cu prim. Dac n list sunt memorate, n aceast ordine, numerele 3, 5, 18, 20, ce se va afia pe ecran n urma executrii secvenei alturate de program? (6p.)

p:=prim; s:=0; while p^.refNIL do begin if p^.inf mod 50 then s:=s+p^.inf; p:=p^.ref end; writeln(' ',s);

a. 21 b. 25 c. 5 d. 46 Scriei pe foaia de examen rspunsul pentru fiecare dintre cerinele urmtoare. 3. Ce se afieaz pe ecran n urma executrii secvenei de

program alturate, n care variabila s memoreaz un ir cu cel mult 10 caractere, iar variabilele i i j sunt de tip ntreg? (4p.)

s:='abcduecda'; i:=1; j:=length(s); writeln(length(s)); while i




ntr-o list liniar simplu nlnuit, alocat dinamic, fiecare element reine n cmpul ref adresa urmtorului nod din list sau NIL n cazul ultimului element al listei, iar n cmpul inf un numr ntreg.

1.

Adresa primului element al listei este reinut n variabila prim, iar p este o variabil de acelai tip cu prim. Ce va afia pe ecran secvena alturat? (6p.)

p:=prim; while (p^.inf mod 2=0) and (pNIL) do p:=p^.ref; if pNIL then writeln(p^.inf) else writeln('NU');

a. Toate valorile impare din list dac astfel de valori exist i NU n caz contrar.

b. Toate valorile pare din list dac astfel de valori exist i NU n caz contrar.

c. Prima valoare impar din list, dac aceasta exist i NU n caz contrar.

d. Prima valoare par din list, dac aceasta exist i NU n caz contrar.

2. Ci frai are nodul 1 din arborele cu rdcin cu 7 noduri, numerotate de la 1 la 7, avnd urmtorul vector de tai: (5,1,5,1,0,7,5)? (4p.)

a. 3 b. 1 c. 0 d. 2 Scriei pe foaia de examen rspunsul pentru fiecare dintre cerinele urmtoare. 3. Ce se afieaz pe ecran n urma

executrii secvenei de program alturate, n care variabila s memoreaz un ir cu cel mult 10 caractere, iar variabila i este de tip ntreg? (4p.)

i:=1; s:='abaemeiut'; while i0) then begin delete(s,i,1); i:=i+1 end else i:=i+2; writeln(' ',s);

4. Se consider graful neorientat cu 8 noduri, numerotate de la 1 la 8, i muchiile [1,2], [1,6], [1,7], [2,3], [2,6], [3,6], [3,4], [4,5], [4,8], [5,6], [7,8]. Care este gradul minim al unui nod din acest graf? Care sunt nodurile care au acest grad minim? (6p.)

Scriei un program Pascal care citete de la tastatur un numr natural cu exact 5 cifre i construiete n memorie o matrice ptrat cu 6 linii i 6 coloane, numerotate de la 1 la 6, format astfel: - elementele aflate pe diagonala principal sunt toate nule; - elementele de pe linia 1, aflate deasupra diagonalei principale precum i elementele de pe coloana 1, aflate sub diagonala principal au toate valoarea egal cu cifra unitilor numrului citit; - elementele de pe linia 2, aflate deasupra diagonalei principale precum i elementele de pe coloana 2, aflate sub diagonala principal au toate valoarea egal cu cifra zecilor numrului citit, i aa mai departe, ca n exemplu.

5.

Matricea astfel construit va fi afiat pe ecran, cte o linie a matricei pe cte o linie a ecranului, elementele de pe aceeai linie fiind separate prin cte un spaiu. Exemplu: dac se citete numrul 28731 matricea construit va fi cea scris alturat. (10p.)

0 1 1 1 1 1 1 0 3 3 3 3 1 3 0 7 7 7 1 3 7 0 8 8 1 3 7 8 0 2 1 3 7 8 2 0



Subiectul II (30 de puncte) - Varianta 016 Pentru fiecare dintre itemii urmtori, scriei pe foaia de examen litera care corespunde rspunsului corect.

1. Dac n este un numr impar mai mare dect 2, un graf neorientat cu n noduri, n care fiecare nod este adiacent cu exact n-1 noduri, este ntotdeauna : (4p.)

a. arbore b. graf eulerian c. graf neconex d. graf aciclic (graf care nu conine niciun

ciclu)

2. Care dintre urmtoarele variante reprezint o declarare corect pentru o variabil x care memoreaz simultan vrsta n ani mplinii i media la bacalaureat a unui elev? (4p.)

a. var x:record media:real; varsta:byte end;

b. type x=record media:real; varsta:byte end;

c. var x.media:real; x.varsta:byte;

d. type elev=record x.media:real; x.varsta:byte end;

Scriei pe foaia de examen rspunsul pentru fiecare dintre cerinele urmtoare. 3. ntr-o list liniar simplu nlanuit, alocat dinamic, fiecare element conine n cmpul nr un

numr real, iar n cmpul urm adresa elementului urmtor. Lista are cel puin dou elemente, iar variabila x memoreaz adresa primului element din list. Cu ce pot fi completate punctele de suspensie din secvena urmtoare, astfel nct s afieze cuvntul ADEVARAT dac media aritmetic dintre valorile cmpului nr ale primelor dou elemente din list este mai mic sau cel puin egal cu 4.75, respectiv cuvntul FALS n caz contrar? if ..... then write(ADEVARAT) else write(FALS); (6p.)

4. Ce va afia secvena alturat tiind c variabila a memoreaz un ir cu cel mult 100 de caractere, iar variabilele i i k sunt de tip ntreg? (6p.)

k:=ord(a)-ord(A); a:=clasa a-XII-a A; writeln(a); for i:=1 to length(a)do if (a[i]>=a) and (a[i]




Pentru fiecare dintre itemii urmtori, scriei pe foaia de examen litera care corespunde rspunsului corect. 1. ntr-o list liniar simplu nlnuit, alocat dinamic, fiecare element memoreaz n cmpul

nr un numr ntreg, iar n cmpul urm adresa elementului urmtor din list sau valoarea NIL dac nu exist un element urmtor. Lista conine exact trei elemente ale cror adrese sunt memorate n variabilele p, q i r. tiind c p^.nr=1, q^.nr=2, r^.nr=3, p^.urmNIL i r^.urm=q, care este ordinea numerelor din list? (4p.)

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

2. Care dintre urmtoarele variante reprezint o declarare corect pentru o variabil x care memoreaz simultan codul de identificare al unui candidat la un examen, exprimat ca un numr natural de cel mult 4 cifre i media obinut de acesta la examen, exprimat ca un numr real? (4p.)

a. type x=record cod:integer; media:real end;

b. var x:record cod:integer; media:real end;

c. var x.cod:integer; x.media:real;

d. type candidat=record x.cod:integer; x.media:real end;

Scriei pe foaia de examen rspunsul pentru fiecare dintre cerinele urmtoare. 3. Care este gradul maxim posibil i care este gradul minim posibil pentru un nod dintr-un

arbore cu n noduri (n>1)? (6p.)

4. Ce va afia secvena alturat de program, tiind c variabila a memoreaz un ir cu cel mult 100 de caractere, iar variabila i este de tip ntreg ? (6p.)

a:=bacalaureat; writeln(length(a)); for i:=1 to length(a) do if pos(a[i],aeiou)0 then write(*);




Subiectul II (30 de puncte) - Varianta 018 Pentru fiecare dintre itemii urmtori, scriei pe foaia de examen litera care corespunde rspunsului corect.

1. Fiecare element al unei liste circulare, nevide, alocat dinamic, memoreaz n cmpul val o valoare ntreag, iar n cmpul adr adresa elementului urmtor. tiind c variabila p reine adresa unui element oarecare din list, iar variabila q este de acelai tip cu p, precizai care dintre urmtoarele variante tiprete toate elementele listei? (4p.)

a. q:=p; while qp do begin write(q^.val); q:=q^.adr end;

b. q:=p; while q^.adrp do begin write(q^.val); q:=q^.adr end;

c. q:=p; repeat write(q^.val); q:=q^.adr until q=p;

d. q:=p^.adr; while qp do begin write(q^.val); q:=q^.adr end;

2. Care dintre urmtoarele variante reprezint o declarare corect pentru o variabil x care memoreaz simultan coordonatele reale (abscisa i ordonata) ale unui punct n planul xOy? (4p.)

a. var x:record ox,oy:real end;

b. var x:string[2];

c. type x=record ox,oy:real end;

d. var x:real;

Scriei pe foaia de examen rspunsul pentru fiecare dintre cerinele urmtoare. 3. Un arbore binar este un arbore cu rdcin n care fiecare nod are cel mult 2 descendeni

direci (fii). nlimea unui arbore este reprezentat de numrul maxim de muchii ale unui lan elementar ce unete rdcina cu un vrf terminal (frunz). Pentru un arbore binar cu exact 8 noduri, care este nlimea minim posibil i care este numrul de noduri terminale (frunze) n acest caz? (6p.)

4. In secvena alturat, variabila a memoreaz un ir cu cel mult 100 de caractere, iar variabila i este de tip ntreg. Completai punctele de suspensie din secven astfel nct aceasta s afieze irul de caractere *nf*rm*t*c*. (6p.)

a:=informatica; for i:=1 to length(a) do if ... then write(...) else write(...);




Subiectul II (30 de puncte) - Varianta 019 Pentru fiecare dintre itemii urmtori, scriei pe foaia de examen litera care corespunde rspunsului corect. 1. Un graf neorientat este complet dac oricare dou noduri distincte ale sale sunt adiacente.

Care este numrul de muchii care trebuie eliminate dintr-un graf neorientat, complet, cu 7 noduri, astfel nct graful parial obinut s fie arbore? (4p.)

a. 15 b. 1 c. 6 d. 21

2. Fiecare element al unei liste liniare, simplu nlnuite, alocat dinamic, reine n cmpul nr un numr ntreg, iar n cmpul adr adresa elementului urmtor din list. Dac p reine adresa primului element, iar lista are cel puin dou elemente, care dintre urmtoarele secvene de instruciuni copiaz n cmpul nr al celui de-al doilea element al listei, coninutul cmpului nr al primului element din list? (4p.)

a. p^.nr:=p^.adr^.nr; b. p^.adr:=p^.nr; c. p^.adr^.nr:=p^.nr; d. p^.adr^.adr^.nr=p^.nr;

Scriei pe foaia de examen rspunsul pentru fiecare dintre cerinele urmtoare. 3. Ce va afia secvena alturat de

program, tiind c variabila x memoreaz un ir cu cel mult 100 de caractere, iar variabila i este de tip ntreg ? (6p.)

x:=bac2008; writeln(x); for i:=1 to length(x) do if pos(x[i],0123456789)=0 then write(x[i]);

Fiecare dintre variabilele a i b, declarate alturat, memoreaz simultan coordonatele reale ale cte unui punct n planul xOy.

var a,b:record x,y:real end;

4.

Completai punctele de suspensie din secvena urmtoare de program, astfel nct aceasta s afieze cuvntul DA dac segmentul determinat de punctele cu coordonatele memorate n variabilele a i b este paralel cu axa Ox, respectiv cuvntul NU n caz contrar. if ... then write(DA) else write(NU); (6p.)




Subiectul II (30 de puncte) - Varianta 020 Pentru fiecare dintre itemii urmtori, scriei pe foaia de examen litera care corespunde rspunsului corect. 1. Matricea de adiacen a unui graf neorientat G are numrul valorilor de 1 egal cu jumtate

din numrul valorilor de 0. Care dintre numerele de mai jos poate fi numrul de noduri ale grafului G? (4p.)

a. 12 b. 14 c. 11 d. 13

2. Care dintre urmtoarele variante reprezint o declarare corect pentru o variabil x care memoreaz simultan numrtorul i numitorul unei fracii ireductibile: (4p.)

a. var x:real; b. var x:string[2]; c. type x=record

n1,n2:integer end;

d. var x:record n1,n2:integer end;


ntr-o list circular, nevid, alocat dinamic, cu exact 9 elemente, fiecare element memoreaz n cmpul val o valoare ntreag, iar n cmpul adr adresa elementului urmtor.

3.

tiind c n list sunt memorate, n ordine, numerele de la 1 la 9, i variabila p reine adresa elementului cu valoarea 4, iar variabila q este de acelai tip cu p, precizai ce va afia secvena alturat? (6p.)

q:=p; writeln(q^.adr^.val); while q^.adrp do q:=q^.adr ;

write(q^.adr^.val);

4. In secvena alturat, variabila a memoreaz un ir cu cel mult 100 de caractere, iar variabila i este de tip ntreg. Completai punctele de suspensie, astfel nct aceasta s afieze doar literele mici i literele mari din irul de caractere memorat n variabila a. (6p.)

a:=Bac 2007 iulie; for i:=1 to length(a) do if ... then write(a[i]);





n secvena de mai jos, variabila a memoreaz un tablou bidimensional cu 20 de linii i 20 de coloane, numerotate de la 1 la 20, cu elementele reale. Variabila p este real, iar i este de tip ntreg.

1.

Care dintre instruciunile de mai jos poate nlocui punctele de suspensie astfel nct secvena s determine memorarea n variabila p a valorii produsului celor 40 de elemente aflate pe diagonalele matricei. (4p.)

p:=1; for i:=1 to 20 do ....

a. p:=p*a[21-i,i]*a[i,21-i]; b. p:=p*a[i,i]*a[i,20-i]; c. p:=p*a[i,i]*a[21-i,21-i]; d. p:=p*a[21-i,21-i]*a[i,21-i];

2. ntr-un graf orientat cu 7 noduri suma gradelor interioare ale tuturor nodurilor este egal cu 10. Care este valoarea sumei gradelor exterioare ale tuturor nodurilor? (4p.)


Se consider declarrile de mai jos, n care variabila ev memoreaz date despre un anumit elev. Scriei instruciunea Pascal prin care se iniializeaz anul naterii acestui elev cu valoarea 1990. (6p.)

3.

type data=record zi:integer; luna:integer; an:integer end;

type elev:record nume:string[30]; data_nasterii:data; media:real end; var ev:elev;

4. Stiva S i coada C memoreaz numere ntregi.n ambele se introduc, n ordine, numerele 1, 2, 3, 4. Se noteaz cu S C operaia de extragere a unui element din stiva S i adugarea acestuia n coada C, iar cu C S operaia de eliminare a unui element din coada C i introducerea acestuia n stiva S. Care este ultima valoare introdus n stiva S la executarea urmtoarei secvene de operaii: C S; C S; S C; C S; S C; S C; C S; (6p.)

Se consider un text alctuit din cel mult 250 de caractere, n care cuvintele sunt formate doar din litere mici ale alfabetului englez i sunt separate prin unul sau mai multe caractere *. Scriei un program Pascal care citete de la tastatur textul i afieaz pe ecran, pe cte o linie, toate secvenele formate din cte dou litere identice, ca n exemplu.

5.

Exemplu: dac textul citit este: se afieaz perechile alturate. (10p.)

ii ii oo



Subiectul II (30 de puncte) - Varianta 022 Pentru fiecare dintre itemii 1 i 2 scriei pe foaia de examen litera care corespunde rspunsului corect. 1. ntr-o stiv ce memoreaz numere ntregi se introduc, n ordine, urmtoarele numere:

1,2,3,4,5,6,7. Cte numere trebuie s eliminm din stiv astfel ca n vrful stivei s se gseasc numrul 5 (4p.)

a. 5 b. 2 c. 3 d. 4 2. Pentru declaraia alturat precizai care din

instruciunile de atribuire este greit: (6p.)

type elev=record nume:string[20]; nota1,nota2:integer end; var e1,e2:elev;;

a. e1:=e2+1; b. e1.nume[2]:=x; c. e1:=e2; d. e1.nota1:=e2.nota2+1;

Scriei pe foaia de examen rspunsul pentru fiecare dintre cerinele urmtoare. 3. Ce valoare are expresia de mai jos dac variabila s memoreaz irul de caractere

alfabet? length(copy(s,3,7)) (6p.)

4. ntr-un graf neorientat cu 10 noduri, numerotate de la 1 la 10, exist cte o muchie ntre oricare dou noduri numerotate cu numere consecutive i cte o muchie ntre nodul numerotat cu 10 i fiecare dintre celelalte noduri. Cte subgrafuri cu exact 3 noduri, toate adiacente dou cte dou, are graful dat? (4p.)

Scriei un program Pascal care citete de la tastatur numerele naturale m i n din intervalul [1,100], apoi construiete n memorie i afieaz pe ecran un tablou bidimensional cu m linii i n coloane astfel nct prin parcurgerea acestuia linie cu linie de sus n jos i fiecare linie de la stnga la dreapta, se obin n ordine descresctoare toate numerele naturale de la 1 la m*n, ca n exemplu.

5.

Fiecare linie a tabloului este afiat pe cte o linie a ecranului, elementele aceleiai linii fiind separate prin cte un spaiu.

Exemplu: pentru m=4 i n=3 se va construi i afia tabloul alturat. (10p.)

12 11 10 9 8 7 6 5 4 3 2 1



Subiectul II (30 de puncte) - Varianta 023 Pentru fiecare dintre itemii 1 i 2 scriei pe foaia de examen litera care corespunde rspunsului corect. 1. Care din urmtoarele expresii are valoarea true dac i numai dac irul de caractere s,

de lungime 10, este obinut prin concatenarea a dou iruri identice? (6p.)

a. s=copy(s,6,5) b. pos(copy(s,6,5),s)=1

c. s=s+5 d. s+copy(s,6,5)=s

2. Funcia predefinit care returneaz modulul unui numr ntreg este: (4p.)

a. sgn b. div c. mod d. abs

Scriei pe foaia de examen rspunsul pentru fiecare dintre cerinele urmtoare. 3. Care sunt nodurile care au exact 2 descendeni pentru un arbore cu rdcin, cu 7 noduri,

numerotate de la 1 la 7, dat de vectorul de tai: (3,3,0,1,2,2,4)? (4p.)

4. Pentru declaraiile alturate care este numrul maxim de numere ntregi ce pot fi memorate n variabila a? (6p.)

type punct3D=record x,y,z:integer end; var a:array[1..10,1..10] of punct3D;

5. Un tablou bidimensional A cu m linii i n coloane (1m100, 1n100) conine pe prima linie numerele 1,2,...,n iar pe prima coloan numerele 1,2,...,m. Celelalte elemente ale tabloului sunt date de relaia: A[i,j]=A[i-1,j]+A[i,j-1]. Scriei un program Pascal care citete de la tastatur numerele m i n i afieaz pe ecran elementul de pe ultima linie i ultima coloan a tabloului. (10p.) Exemplu: pentru m=3 i n=4 se va afia 25 1 2 3 4 deoarece elementele tabloului A sunt: 2 4 7 11 3 7 14 25



Subiectul II (30 de puncte) - Varianta 024 Pentru fiecare dintre itemii 1 i 2 scriei pe foaia de examen litera care corespunde rspunsului corect. 1. Care este structura de date adecvat memorrii unui numr neprecizat de iruri de

caractere reprezentnd cuvintele dintr-un text? (4p.) a. o list nlnuit n care fiecare nod

memoreaz un cuvnt b. un tablou bidimensional de caractere

c. un ir de caractere de lungime egal cu lungimea textului

d. o nregistrare cu attea cmpuri cte cuvinte exist

2. Care din urmtoarele proprieti este adevrat pentru un graf orientat cu n vrfuri i n arce (n>3) care are un circuit de lungime n: (6p.)

a. exist un vrf cu gradul n-1 b. pentru orice vrf gradul intern i gradul extern sunt egale

c. graful nu are drumuri de lungime strict mai mare dect 2

d. gradul intern al oricrui vrf este egal cu 2

Scriei pe foaia de examen rspunsul pentru fiecare dintre cerinele urmtoare. 3. Considerm c variabila s memoreaz un ir de minimum dou caractere. Scriei o

instruciune sau o secven de instruciuni Pascal care s elimine, la nivelul memoriei, cel de-al doilea carater din irul reinut de s. (4p.)

4. Scriei o secven de instruciuni Pascal care s iniializeze elementele unui tablou bidimensional cu cu n linii i n coloane, n100, cu numerele naturale 1,2,...,n, astfel nct pe fiecare linie sau coloan s existe toate numerele din mulimea {1,2,...,n} (6p.)

5. Scriei un program Pascal care citete de la tastatur dou iruri de caractere formate din maximum 100 litere mici ale alfabetului englez i afieaz pe ecran cel mai lung sufix comun al celor dou iruri de caractere.

Exemplu: pentru irurile marina i elena se va afia na (10p.)



Subiectul II (30 de puncte) - Varianta 025 Pentru fiecare dintre itemii 1 i 2 scriei pe foaia de examen litera care corespunde rspunsului corect. 1. Structura de date la care se aplic principiul primul venit, primul ieit: (first in, first out)

este: (4p.)

a. lista nlnuit b. stiva

c. coada d. graf orientat

2. Un graf neorientat cu 8 noduri are gradele nodurilor egale cu 1,2,4,2,3,2,1,x. Pentru ce valoare a lui x graful este arbore? (6p.)

a. x=1 b. x3 d. nicio valoare Scriei pe foaia de examen rspunsul pentru fiecare dintre cerinele urmtoare. 3. Scriei n Pascal o instruciune de atribuire n urma creia o variabil real y va memora

valoarea expresiei care calculeaz |x|x1

x ++ pentru variabila ntreag x. (6p.)

4. Scriei secvena de instruciuni Pascal care permite afiarea pe ecran a mesajului Corect dac un ir de maximum 100 caractere, memorat de variabila s, este palindrom sau mesajul Incorect n caz contrar. Un ir de caractere este palindrom dac citit de la nceput la sfrit este identic cu irul citit de la sfrit la nceput. Exemplu: irul de caractere cojoc este palindrom (4p.)

Se consider un tablou bidimensional cu m linii i n coloane (1m100,1n100), ale crui elemente aparin mulimii {0,1,2}. Scriei un program Pascal citete de la tastatur valorile m, n i elementele tabloului i care afieaz pe ecran numerele de ordine ale coloanelor pentru care produsul elementelor situate pe ele, este maxim. Liniile i coloanele tabloului se numeroteaz de la 1 la m respectiv de la 1 la n. Numerele se vor afia separate prin cte un spaiu.

5.

Exemplu: pentru m=4 i n=4 i tabloul alturat se va afia: 1 2 (10p.)

2 1 1 0 1 1 1 1 2 2 2 1 1 2 1 1




Pentru fiecare dintre itemii 1 i 2 scriei pe foaia de examen litera care corespunde rspunsului corect. 1. Pentru graful neorientat din figura alturat, care este numrul de

muchii ale celui mai lung lan, format din noduri distincte, ce are ca extremiti nodurile 1 i 3 ? (4p.)

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

2. Care este nodul ce poate fi ales ca rdcin a arborelui din figura alturat, astfel nct fiecare nod care nu este de tip frunz s aib un numr impar de descendeni direci (fii) ? (4p.) a. 3 b. 4 c. 6 d. 1


3. Care va fi irul de caractere afiat dup executarea secvenei alturate, n care variabila s memoreaz un ir cu cel mult 5 caractere? (6p.)

s:=raton;

s[2]:=s[4];

write(s);

4. ntr-o stiv care memoreaz numere, o valoare x poate fi adugat numai dac n vrful stivei se afl un element cu o valoare strict mai mare dect x; n caz contrar sunt eliminate toate elementele care nu ndeplinesc aceast condiie i apoi se adaug valoarea x. Exemplu: pentru stiva din fig.1, adugarea elementului 11 este precedat de eliminarea elementelor ce conin valorile 2 i 10. Dup adugare, stiva va avea coninutul din fig.2.

Dac stiva este iniial vid, care este numrul elementelor aflate n aceast stiv dup adugarea, respectnd condiiile de mai sus, n ordine, a numerelor 20,5,16,9,3,7,5,4,8 ?(6p.)

5. Scriei un program Pascal care citete de la tastatur un numr natural n (1




Pentru fiecare dintre itemii 1 i 2 scriei pe foaia de examen litera care corespunde rspunsului corect. 1. Care este numrul minim de arce ce trebuie adugate n graful orientat

din figura alturat astfel nct fiecare vrf s aparin unui circuit (4p.)

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

2. Care este numrul nodurilor de tip frunz din arborele cu rdcin, cu 8 noduri, numerotate de la 1 la 8, reprezentat prin vectorul de tai (2,0,6,2,4,4,5,5)? (6p.)

a. 3 b. 4 c. 5 d. 2 Scriei pe foaia de examen rspunsul pentru fiecare dintre cerinele urmtoare. 3. n declararea alturat, cmpurile x i y ale nregistrrii reprezint

numrtorul, respectiv numitorul unei fracii de forma . Scriei instruciunile prin executarea crora se memoreaz n variabila H fracia obinut prin adunarea fraciilor reinute n F i G. (6p.)

type fractie=record x,y:integer end;

var F,G,H:fractie;

4. O list liniar simplu nlnuit, alocat dinamic, reine n cmpul nr al fiecrui element cte un numr natural, iar n cmpul urm, adresa elementului urmtor din list sau nil dac nu exist un astfel de element. Lista memoreaz, n ordine, numai elementele 1,2,3,4,5.

p:=prim; while p^.urmnil do begin p^.urm^.nr := p^.nr* p^.urm^.nr;p:=p^.urm end;

tiind c variabila prim memoreaz adresa primului element al listei i c p este o variabil de acelai tip cu prim, care va fi valoarea reinut n ultimul element dup executarea secvenei de mai sus? (4p.)





Pentru fiecare dintre itemii 1 i 2 scriei pe foaia de examen litera care corespunde rspunsului corect. 1. Care este numrul minim de muchii ce pot fi eliminate din graful

alturat astfel nct n graful parial rezultat s existe exact un vrf de grad 0? (6p.)

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

2. ntr-un arbore cu rdcin nivelul unui nod este egal cu lungimea lanului format din noduri distincte care unete rdcina cu acel nod. Rdcina se afl pe nivelul 0. Dac toate frunzele se afl pe nivelul 3 i oricare nod neterminal aflat pe un nivel k are exact k+1 descendeni direci (fii), care este numrul de noduri din acest arbore ? (4p.)

a. 8 b. 9 c. 10 d. 6 Scriei pe foaia de examen rspunsul pentru fiecare dintre cerinele urmtoare. 3. ntr-un tablou bidimensional A cu n linii i n coloane notm cu Aij elementul aflat pe linia i i

coloana j (1in, 1jn). Care este valoarea expresiei j-i dac elementul Aij este situat pe diagonala principal a tabloului A? (4p.)

4. O list liniar simplu nlnuit, alocat dinamic, reine n cmpul nr al fiecrui element cte un numr natural, iar n cmpul urm, adresa elementului urmtor din list sau nil dac nu exist un element urmtor. Lista memoreaz, n ordine doar elementele 1,2,3,4,5. tiind c variabila prim memoreaz adresa primului element al listei i c p este o variabil de acelai tip cu prim, care sunt, n ordine, elementele listei dup executarea secvenei alturate? (6p.)

p:=prim; x:=p^.nr; while p^.urmnil do begin p^.nr := p^.urm^.nr; p:=p^.urm end; p^.nr:=x;

5. irul de caractere s2 este clona irului de caractere s1 dac se poate obine din s1 prin eliminarea tuturor apariiilor unei singure vocale. Se consider vocal orice liter din mulimea {a,e,i,o,u}. Scriei programul Pascal care citete de la tastatur un cuvnt format din cel mult 20 litere mici ale alfabetului englez i afieaz pe ecran (dac exist), toate clonele acestui cuvnt, fiecare pe cte o linie a ecranului.

Exemplu: pentru cuvntul informatica se afieaz, nu neaprat n aceast ordine, clonele scrise alturat. (10p.)

nformatca infrmatica informtic




Pentru fiecare dintre itemii 1 i 2 scriei pe foaia de examen litera care corespunde rspunsului corect. 1. Care este numrul maxim de noduri de grad 3 ntr-un graf neorientat cu 5 noduri? (4p.)

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

2. ntr-un arbore cu rdcin nivelul unui nod este egal cu lungimea lanului format din noduri distincte care unete rdcina cu acel nod. Care dintre noduri trebuie ales ca rdcin n arborele din figura alturat astfel nct pe fiecare nivel s se gseasc un numr impar de noduri? (6p.)

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

Scriei pe foaia de examen rspunsul pentru fiecare dintre cerinele urmtoare. 3. Care va fi irul de caractere afiat pe ecran dup

executarea secvenei alturate, n care variabila s memoreaz un ir de cel mult 4 caractere? (4p.)

s:=arac;

s[2]:=t;

write(s);

4. O list liniar dublu nlnuit, alocat dinamic, reine n cmpul nr al fiecrui element cte un numr natural, n cmpul urm, adresa elementului urmtor din list, iar n cmpul prec, adresa elementului precedent din list. Variabilele p i q memoreaz adresa primului, respectiv ultimului element al listei. Care este numrul maxim de elemente pe care le poate avea lista astfel nct, dup executarea secvenei alturate, valoarea variabilei n s fie 3? (6p.)

n:=0;

while(pq)and(q^.urmp)do

begin

p:=p^.urm;

q:=q^.prec;

n:=n+1

end;

5. Scriei un program Pascal care citete de la tastatur un numr natural n (1n6) i elementele unui tablou bidimensional A cu n linii i n coloane, care memoreaz numere naturale nenule mai mici dect 100, i afieaz pe ecran produsul numerelor pivot pentru matricea A. Un numr natural x este pivot pentru matricea A dac nmulind fiecare element de pe prima coloan cu numrul x, se obin, n aceeai ordine, elementele unei coloane din matrice. Exemplu: pentru matricea din figura alturat se afieaz 8. (10p.)




Pentru fiecare dintre itemii 1 i 2 scriei pe foaia de examen litera care corespunde rspunsului corect. 1. Care este numrul minim de muchii ce trebuie mutate n graful din

figura alturat astfel nct acesta s fie conex i fiecare nod s aparin unui ciclu? (6p.)

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

2. Care este valoarea expresiei length(s) pentru variabila s de tip ir de caractere, declarat var s:string[15]; i iniializat astfel: s:=Proba_E; (4p.)

a. 7 b. 15 c. 6 d. 5 Scriei pe foaia de examen rspunsul pentru fiecare dintre cerinele urmtoare. 3. Care sunt nodurile de tip frunz din arborele alturat dac se alege

ca rdcin nodul 6? (6p.)

4. O list liniar simplu nlnuit, cu cel puin 5 elemente, alocat dinamic, reine n cmpul nr al fiecrui element cte un numr natural, iar n cmpul urm, adresa elementului urmtor din list sau nil dac nu exist un element urmtor. Variabila prim memoreaz adresa elementului aflat pe prima poziie n list, ultim adresa elementului aflat pe ultima poziie n list, iar p i q sunt dou variabile de acelai tip cu prim. Pe ce poziie se va gsi n lista modificat n urma executrii secvenei alturate, elementul aflat pe poziia a doua, n lista iniial? (4p.)

p:=prim;prim:=ultim;

while(pprim) do

begin

q:=p;p:=p^.urm;

ultim^.urm:=q;

ultim:=q

end;

ultim^.urm:=nil;






1. Se consider graful neorientat cu 7, noduri numerotate de la 1 la 7, i muchiile[1,3],[2,3], [3,4], [3,5], [5,4], [1,2], [2,5], [2,4], [6,7], [3,6]. Care dintre urmtoarele succesiuni de noduri reprezint un lan care trece o singur dat prin toate nodurile grafului? (4p.)

a. (1, 2, 3, 4, 5, 6, 7) b. (4, 5, 3, 6, 7)

c. (7, 6, 3, 5, 4, 2, 1) d. (1, 3, 5, 4, 2, 3, 6)

2. Un arbore cu 11 noduri, numerotate de la 1 la 11, este memorat cu ajutorul vectorului de tai t=(2,5,5,3,0,2,4,6,6,2,3). Mulimea tuturor ascendenilor nodului 8 este: (4p.)

a. {1, 2, 5, 6, 10} b. {6, 2, 5} c. {6} d. {5, 2} Scriei pe foaia de examen rspunsul pentru fiecare dintre cerinele urmtoare: 3. Scriei definiia corect a unui tip de date necesar pentru a memora simultan, ntr-o singur

variabil de acest tip, urmtoarele caracteristici ale unui autoturism: marca (cuvnt de maximum 20 caractere) i anul fabricaiei (numr natural), astfel nct expresia Pascal de mai jos s aib ca valoare vechimea mainii ale crei caracteristici sunt memorate n variabila x.

2008-x.anul_fabricatiei (6p.)

4. n secvena alturat, variabilele i i j sunt de tip ntreg, iar variabila a memoreaz o matrice n care prima linie i prima coloan sunt numerotate cu 1. Toate elementele matricei primesc valori n urma executrii secvenei. Scriei n ordine, ncepnd cu prima linie, doar elementele situate pe cea de-a treia coloan a matricei. (6p.)

for j:=1 to 6 do for i:=1 to 4 do a[i,j]:=2*i+j;

5. Se consider o list liniar simplu nlnuit, alocat dinamic, n care fiecare nod memoreaz n cmpul info un cuvnt, iar n cmpul urm, adresa urmtorului nod al listei. Scriei un program PASCAL care citete de la tastatur un numr natural n (n100) i apoi n cuvinte distincte, fiecare cuvnt avnd maximum 20 de litere, toate majuscule, i construiete o list simplu nlnuit, cu acele cuvinte citite, care ncep i se termin cu aceeai liter. Cuvintele se vor memora n list n ordinea invers a citirii lor. Exemplu: pentru n=9 i cuvintele citite: URSUZU IRI E SUPARAT POP DORIS SI ANA CITESC

lista va fi

(10p.)




1. Un graf orientat este memorat cu ajutorul listelor de adiacen scrise alturat. Nodurile care au gradul exterior egal cu 2 sunt: (4p.)

1:(5,6) 2:(1,5,4) 3:(1,5)

4:(1,2) 5:(2) 6:(2,4,5)

a. 2 i 5 b. 1,3 i 4 c. 6 d. 2 i 3

2. Graful neorientat cu 8 noduri, numerotate de la 1 la 8, este reprezentat cu ajutorul matricei de adiacen alturate. Pentru acest graf este adevrat afirmaia: (4p.)

a. Graful este hamiltonian b. Graful nu are noduri de grad 0

c. Gradul maxim al unui nod este 3 d. Graful are trei componente conexe

Scriei pe foaia de examen rspunsul pentru fiecare dintre ntrebrile urmtoare: 3. ntr-o structur de date de tip coad au fost adugate, n aceast ordine, urmtoarele valori:

3, 10, 2, 8 i 6. Care este ultima valoare care s-a extras din coad dac s-au efectuat, n aceast ordine, urmtoarele operaii: extragerea unui element, adugarea valorii 100, extragerea a trei elemente. (6p.)

4. n secvena alturat, variabilele i i j sunt de tip ntreg, iar variabila A memoreaz o matrice n care prima linie i prima coloan sunt numerotate cu 1. Toate elementele matricei primesc valori n urma executrii secvenei. Scriei n ordine, ncepnd cu prima coloan, doar elementele situate pe a doua linie a matricei. (6p.)

for j:=1 to 6 do for i:=3 downto 1 do A[i,j]:=i+j;

5. Scriei un program Pascal care citete de la tastatur dou caractere c1 i c2, i un text avnd cel mult 250 caractere (spaii i litere ale alfabetului englez), pe care l modific nlocuind toate apariiile caracterului memorat n c1 cu cel memorat n c2 i toate apariiile caracterului memorat n c2 cu cel memorat n c1. Programul afieaz pe linii separate ale ecranului att textul iniial ct i textul obinut dup efectuarea nlocuirilor. (10p.)

Exemplu: dac pentru c1 se citete a, pentru c2 se citete o iar textul citit este: hocus pocus preparatus se va afia : hocus pocus preparatus hacus pacus preporotus





1. Se consider graful neorientat cu 6 noduri, definit cu ajutorul listelor de adiacen alturate. Care dintre mulimile urmtoare de noduri are toate elementele extremiti ale unor lanuri de lungime 2 cu cealalt extremitate n nodul 5? (4p.)

1: 4,5,6 2: 5 3: 4

4: 1,3 5: 1,2,6 6: 1,5

a. {1,4,6} b. {2} c. {3} d. {2,6} 2. Un arbore cu rdcin are nodurile numerotate de la 1 la 18 i este reprezentat prin

vectorul de tai t:(8,8,0,3,4,3,4,7,1,2,3,3,7,8,3,5,6,8). Numrul tuturor descendenilor nodului 3 este egal cu: (4p.)

a. 3 b. 6 c. 17 d. 18 Scriei pe foaia de examen rspunsul pentru fiecare dintre cerinele urmtoare: 3. Scriei definiia corect a unui tip de date necesar pentru a memora simultan ntr-o singur

variabil de acest tip, urmtoarele caracteristici ale unui cerc: abscisa i ordonata centrului cercului (numere ntregi) i raza acestuia (numr real), astfel nct expresia de mai jos s calculeze diametrul cercului ale crui caracteristici sunt memorate n variabila x. 2*x.raza (6p.)

4. n secvena alturat, variabilele i, j i x sunt de tip ntreg, iar variabila a memoreaz o matrice n care prima linie i prima coloan sunt numerotate cu 1. Toate elementele matricei primesc valori n urma executrii secvenei. Scriei n ordine, ncepnd cu prima coloan, elementele situate pe fiecare linie a matricei care se va construi n urma executrii secvenei alturate. (6p.)

x:=2; for j:=1 to 5 do for i:=1 to 3 do

begin

a[j,i]:=x;

x:=x+1

end;

5. O list dublu nlnuit, alocat dinamic, memoreaz n cmpul info al fiecrui nod un numr real, iar n cmpurile urm i prec adresa nodului urmtor, respectiv precedent din list. Adresa primului nod este memorat n variabila prim. Considerndu-se creat lista dublu nlnuit, scriei declarrile de date necesare definirii listei precum i secvena de program Pascal care modific lista, insernd dup fiecare valoare negativ din list, un nou nod, n care se va memora valoarea 0, i afieaz toate informaiile din nodurile listei dup efectuarea acestei operaii. (10p.)





1. Graful neorientat cu 60 de noduri, numerotate de la 1 la 60, are numai muchiile [1,60], [60,20], [2,30] i [4,30]. Numrul componentelor conexe ale grafului este egal cu: (4p.)

a. 3 b. 56 c. 54 d. 0 2. ntr-un arbore cu rdcin cu 10 noduri, numerotate de la 1 la 10, nodul 10 este rdcin,

iar ntre celelate noduri exist relaia: nodul cu numrul i+1 este tatl celui cu numrul i, pentru i {1,2,3,4,5,6,7,8,9}. Vectorul de tai al arborelui astfel definit, este: (4p.)

a. (0,1,2,3,4,5,6,7,8,9) b. (1,2,3,4,5,6,7,8,9,0) c. (2,3,4,5,6,7,8,9,10,0) d. (9,8,7,6,5,4,3,2,1,0)

Scriei pe foaia de examen rspunsul pentru fiecare dintre ntrebrile urmtoare.

3. ntr-o list simplu nlnuite alocat dinamic sunt memorate n ordine, urmtoarele valori: 2 ->3 ->4 ->7 ->5 ->9 ->14 Dac p este adresa primului element al listei i fiecare element reine n cmpul urm adresa elementului urmtor, care este informaia din elementul a crui adres o va reine p n urma executrii secvenei alturate? (6p.)

p:=p^.urm;

while p^.urm^.urmNIL do

p:=p^.urm^.urm;

4. Ce se va afia n urma executrii secvenei alturate n care c este o variabil ce poate memora un ir cu cel mult 20 de caractere, iar celelalte variabile sunt de tip ntreg? (6p.)

c:='tamara';

for i:=1 to length(c) do

begin

p:=pos('a',c);write(p)

end; Scriei programul Pascal care citete de la tastatur un numr natural n (n20), construiete n memorie i afieaz pe ecran, matricea cu n linii i n coloane, n care se vor memora n ordinea cresctoare a valorii, pe linii i coloane, primele n2 numere naturale nenule, pare, care nu sunt divizibile cu 3.

5.

Fiecare linie a matricei se va afia pe cte o linie a ecranului, cu elementele de pe aceeai linie separate prin cte un spaiu. Exemplu: pentru n=4 se va construi i afia matricea alturat. (10p.)

2 4 8 10 14 16 20 22 26 28 32 34 38 40 44 46





1. Se consider graful neorientat cu mulimea nodurilor {1,2,3,4,5,6,7,8} i mulimea muchiilor {[1,2], [2,3], [2,4], [4,7], [2,6], [1,5], [5,6], [6,8], [7,8]}. Pentru a trasforma graful ntr-un arbore, putem elimina: (4p.)

a. muchiile [1,5] i [1,2] b. muchia [5,6] c. nodul 3 d. muchiile [2,6] i [4,7]

Se consider o list alocat dinamic care are cel puin 10 elemente i fiecare element al listei memoreaz n cmpul info un numr ntreg, iar n cmpul next adresa elementului urmtor n list sau NIL dac nu exist un element urmtor.

2.

Variabila p memoreaz adresa de nceput a listei, iar variabila aux este de acelai tip cu p. Dac n urma executrii secvenei alturate de program, variabila p are valoarea NIL, atunci: (4p.)

while (pNIL) and (p^.info MOD 50) dobegin aux:=p; p:=aux^.next; dispose(aux) end;

a. toate numerele din list sunt divizibile cu 5

b. doar primul element din list este divizibil cu 5

c. n list nu s-a memorat niciun numr divizibil cu 5

d. doar ultimul element memorat n list este divizibil cu 5

Scriei pe foaia de examen rspunsul pentru fiecare dintre cerinele urmtoare. 3. Ce se va afia n urma executrii secvenei

alturate, n care variabila c memoreaz un ir cu cel mult 20 de caractere, iar variabila i este de tip ntreg? (6p.)

c:='tamara'; i:=4;

while i>=1 do

begin

c[i]:=c[i+1];i:=i-1

end;

write(c);

4. Un graf neorientat cu 10 noduri, numerotate de la 1 la 10, este reprezentat cu ajutorul listelor de adiacen alturate. Cte componente conexe are graful i care este numrul minim de muchii ce trebuie adugate pentru ca graful s fie conex? (6p.)

1:3,5 2:4 3:1,5 4:2,8 5:1,3

6:- 7:10 8:4 9:- 10:7

Scriei programul Pascal care citete de la tastatur un numr natural n (n50) i construiete n memorie o matrice cu n linii i n coloane, ale crei elemente sunt numere ntregi citite de la tastatur. Pentru fiecare coloan a matricei, n ordine, programul afieaz pe ecran cel mai mic numr de pe respectiva coloan. Numerele afiate vor fi separate prin cte un spaiu.

5.

Exemplu: pentru n=4 i matricea alturat, se vor afia pe ecran valorile: -7 18 -10 2. (10p.)

122 103 5 10 -7 18 -10 2 107 999 59 4 1 200 100 7




Pentru fiecare dintre itemii 1 i 2 scriei pe foaia de examen litera care corespunde rspunsului corect. 1. tiind c n urma executrii secvenei alturate s-a afiat

succesiunea de caractere EXAMEN, care este irul de caractere memorat de variabila s? (6p.)

x:=length(s); for i:=1 to x div 2 do write(s[i],s[x-i+1]);

a. ENXAME b. EAENMX c. NEEXMA d. NEMAXE 2. ntr-o list liniar simplu nlnuit, alocat dinamic, fiecare element reine n cmpul adr

adresa urmtorului element din list, iar n cmpul info un numr ntreg. Adresa primului element al listei este memorat n variabila p. tiind c lista conine exact 4 elemente, atunci expresia p^.adr^.info reprezint: (4p.)

a. adresa celui de al doilea element b. adresa celui de al treilea element c. valoarea memorat n al doilea element d. valoarea memorat n al treilea element

Scriei pe foaia de examen rspunsul pentru fiecare dintre cerinele urmtoare. 3. Se consider un graf neorientat cu 7 noduri numerotate de la 1 la 7 i muchiile

[1,2],[1,3],[2,3],[2,4],[2,5],[2,6],[4,6],[5,7],[6,7]. Care este numrul minim de muchii care trebuie adugate pentru ca acest graf s devin eulerian? (4p.)

4. Cte muchii trebuie eliminate dintr-un graf neorientat complet cu 20 de noduri, pentru ca acesta s devin arbore? Un graf este complet dac oricare dou noduri distincte sunt adiacente. (6p.)

5. Se consider o matrice cu n linii i m coloane (1n30, 1m30), ce memoreaz numere ntregi de cel mult 4 cifre fiecare. Scriei un program Pascal care citete de la tastatur valorile n, m i elementele matricei i care afieaz pe ecran, separate prin cte un spaiu, valorile minime de pe fiecare coloan, n ordine de la prima la ultima coloan. Exemplu: pentru n=4, m=4 i matricea alturat se vor afia pe ecran valorile 3 2 7 3. (10p.)




1. Fie declarrile alturate. Dac variabila x reine informaii despre un elev, precizai care este varianta corect ce afieaz prima liter din numele acestuia? (6p.)

type elev=record nume: string[30]; nota: real end; var x:elev;

a. write(nume); b. write(x); c. write(x.nume); d. write(x.nume[1]);

2. ntr-o list liniar simplu nlnuit, alocat dinamic, fiecare element reine n cmpul adr adresa urmtorului nod din list, iar n cmpul info un numr ntreg. Variabilele d i q rein adresele cte unui nod din list. S se identifice secvena de instruciuni care realizeaz inserarea corect, n list, a nodului memorat la adresa q, ca succesor al nodului reinut la adresa d. (4p.)

a. d^.adr:=q; q^.adr:=d; b. q^.adr:=d^.adr; d^.adr:=q; c. d^.adr:=q; q^.adr:=d^.adr; d. d:=q; q^.adr:=d^.adr;

Scriei pe foaia de examen rspunsul pentru fiecare dintre cerinele urmtoare. Urmtorii doi itemi se refer graful la orientat din figura urmtoare:

3. Se consider un graf orientat cu 5 vrfuri reprezentat n figura alturat. Care este matricea de adiacen corespunztoare grafului? (6p.)

4. Scriei care este gradul intern al vrfului 5 i gradul extern al vrfului 1. (4p.)

5. Un ir cu maximum 255 de caractere conine cuvinte separate prin unul sau mai multe spaii. Cuvintele sunt formate numai din litere mici ale alfabetului englez. Scriei un program Pascal care citete un astfel de ir i l afieaz modificat, prima i ultima liter a fiecrui cuvnt fiind afiat ca liter mare. Exemplu: pentru irul: maine este proba la informatica se va afia: MainE EstE ProbA LA InformaticA (10p.)



Subiectul II (30 de puncte) - Varianta 038 Pentru fiecare dintre itemii 1 i 2 scriei pe foaia de examen litera care corespunde rspunsului corect. 1. ntr-o list liniar simplu nlnuit, alocat dinamic, fiecare element reine n cmpul adr

adresa urmtorului nod din list, iar n cmpul info un numr ntreg. Considerm c o astfel de list memoreaz, n ordine, doar valorile 7, 5, 4, 9, 3. Variabila d reine adresa nodului la care este memorat valoarea 4. Care este secvena de instruciuni care trebuie executat pentru ca lista s conin, n ordine, doar valorile 7, 5, 9, 3? (6p.)

a. d^.adr:=d^.adr; d^.info:=d^.adr^.info;

b. d^.adr:=d^.adr^.adr;

c. d^.info:=d^.adr^.info; d^.adr:=d^.adr^.adr;

d. d^.adr^.adr:=d^.adr; d^.adr^.info:=d^.info;

2. Considerm c variabila s memoreaz irul de caractere examen. Care va fi valoarea lui s dup executarea instruciunilor? s[1]:= E;s[length(s)]:= N;s[length(s)div 2]:= A; s[length(s) div 2+1]:= M. (4p.)

a. ExameN b. exAMen c. EXAMEN d. ExAMeN

Scriei pe foaia de examen rspunsul pentru fiecare dintre cerinele urmtoare. Urmtorii doi itemi se refer la un graf neorientat cu 7 noduri, numerotate de la 1 la 7 i muchiile [1,5], [2,3], [2,4], [2,5], [3,4], [4,5], [4,7], [5,6], [5,7].

3. Care este numrul minim de muchii care trebuie eliminate astfel nct graful s aib 3 componente conexe? (6p.)

4. Cte cicluri elementare distincte exist n graf? Dou cicluri sunt distincte dac difer prin cel puin o muchie. (4p.)

5. Se consider o matrice ptratic cu n linii i n coloane (1n30), ce memoreaz numere ntregi de cel mult 2 cifre fiecare. Scriei un program Pascal care citete de la tastatur valoarea n i elementele matricei i care afieaz pe ecran, produsul acelor elemente de pe diagonala secundar care au proprietatea c sunt valori minime pe coloanele lor. Exemplu: pentru n=4 i matricea alturat se va afia pe ecran valoarea 21 (3*7=21). (10p.)



Subiectul II (30 de puncte) - Varianta 039 Pentru fiecare dintre itemii 1 i 2 scriei pe foaia de examen litera care corespunde rspunsului corect. 1. Stabilii care dintre urmtorii vectori este vector de tai pentru

arborele cu 7 noduri, numerotate de la 1 la 7, cu rdcina 1 reprezentat prin matricea de adiacen alturat: (4p.)

0 1 0 0 1 0 0 1 0 1 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0

a. (1, 0, 2, 2, 1, 5, 5) b. (0, 1, 2, 2, 1, 5, 5) c. (3, 1, 0, 2, 1, 5, 6) d. (2, 1, 0, 2, 1, 5, 2)

2. Considerm c variabila s memoreaz irul de caractere mama. Care va fi valoarea lui s dup executarea instruciunilor de mai jos? s[1]:=M; s[length(s)-2]:= A; (4p.)

a. MaAa b. MamA c. MAma d. MAMA Scriei pe foaia de examen rspunsul pentru fiecare dintre cerinele urmtoare. 3. ntr-o list liniar simplu nlnuit, alocat dinamic, fiecare

element reine n cmpul info un numr ntreg, iar n cmpul leg adresa urmtorului nod din list sau nil dac nu exist un nod urmtor. Adresa primului element al listei este memorat n variabila p. Ce valoare se va afia, n urma executrii secvenei alturate, dac lista memoreaz, n ordine, doar valorile 5, 4, 3, 2, 6 ? (6p.)

x:=1; while (p^.legnil) do begin x:=x * p^.leg^.info; p:=p^.leg end; write(x);

4. Considerm declaraiile: var i,j:integer; a:array[1..10,1..10]of integer; Ce se va afia dup executarea secvenei de instruciuni alturate? (6p.)

for i:=1 to 3 do for j:=1 to 3 do a[i,j]:=i+j; for i:=1 to 3 do begin for j:=1 to 3 do write(a[i,j]); writeln end;

5. Un ir cu maximum 255 de caractere conine cuvinte separate prin cte un spaiu. Cuvintele sunt formate numai din litere mici ale alfabetului englez. Scriei un program Pascal care citete un astfel de ir i l afieaz modificat, inversnd prin oglindire doar cuvintele care ncep cu vocal, ca n exemplu. Exemplu: pentru irul: maine este proba la informatica se va afia: maine etse proba la acitamrofni (10p.)




Pentru fiecare dintre itemii 1 i 2 scriei pe foaia de examen litera care corespunde rspunsului corect. 1. Se consider vectorul de tai" al unui arbore cu rdcin t=(3,4,0,3,3,5) ale crui

noduri sunt numerotate de la 1 la 6. Alegei afirmaia corect: (4p.) a. nodurile 4 i 6 sunt noduri de tip frunz b. nodul 3 are un singur descendent direct

(fiu) c. nodul 6 este tatl nodului 5 d. nodurile 1,2,6 sunt noduri de tip frunz

2. Se consider o coad, n care au fost introduse iniial, n aceast ordine, dou numere: 2 i 1. Coninutul cozii este reprezentat n figura alturat. Notm cu AD X operaia prin care se adaug informaia X n coad i cu EL operaia prin care se elimin un element din coad. Asupra cozii se efectueaz, exact n aceast ordine, operaiile AD 10; AD 15; EL; AD 4; EL; AD 20; EL. Care este coninutul cozii dup executarea operaiilor de mai sus? (4p.)

a. 15 4 b. 15 4 20 c. 4 20 d. 20 Scriei pe foaia de examen rspunsul pentru fiecare dintre cerinele urmtoare. 3. Se consider un graf neorientat cu 8 noduri numerotate de la 1 la 8 i muchiile [1,5],

[1,6], [2,6], [3,4], [3,6], [3,7], [4,6], [6,8], [7,8]. Dac se elimin nodul 6 i toate muchiile incidente cu acesta cte componente conexe va avea subgraful rezultat? (6p.)

4. Considerm declaraiile: var i,j:integer; a:array[1..10,1..10]of integer;Ce se va afia dup executarea secvenei de instruciuni alturate? (6p.)

for i:=1 to 3 do for j:=1 to 3 do if i





1. Cte dintre vrfurile grafului neorientat G, reprezentat prin matricea de adiacen alturat, au gradul un numr par? (4p.)

0 1 0 0 1 1 0 1 1 0 0 1 0 1 1 0 1 1 0 1 1 0 1 1 0

a. 1 b. 3 c. 2 d. 5 2. Fiecare nod al unei liste simplu nlnuite, cu cel puin 4 noduri, reine in cmpul urm

adresa nodului urmtor din list sau nil dac nu are un nod urmtor. tiind c variabila p reine adresa primului nod din list, variabila q reine adresa celui de-al doilea nod din list, iar variabila r reine adresa celui de-al treilea nod din list, care este secvena prin care se interschimb al doilea cu al treilea element din lista iniial? (4p.)

a. p^.urm:=r; q^.urm:=r^.urm; r^.urm:=q;

b. p^.urm:=r; r^.urm:=q^.urm; q^.urm:=r^.urm;

c. r^.urm:=q^.urm; q^.urm:=r^.urm; p^.urm:=r;

d. q^.urm:=r^.urm; p^.urm:=r; r^.urm:=q^.urm;

Scriei pe foaia de examen rspunsul pentru fiecare dintre cerinele urmtoare. 3. Pentru reprezentarea unui arbore cu radacin cu 10 noduri, etichetate cu numere naturale

de la 1 la 10, se utilizeaz vectorul de tai: TATA=(4, 8, 8, 0, 10, 4, 8, 6, 2, 6). Care sunt frunzele arborelui? (6p.)

4. Ce afieaz pe ecran secvena de program scris alturat, n care i este o variabil de tip char? (6 p.)

for i:='a' to 'z' do if pos(i,'info')>0 then write(i);

5. Scriei un program Pascal care citete de la tastatur un numr natural n (1n23) i apoi construiete n memorie o matrice cu n linii i n coloane, numerotate de la 1 la n, astfel nct fiecare element situat pe o linie i (1in) i pe o coloan j (1in) va fi egal cu suma dintre i i j. Programul va afia matricea pe ecran, cte o linie a matricei pe o linie a ecranului, elementele de pe aceeai linie fiind separate prin cte un spaiu. Exemplu: dac n=4, se va afia matricea alturat. (10p.)

2 3 4 53 4 5 64 5 6 75 6 7 8





1. Cte dintre vrfurile grafului neorientat G, reprezentat prin matricea de adiacen alturat, au gradul 0? (4p.)

0 0 0

bac 2008- s2

Documents