Page 100 - MATINF Nr.2

˘
100 PROBLEME DE INFORMATICA PENTRU EXAMENE

2. Se consider˘a subprogramul rec cu definit , ia void rec(int n, int d)
din dreapta. {
if (d*d<n)
Scriet , i o valoare pe care o poate primi pa-
{ cout <<d<<" ";
rametrul n astfel ˆıncˆat ˆın urma apelului
rec(n,2) s˘a se afis , eze valorile 2 3. (4p.) |printf ("%d",d);
d++;
a) 7
rec(n,d+1);
b) 17
cout <<d<<" ";
c) 0
|printf ("%d",d);
d) 4 }
}

3. Folosind numai cifrele {0, 1, 2, 3}, se construiesc, prin metoda Backtracking, toate
numerele cu 3 cifre ˆın care oricare dou˘a cifre al˘aturate nu au aceeas , i paritate. Se obt , in ˆın
ordine numerele: 101, 103, 121, 123, 213,.... Utilizˆand aceeas , i metod˘a pentru a obt , ine
numere cu patru cifre din mult , imea {0,1,2,3,4} ˆın care oricare dou˘a cifre al˘aturate nu au
aceeas , i paritate care este al 4-lea num˘ar generat? (4p.)

a) 1034 b) 1030 c) 1012 d) 1232
4. Se consider˘a arborele dat prin urm˘atorul vector ”de tat , i”: (5, 5, 2, 5, 0, 2, 2, 9, 7, 7).
S , tiind c˘a r˘ad˘acina se afl˘a pe nivelul 0, stabilit , i care este num˘arul ascendent , ilor nodului 8
din arbore: (4p.)

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

5. Fie G=(X,V) un graf neorientat, unde X este mult , imea vˆarfurilor s , i V mult , imea muchiilor.
Graful G este complet dac˘a: (4p.)
a) un vˆarf are cel put , in n muchii adiacente;
b) matricea de adiacent , ˘a asociat˘a are toate elementele egale cu 1;
c) ordinul grafului este n-1;
d) are n(n-1)/2 muchii, unde n este num˘arul de vˆarfuri.
SUBIECTUL al II-lea (40 de puncte)

1. Se consider˘a algoritmul din dreapta repre- citeste n (numar natural)
zentat ˆın pseudocod. r←0
cat timp n>0 executa
S-a notat cu a%b restul ˆımp˘art , irii
| r←r*10+n%10
num˘arului ˆıntreg a la num˘arul ˆıntreg ne-
nul b s , i cu [a] partea ˆıntreag˘a a num˘arului |_ n←[n/10]
cat timp r>0 executa
real a.
| daca r%2 = 0 atunci
| |_ n←n*10+r%10
|_ r←[r/100]
scrie n

a) Ce valoare va fi afis , at˘a dac˘a se cites , te pentru n valoarea 23758? (6p.)
b) Scriet , i un num˘ar natural format din exact 5 cifre care poate fi citit pentru variabila
n astfel ˆıncˆat ˆın urma execut˘arii algoritmului s˘a se afis , eze valoarea 4. (6p.)
c) Scriet , i programul C/C++ corespunz˘ator algoritmului dat. (10p.)