Page 82 - REVISTA MATINF Nr. 5

˘
82 PROBLEME DE INFORMATICA PENTRU EXAMENE

a) 91 b) 942 c) 0071 d) 0071249

3. Utilizˆand metoda backtracking, se genereaz˘a toate meniurile care cuprind cˆate patru feluri
distincte de mˆancare din mult , imea {aperitiv, desert, legume, paste, salat˘ a, sup˘ a},
fiecare meniu respectˆand urm˘atoarele condit , ii:

· dac˘a exist˘a aperitiv, este servit primul;
· dac˘a exist˘a desert, este servit ultimul;
· NU sunt servite legume s , i salat˘ a ˆın acelas , i meniu;
· dac˘a exist˘a paste s , i sup˘ a ˆın acelas , i meniu, pastele NU sunt servite ˆınainte de sup˘ a.

Dou˘a meniuri sunt distincte dac˘a difer˘a prin cel put , in un fel de mˆancare sau prin ordinea ser-
virii acestora. Primele cinci meniuri generate sunt, ˆın aceast˘a ordine: (aperitiv, legume,
paste, desert), (aperitiv, legume, sup˘ a, desert), (aperitiv, legume, sup˘ a, paste),
(aperitiv, paste, legume, desert), (aperitiv, paste, salat˘ a, desert). Indicat , i al
s , aselea meniu generat. (4p.)
a) (aperitiv, salat˘ a, paste, desert) c) (aperitiv, salat˘ a, sup˘ a, paste)
b) (aperitiv, salat˘ a, sup˘ a, desert) d) (aperitiv, sup˘ a, legume, desert)

4. Un graf orientat cu 5 vˆarfuri, numerotate de la 1 la 5, este reprezentat ˆın figura de mai
jos. Indicat , i num˘arul de componente tare conexe ale grafului. (4p.)
a) 1
b) 2
c) 3
d) 4

5. Un arbore cu r˘ad˘acin˘a are 20 de noduri, dintre care 10 noduri de tip ”frunz˘a”. Indicat , i
num˘arul maxim de noduri care au acelas , i ”tat˘a” ˆın acest arbore. (4p.)
a) 5 b) 7 c) 10 d) 15

SUBIECTUL al II-lea (40 de puncte)
Scriet , i pe foaia de examen r˘aspunsul pentru fiecare dintre cerint , ele urm˘atoare.

1. Se consider˘a algoritmul de mai jos, scris ˆın pseudocod. S-a notat cu a%b restul ˆımp˘art , irii
num˘arului natural a la num˘arul natural nenul b s , i cu [c] partea ˆıntreag˘a a num˘arului
real c.
citeste n (numar natural nenul)
m←0
pentru i=1,n executa
| citeste x (numar natural)
| cat timp x%10 > [x/10]%10 executa
| |_ x←[x/10]
|_ m←m+x
daca m>0 atunci scrie m
|_altfel scrie "niciunul"

a) Scriet , i ce se afis , eaz˘a dac˘a se citesc, ˆın aceast˘a ordine, numerele 5, 127, 2019, 1005,
7, 1900. (6p.)
b) Dac˘a primul num˘ar citit este 2, scriet , i un set de numere distincte din intervalul
4
3
[10 , 10 ) care pot fi citite ˆın continuare astfel ˆıncˆat, ˆın urma execut˘arii algoritmului,
s˘a se afis , eze mesajul niciunul. (6p.)