Pregătire cu un profesor

UNIVERSITATEA DE VEST TIMIS, OARA
FACULTATEA DE MATEMATICĂ S, I INFORMATICĂ
Concurs FMI ed. VI-a 2021
Informatică
1. Se consideră funct, ia T descrisă mai jos care primes, te un parametru întreg s, i returnează o valoare întreagă
(operatorii DIV s, i MOD specifică câtul respectiv restul împârt, irii întregi).
funct, ie T(n)
dacă n=1 atunci returnează 1 sf_dacă
S ← 0
m ← n DIV 2
dacă n M OD 2 = 0 atunci
m ← m − 1
sf_dacă
i ← 1
cât_timp i <= m execută
S ← S + T (i) ∗ T (n − i)
i ← i + 1
sf_cât_timp
dacă n M OD 2 = 0 atunci
x ← T (n/2)
returnează 2 ∗ S + x ∗ x
altfel
returnează 2 ∗ S
sf_dacă
sf_funct, ie
Ce valoare va returna funct, ia dacă este apelată pentru n = 5?
(a) 61
(b) 23
(c) 12
(d) 14 Răspuns corect
(e) 15
2. Se consideră următoarea secvent, ă de prelucrări prin care se completează elementele unui tablou a:
pentru i ← 1, 200 execută
a[i] ← i ∗ i − i
sf_pentru
Câte dintre elementele tabloului a au cifra unităt, ilor egală cu 0?
(a) 20
(b) 21
1

Subiect și barem · pagina 2

(c) 79
(d) 80 Răspuns corect
(e) 81
(f) 82
Indicat, ie. Se determină câte numere sunt multiplu de 5 de la 1 la 200 s, i de la 0 zero 199.
3. Pentru decorarea cu pitici artizanali a unei grădini avem la dispozit, ie 130 de lei. S, tiind că un pitic mare costă
50 lei, un pitic mijlociu costă 25 lei s, i un pitic mic costă 10 lei, câte variante de decorare pot fi identificate
astfel încât să nu rămână mai mult de 9 lei neutilizat, i?
(a) 12 Răspuns corect
(b) 10
(c) 13
(d) 5
Indicat, ie. Se poate construi arborele de parcurgere a spat, iului solut, iilor pornind de la nodul cu suma
totală s, i ramificând prima dată după pitici mari (pot fi 2, 1 sau 0), dupa aceea pentru pitici medii (de restul
banilor se cumpără pitici mici ca sa nu rămână rest mai mare ca 9):
• 2 mari → 1 sau 0 medii (2 variante)
• 1 mare → 3, 2, 1, 0 medii (4 variante)
• 0 mari → 5, 4, 3, 2, 1, 0 medii (6 variante)
În total 12 variante.
4. Câte zerouri are la sfârs, it 2021! (factorialul numărului 2021)?
(a) 202
(b) 420
(c) 500
(d) 501
(e) 503 Răspuns corect
Indicat, ie. Se vor număra numerele până la 2021 care sunt multipli de 5. Fiecare multiplu de 5 va adăuga
un 0. Fiecare multiplu de 52 va adauga cate un 0 în plus pentru că a fost deja numărat ca s, i multiplu de 5.
Se va continua cu multiplii lui 53 apoi 54.
2021 / 5 = 404
2021 / 25 = 80
2021 / 125 = 16
2021 / 625 = 3
total = 503
5. Se consideră secvent, a de instruct, iuni care transformă un tablou x ce cont, ine n valori reale:
pentru i ← 1, n − 1 execută
dacă x[i] > x[i + 1] atunci
aux ← x[i]
x[i] ← x[i + 1]
x[i + 1] ← aux
2

Subiect și barem · pagina 3

