e_info_intensiv_subiii

8/7/2019 E_Info_intensiv_subIII

1/100

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

INFORMATIC, limbajul C/C++ Subiectul IIISpecializarea Matematic-informatic intensiv informatic

Subiectul III (30 de puncte)

Pentru itemul 1, scriei pe foaia de examen litera corespunztoare rspunsului corect.

1. Utiliznd metoda backtracking se genereaz n ordine lexicografic cuvintele de cte patrulitere din mulimea A={a,b,c,d,e}, cuvinte care nu conin dou vocale alturate. Primeleopt cuvinte generate sunt, n ordine: abab, abac, abad, abba, abbb, abbc, abbd, abbe.Cte dintre cuvintele generate ncep cu litera bi se termin cu litera e? (4p.)

a. 9 b. 15 c. 12 d. 20Scriei pe foaia de examen rspunsul pentru fiecare dintre cerinele urmtoare.

Pentru definiia de mai jos a subprogramului f, ce se afieaz ca urmare a apeluluif(121,1);? (6p.)

2.

//C

void f(long n, int i)

{ if(n!=0)if(n%3>0)

{ printf("%d",i); f(n/3,i+1); }}

//C++


{ if(n!=0)if(n%3>0)

{ cout


2/100





1. Utiliznd metoda backtracking se genereaz n ordine lexicografic cuvintele de cte patrulitere din mulimea A={a,b,c,d,e}, cuvinte care nu conin dou vocale alturate. Primele

opt cuvinte generate sunt, n ordine: abab, abac, abad, abba, abbb, abbc, abbd, abbe.Care este ultimul cuvnt generat? (4p.)

a. edcb b. eeee c. edde d. eded Scriei pe foaia de examen rspunsul pentru fiecare dintre cerinele urmtoare.

2. Pentru definiia de mai jos a subprogramului f, ce se afieaz ca urmare a apeluluif(12345);? (6p.)

//C

void f(long n){ printf("%d",n%10);

if(n!=0)

{ f(n/100); printf("%d",n%10); }}

//C++

void f(long n){ cout


3/100






opt cuvinte generate sunt, n ordine: abab, abac, abad, abba, abbb, abbc, abbd, abbe.Care este penultimul cuvnt generat? (4p.)

a. edec b. eded c. edde d. edcbScriei pe foaia de examen rspunsul pentru fiecare dintre cerinele urmtoare.

2. Pentru definiia alturat asubprogramului f, ce se afieaz caurmare a apelului f(26);? (6p.)

void f (int x)

{if(x>0)

if(x%4==0){ cout


4/100






opt cuvinte generate sunt, n ordine: abab, abac, abad, abba, abbb, abbc, abbd, abbe.Care este antepenultimul cuvnt generat? (4p.)

a. edde b. eddb c. edeb d. edcbScriei pe foaia de examen rspunsul pentru fiecare dintre cerinele urmtoare.

2. Pentru definiia alturat a subprogramului f,ce se afieaz ca urmare a apeluluif(15,2);? (6p.)

void f (int n, int x)

{ if(x>n)cout


5/100



Subiectul III (30 de puncte)Pentru itemul 1, scriei pe foaia de examen litera corespunztoare rspunsului corect.

1. Folosind modelul combinrilor se genereaz numerele naturale cu cte trei cifre distincte dinmulimea {1,2,3,7}, numere cu cifrele n ordine strict cresctoare, obinndu-se, n ordine:

123,127, 137, 237. Dac se utilizeaz exact aceeai tehnic pentru a genera numerelenaturale cu patru cifre distincte din mulimea {1,2,3,4,5,6,7,8}, cte dintre numerelegenerate au prima cifr2i ultima cifr7? (4p.)

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

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

Pentru subprogramul f definit mai jos, ce se afieaz ca urmare a apelului f(3,17)?(6p.)2.//C

void f ( int a, int b){ if(a


6/100





1. Utiliznd metoda backtracking sunt generate numerele de 3 cifre, avnd toate cifrele

distincte i cu proprietatea c cifrele aflate pe poziii consecutive sunt de paritate diferit.tiind c primele ase soluii generate sunt, n aceast ordine, 103, 105, 107, 109, 123,125,care este a zecea soluie generat? (4p.)

a. 145 b. 147 c. 230 d. 149


2. Se consider subprogramul alturat:Ce valoare are f(128,2)? (6p.)

int f(int a, int b){

if (b


7/100





1. Se consider subprogramul f definit

alturat. Ce se va afia n urmaapelului f(12345);? (4p.)

void f(long int n)

{ if (n!=0)

{if (n%2 == 0)cout


8/100





1. Utiliznd metoda backtracking sunt generate numerele de 3 cifre care au cifrele n ordine

cresctoare, iar cifrele aflate pe poziii consecutive sunt de paritate diferit. tiind c primelecinci soluii generate sunt, n aceast ordine, 123, 125, 127, 129, 145, care este cel de al8-lea numr generat? (4p.)

a. 169 b. 149 c. 167 d. 147


2. Se consider subprogramul f,descris alturat. Ce se va afian urma apelului f(3);? (6p.)

void f(int n){ if (n!=0){ if (n%2==0)cout


9/100





1. Se consider subprogramul f cu definiia

alturat. Ce valoare are f(1213111,1)?(4p.)

int f (long int n, int k){

if (n!=0)if(n%10==k)

return 1+f(n/10,k);else return 0;

else return 0;}a. 5 b. 3 c. 2 d. 1


2. Utiliznd metoda backtracking, sunt generate toate numerele de 3 cifre, astfel nct cifrelesunt n ordine cresctoare, iar cifrele aflate pe poziii consecutive sunt de paritate diferit.tiind c primele trei soluii generate sunt, n aceast ordine, 123, 125, 127,cte dintretoate numerele generate au suma cifrelor egal

cu 6? (6p.)

3. Scriei definiia complet a subprogramului sub cu doi parametri: n (numr natural,0


10/100





1. Se consider subprogramul cu definiia

alturat. Ce valoare are f(3,1)? (4p.)

int f(int n,int y){ if(n!=0)

{ y=y+1;return y+f(n-1,y);

}

else return 0;}

a. 9 b. 6 c. 7 d. 8


2. Folosind tehnica backtracking, un elev a scris un program care genereaz toate numerelede cte n cifre (1n9), cifrele fiind n ordine strict cresctoare. Dacn este egal cu 5, ctedintre numerele generate au prima cifr4? (6p.)

3. Scriei definiia complet a subprogramului sub cu trei parametri: n (numr natural,5


11/100




1. Un algoritm de tip backtracking genereaz, n ordine lexicografic, toate irurile de 5 cifre 0i 1 cu proprietatea c nu exist mai mult de dou cifre 0 pe poziii consecutive. Primele 7

soluii generate sunt: 00100, 00101, 00110, 00111, 01001, 01010, 01011. Care este a8-a soluie generat de acest algoritm? (4p.)

a. 01110 b. 01100 c. 01011 d. 01101


2. Care este valoarea expresiei f(23159)pentru funcia f, cu definiia alturat? (6p.)

int f(int n){

int c;

if (n==0) return 9;

else

{c=f(n/10);

if (n%10


12/100




1. Se consider subprogramul P, definit alturat.tiind c valoarea variabilei ntregi a este inainte

de apel 4, care este valoarea ei dup revenirea dinapelul P(a)? (4p.)

void P(int &x)

{ x=x+5; }


2. Pentru a scrie valoarea 10 ca sum de numere prime se folosete metoda backtracking ise genereaz, n aceast ordine, sumele distincte: 2+2+2+2+2, 2+2+3+3, 2+3+5, 3+7,5+5. Folosind exact aceeai metod, se scrie valoarea 9 ca sum de numere prime. Caresunt primele trei soluii, n ordinea generrii lor? (6p.)

3. Fiierele text NR1.TXTi NR2.TXT conin, separate prin cte un spaiu, mai multe numere

ntregi de cel mult 9 cifre fiecare. Fiecare dintre fiiere conine cel mult 100 de valori inumerele din fiecare fiier sunt ordonate strict cresctor. Se cere s se afieze pe ecran, nordine cresctoare, numerele divizibile cu 5 care se gsesc doar n unul din cele doufiiere.Exemplu: dac fiierul NR1.TXT conine numerele 1 2 3 4 7 20 60, iar fiierulNR2.TXT conine numerele 3 5 7 8 9 10 12 20 24, atuncise vor afia pe ecranvalorile 5 10 60.

a) Descriei un algoritm de rezolvare a acestei probleme, eficient din punct de vedere altimpului de executare i al spaiului de memorie utilizat, explicnd n ce const eficienaacestuia. (4p.)

b) Scriei programul C/C++ corespunztor algoritmului descris. (6p.)4. Scriei un program C/C++ care citete de la tastatur o valoare natural nenuln (n20),

apoi un ir de n numere naturale, avnd fiecare exact 5 cifre, i determini afieaz peecran cte dintre cele n numere citite au toate cifrele egale.

Exemplu: pentrun=5i numerele 33333 12423 59824 11111 33443 se va afiavaloarea 2 (exist dou numere cu toate cifrele egale i anume 33333i 11111). (10p.)

12

www.bacalaureat2008.info

Tot ce trebuie sa stii despre Examenul de Bacalaureat 2008


13/100




1. Fie subprogramul fct definit alturat, parial. Iniial, variabile ntregia, bi c au valorile a=8, b=31i c=9, iar dup apelul fct(a,b,c),

valorile celor trei variabile sunt a=9, b=31i c=40. Care poate fiantetul subgrogramului fct? (4p.)

void fct(....)

{ x++; y--;

z=x+y;}

a. void fct(int &x,int &y,int &z) b. void fct(int x,int &y,int &z)

c. void fct(int x,int y,int z) d. void fct(int &x,int y,int &z)


2. Trei biei Alin, Bogdani Ciprian, si trei fete Delia, Elenai Felicia, trebuie sformeze o echip de 3 copii, care s participe la un concurs. Echipa trebuie s fie mixt(adic s conin cel puin o fati cel puin un biat). Ordinea copiilor n echip esteimportant deoarece aceasta va fi ordinea de intrare a copiilor n concurs (de exempluechipa Alin, Bogdan, Delia este diferit de echipa Bogdan, Alin, Delia). Cte echipese pot forma, astfel nct din ele s fac parte simultan Alini Bogdan? (6p.)

3. Se considerirul 1, 2,1, 3,2,1, 4,3,2,1, ...construit astfel: prima grup este format din numrul 1, a doua grup este format dinnumerele 2 i 1, iar grupa a k-a, este format din numerele k, k-1,..., 1.Se cere s se citesc de la tastatur un numr natural n (n1000) i s se afieze pe ecrancel de al n-lea termen al irului dat.

a) Descriei un algoritm de rezolvare a acestei probleme, eficient din punct de vedere altimpului de executare i al spaiului de memorie, explicnd n ce const eficiena acestuia. (4p.)b) Scriei programul C/C++ corespunztor algoritmului descris (6p.)

4. Pe prima linie a fiierului text BAC.IN se gsesc, separate prin cte un spaiu, mai multenumere naturale de cel mult 9 cifre fiecare. Scriei un program C/C++ care citete numereledin acest fiier, elimin toate cifrele impare din fiecare dintre aceste numere i apoi scrie nfiierul text BAC.OUT numerele astfel obinute. Dac un numr din fiierul BAC.IN coninedoar cifre impare i cifra 0, acesta nu va mai aprea deloc n fiierul de ieire. (10p.)

Exemplu: dac fiierul BAC.IN conine numerele 25 7 38 1030 45127 0 35 60 15atunci BAC.OUT va avea coninutul: 2 8 42 60.

13




14/100




1. Care dintre urmtoarele variante reprezint antetul corect al unui subprogram care primeteprin parametrii xi y dou numere ntregi i furnizeaz prin parametrul mcea mai mic

dintre cele dou valori xi y? (4p.)a. int minim(int x,int y,int m) b. void minim(int x,int y,int &m)

c. int minim(int x,int y) d. void minim(int x,int y,int m)


2. Pentru funciile f1i f2 definitealturat, stabilii care este valoarea luif2(41382)? (6p.)

long f1(int c)

{ if (c%2==1) return 1;else return 2;

}long f2(long n){ if (n==0) return 0;else return f1(n%10)+f2(n/10);

}

3. Se citete de la tastatur un numr natural n (n500) i apoi n cifre. Se cere s se afiezepe ecran cele n cifre citite, n ordine cresctoare, separate prin cte un spaiu.Exemplu: pentru n=19i cifrele 3 3 0 9 2 1 2 1 3 7 1 5 2 7 1 0 3 2 3 se vaafia pe ecran 0 0 1 1 1 1 2 2 2 2 3 3 3 3 3 5 7 7 9.

a) Descriei pe scurt un algoritm de rezolvare al problemei, eficient din punct de vedere alspaiului de memorie utilizat i al timpului de executare, explicnd n ce const eficienametodei alese. (4p.)

b) Scriei programul C/C++ corespunztor algoritmului descris. (6p.)

Fiierul text BAC.TXT conine mai multenumere naturale, cu cel mult 6 cifre fiecare, cteun numr pe fiecare linie a fiierului.

4.

Scriei un program C/C++ care citete toate numerele din fiierul BAC.TXTi leafieaz pe ecran, cte 5 pe fiecare linie, separate prin cte un spaiu, cu excepiaultimei linii care poate conine mai puin de 5 numere. Programul va afia apoi peecran, pe o linie separat, cte numere din fiier au suma cifrelor par.Exemplu: dac fiierul are coninutul alturat, pe ecran se vor afia numerelede mai jos:11 21 30 40 51

16 17 10 1

4 (10p.)

11

2130

4051

161710

1

14




15/100




1. Cte numere cu exact 3 cifre pot fi construite folosind doar cifre pare? (4p.)

a. 125 b. 100 c. 64 d. 128


Pentru funciile fi g definite mai jos, stabilii care este rezultatul returnat la apelul f(6)?(6p.)

2.

long g(long x)

{ if (x>9)

return (x/10 + x%10);else

return x }

long f(int c){ if (c


16/100




1. Funcia F are definiia alturat. Ce valoareare F(3)? (4p.)

int F(int n)

{if(n==0 || n==1) return 1;

elsereturn 2*F(n-1)+2*F(n-2);}

a. 1 b. 12 c. 6 d. 10

Scriei pe foaia de examen rspunsul pentru fiecare dintre cerinele urmtoare

2. Un algoritm genereaz n ordine cresctoare toate numerele de n cifre, folosind doar cifrele3, 5 i 7. Dac pentru n=5, primele 5 soluii generate sunt 33333, 33335, 33337,33353, 33355, precizai care sunt ultimele 3 soluii generate, n ordinea generrii. (6p.)

3. Scriei definiia complet a subprogramului multiplu care are 3 parametri: a, prin careprimete un tablou unidimensional cu maximum100 de numere naturale mai mici dect1000, n, numrul de elemente ale tabloului i k, un numr natural (k9). Subprogramulreturneaz numrul de elemente din tablou care sunt multipli ai numrului k i au ultimacifr egal cu k.Exemplu: dacn=6, a=(2,273,63,83,93,123), iar k=3, subprogramul va returnavaloarea 4. (10p.)

4. n fiierul numere.txt sunt memorate maximum 10000 de numere naturale cu cel mult 9cifre fiecare. Fiecare linie a fiierului conine cte un numr. Se cere afiarea pe ecran, nordine descresctoare, a tuturor cifrelor care apar n numerele din fiier. Alegei un algoritmde rezolvare eficient din punct de vedere al memoriei utilizate i al timpului de execuie.Exemplu:dac fiierulnumere.txt conine:267

3962879

se va tipri 9987766322.

a) Descriei succinct, n limbaj natural, strategia de rezolvare i justificai eficienaalgoritmului ales. (4p.)

b) Scriei programul C/C++ corespunztor algoritmului ales. (6p.)

16




17/100




1. Subprogramul f are definiiaalturat. Ce se va afia n urma

apelului f(12345)? (4p.)

void f(long n)

{if (n>9)

{cout


18/100




1. Funcia f are definiia alturat. Ce seva afia n urma apelului

f(12345,0);? (4p.)


{if (i


19/100





int F(int x){

if (x


20/100





int F(int x)

{if(x!=0) return x+F(x-1);

else

return x;}

a. 5 b. 10 c. 15 d. 6

Scriei pe foaia de examen rspunsul pentru fiecare dintre cerinele urmtoare

2. Un algoritm genereaz n ordine descresctoare, toate numerele de n cifre (n


21/100




1. Care din urmtoarele probleme referitoare la mulimea de numere reale M={x1, x2, , xn}(n>1000) poate fi rezolvat cu un algoritm care are un numr minim de pai? (4p.)

a. sortarea elementelor mulimii M b. generarea elementelor produsuluicartezian Mx M

c. determinarea elementului minim almulimii M

d. generarea tuturor permutrilor mulimii M


2. Se consider subprogramul, f, definitalturat. Ce valoare are f(100)? (6p.)

int f(int n){ if(n==0) return 0;else return n%2+f(n/2);

}

3. Scriei definiia complet a unui subprogram i_primcare primete prin singurul suparametru, n, un numr natural din intervalul [2,30000]i returneaz diferena minimp2-p1 n care p1i p2 sunt numere prime i p1np2.Exemplu: dacn=20 atunci i_prim(n)=4, valoare obinut pentru p1=19i p2=23.

(10p.)

Fiierul BAC.TXT conine pe prima linie dou numere naturale ni k separat de un spaiu(3n10000, 2kn/2), iar pe a doua linie un ir de n numere naturale x1, x2, ..., xnseparate prin cte un spaiu, fiecare numr din acest ir avnd cel mult patru cifre.

a) Scriei un program C/C++ care citete numerele din fiier i determin, utiliznd o

metod eficient din punct de vedere al timpului de executare, cel mai mic indice i (1in-k+1) pentru care media aritmetic a numerelor xi, xi+1, ..., xi+k-1 este maxim. Programulafieaz valoarea lui i pe ecran.Exemplu: pentru fiierul alturat se afieaz2, deoarece mediamaxim se obine pentru 9, 4, 7. (6p.)

7 32 9 4 7 5 2 9

4.

b) Explicai succint, n limbaj natural, metoda utilizat la punctul a, justificnd eficienaacesteia. (4p.)

21




22/100




1. In timpul procesului de generare a permutrilor mulimii {1,2,,n} prin metodabacktracking, n tabloul unidimensional x este plasat un element xk (1kn). Acesta esteconsiderat valid dac este ndeplinit condiia: (6p.)

a. xk{x1, x2, , xk-1} b. xkxk-1c. xk{x1, x2, , xn} d. xkxk-1i xkxk+1


2. Considerm subprogramul recursiv definitalturat. Ce se va afia n urma apelului:f(C) (4p.)

void f(char c){ if (c>A) f(c-1);

cout


23/100




1. Algoritmul de generare a tuturor numerelor de 5 cifre nenule, fiecare avnd cifrele ordonatestrict cresctor, este echivalent cu algoritmul de generare a: (6p.)

a. submulimilor unei mulimi cu 5 elemente b. produsului cartezian a unor mulimi decifre

c. aranjamentelor de 9elemente luate cte 5 d. combinrilor de 9 elemente luate cte 5Scriei pe foaia de examen rspunsul pentru fiecare dintre cerinele urmtoare.

2. Pentru subprogramul suma definitalturat, scriei valoarea expresieisuma(5,4). (4p.)

int suma (int a,int b)

{ if (a==0 && b==0) return 0;

else if (a==0) return 1+suma(a,b-1);

else return 1+suma(a-1,b);

}

3. a) Scriei definiia complet a subprogramului shift care primete prin intermediulparametrului n o valoare natural nenul (n100), iar prin intermediul parametrului x, cele ncomponente ale unui tablou unidimensional. Fiecare component a acestui tablou este unnumr ntreg care are cel mult 4 cifre. Subprogramul permut circular cu o poziie sprestnga, elementele tabloului x. i furnizeaz tabloul modificat tot prin parametrul x.Exemplu: dac nainte de apel x=(1,2,3,4),dup apel x=(2,3,4,1). (4p.)

b) Scriei un program C/C++ care citete de la tastatur o valoarea natural nenuln(n100), apoi cele n elemente ale unui tablou unidimensional x. Programul va inversaordinea elementelor tabloului x folosind apeluri utile ale subprogramului shift i va afiape ecran, separate prin cte un spaiu, elementele tabloului rezultat n urma acesteiprelucrri.Exemplu: dac se citesc pentru n valoarea 5, iar tabloul x este (1,2,3,4,5) programulva determina ca x s devin(5,4,3,2,1). (6p.)

Fiierul BAC.TXT conine pe prima linie un numr natural nenul n (1n1000), iar pefiecare dintre urmtoarele n linii, cte dou numere ntregi ai b (1ab32000), fiecarepereche reprezentnd un interval nchis de forma [a,b]. Scriei un program C/C++ caredetermin intervalele care au proprietatea c intersecia cu oricare dintre celelalte n-1intervale este vidi afieaz pe cte o linie a ecranului, separate printr-un spaiu,numerele care reprezint capetele intervalelor determinate. (10p.)

4.

Exemplu: dac fiierul BAC.TXT are coninutulalturat, pe ecran se vaafia:2 6

17 20

4

17 20

2 6

10 158 16

23




24/100




1. Genernd irurile de maximum 3 caractere distincte din mulimea {A,B,C,D,E}, ordonatelexicografic, obinem succesiv: A, AB, ABC, ABD,. Ce ir va fi generat dupBAE? (4p.)

a. BCA b. CAB

c. BC d. BEA


2. Funcia f are definiia alturat.a) Ce valoarea are f(17)? (3p.)b) Ce valoare are f(22)? (3p.)

int f(int n)

{if (n


25/100




1. Un program citete o valoare natural nenul impar pentru ni apoi genereazi afieazn ordine cresctoare lexicografic toate combinaiile formate din n cifre care ndeplinesc

urmtoarele proprieti:- conin doar valori pozitive sau nule;- ncep i se termin cu 0;- modulul diferenei ntre oricare dou cifre alturate dintr-o combinaie este 1.

Astfel, pentru n=5, combinaiile afiate sunt, n ordine, urmtoarele: 01010, 01210. Dacse ruleaz acest program i se citete pentru n valoarea 7, imediat dup combinaia0101210 va fi afiat combinaia: (4p.)

a. 0121210 b. 0123210 c. 0111210 d. 0121010


2. Funcia f are definiia alturat:a) Ce valoare are f(16)? (3p.)

b) Scriei cea mai mare valoare de dou cifre pe care opoate avea n astfel nct f(n) s fie egal cu 2. (3p.)

int f(int n)

{ if (n


26/100


27/100




1. Pentru generarea numerelor cu n cifre formate cu elementele mulimii {0,2,8} seutilizeaz un algoritm backtracking care, pentru n=2, genereaz, n ordine, numerele20,22,28,80,82,88.

Dacn=4 i se utilizeaz acelai algoritm, precizai cte numere generate sunt divizibilecu 100? (4p.)

a. 601 b. 100 c. 6 d. 10


2. Subprogramul scrie este definit alturat.

Ce se afieaz ca urmare a apeluluiscrie(1,7); (6p.)

void scrie (int x,int y)

{cout


28/100




1. Generarea tuturor combinaiilor de trei litere mici ale alfabetului englez, se poate realiza cuajutorul unui algoritm echivalent cu cel de generare a: (4p.)

a. produsului cartezian b. combinrilorc. aranjamentelor d. permutrilorScriei pe foaia de examen rspunsul pentru fiecare dintre cerinele urmtoare.

2. Subprogramul f este definit alturat.

Ce valoarea are f(8,4)? (4p.)

int f (int x,int y)

{ if(x


29/100




1. n cte dintre permutrile elementelor mulimii {I,N,F,O} vocalele apar pepoziii consecutive? (4p.)


2. Ce se afieaz ca urmare aapelului p(123); dacsubprogramul p are definiiaalturat. (6p.)

void p (int x)

{cout


30/100




1. Pentru generarea numerelor cu n cifre formate cu elementele mulimii {0,4,8} seutilizeaz un algoritm backtracking care, pentru n=2, genereaz, n ordine, numerele

40,44,48,80,84,88.Dacn=4 i se utilizeaz acelai algoritm, care este numrul generat imediat dup numrul4008 ? (4p.)

a. 4040 b. 4004 c. 4080 d. 8004


2. Subprogramul f este definit alturat.

Ce se afieaz ca urmare a apeluluif(1,4); (6p.)

void f (int x,int y)

{ for (int i=x;i


31/100




Pentru itemul 1, scriei pe foaia de examen litera corespunztoare rspunsului corect.1. Avnd la dispoziie cifrele 0, 1i 2 putem genera, n ordine cresctoare,numere care au

suma cifrelor egal cu 2 astfel nct primele 6 numere generate sunt, n aceast ordine: 2,11, 20, 101, 110, 200. Folosind acelai algoritm se genereaz numere cu cifrele 0, 1, 2i3 care au suma cifrelor egal cu 4. Care va fi al 7-lea numr din aceast generare ? (4p.)

a. 103 b. 301 c. 220 d. 130


2. Se consider subprogramul recursiv f1definit alturat. Ce se va afia n urmaapeluluif1(5)? (6p.)

void f1(int x)

{ if (x


32/100




Pentru itemul 1, scriei pe foaia de examen litera corespunztoare rspunsului corect.1. n vederea participrii la un concurs, elevii de la liceul sportiv au dat o prob de selecie, n

urma creia primii 6 au obinut punctaje egale. n cte moduri poate fi format echipa

selecionattiind c poate avea doar 4 membri, alei dintre cei 6, i c ordinea acestora ncadrul echipei nu conteaz? (4p.)

a. 24 b. 30 c. 15 d. 4


2. Subprogramul afis este definit alturat.Ce se va afia n urma apeluluiafis(17)?

(6p.)

void afis(int x)

{ if (x>3){ cout


33/100


34/100





1. Completarea unui bilet de LOTO presupune colorarea a6 numere din cele 49 nscrise pe

bilet. O situaie statistic pe o anumit perioad de timp arat c cele mai frecvente numerecare au fost extrase la LOTO sunt: 2, 20, 18, 38, 36, 42, 46, 48. Cte bilete de 6numere se pot completa folosind doar aceste valori tiind c numrul 42 va fi colorat pefiecare bilet. (4p.)

a. 21 b. 6! c. 42 d. 56


2. Se consider definit subprogramul f .

Scriei dou valori naturale,x1ix2, (x1


35/100





1. Pentru generarea tuturor mulimilor de cte 5 cifre, avnd la dispoziie cifrele de la 1 la 9,

se poate utilza un algoritm echivalent cu algoritmul de generare a: (4p.)a.permutrilor de 5 elemente b. submulimilor mulimii{1,2,3,4,5,6,7,8,9}

c. combinrilor de 9 elemente luate cte 5 d. aranjamentelor de 9 elemente luate cte5


2. Subprogramul f este definit alturat. Ce seva afia n urma executrii secvenei de maijos?a=3,b=9; f(a,b);f(b,b);

(6p.)

void f(int &a,int b){

a=a-5;b=a-2;cout


36/100




1. Subprogramul scif returneaz suma cifrelor unui numr natural transmis ca parametru.Care este valoarea expresiei scif(scif(518)+scif(518))? (4p.)


2. Utilizm metoda backtracking pentru generarea tuturor modalitilor de a scrie numrul 9 casum a cel puin dou numere naturale nenule distincte. Termenii descompunerii sunt nordine strict cresctoare. Soluiile se genereaz n ordinea: 1+2+6, 1+3+5, 1+8,2+3+4, 2+7, 3+6 i 4+5. Se aplic exact aceeai metod pentru scrierea lui 12. Scriein ordine toate soluiile de forma 2+...? (6p.)

3. Subprogramul cifra primete prin intermediul parametrului a un numr natural cu cel mult4 cifre i returneaz ultima cifr par a sa. Dac numrul nu conine cifre pare subprogramul

ntoarce valoarea -1. De exemplu la apelul cifra(8345) subprogramul va returna 4. a) S se scrie definiia complet a subprogramului cifra. (10p.)

b) Pe prima linie a fiierului bac.in se afl un numr natural nenul n15000, iar pe adoua linie a fiierului se afl un ir de n numere naturale, desprite prin cte un spaiu,fiecare numr fiind format din cel mult 4 cifre.

Scriei un program C/C++ care citete numerele din fiier i afieaz pe ecran, folosindapeluri utile la subprogramuluicifra, cel mai mare numr care se poate forma cu ultimelecifre pare ale fiecrui element, dac acestea exist. Alegei o metod de rezolvare eficientca timp de executare.

Exemplu: dac fiierul bac.in are coninutulalturat pe ecran se va afia: 64220 (6p.)

7

369 113 2 0 33 1354 42

c) Descriei succint n limbaj natural, metoda de rezolvare folosit, explicnd n ce consteficiena ei (3 - 4 rnduri). (4p.)

36




37/100




1. Se utilizeaz un algoritm pentru a genera n ordine lexicografic invers toate permutrilemulimii {1,2,3,4,5}. Primele patru permutri generate sunt: 54321, 54312, 54231,

54213. A cincea permutare este: (4p.)a. 53421 b. 54321 c. 54132 d. 54123Scriei pe foaia de examen rspunsul pentru fiecare dintre cerinele urmtoare.

2. Considerm subprogramul f definit alturat.Ce valoare are f(11,7)? (6p.)

int f(int x,int y){if(x


38/100




1. Utilizm metoda backtracking pentru generarea tuturor modalitilor de a scrie numrul 9 casum a cel puin dou numere naturale nenule distincte. Termenii descompunerii sunt n

ordine strict cresctoare. Soluiile se genereaz n ordinea: 1+2+6, 1+3+5, 1+8,2+3+4, 2+7, 3+6 i 4+5. Se aplic exact aceeai metod pentru scrierea lui 8. Ctesoluii vor fi generate? (4p.)

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


2. Pentru definiia alturat asubprogramului sc, stabilii ce valoareare sc(901324)? (6p.)

int sc(long x)

{if(x


39/100




1. Utilizm metoda backtracking pentru generarea tuturor modalitilor de a scrie numrul 6 casum a cel puin dou numere naturale nenule. Termenii descompunerii sunt n ordine

cresctoare. Soluiile se genereaz n ordinea: 1+1+1+1+1+1, 1+1+1+1+2, 1+1+1+3,1+1+4, 1+5, 2+2+2, 2+4 i 3+3. Se aplic exact aceeai metod pentru scrierealui 9. Care este penultima soluie? (6p.)

a. 3+3+3 b. 3+6 c. 4+5 d. 2+7


2. Pentru definiia alturat a subprogramului f,ce valoare are f(8)? (4p.)

int f(int x)

{if(x

99 cu cel mult 9 cifre. S se realizeze un programC/C++ care citete numrul ni care, folosind apeluri utile ale subprogramul pr, afieazpe ecran, separate prin cte un spaiu, doar valorile prime din irul numerelor obinute din n,prin eliminarea succesiv a ultimei cifre, apoi a ultimelor dou cifre, apoi a ultimelor trei cifreetc., pn se obine un numr de dou cifre, ca n exemplu.

Exemplu: pentru n=193124 se obine irul de valori 19312,1931, 193, 19. din care sevor afia pe ecran doar valorile 1931 193 19. (6p.)

39




40/100




1. Utilizm metoda backtracking pentru generarea tuturor modalitilor de a scrie numrul 6 casum a cel puin dou numere naturale nenule. Termenii descompunerii sunt n ordine

cresctoare. Soluiile se genereaz n ordinea: 1+1+1+1+1+1, 1+1+1+1+2, 1+1+1+3,1+1+4, 1+5, 2+2+2, 2+4 i 3+3. Se aplic exact aceeai metod pentru scrierealui 9. Cte soluii de forma 2+... vor fi generate? (6p.)

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


2. Pentru definiia alturat asubprogramului f, stabilii ce valoare aref(23461)? (4p.)

int f(int x)

{if(x


41/100





1. Utiliznd metoda backtracking se genereaz numerele naturale formate din exact 3 cifre icare au suma cifrelor egal cu 4, n aceast ordine: 103, 112, 121, 130, 202,211, 220, 301, 310, 400. Dac utilizm acelai algoritm pentru a genera toatenumerele de 4 cifre ce au suma cifrelor egala cu 7 precizai care este numarul generatimediat dupa 1222. (4p.)

a.1231 b. 1223 c. 1213 d. 1321


2. Subprogramul f are definiia alturat. Ce valoareare f(7,2)?Dar f(35,2)? (6p.)

int f(int x, int y)

{if(x%y==0)return y;

else return f(x,y+1);

}

3. S se scrie o funcie cu 2 parametrii care primete prin intermediul parametrului a un vectorcu cel mult 100 de elemente numere naturale de cel mult 4 cifre fiecare i prin intermediulparametrului n un numr natural nenul, n


42/100





1. Utiliznd metoda backtracking se genereaz toate permutrile mulimii {1,2,3,4}. Dacprimele trei permutri generate sunt, n acest ordine: 1234, 1243, 1324 precizai careeste permutarea generat imediat dup3412. (4p.)

a. 3421 b. 3413 c. 4123 d. 3214


2. Subprogramul f are definiia alturat. Ce valoareare f(7)?Dar f(100)? (6p.)

int f(int x)

{if(x%6==0)return x;

else return f(x-1);

}

3. Scriei programul C/C++ care citete de la tastatura dou numere naturale ni k (3


43/100





1. Utiliznd metoda backtracking se genereaz numerele formate din cte 3 cifre distincte dinmulimea {1,3,5,7}. Dac primele trei numere generate sunt, n acest ordine: 135,137,153 care este cel de-al patrulea numr generat? (4p.)

a. 157 b. 173 c. 315 d. 357


2. Subprogramul f are definiia alturat. Ce valoareare f(3)?Dar f(10)? (6p.)

int f(int x)

{if(x==0)return 0;

else return f(x-1)+2;

}

3. Scriei programul C/C++ care citete de la tastatur numrul natural n (0


44/100





1. Utiliznd metoda backtracking se genereaz permutrile cuvntului info. Dac primele treisoluii generate sunt: fino, fion, fnio care este cea de-a cincea soluie? (4p.)

a. Foin b. Fnoi c. Foni d. Ifon


2. Subprogramul f are definiia alturat. Cevaloare are f(5,10)? (6p.)

int f(int x,int y)

{if(x==y)return x;

else if(x


45/100





1. Utiliznd metoda backtracking se genereaz toate cuvintele de cte 3 litere din mulimea{a,b,c}. Dac primele patru cuvinte generate sunt, n acest ordine: aaa, aab, aac,aba, care este cel de-al optulea cuvnt generat? (4p.)

a. acb b. acc c. aca d. bca


2. Subprogramul f are definiia alturat. Ce valoare aref(4)?Dar f(11)? (6p.)

int f(int x)

{if(x


46/100




1. Un program genereaz, n ordine cresctoare, numerele naturale, de exact 5 cifre din

mulimea {1, 2, 3, 4, 5}. Fiecare dintre numerele generate are cifrele distincte dou ctedou. Primele 3 numere astfel generate sunt: 12345, 12354, 12435. Care este numrulgenerat imediat dup12543? (4p.)

a. 15342 b. 12534 c. 13245 d. 13452


2. Funcia f are definiia alturat. Dacf(x)are valoarea 10100, care este valoarea lui x?

(6p.)

long f(int n)

{

if(n


47/100





1. Valorile memorate de componentele

vectorului v, cu indicii de la 0 la 5, sunt, naceast ordine: 183, 212, 453, 18, 42, 83.Care dintre urmtoarele apeluri alesubprogramului tab cu definiia alturat,NU returneaz un numr par?

(4p.)

int tab (int i,int v[], int c)

{ int n;if(i


48/100





vectorului v, cu indicii de la 0 la 5, sunt, naceast ordine: 183, 212, 453, 18, 42,83. Care este apelul corect alsubprogramului tablou alturat pentruca, n urma executrii apelului, valoareavariabilei ntregi x s fie 2?

(4p.)

int tablou (int i,int v[], int c){int n;

if(i9)

{ if(n%10==c)

return 1+tablou(i-1,v,c);n=n/10;

}return tablou(i-1,v,c);

}

}

a. x=tablou(2,v,2); b. x=tablou(2,v,5);c. x=tablou(5,v,2); d. x=tablou(2,v,8);


2. Se genereaz prin metoda backtracking mulimile distincte ale cror elemente sunt numerenaturale nenule i care au proprietatea c suma elementelor fiecrei mulimi este egal cu7. Astfel, sunt generate, n aceast ordine, mulimile: {1,2,4}, {1,6}, {2,5}, {3,4},{7}. Folosind aceeai metod pentru a genera mulimile distincte ale cror elemente suntnumere naturale nenule i care au proprietatea c suma elementelor fiecrei mulimi esteegal cu 9,stabilii n ce ordine sunt generate urmtoarele mulimi: M1={2,3,4};M2={3,6}; M3={2,7}; M4={4,5}. (6p.)

3. Se consider subprogramul div care primete prin parametrii xi y dou valori ntregipozitive (0


49/100





vectorului v, cu indicii de la 0 la 5, sunt, naceast ordine: 420, 48, 635, 628, 837,93. Care este apelul corect alsubprogramului tablou alturat pentruca, n urma executrii apelului, valoareavariabilei ntregi x s fie 3? (4p.)

int tablou (int i,int v[])

{if(i


50/100





vectorului v, cu indicii de la 0 la 5, sunt, naceast ordine: 973, 51, 871, 350, 691,15. Care este apelul corect alsubprogramului tablou alturat pentru ca,n urma executrii apelului, valoareavariabilei ntregi x s fie 3?

(4p.)

int tablou (int i,int v[], int c)

{if(i


51/100




1. Care este antetul corect al subprogramului cifre care primete prin intermediul primuluiparametru x un numr natural i furnizeaz prin intermediul celui de-al doilea parametru,y, suma cifrelor numrului natural x? (4p.)

a. void cifre(int x, int &y) b. int cifre(int x)

c. void cifre(int x, int y) d. int cifre(int &x, int y)


2. Se consider un numr natural nenul x avnd exact 8 cifre, cifrele lui fiind distincte 2 cte 2,iar printre cifrele sale se gsete i cifra 0. Permutnd cifrele lui x se obin alte numerenaturale. Cte dintre numerele obinute, inclusiv x, au exact 8 cifre? (6p.)

3. Se consider subprogramul dist2, care primete prin intermediul parametrilor xa, ya, xbirespectiv yb, coordonatele carteziene ntregi pentru dou puncte din plan. Subprogramul

returneaz ptratul distanei dintre cele dou puncte.a) Scriei n limbajul C/C++ definiia complet a subprogramului dist2. (4p.)

b) Scriei un program C/C++ care citete de la tastatur8 valori ntregi reprezentndcoordonatele carteziene pentru patrupuncte din plan i afieaz mesajul Da dac celepatru puncte pot fi vrfurile unui ptrat, iar n caz contrar afieaz mesajul Nu,folosindapeluri utile ale subprogramului dist2.Exemplu: dac coordonatele punctelor sunt cele alturateatunci se va afia mesajul Da (6p.)

0 0

3 03 30 3

Fiierul text date.in conine pe prima linie un numr natural nenul n (n100), iar pe adoua linie n numere naturale nenule, separate prin cte un spaiu, fiecare numr avndmaximum 4 cifre. Scriei un program C/C++care citete toate numerele din fiierul textdate.in, construiete n memorie un tablou unidimensional a, cu cele n elemente din fiieri afieaz pe ecran perechile (a[i], a[j]) , 1i


52/100




1. Utiliznd metoda backtracking se genereaz n ordine lexicografic toate anagramelecuvntului caiet ( cuvinte formate din aceleai litere, eventual n alt ordine). Cte cuvinte

vor fi generate? (4p.)a. 60 b. 100 c. 200 d. 120Scriei pe foaia de examen rspunsul pentru fiecare dintre cerinele urmtoare.

2. Se consider subprogramul f, definit alturat.Ce valoare are f(4)? Dar f(100)? (6p.)

long f(unsigned int n)

{ if (n==0) return 0;

else return n+f(n-1);

}

3. Subprogramul dist, cu doi parametri, primete prin intermediul primului parametru a unnumr natural cu maximum 8 cifre i returneaz prin intermediul celui de-al doileaparametru b numrul cifrelor distincte ale lui a.

Exemplu: dist(1223712) returneaz valoarea 4 ( deorece cifrele distincte ale parametruluide apel sunt 1, 2, 3, 7)

a) Scriei definiia complet a subprogramului dist. (4p.)

b) Fiierul text date.in conine pe prima linie un numr natural nenul n (n100), iar pe adoua linie n numere naturale, separate prin cte un spaiu, fiecare numr avnd maximum 8cifre. Scriei un program C/C++ care citete numerele din fiier i afieaz pe ecran,desprite prin cte un spaiu, numerele de pe a doua linie a fiierului text date.in, ce aunumr maxim de cifre distincte, folosind apeluri utile ale subprogramului dist.Exemplu: dac fiierul date.in are coninutul

alturat, atunci se vor afianumerele:1775 242477 123 (6p.)

6

16 1775 333 242477 123 55566

4. Scriei un program C/C++ care citete de la tastatur un numr natural nenul n (n100)iapoi n numere naturale nenule, de maximum 4 cifre fiecare, reprezentnd elementele unuitablou unidimensional; programul afieaz mesajul Da n cazul n care elementele tablouluireprezint o permutare a elementelor mulimii {1,2,3,...,n}, iar n caz contrar afieazmesajul Nu. (10p.)

52




53/100




1. Subprogramul f realizeaz interschimbarea valorilor a 2 variabile ntregi. Care este antetulcorect al subprogramului f ? (4p.)

a. void f(int &x, int &y) b. int f(int x,int y)c. void f(int x, int &y) d. void f(int &x, int y)


2. Se consider subprogramul f, definitalturat. Cte valori ale lui n aparinndintervalului [10, 20] au proprietatea cla apelul f(n) se obine valoarea 0?

( 6p.)

int f(unsigned int n)

{if (n==0) return 0;

else if(n%2==0)return n%10+f(n/10);

else return f(n/10);

}

Se consider subprogramul cmmdc, care primete prin intermediul a doi parametri, ai b,

dou numere naturale nenule, cu maximum 8 cifre fiecare, i returneaz cel mai maredivizor comun al valorilor parametrilor ai b.

a) Scriei numai antetul subprogramului cmmdc. (4p.)

b) Fiierul text date.in conine pe prima linie un numr natural nenul n (n100), iar pe adoua linie un ir format din nnumere naturale nenule, separate prin cte un spaiu, fiecarenumr avnd maximum 8 cifre. Scriei un program C/C++ care citete toate numerele dinfiierul text date.ini afieaz pe ecran lungimea maxim a unei secvene din ir cuproprietatea c orice dou elemente aflate pe poziii consecutive sunt prime ntre ele. Osecven a unui ir este format din unul sau mai multe elemente aflate pe poziiiconsecutive.

3.

Exemplu: dac fiierul date.in are coninutul alturat, se vaafia 3 pentru c cea mai lung secvena cu proprietateacerut este 6 25 6. (6p.)

716 25 6 12 10 4 5

4. Scriei un program C/C++ care citete de la tastatur un numr natural nenul n (n


54/100




1. Utiliznd metoda backtracking se genereaz n ordine lexicografic toate anagramelecuvntului caiet ( cuvinte formate din aceleai litere, eventul n alt ordine). Care este a

asea soluie? (4p.)a. catei b. actiec. actei d. catie


2. Se consider subprogramul fdefinit alaturat. Ce se afieaz laapelul f(1)?

(6p.)

void f(int i)

{if(i


55/100




Utiliznd metoda backtracking se genereaz toate matricele ptratice de ordinul 4 ale crorelemente aparin mulimii {0,1} cu proprietatea c pe fiecare linie i pe fiecare coloanexisto singur valoare 1. Primele 3 soluii generate sunt, n aceast ordine:

1.

1 0 0 0

0 1 0 00 0 1 00 0 0 1

1 0 0 0

0 1 0 00 0 0 10 0 1 0

1 0 0 0

0 0 1 00 1 0 00 0 0 1

Care este penultima soluie? (4p.)a. 0 0 0 1

0 0 1 0

1 0 0 00 1 0 0

b. 0 1 0 01 0 0 0

0 0 1 00 0 0 1

c. 0 0 0 10 1 0 0

0 0 1 01 0 0 0

d. 0 0 1 01 0 0 0

0 1 0 00 0 0 1


2. Se consider subprogramul f, definitalturat. Cte valori ale parametrului naprinnd intervalului [1,100] auproprietatea c la apelul f(n) seobine o valoare nenul ? (6p.)

int f(unsigned int n){ if (n>20) return 0;

else return 5+f(n+5);

}

3. Se consider subprogramul cifre care primete prin intermediul primului parametru a unnumr natural cu maximum 8 cifre nenule i returneaz, prin intermediul celui de-al doileaparametrul b, cel mai mic numr care se poate forma cu toate cifrele distincte ale lui a.

a) Scriei definiia complet a subprogramului cifre. (4p.)

b) Se consider fiierul text date.in ce conine pe prima linie un numr natural nenul n(n100) iar pe a doua linie n numere naturale, separate prin spaiu, fiecare numr avndmaximum 8 cifre nenule. Scriei un program C/C++care citete toate numerele din fiierultext date.ini afieaz pe ecran, desprite printr-un spaiu, numerele situate pe a doualinie a fiierului, formate numai din cifre distincte ordonate strict cresctor, folosind apeluriutile ale subprogramului cifre. n cazul n care nu exist niciun astfel de numr se va afiavaloarea 0.

Exemplu: dac fiierul date.in are coninutul alturat,atunci se vor afia numerele: 16 269 (6p.)

6

16 175 333 242477 321 269

Scriei un program C/C++ care citete de la tastatur un numr natural nenul n(n100) i

2*n numere naturale de maximum3 cifre reprezentnd elementele a 2 tablouriunidimensionale ai b, apoi construieste n memorie i afieaz pe ecran cele n elementeale unui tablou unidimensional c. Elementul c[i] (1in) se obine conform definiieiurmtoare:c[i] = a[i] concatenat cu b[i] , dac a[i]


56/100




1. Pentru a genera toate numerele naturale cu exact 4 cifre i care au cifrele n ordine strictdescresctoare, se poate utiliza un algoritm echivalent cu cel pentru generarea: (4p.)

a. aranjamentelor de 4 obiecte luate cte 10b. combinrilor de 10 obiecte luate cte 4c. permutrilor a 10 obiecte d. permutrilor a 4 obiecteScriei pe foaia de examen rspunsul pentru fiecare dintre cerinele urmtoare.

2. Se consider subprogramul f,definit alturat. Ce valoare aref(21114,1)?

(6p.)

int f(int n,int c)

{if(n==0)return 0;if(n%10==c) return n%100+f(n/10,c);

return f(n/10,c);}

3. Fisierul text numere.txt conine, pe o singur linie, cel mult 1000 de numere naturalenenule cu cel mult 4 cifre fiecare, numerele fiind separate prin cte un spaiu. Scriei unprogram C/C++ care citete toate numerele din fiier i scrie pe ecran toate numerele parecitite, ordonate cresctor. Dac fiierul numere.txt nu conine niciun numr par, atunci seva afia pe ecran mesajul nu exista.Exemplu: dac fiierul numere.txt conine numerele 2 3 1 4 7 2 5 8 6, atunci peecran se va afia: 2 2 4 6 8 (10p.)

4. Se consider subprogramul numar, care: primete prin intermediul parametrului, x, un numr natural nenul de cel mult 4 cifre; furnizeaz prin intermediul parametrului nrp numrul de numere prime mai mici sau egale

cu x;

a) Scriei numai antetul subprogramului numar. (4p.)

b) Scriei declarrile de date i programul principal C/C++ n care se citesc de la tastaturdou numere naturale nenule de cel mult 4 cifre, ai bi prin apeluri utile al subprogramuluinumar, se verific dac intervalul determinat de ai b conine cel puin un numr prim.Programul va afia pe ecran n caz afirmativ mesajul DA, iar n caz contrar mesajul NU. Prinintervalul determinat de a i b se nelege intervalul [a,b] daca


57/100




1. Se utilizeaz metoda backtracking pentru a genera toate cuvintele de cte patru litere distinctedin mulimea {d,a,n,s}. tiind c al doilea cuvnt generat este dans, iar al treilea estedsan, care va fi ultimul cuvnt obinut? (4p.)

a. nsad b. snad c. snda d. dansScriei pe foaia de examen rspunsul pentru fiecare dintre cerinele urmtoare.

2. Se consider subprogramul f,definit alturat. Ce se va afia laapelul f(38)?

(6p.)

void f(int x){

if(x){if(x%3==0){

cout


58/100




1. Se utilizeaz metoda backtracking pentru a genera toate cuvintele de cte trei litere distinctedin mulimea {i,n,f,o}. tiind c ultimele trei cuvinte generate sunt, n ordine, ion, infiino, care este cel de-al doilea cuvnt obinut? (4p.)

a. ofn b. ifo c. foi d. nifScriei pe foaia de examen rspunsul pentru fiecare dintre cerinele urmtoare.

2. Se consider subprogramul f, definitalturat. Ce valoare are f(3713,3)?

(6p.)

int f(int n,int c){

if(n==0)

return 0;

if(n%10==c)

return f(n/10,c)*10+c;

return f(n/10,c);

}

3. Fisierul text BAC.TXT conine, pe o singur linie, cel puin 3i cel mult 100 de numerenaturale nenule distincte de cel mult 4 cifre fiecare, numerele fiind separate prin cte unspaiu. Scriei un program C/C++ care citete toate numerele din fiierul BAC.TXTi scriepe ecran, n ordine descresctoare, cele mai mici 3 numere citite.Exemplu: dac fiierul BAC.TXT conine numerele 1017 48 310 5710 162, atunci seva afia: 310 162 48 (10p.)

4. Se consider subprogramul divizor, care: primete prin intermediul parametrului, a, un numr natural nenul de cel mult 4 cifre; furnizeaz prin intermediul parametrului d cel mai mare divizor al lui a strict mai mic dect

a;

a) Scriei numai antetul subprogramului divizor. (4p.)

b) Scriei declarrile de date i programul principal C/C++ care citete de la tastatur unnumr natural nenul x, de cel mult 4 cifre i, prin apeluri utile ale subprogramului divizor,verific dacx este numr prim. Programul va afia pe ecran n caz afirmativ mesajul DA, iarn caz contrar mesajul NU. (6p.)

58




59/100




1. Se utilizeaz metoda backtracking pentru a genera toate cuvintele care conin toate literele dinmulimea {i,n,f,o}, astfel nct fiecare liter s apar exact o dat ntr-un cuvnt. tiind c al

doilea cuvnt generat este info iar al treilea este ionf, care este ultimul cuvnt obinut?(4p.)a. nifo b. ofni c. ofin d. foni



(6p.)

int f(int a,int b)

{

if(a1), i, prin apeluri utile ale subprogramului divizor, verific dacxeste numr prim. Programul va afia pe ecran, n caz afirmativ, mesajul DA, iar n cazcontrar mesajul NU. (6p.)

59




60/100




1. Se utilizeaz metoda backtracking pentru a genera toate cuvintele care conin toate literele dinmulimea {i,n,f,o}, astfel nct fiecare liter s apar exact o dat ntr-un cuvnt i literele n

i o s nu se afle pe poziii vecine. tiind c primul cuvnt generat este info, iar al treilea estenifo care este cel de-al doilea cuvnt obinut? (4p.)

a. iofn b. inof c. ionf d. niofScriei pe foaia de examen rspunsul pentru fiecare dintre cerinele urmtoare.


(6p.)

int f(int a,int b){

if(2*a>=b)

return 0;

if(b%a==0)

return b-a;

return f(a+1,b-1);

} 3. Fisierul text bac.txt contine, pe o singur linie, cel mult 100 de numere naturale nenule de

cel mult 4 cifre fiecare, numerele fiind ordonate cresctor i separate prin cte un spaiu.Scriei un program C/C++ care citete de la tastatur un numr natural x de cel mult 4 cifrei verific dacx se afl n fiierul bac.txt. n caz afirmativ, se va afia pe ecran mesajulDA, altfel se va afia mesajul NU.Exemplu: dacx=312, iar fiierul bac.txt conine numerele:17 48 312 5742 8692 atunci se va afia: DA;dacx=20, iar fiierul bac.txt conine numerele:17 48 312 5742 8692

atunci se va afia: NU . (10p.)

4. Se consider subprogramul radical, care: primete prin intermediul parametrului a, un numr natural nenul de cel mult 4 cifre; furnizeaz prin intermediul parametrului x cel mai mare numr natural cu proprietatea c

x2 este mai mic sau egal cu a; de exemplu, daca=20, subprogramul va furniza prin xvaloarea 4;

a) Scriei numai antetul subprogramului radical. (4p.)

b) Scriei declarrile de date i programul principal C/C++ care citete de la tastatur unnumr natural nenul de cel mult 4 cifre, n, i prin apeluri utile ale subprogramului radical,

verific dacn este ptrat perfect. Programul va afia pe ecran n caz afirmativ mesajul DA,iar n caz contrar mesajul NU. (6p.)

60




61/100




1. Generarea matricelor ptratice de ordinul n, cu elemente 0i 1, cu proprietatea c pefiecare linie i pe fiecare coloan exist un singur element egal cu 1, se poate realiza

utiliznd metoda backtracking. Algoritmul utilizat este echivalent cu algoritmul de generarea: (4p.)a. combinrilor b. permutrilor c. aranjamentelor d. produsului

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

2. Se consider tabloul unidimensional a definitglobal, ce memoreaz elementele a1=12, a2=35,a3=2, a4=8i subprogramul f, definit alturat. Cevaloare are f(4)? (6p.)

int f(int x)

{if(x>=1)

return (a[x]+f(x-1))%10;

else

return 0;}

3. Subprogramul cifra primete prin singurul su parametru x, un numr real nenul pozitiv ifurnizeaz prin parametrul y valoarea cifrei unitilor prii ntregi a lui x.Exemplu: la apelul cifra(34.567) se va returna 4.

a) Scriei definiia complet a subprogramului cifra. (10p.)

b) Fiierul text medii.txt conine cel mult 600 de linii. Pe fiecare linie se afl, separateprintr-un spaiu, dou numere reale, cu cel mult dou zecimale, din intervalul[1,10], carereprezint media pe semestrul 1 respectiv media pe semestrul al 2-lea, ale unui elev. nsituaiile statistice pe care coala le realizeaz, fiecare medie este ncadrat ntr-una dintreurmtoarele categorii de medii: [3,3.99], [4,4.99], [5,5.99], [6,6.99],

[7,7.99], [8,8.99], [9,10]. Scriei un program C/C++ care citete datele din fiier iafieaz pe ecran numrul elevilor care au media din semestrul al 2-lea n categoria imediaturmtoare categoriei creia i aparine media din semestrul 1. Ordinea categoriilor este ceadin enumerarea de mai sus. n program se vor folosi apeluri utile ale subprogramului cifra.Se va utiliza un algoritm eficient din punctul de vedere al memoriei utilizate.

Exemplu: dac fiierul medii.txt conine:9.45 7.90

6.34 7.60

8.75 9.90

(6p.)

Pe ecran se afieaz:2

c) Descriei succint, n limbaj natural, metoda de rezolvare folosit, explicnd n ce consteficiena ei (3 4 rnduri). (4p.)

61




62/100




1. Utiliznd metoda backtracking pentru afiarea tuturor modalitilor de descompunere a unuinumr natural ca o sum de numere naturale nenule, pentru n=3 se obin, n ordine,

soluiile: 1+1+1; 1+2; 2+1; 3. Ordinea de scriere a termenilor dintr-o descompunere estesemnificativ. Folosind aceeai metod pentru n=10, care este soluia generat imediatdup1+1+3+5? (4p.)

a. 1+1+4+1+1+1+1 b. 1+1+7+1 c. 1+2+7 d. 1+1+4+4


2. Considerm subprogramul f, definit alturat. Care vafi valoarea variabilei globale x dup apelulf(4962,x),dac nainte de apel, x are valoarea 0?

(6p.)

void f1(int n,int &a)

{int c;

if(n!=0){c=n%10;

if(a


63/100




1. Se genereaz, prin metoda backtracking toate partiiile mulimii A={1,2,3} obinndu-seurmtoarele soluii: {1}{2}{3};{1}{2,3};{1,3}{2};{1,2}{3};{1,2,3}. Se observ

c dintre acestea, prima soluie e alctuit din exact trei submulimi. Dac se foloseteaceeai metod pentru a genera partiiile mulimii {1,2,3,4} stabilii cte dintre soluiilegenerate vor fi alctuite din exact trei submulimi. (4p.)

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


2. Se consider tabloul unidimensional a definitglobal, ce memoreaz elementele a1=1, a2=2,a3=0i subprogramul f, definit alturat. Cevaloare are f(3,3)? (6p.)

int f(int b,int i)

{ if(i>=1)

return f(b,i-1)*b+a[i];

else return 0;}

3. Subprogramul verif primete prin singurul su parametru, x, un numr natural nenul cucel mult 9 cifre i returneaz valoarea 1 dac numrul conine cel puin o secven de 3cifre impare alturate i 0 n caz contrar.Exemplu: la apelul verif(7325972) se va returna valoarea 1.

a) Scriei definiia complet a subprogramului verif. (10p.)

b) Fiierul text date.txt conine pe prima linie un numr natural nenul n cu cel mult 4 cifrei pe fiecare dintre urmtoarele n linii cte un numr natural, cu exact 6 cifre. Scriei unprogram C/C++ care citete numerele din fiierul date.txti afieaz pe ecran, separateprin cte un spaiu, acele numere care au primele 3 cifre impare. Se vor utiliza apeluri utileale subprogramului verif. Dac nu exist niciun numr cu aceast proprietate, se va afia

mesajul nu. Alegei o metod eficient din punctul de vedere al memoriei utilizate.

De exemplu: dac fiierul date.txt conine3

133579

345796

973314

(6p.)

Pe ecran se afieaz:133579 973314

c) Descriei succint, n limbaj natural, metoda de rezolvare folosit, explicnd n ce consteficiena ei (3 4 rnduri). (4p.)

63




64/100




1. Se genereaz, prin metoda backtracking, toate modalitile de aezare a numerelornaturale de la 1 la 5, astfel nct oricare 2 numere consecutive s nu se afle pe poziii

alturate. Dac primele 2 soluii sunt: (1,3,5,2,4) i (1,4,2,5,3), care este primasoluie generat n care primul numr este 4? (4 p.)a. (4, 1, 3, 2, 5) b. (4,2,5,1, 3) c. (4, 3, 5, 3, 1) d. (4, 1, 3, 5, 2)


2. Se consider subprogramul f, definitalturat. Ce se va afia n urma apeluluif(5,0)?

(6p.)

void f(int i,int j)

{ if(j


65/100




1. Se genereaz, prin metoda backtracking, toate modalitile de aezare a numerelornaturale de la 1 la 5 astfel nct oricare dou numere consecutive s nu se afle pe poziii

alturate. Dac primele 2 soluii sunt: (1,3,5,2,4) i (1,4,2,5,3), care este primasoluie generat care ncepe cu 2? (4p.)a. (2, 4, 1, 3, 5) b. (2, 5, 4, 3, 1) c. (2, 4, 1, 3, 1) d. (2, 3, 5, 4, 1)


2. Se consider funcia f, definit alturat.Ce se afieaz ca urmare a executrii secvenei demai jos ?a=4; b=18;printf(%d,f(a,b));/ cout


66/100




1. Se genereaz n ordine cresctoare, toate numerele naturale de 5 cifre distincte, care sepot forma cu cifrele 2,3,4,5i6. S se precizeze numrul generat imediat naintea inumrul generat imediat dup secvena urmtoare : 34256, 34265, 34526, 34562(4p.)

a. 32645 i 34625 b. 32654 i 34655

c. 32654 i 34625 d. 32645 i 34655


2. Se consider subprogramul recursiv definitalturat. Ce valoare are functie(4)? (6p.)

int functie(int x)

{

if (x


67/100




1. Se genereaz n ordine cresctoare, toate numerele naturale de 5 cifre distincte, care sepot forma cu cifrele 5,6,7,8i9. S se precizeze numrul generat imediat naintea inumrul generat imediat dup secvena urmtoare : 67589,67598,67859,67895. (4p.)

a. 65987 i 67958 b. 65978 i 67988

c. 65978 i 67958 d. 65987 i 67988Scriei pe foaia de examen rspunsul pentru fiecare dintre cerinele urmtoare.

2. Se consider subprogramul recursiv definitalturat. Pentru ce valoare a parametrului u,alfa(u)are valoarea 25 ? Pentru u=6, cevaloarea returneaz alfa(u)? (6p.)

int alfa(int u)

{if (u==0) return 3;

else return alfa(u-1)+3*u-2;

}

3. S se scrie n limbajulC/C++

definiia complet a subprogramuluicalcul

, care primeteprin intermediul parametrului n un numr natural nenul (1n10000), iar prin intermediulparametrului a, un tablou unidimensional care conine n valori ntregi, fiecare dintre acestevalori ntregi avnd cel mult 9 cifre. Subprogramul returneaz numrul de numere prime dintablou. (10p.)

Exemplu: n urma apelului calcul(n,a) pentru n=5i tabloul unidimensional12,37,43,6,71 se va returna 3.

4. Fiierul text NUMERE.TXT conine pe prima linie un numr natural n (1n10000)i pe adoua linie, un ir cresctor de n numere naturale, fiecare avnd cel mult 9 cifre. Numerelede pe a doua linie sunt separate prin cte un spaiu.

a) Scriei un program C/C++ care utiliznd o metod eficient din punct de vedere altimpului de executare i al spaiului de memorie, afieaz pe ecran elementele distincte aleirului aflat pe a doua linie a fiierului. (6p.)

Exemplu: dac fiierul NUMERE.TXT areconinutul alturat

7

111 111 111 2111 4111 71111 71111

atunci programul va afia pe ecran 111 2111 4111 71111

b) Descriei succint, n limbaj natural, metoda utilizat la punctul a, justificnd eficienaacesteia. (4p.)

67




68/100




1. Se utilizeaz metoda backtracking pentru a genera toate submulimile cu p elemente aleunei mulimi cu melemente.Dacm=7i p=4 atunci numrul de submulimi generate este : (4p.)

a. 60 b. 35 c. 5 d. 15


2. Se consider subprogramulrecursiv definit alturat. Ce valorivor fi afiate pe ecran n urmaapelului gama(6)? (6p.)

void gama(int n)

{int i;if(n>=3){for(i=3;i


69/100




1. Construim anagramele unui cuvnt c1c2c3c4 prin generarea n ordine lexicografic apermutrilor indicilor literelor cuvntului i obinem c1c2c3c4 c1c2c4c3 c1c3c2c4 c4c3c1c2c4c3c2c1. Pentru anagramele cuvntului rateu, dupirul raetu, raeut, raute cuvinteleimediat urmtoare sunt: (4p.)

a. rauet i rtaeu b. rtaeu i rtaue

c. rauet i rtaue d. rtaeu i ratueScriei pe foaia de examen rspunsul pentru fiecare dintre cerinele urmtoare.

2. Se consider subprogramul recursivdefinit alturat. Ce valori vor fiafiate pe ecran n urma apeluluibeta(15)? (6p.)

void beta(int n)

{if (n!=1)

{printf(%d ,n); | cout


70/100




1. Pentru rezolvarea crei probleme dintre cele enumerate mai jos se poate utiliza metodabacktracking ? (4p.)

a. determinarea reuniunii a 3 mulimi b. determinarea tuturor divizorilor unuinumr din 3 cifre

c. determinarea tuturor elementelor mai micidect 30000 din irul lui Fibonacci

d. avnd 3 culori (rou, galben,albastru), determinarea tuturorvariantelor n care se pot genera toatesteagurile cu 3 culori avnd la mijlocculoarea galben


2. Se consider subprogramul recursiv definit alturat.

Care este cea mai mic valoare de 2 cifre a lui u pentru carefunciabac(u,2) are valoarea 1 ? (6p.)

int bac(int u, int x)

{if (u


71/100





1. S

e_info_intensiv_subiii

Documents