sf_dacă
sf_pentru
Care dintre următoarele proprietăt, i este satisfacută de către elementele tabloului x după execut, ia secvent, ei
de mai sus?
(a) x[n] ≤ x[i] pentru orice i ∈ {1, 2, . . . , n}
(b) x[n] ≥ x[i] pentru orice i ∈ {1, 2, . . . , n} Răspuns corect
(c) x[i] ≤ x[i + 1] pentru orice i ∈ {1, 2, . . . , n − 1}
(d) x[i] ≥ x[i + 1] pentru orice i ∈ {1, 2, . . . , n − 1}
(e) x[1] ≤ x[i] pentru orice i ∈ {1, 2, . . . , n}
(f) x[1] ≥ x[i] pentru orice i ∈ {1, 2, . . . , n}
Indicat, ie. Prin interschimbarea elementelor vecine, valoarea maximă va fi plasată pe ultima pozit, ie.
6. Se consideră un text stocat într-un s, ir de caractere, s, cu n elemente indexate începând cu 1. Se pune
problema transformării s, irului de caractere prin eliminarea spat, iilor multiple (de exemplu s, irul de caractere
”un sir” este transformat în ”un sir”).
i ← 1
cât_timp i < n execută
k ← 0
cât_timp s[i] =′ ′ execută k ← k + 1; i ← i + 1; sf_cât_timp
dacă k > 1 atunci
〈 fragment pseudocod 〉
n ← n − k + 1
i ← i − k
sf_dacă
i ← i + 1
sf_cât_timp
Care dintre fragmentele de cod asigură eliminarea spat, iilor adit, ionale?
(a) Răspuns corect
j ← i
cât_timp j <= n execută
s[j − k + 1] ← s[j]
j ← j + 1
sf_cât_timp
(b) Răspuns corect
j ← i
h ← i − k + 1
cât_timp j <= n execută
s[h] ← s[j]
j ← j + 1
h ← h + 1
sf_cat_timp
3

Subiect și barem · pagina 4

(c) j ← i
cât_timp j <= n execută
s[j − k] ← s[j]
j ← j + 1
sf_cât_timp
(d) Niciuna din variantele propuse nu este corectă
7. Se consideră o secvent, ă de n valori naturale stocate într-un tablou x cu elemente indexate începând cu 1.
În ipoteza că secvent, a cont, ine exact o valoare egală cu 0 se dores, te transformarea tabloului prin permutare
circulară înspre stânga, astfel încât valoarea 0 să ajungă pe prima pozit, ie (de exemplu secvent, a (2, 1, 3, 0, 5, 4)
este transformată în (0, 5, 4, 2, 1, 3)):
i ← 1
cât_timp x[?a] 6 = 0 execută
aux ←?b
pentru i ← 2, n execută
x[?c] ← x[?d]
sf_pentru
x[?e] ← aux
sf_cât_timp
Care dintre următoarele variante de completare a pseudocodului de mai sus asigură cerint, a problemei?
(a) ?a → 1, ?b → x[1], ?c → i − 1, ?d → i, ?e → n Răspuns corect
(b) ?a → i, ?b → x[1], ?c → i − 1, ?d → i, ?e → n
(c) ?a → 1, ?b → x[i], ?c → i − 1, ?d → i, ?e → n
(d) ?a → n, ?b → x[n], ?c → i, ?d → i − 1, ?e → 1
(e) Niciuna din variante nu este corectă.
8. Pentru care din următoarele apeluri funct, ia F va returna valoarea 1?
Varianta C
int F(int n, int x)
if (n<2) return 1;
else if (n % 2 == 0)
return F(n/x,x+1);
else return 0;
Varianta Pascal
function F(n,x:integer):integer;
begin
if (n<2) then F := 1
else if (n MOD x=0) then
F := F(n DIV x, x+1)
else
F := 0;
end;
4

Subiect și barem · pagina 5

(a) F (5040, 2) Răspuns corect
(b) F (24, 2) Răspuns corect
(c) F (25, 2)
(d) F (36, 2)
9. Ce valoare va avea variabila k în urma execut, iei secvent, ei de prelucrări pentru un număr natural nenul n
(operatorul DIV produce câtul împărt, irii întregi, iar [x] reprezintă partea întreaga a numărului x)?
k ← 0
cât_timp n > 0 execută
n ← n/2
k ← k + 1
sf_cât_timp
(a) n/2
(b) [log2n]
(c) n
(d) [log2n] + 1 Răspuns corect
10. Se consideră matricea
A =
[ 1 1
1 0
]
Care este valoarea elementului de pe prima linie, prima coloană (elementul din stânga sus) din matricea
A100 = A ∗ A ∗ . . . ∗ A (de 100 de ori)
(a) 100
(b) 1
(c) elementul cu indicele 100 din s, irul dat prin relat, ia de recurentă: f0 = 1, f1 = 1, fn = fn−1 + fn−2
Răspuns corect
(d) elementul cu indicele 99 din s, irul dat prin relat, ia de recurentă: f0 = 1, f1 = 1, fn = fn−1 + fn−2
(e) 2100
11. Se consideră funct, ia recursivă:
funct, ie F (a)
dacă a <= 3
returneaza 1
altfel
returneaza F (a − 1) + F (a − 2) + F (a − 3)
sf_daca
sf_functie
De câte ori se calculează F(4) dacă primul apel este F(10)?
(a) 25
(b) 24 Răspuns corect
(c) 28
5

Subiect și barem · pagina 6

(d) 15
12. Ce va afis, a subprogramul de mai jos în cazul apelului F(27)?
subprogram F (n)
dacă n <= 0 atunci afis, are(0)
altfel
afis, are( n )
F (n − 5)
afis, are( n )
sf_dacă
sf_subprogram
(a) 0 2 7 12 17 22 27
(b) 27 22 17 12 7 2 0 2 7 12 17 22 27 Răspuns corect
(c) 27 22 17 12 7 2 -2 2 7 12 17 22 27
(d) 25 20 15 10 5 0 5 10 15 20 25
(e) 27 22 17 12 7 2 0
13. Se consideră un număr natural n constituit din k +1 cifre (n = ckck−1 . . . c1c0). Care sunt cifrele numărului m
construit prin secvent, a de prelucrări de mai jos în ipoteza că k=3? (operatorii DIV s, i MOD permit calculul
câtului respectiv restului împărt, irii în domeniul numerelor întregi)
p ← 1
m ← n M OD 10
n ← n DIV 10
q ← 1
cât_timp n 6 = 0 execută
q ← q + 1
pentru i ← 1, q execută
p ← p ∗ 10
sf_pentru
m ← (n M OD 10) ∗ p + m
n ← n DIV 10
sf_cât_timp
(a) c00c10c20c3
(b) c30c20c10c0
(c) c300c20c1c0
(d) c3000c200c10c0 Răspuns corect
(e) c0000c100c20c3
14. De câte ori se execută instruct, iunea x ← x + 1 în secvent, a de mai jos?
x ← 0
pentru i ← 2, N execută
pentru j ← 1, i − 1 execută
6

Subiect și barem · pagina 7

x ← x + 1
sf_pentru
sf_pentru
(a) N (N − 1)
(b) N (N − 1)/2 Răspuns corect
(c) N (N + 1)/2
(d) (N − 1)(i − 1)
Indicat, ie. Numărul de execut, ii a liniei x ← x + 1 este dat de calculul următoarei sume ∑N
i=2
∑i−1
j=1 1 =
∑N −1
i=1 i.
15. Se consideră un tabloul t cu n elemente indexate începând cu 1 s, i următoarea secvent, ă de prelucrări aplicate
asupra elementelor tabloului:
i ← 1
j ← n
cât_timp i < j execută
cât_timp (t[i] > 0 si i <= n) execută i ← i + 1 sf_cât_timp
cât_timp (t[j] < 0 si j >= 1) execută j ← j − 1 sf_cât_timp
dacă i < j atunci
aux ← t[i]
t[i] ← t[j]
t[j] ← aux
sf_dacă
sf_cât_timp
Ce efect are secvent, a de prelucrări asupra tabloului t?
(a) Ordonează crescător tabloul t
(b) Plasează elementele pozitive în prima parte a tabloului t Răspuns corect
(c) Nu se poate spune nimic despre structura tabloului t
(d) Ordonează decrescător tabloul t
(e) Plasează elementele negative în prima parte a tabloului t
Problema 1
Se consideră un dreptunghi de dimensiune 2 × n (două linii s, i n coloane) s, i se dores, te acoperirea dreptunghiului
cu piese de domino de forma 2 × 1 sau 1 × 2.
(a) Propunet, i o funct, ie care determină numărul de modalităt, i de acoperire exactă a dreptunghiului cu piese (nu
pot să rămână port, iuni neacoperite iar piesele nu pot depăs, i conturul dreptunghiului).
(b) În ipoteza că două dintre celulele dreptunghiului aflate in colt, uri opuse sunt inaccesibile (de exemplu celula
(1, 1) s, i celula (2, n) sau celule (2, 1) s, i celula (1, n)), propunet, i o funct, ie care determină numărul de modalităt, i
de acoperire exactă a dreptunghiului cu piese (exceptând celulele din cele două colt, uri).
Prezentat,i pe scurt ideea de rezolvare s, i descriet,i solut,ia în pseudocod sau într-un limbaj de programare la alegere
(C/C++, Pascal, Python).
7

Subiect și barem · pagina 8

Idee de rezolvare
(a) Considerând dreptunghiul de dimensiune n se poate începe acoperirea fie cu:
1 - o piesă plasată vertical, caz în care problema se reduce la o problemă de dimensiune n − 1
2 - două piese plasate orizontal, caz în care problema se reduce la o problemă de dimensiune n − 2
Prin urmare formula de calcul a numărului de variante posibile este:
C(1) = 1
C(2) = 2 (se pot pune orizontal sau vertical)
C(n) = C(n-1) + C(n-2) (de tip Fibonacci)
(b) Se analizează paritatea lui n, dacă n este par nu există varianta de acoperire fără să se suprapună piesele.
Dacă n este impar există o singura posibilitate de acoperire cu piese plasate orizontal (nu se poate pune nicio
piesă verticală).
BAREM
Start . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 pct.
(a) Descrierea ideii de rezolvare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 pct.
Implementarea funct, iei:
Declarat, ii de variabile . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 pct.
Implementare corectă C(1) = 1, C(2) = 2, C(n) = C(n − 1) + C(n − 2) . . . . . . . . . . . . . . . . . . . . . . . . . 2 pct.
Definirea corectă a funct, iei s, i returnarea rezultatului . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 pct.
(b) Descrierea ideii de rezolvare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 pct.
Declarat, ii, definire s, i implementare corectă a subprogramului . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 pct.
Problema 2
Se consideră două secvent, e de câte n valori naturale a1, a2, . . ., an respectiv b1, b2, . . ., bn. Se pune problema
determinării unei permutări de ordin n, p = (p(1), p(2), . . . , p(n)) astfel încât suma |a1 − bp(1)| + |a2 − bp(2)| + . . . +
|an − bp(n)| să fie cât mai mare. Descriet, i un algoritm care permite obt, inerea permutării s, i sumei corespunzătoare.
De exemplu pentru a = (5, 9, 12, 4) s, i b = (7, 2, 15, 5) o permutare care satisface cerint, a este p = (1, 4, 2, 3),
suma fiind |5 − 7| + |9 − 5| + |12 − 2| + |4 − 15| = 27.
Prezentat,i pe scurt ideea de rezolvare, justificat,i că ideea este corecta si s, i descriet,i solut,ia în pseudocod sau
într-un limbaj de programare la alegere (C/C++, Pascal, Python).
Idei de rezolvare
Varianta 1: Pentru construirea permutării se parcurg elementele lui a în ordine descrescătoare s, i a lui b în ordine
crescătoare. La primul pas se va completa în permutare p[pozmaxa ] = pozminb s, i se continua procesul.
Varianta 2: Generarea tuturor permutărilor s, i selectarea celei de sumă maximă (varianta aceasta este ineficientă).
BAREM
Start . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 pct.
Idee rezolvare - specificare modului de obt, ine al permutării . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 pct.
Argumentarea corectitudinii algoritmului propus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 pct.
Declarat, ii de variabile care descriu structurile utilizate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 pct.
Construirea corectă a permutarii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2 pct.
Calculul corect al sumei . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 pct.
8

Subiect și barem · pagina 9

Problema 3
Pentru un grup de n persoane se cunosc perechile de persoane care intră frecvent în contact (fac parte din aceeas, i
familie sau lucrează împreună). În contextul răspândirii unei epidemii se consideră că toate persoanele care au
intrat în contact cu o persoană infectată devin infectate. Cunoscând care este pacientul 0 determinat, i numărul de
persoane care au fost infectate.
Exemplu: n = 7 s, i perechile de persoane care intră în contact sunt: (P1, P2), (P1, P4), (P1, P7), (P3, P6) s, i
(P5, P6). În ipoteza că pacientul zero este P2 modul de răspândire al infect, ie este: la etapa 1 se infectează P1,
la etapa 2 se infectează P4 s, i P7 s, i procesul de răspândire a infect, iei se opres, te deoarece nu mai există persoane
neinfectate care au intrat în contact cu o persoană infectată, numărul de persoane infectate fiind 4.
Prezentat,i pe scurt ideea de rezolvare s, i descriet,i solut,ia în pseudocod sau într-un limbaj de programare la alegere
(C/C++, Pascal, Python).
Idei de rezolvare
Varianta 1: Relat, iile dintre persoane se pot reprezenta sub forma unui graf, iar numărul de noduri (determinat
prin parcurgere în adancime sau în lăt, ime) din subgraful care cont, ine persoana zero reprezintă solut, ia problemei.
Varianta 2: Pentru a reprezenta contactele se poate folosi o matrice (m), mi,j = 1 dacă persoana i a intrat
în contact cu persoana j. Pentru a determina numărul de persoane infectate se poate folosi un vector (v) care
stochează informat, ia dacă persoana este infectată sau nu. Se pornes, te de la persoana zero (p0) s, i se caută persoanele
cu care este în contact mp0,k = 1, k = 1, n. În prima etapă se marchează ca infectate toate persoanele aflate în
contact direct cu pacientul p0. La etapa următoare se marchează ca infectate toate persoanele neinfectate care sunt
în contact direct cu cele infectate la etapa anterioară. Procesul va continua până când nu mai apar persoane nou
infectate.
BAREM
Start . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 pct.
Idee rezolvare - descrierea procesului de răspândire a infect, iei . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 pct.
Descrierea structurilor de date folosite s, i declarat, ii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 pct.
Implementarea algoritmului de răspândire a infect, iei . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 pct.
Determinarea corectă a numărului de persoane infectate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 pct.
9

Deschide documentul original

Continuă pregătirea

Vezi arhiva completă

Concurs de pregătire · 2021Informatică · Etapa 2Deschide fișa Concurs de pregătire · 2021Matematică · Clasa a XI-a, etapa 1Deschide fișa Concurs de pregătire · 2021Matematică · Clasa a XII-a, etapa 1Deschide fișa Examen de admitere · 2021Informatică · Sesiunea iulie; subiect oficialDeschide fișa Examen de admitere · 2021Matematică · Sesiunea iulie; subiect oficialDeschide fișa Concurs de pregătire · 2022Informatică · Etapa 1Deschide fișa

Răspunsuri directe

Ce trebuie să știi despre acest subiect?

Ce document de admitere este acesta?

Pagina prezintă concurs de pregătire din 2021 pentru Informatică, la Facultatea de Informatică. Documentul este etichetat după instituție, facultate, program și tipul probei folosind inventarul public verificat. Consultă metodologia actuală a instituției pentru condițiile examenului viitor.

Există și barem sau răspunsuri pentru acest subiect?

Da. Pagina include baremul sau răspunsurile publice asociate acestui subiect, afișate separat ori în același document atunci când sursa le publică împreună. Verifică fiecare rezolvare după ce ai terminat varianta și urmărește exact criteriile de punctare indicate de instituție.

Cum folosesc acest subiect în pregătirea pentru admitere?

Rezolvă documentul fără ajutor și respectă timpul prevăzut de metodologia examenului. Corectează cu baremul disponibil, marchează capitolele unde ai pierdut puncte și repetă exerciții similare. Compară apoi cu alte probe din aceeași facultate și confirmă programa curentă pe site-ul oficial al instituției.

Pregătire cu un profesor

Subiect și barem

Concurs de pregătire · Informatică · 2021

Despre acest subiect

Subiectul și baremul în format text

Subiect și barem · pagina 1