Pregătire cu un profesor

Concurs de admitere – Barem
Facultatea de Matematic˘a s, i Informatic˘a
Universitatea de Vest din Timis, oara
Sesiunea Iulie, 2024
1. Timp total de lucru: 3 ore
2. Toate subiectele sunt obligatorii!
3. Citit, i cu atent, ie informat, iile legate de tipurile de întreb˘ari, prezentate mai jos.
Tipuri de întreb˘ari
Pe foaia de concurs vet, i întâlni trei tipuri de întreb˘ari. Pentru a le recunoas, te mai us, or, în partea dreapt˘a
vet, i reg˘asi un s, ablon pentru r˘aspunsuri, cu indicat, ii legate de tipul de întrebare.
Tipul 1 Pentru întreb˘arile de acest tip vet, i marca pe foaia de concurs MODEL, marcat, i exact un r˘aspuns:
1 2 3 4un singur r˘aspuns corect. Le vet, i recunoas, te dup˘a modelul indicat
în partea dreapt˘a a acestui rând.
Punctaj pe întrebare: 2p (standard)+1p (bonus pentru r˘aspuns complet).
Tipul 2 Pentru întreb˘arile de acest tip vet, i marca pe foaia de concurs MODEL, marcat, i 1-2 r˘aspunsuri:
1 2 3 4 5fie un singur r˘aspuns corect, fie dou˘a r˘aspunsuri corecte. Le vet, i
recunoas, te dup˘a modelul indicat în partea dreapt˘a a acestui rând.
Punctaj maxim pe întrebare: 2p (standard)+1p (bonus pentru r˘aspuns complet) sau 2x2p (standard, pe
variant˘a)+1p (bonus pentru r˘aspuns complet).
Tipul 3 Pentru întreb˘arile de acest tip vet, i marca pe foaia de concurs MODEL, marcat, i 1-3 r˘aspunsuri:
1 2 3 4 5fie un singur r˘aspuns corect, fie dou˘a r˘aspunsuri corecte, fie trei
r˘aspunsuri corecte. Le vet, i recunoas, te dup˘a modelul indicat în
partea dreapt˘a a acestui rând.
Punctaj maxim pe întrebare: 2p (standard)+1p (bonus pentru r˘aspuns complet) sau 2x2p/2x3p (stan-
dard, pe variant˘a)+1p (bonus pentru r˘aspuns complet).
Punctaj
Fiecare variant˘a de r˘aspuns corect˘a valoreaz˘a exact 2 puncte. Dac˘a r˘aspunsul oferit identific˘a toate vari-
antele corecte de r˘aspuns, la punctajul întreb˘arii se adaug˘a un bonus pentru r˘aspuns complet de 1 punct.
Orice r˘aspuns gres, it anuleaz˘a întregul punctaj al întreb˘arii respective, indiferent de num˘arul de r˘aspunsuri
corecte.
La punctajul obt, inut se adaug˘a 10 puncte, pentru start.
Pentru nota 5 sunt necesare 40 de puncte, inclusiv punctele de start, pentru nota 10 sunt necesare cel put, in
80 de puncte, inclusiv punctele de start.

Subiect · pagina 2

2
Partea I
Problema 1: Calcul statistic
Profesor Zoom preg˘ates, te un chestionar cu 6 întreb˘ari. Singurele r˘aspunsuri posibile la fiecare întrebare
sunt „Da”, „Nu”, „Poate”. Deoarece profesorul Zoom dores, te s˘a afle combinat, iile de r˘aspunsuri posibile,
acesta apeleaz˘a la Departamentul de Calcul Statistic pentru a realiza o structur˘a de date care s˘a colecteze
r˘aspunsurile chestionarului. Statisticienii decid s˘a utilizeze o structur˘a de baz˘a care va cont, ine 6 pozit, ii de
memorie, câte o pozit, ie pentru fiecare întrebare. Fiecare pozit, ie poate cont, ine valoarea 0 pentru r˘aspunsul
„Da”, valoarea 1 pentru „Nu” s, i valoarea 2 pentru „Posibil”. R˘aspunsul unui respondent la chestionar
poate ar˘ata astfel:
2 0 0 1 2 1
Departamentul de Calcul Statistic decide s˘a declare o matrice pentru toate combinat, iile posibile de
r˘aspunsuri. Care va fi num˘arul maxim de r˘aspunsuri posibile? Ciorn˘a, marcat, i exact un r˘aspuns:
1 2 3 4
1 3 2 6 3 18 4 729 "
Fiecare r˘aspuns posibil este un vector cu 6 elemente în care fiecare element are una din 3 valori posibile.
Prin urmare, r˘aspunsul corect este 36 = 729.
Problema 2: Amintiri din... facultate
Doi fos, ti colegi de la FMI/UVT, Andrei s, i Radu, se întâlnesc dup˘a 20 de ani de la terminarea facult˘at, ii,
pe trotuarele opuse ale aceleias, i str˘azi. Dup˘a ce se salut˘a s, i se întreab˘a reciproc despre situat, ia person-
al˘a, Radu îi spune celuilalt c˘a are trei b˘aiet, i. Curios, Andrei îl întreab˘a care sunt vârstele acestora. Radu,
glumet, din fire, îi spune c˘a produsul vârstelor lor este 72, s, i c˘a suma vârstelor lor este egal˘a cu num˘arul
casei din colt, , indicând spre casa din colt, în acelas, i timp. Andrei, dup˘a ce vede num˘arul casei, st˘a o clip˘a
pe gânduri, s, i îi spune apoi - "Bine, dar... mai am nevoie de ceva indicii!". Radu îi spune pe urm˘a: "As, a e,
îmi cer scuze - pe cel mai mare dintre ei îl cheam˘a tot Andrei!".
Care sunt vârstele celor trei b˘aiet, i? Ciorn˘a, marcat, i exact un r˘aspuns:
1 2 3 4
1 2, 2, 18 2 2, 6, 6 3 3, 3, 8 " 4 2, 3, 12
Dac˘a x ≤ y ≤ z sunt vârstele celor trei b˘aiet, i, ¸stim c˘a xyz = 72, deci (x, y, z) ∈ {(1,3,24), (1,4,18), (1,6,12),
(1,8,9), (2,2,18), (2,3,12),(2,4,9), (2,6,6), (3,3,8), (3,4,6)}. Deoarece Andrei nu poate deduce x, y, z, înseamn˘a
c˘a sunt 2 gemeni (x, y, z) ¸si (x′, y′, z′) pentru care x + y + z = x′ + y′ + z′. Singurele cazuri sunt (2,6,6)
¸si (3,3,8). Dup˘a ce afl˘a c˘a exist˘a un frate mai mare, Andrei ¸stie c˘a y < z, deci singura posibilitate este
(x, y, z) = (3, 3, 8).
Problema 3: Arbore genealogic
Andreea îl prezint˘a pe Marius ca fiind fiul fratelui mamei ei. Care dintre urm˘atoarele afirmat, ii este ade-
v˘arat˘a?

Subiect · pagina 3

admiterefmi@uvt, iulie 2024 3
Ciorn˘a, marcat, i exact un r˘aspuns:
1 2 3 4
1 Andreea este mama lui Marius.
2 Marius este nepotul Andreei.
3 Andreea este veris, oara lui Marius. "
4 Andreea s, i Marius sunt frate/sor˘a.
Problema 4: Minerul
Într-un joc, personajul principal – s˘a zicem, Mr. Mine, un miner – trebuie s˘a sape o galerie de zece metri
pentru a ajunge la un filon de aur. În fiecare zi sap˘a câte trei metri, dar noaptea, când se odihnes, te, se
surp˘a câte doi metri.
În a câta zi ajunge acesta la filonul de aur? Ciorn˘a, marcat, i exact un r˘aspuns:
1 2 3 4
1. în ziua a 8-a "
2. în ziua a 9-a
3. niciodat˘a
4. în ziua a 10-a
Se observ˘a c˘a înainte de c˘aderea nop¸tii în ziua n, Mr. Mine ajunge la 3n − 2(n − 1) = n + 2 metri adân-
cime. Din ecuat, ia n + 2 = 10 rezult˘a n = 8. Deci Mr. Mine ajunge la filonul de aur de la zece metri adân-
cime în ziua a 8-a.
Problema 5: Robotul Felix
Robotul Felix poate executa doar dou˘a tipuri de comenzi: s˘a mearg˘a 1 metru în fa¸t˘a sau s˘a mearg˘a 1 metru
la dreapta. Un ordin este o secven¸t˘a de comenzi ce pot fi executate de Felix. De exemplu, ordinul FDDF îi
comand˘a lui Felix s˘a mearg˘a 1 metru în fa¸t˘a, apoi 2 metri la dreapta, apoi 1 metru în fa¸t˘a.
Câte ordine îl pot determina pe Felix s˘a ajung˘a la pozi¸tia aflat˘a la 5
metri în fa¸t˘a s, i 4 metri la dreapta? Ciorn˘a, marcat, i exact un r˘aspuns:
1 2 3 4
1 20 2 126 " 3 9 4 120
Orice astfel de ordin este o secven¸t˘a de 9 comenzi alc˘atuit˘a din cinci F pentru deplasare în fa¸t˘a, ¸si patru
D pentru deplasare la dreapta. Num˘arul ordinelor coincide cu num˘arul posibilit˘a¸tilor de a alege 4 din 9
pozi¸tii unde s˘a apar˘a D în secven¸ta de comenzi, adic˘a C4
9 = 126.
Problema 6: Ce face?
Se consider˘a func¸tia definit˘a în modul ilustrat mai jos:
funct, ia ceFace(întreg n) : întreg
întreg b, m = n, r = 0
cât timp m ≥ 10 execut˘a
b = m mod 10
dac˘a b mod 2 > 0 atunci

Subiect · pagina 4

4
r = r + 1
m = (m − b)/10
dac˘a m mod 2 > 0 atunci
r = r + 1
întoarce r
unde a mod b returneaz˘a restul împ˘ar¸tirii lui a cu b.
Presupunând c˘a n este un întreg pozitiv, ce reprezint˘a valoarea returnat˘a de ceFace(n)?
1 Reprezentarea num˘arului n în baza 2 Ciorn˘a, marcat, i exact un r˘aspuns:
1 2 3 4
2 Cel mai mare num˘ar întreg r astfel încât 2r < n
3 Cel mai mic num˘ar întreg r astfel încât 2r ≥ n
4 Num˘arul cifrelor impare din reprezentarea zecimal˘a a lui n"
b este instan¸tiat succesiv cu toate cifrele din reprezentarea zecimal˘a a lui n. r este incrementat ori de câte
ori b este cifr˘a impar˘a. Deci func¸tia aceasta calculeaz˘a num˘arul cifrelor impare din reprezentarea zecima-
l˘a a lui n.
Problema 7: Ce face?
Se consider˘a algoritmul urm˘ator
procedura Afiseaza(întreg n)
întreg x = 1, y = f loor(n/2), z
cât timp x̸ = 0 ¸si y > 0 execut˘a
z = n
cât timp z ≥ y execut˘a
z = z − y
x = z
y = y − 1
y = y + 1
Tip˘are¸ste y
unde f loor(x) returneaz˘a partea întreag˘a a num˘arului real x.
Care este valoarea tip˘arit˘a de Afiseaza(435)? Ciorn˘a, marcat, i exact un r˘aspuns:
1 2 3 4
1 217 2 3 3 145 " 4 29
Afiseaza(n) afi¸seaz˘a cel mai mare divizor al lui n, diferit de n.
Partea a II-a
Problema 8: Secven¸t˘a maximal˘a
Se consider˘a algoritmul RunMe(T, n), descris mai jos, unde T este un tablou de n numere întregi, iar n
num˘ar natural, pozitiv.

Subiect · pagina 5

admiterefmi@uvt, iulie 2024 5
funct, ia RunMe(întreg T[1..n], întreg n)
Smax = −MAXINT
S = −1
pentru i = 1, n execut˘a
dac˘a (A) atunci
S = 0
S = S + T[i]
dac˘a (B) atunci
Smax = S
Pentru ca algoritmul de mai sus s˘a calculeze suma elementelor din secvent, a maximal˘a, adic˘a acea
secvent, ˘a de elemente consecutive pentru care suma este maxim˘a, condi¸tiile (A) s, i (B) trebuie înlocuite
cu: Ciorn˘a, marcat, i 1-2 r˘aspunsuri:
1 2 3 4 5
1 A := S < 0 "
2 A := S > 0
3 B := S < Smax
4 B := S > Smax "
5 B := S > Smax − T[i]
Variantele corecte sunt A := S < 0 ¸si B := S > Smax.
Problema 9: Silogism cu culori
Se consider˘a adev˘arate afirmat, iile urm˘atoare: (Afirmat, ia 1) ROS, U sunt doar ROZ; (Afirmat, ia 2) Unele
ROZ sunt MAGENTA; (Afirmat, ia 3) Doar câteva MAGENTA sunt ALBASTRU.
Folosindu-v˘a de afirmat, iile de mai sus, evaluat, i urm˘atoarele concluzii: (Concluzia 1) Unele MAGENTA
sunt ROS, U; (Concluzia 2) Exist˘a ALBASTRU care este ROZ; (Concluzia 3) Exist˘a MAGENTA care nu este
ALBASTRU; (Concluzia 4) Unele ALBASTRU nu sunt MAGENTA.
Care dintre urm˘atoarele r˘aspunsuri se poate deduce cu certitudine?
1 Cel put, in una dintre concluziile 1 sau 2 este corect˘a; Ciorn˘a, marcat, i 1-2 r˘aspunsuri:
1 2 3 4 5
2 Cel put, in una dintre concluziile 2 sau 3 este corect˘a; "
3 Nicio concluzie nu este corect˘a;
4 Cel put, in una dintre concluziile 1 sau 3 este corect˘a; "
5 Concluzia 4 este corect˘a.
Doar concluzia 3 se poate deduce cu certitudine, deci r˘aspunsurile corecte sunt 2 ¸si 4.
Problema 10: Zoo-Ro
Se s, tie c˘a n ¸si a sunt numere întregi strict pozitive, s, i c˘a v este un vector de n numere întregi strict pozitive.
Se consider˘a func¸tiile urm˘atoare (mod este operator pentru determinarea restului împ˘art, irii a dou˘a numere
întregi, iar div este operator pentru determinarea câtului împ˘art, irii a dou˘a numere întregi):

Subiect · pagina 6

6
funct, ia Ro(întreg n, întreg a): întreg
dac˘a (n mod a) == 0 atunci
întoarce 1+Ro(n div a,a)
altfel
întoarce 0
funct, ia Zoo(întreg v[1..n],întreg n): întreg
întreg r = 0, tmp
întreg x[1..n], y[1..n]
pentru i = 1, n execut˘a
x[i] = Ro(v[i], 2)
y[i] = Ro(v[i], 5)
pentru i = 1, n − 1 execut˘a
pentru j = i + 1, n execut˘a
tmp = min(x[i] + x[j], y[i] + y[j])
dac˘a tmp > r atunci
r = tmp
întoarce r
Care dintre urm˘atoarele afirmat, ii sunt adev˘arate? Aleget, i toate variantele corecte.
1 Ro(n, a) returneaz˘a câtul împ˘ar¸tirii lui n cu a. , marcat, i 1-2 r˘aspunsuri:
1 2 3 4 5
2 Ro(n, a) returneaz˘a cel mai mare întreg r astfel încât ar divide pe
n. "
3 Zoo(v, n) returnez˘a cel mai mare întreg r astfel încât 10r divide un
element al lui v.
4 Zoo(v, n) returnez˘a cel mai mare întreg r astfel încât 2r sau 5r
divide un produs de dou˘a elemente distincte ale lui v.
5 Zoo(v, n) returnez˘a num˘arul maxim de zerouri de la sfâr¸situl unui
produs de dou˘a elemente distincte ale lui v."
Ro(n, a) returneaz˘a cel mai mare întreg r astfel încât ar divide pe n. De asemenea, Zoo(v, n) instan¸tiaz˘a
fiecare x[i] cu cel mai mare întreg a.î. 2x[i] s˘a fie factor al lui v[i], ¸si y[i] cu cel mai mare întreg a.î. 5y[i]
s˘a fie factor al lui v[i]. Prin urmare, min(x[i] + x[j], y[i] + y[j]) va fi cel mai mare întreg z astfel încât 10z
s˘a fie factor al produsului v[i] ∗ v[j]. Deci Zoo(n) returneaz˘a num˘arul maxim de zerouri de la sfâr¸situl
unui num˘ar din mul¸timea {v[i] ∗ v[j] | 1 ≤ i < j ≤ n}, adic˘a ale unui produs de dou˘a elemente dis-
tincte ale lui v.
Problema 11: Elemente de matrici
Se consider˘a o matrice p˘atratic˘a A de ordin n, s, i se presupune c˘a elementele aflate sub diagonala princi-
pal˘a sunt stocate într-un tablou prin parcurgerea linie cu linie a matricii. Presupunând c˘a indicii tabloului
pornesc de la 1, c˘arui element din matrice corespunde elementul din tablou de pe pozit, ia (i − 2)(i − 1)/2 +
j, cu i > j ≥ 1? Ciorn˘a, marcat, i 1-2 r˘aspunsuri:
1 2 3 4 5

Subiect · pagina 7

admiterefmi@uvt, iulie 2024 7
1 ai−2,j
2 ai−1,j
3 ai,j "
4 ai+1,j
5 ai−1,j−1
Tabloul va cont, ine elementele a21, a31, a32, a41, a42, a43, ... deci pozit, ia pe care se afl˘a elementul ai,j este 1 +
2 + . . . + (i − 2) + j adic˘a (i − 2)(i − 1)/2 + j. Deci r˘aspunsul corect este ai,j.
Problema 12: O clic˘a de arbori
Fie T un arbore cu n noduri, ¸si v un nod al acestuia. Construim un graf neorientat G în felul urm˘ator:
cre˘am m > 2 copii distincte T1, . . . , Tm ale lui T ¸si ad˘aug˘am toate muchiile posibile între nodurile v1, . . . ,
vm, unde vi este copia din arborele Ti a nodului v. În G, num˘arul total de muchii este 27.
Care dintre urm˘atoarele afirmat, ii pot fi adev˘arate? Aleget, i toate
variantele corecte. Ciorn˘a, marcat, i 1-2 r˘aspunsuri:
1 2 3 4 5
1 m = 3, n = 3.
2 m = 3, n = 9. "
3 m = 3, n = 6.
4 m = 6, n = 3. "
5 m = 6, n = 9.
G are m · (n − 1) + m · (m − 1)/2 = m · (m + 2 n − 3)/2 muchii. Din ecua¸tia
m · (n − 1) + m · (m − 1)/2 = m · (m + 2 n − 3)/2 = 27
rezult˘a c˘a m · (m + 2 n − 3) = 54, prin urmare (m, n) ∈ {(3, 9), (6, 3)}.
Problema 13: C˘autare în labirint
Se consider˘a labirintul ilustrat mai jos, în care celulele negre reprezint˘a obstacole.
S
G1 2 5
6 7 9 10
12 14 15
16 17 19 20
21 22 23 24 25
Se pune problema g˘asirii unui drum de la celula de start S la celula G cu ajutorul metodei de parcurgere
în l˘a¸time (Breadth First). Pe durata parcurgerii în l˘a¸time se aplic˘a urm˘atoarele reguli:
1. Vizitarea celulelor se face în ordinea: sus, dreapta, jos, stânga. Nu este posibilã mutarea pe diagonalã.
2. Nici o celul˘a nu se poate vizita de dou˘a ori.
De exemplu, c˘autarea în l˘a¸time a unui drum pornind de la S începe cu vizitarea celulelor 6, 12, 16, în
aceast˘a ordine. Fie σ secven¸ta de celule de pe drumul g˘asit de c˘autarea în l˘a¸time, care începe cu S ¸si se
termin˘a cu G.
Care dintre urm˘atoarele afirmat, ii sunt adev˘arate? Aleget, i toate vari-
antele corecte. Ciorn˘a, marcat, i 1-2 r˘aspunsuri:
1 2 3 4 5

Subiect · pagina 8

8
1 σ are 11 celule.
2 σ are 12 celule. "
3 14 este în σ.
4 10 este în σ. "
5 9 este în σ.
Parcurgerea în l˘a¸time de la celula de start S produce arborele de c˘autare ilustrat mai jos
Drumul de la S la G este σ = [S, 12, 17, 22, 23, 24, 25, 29, 15, 10, 5,G].
S
17 2117
22
23
24
25
20
15
10
5
G
9
14
6 12 16
1
2
7
Problema 14: Continuarea c˘autarii
Pentru labirintul de la problema anterioar˘a se dore¸ste g˘asirea unui drum de la S la G cu metoda de par-
curgere în adâncime (Depth First). Pe durata parcurgerii în adâncime se aplic˘a acelea¸si reguli:
1. Vizitarea celulelor se face în ordinea: sus, dreapta, jos, stânga. Nu este posibilã mutarea pe diagonalã.
2. Nici o celul˘a nu se poate vizita de dou˘a ori.
Fie γ secven¸ta de celule de pe drumul g˘asit de c˘autarea în adâncime, care începe cu S ¸si se termin˘a cu G.
Care dintre urm˘atoarele afirmat, ii sunt adev˘arate? Aleget, i toate vari-
antele corecte. Ciorn˘a, marcat, i 1-2 r˘aspunsuri:
1 2 3 4 5

Subiect · pagina 9

admiterefmi@uvt, iulie 2024 9
1 γ are 12 celule.
2 γ are 13 celule.
3 γ are 16 celule. "
4 2 este în γ. "
5 14 este în γ.
Parcurgerea în adâncime de la celula de start S g˘ase¸ste urm˘atorul drum de la S la G:
[S, 6, 1, 2, 7, 12, 17, 22, 23, 24, 25, 20, 15, 10, 5,G]. Prin urmare op¸tiunile corecte sunt cele bifate.
Problema 15: Backtracking
Având la dispozi¸tie cinci m˘argele de culori diferite: ro¸su, galben, verde, albastru, violet, se utilizeaz˘a
metoda backtracking pentru a ob¸tine toate posibilit˘a¸tile de a forma ¸siruri de câte trei m˘argele, ¸stiind c˘a
în cadrul unui ¸sir conteaz˘a ordinea de a¸sezare a m˘argelelor. Culorile m˘argelelor, corespunz˘atoare primelor
trei solu¸tii ob¸tinute sunt, în aceast˘a ordine; (verde, galben,ro¸su), (verde, galben, albastru), (verde, galben,
violet).
Indica¸ti care dintre variantele de mai jos sunt printre ultimele dou˘a
solu¸tii generate. Ciorn˘a, marcat, i 1-2 r˘aspunsuri:
1 2 3 4 5
1 (galben, verde, albastru)
2 (violet, albastru, verde)
3 (violet, albastru, galben) "
4 (violet, albastru, ro¸su) "
5 (violet, galben, verde)
¸Stim c˘a algoritmul de backtracking enumer˘a primele patru solu¸tii în ordinea (1, 2, 3), (1, 2, 4), (1, 2, 5).
Deducem c˘a cele cinci culori disponibile sunt vizitate în ordinea: verde (1), galben (2), ro¸su (3), albas-
tru (4), violet (5). Algoritmul de backtracking enumer˘a, de la stânga la dreapta, toate tripletele de culori
ale c˘ailor de la r˘ad˘acin˘a la nodurile frunz˘a ale arborelui ilustrat mai jos:
•
1
2
3
5
4
2
1
3
5
4
3
1
2
5
4
4
1
2
5
3
5
1
2
4
2 3
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
Ultimele dou˘a solu¸tii generate sunt (5, 4, 2) ¸si (5, 4, 3), adic˘a
(violet, albastru, galben), (violet, albastru, ro¸su).

Subiect · pagina 10

10
Partea a III-a
Problema 16: Funct, ia Fct
Se d˘a urm˘atoarea funct, ie (mod este operator pentru determinarea restului împ˘art, irii a dou˘a numere întregi,
iar div este operator pentru determinarea câtului împ˘art, irii a dou˘a numere întregi):
funct, ia fct(întreg a[1..n], întreg b) : întreg
întreg c = b, s = 0
pentru i = 1, n execut˘a
b = c
ok = true
cât timp (a[i] > 0) and (b > 0) and ok execut˘a
dac˘a (a[i] mod 10)̸ = (b mod 10) atunci
ok = false
altfel
a[i] = a[i] div 10
b = b div 10
dac˘a (a[i] > 0) and (b == 0) atunci
s = s + 1
întoarce s
Care dintre urm˘atoarele afirmat, ii sunt adev˘arate? Aleget, i toate variantele corecte.
1 Funct, ia de mai sus determin˘a num˘arul de numere din tabloul a
care cont, in num˘arul b. Ciorn˘a, marcat, i 1-3 r˘aspunsuri:
1 2 3 4 5
2 Funct, ia de mai sus determin˘a num˘arul de numere din tabloul a
care au ca sufix num˘arul b. "
3 Funct, ia de mai sus determin˘a num˘arul de numere din tabloul a
care au ca prefix num˘arul b.
4 Dac˘a a cont, ine numerele 1234, 2345, 345634, 34, 5634 s, i b este egal
cu 34, funct, ia returneaz˘a 3. "
5 Dac˘a a cont, ine numerele 1234, 2345, 345634, 34, 563 s, i b este egal
cu 34, funct, ia returneaz˘a 4.
Funct, ia analizeaz˘a fiecare element din tabloul a, verificând dac˘a acesta se termin˘a cu secvent, a de cifre re-
prezentat˘a de b, s, i contorizeaz˘a câte dintre aceste elemente respect˘a condit, ia dat˘a.
Problema 17: Arbori ¸si p˘aduri
Se s, tie c˘a n > 0 este un num˘ar întreg ¸si c˘a v este un vector de n elemente distincte indexate de la 1 la n. E-
lementele lui v sunt noduri într-o p˘adure de arbori, reprezentat˘a cu un vector de predecesori p[1], . . . , p[n]:
Dac˘a p[i] = j atunci v[j] este p˘arintele lui v[i]. Dac˘a p[i] = 0 atunci v[i] este nod r˘ad˘acin˘a.
Se consider˘a func¸tiile urm˘atoare:

Subiect · pagina 11

admiterefmi@uvt, iulie 2024 11
funct, ia Foo(): întreg
boolean flag[1..n]
întreg r = 0
pentru i = 1, n execut˘a
flag[i] = true
pentru i = 1, n execut˘a
dac˘a p[i] > 0 atunci
flag[p[i]] = false
pentru i = 1 to n execut˘a
dac˘a flag[i] == true atunci
r = r + 1
întoarce r
funct, ia Moo(întreg i, întreg j): boolean
întreg d1 = i, d2 = j
cât timp p[d1] > 0 execut˘a
dac˘a p[d1] == j atunci
întoarce true
d1 = p[d1]
cât timp p[d2] > 0 execut˘a
dac˘a p[d2] == i atunci
întoarce true
d2 = p[d2]
întoarce false
Care dintre urm˘atoarele afirmat, ii sunt adev˘arate când 1 ≤ i, j ≤ n, i̸ = j? Aleget, i toate variantele
corecte.
1 Foo() returneaz˘a num˘arul de arbori din p˘adure. Ciorn˘a, marcat, i 1-3 r˘aspunsuri:
1 2 3 4 5
2 Moo(i, j) returneaz˘a true dac˘a v[i] ¸si v[j] sunt în acela¸si arbore.
3 Foo() returneaz˘a num˘arul de noduri frunz˘a. "
4 Moo(i, j) returneaz˘a true dac˘a v[j] este un descendent direct sau
indirect al nodului v[i] într-un arbore."
5 Moo(i, j) returneaz˘a true dac˘a v[i] este un descendent direct sau
indirect al nodului v[j] într-un arbore."
Foo() seteaz˘a flag[j] s˘a fie false doar dac˘a j = p[i] pentru un i cuprins între 1 ¸si n, adic˘a dac˘a v[j] nu
este nod frunz˘a. Prin urmare ultima bucl˘a a func¸tiei Foo() contorizeaz˘a în r num˘arul de noduri frunz˘a.
Primul
intoarce true
din Moo(i, j) are loc dac˘a v[i] este descendent al lui v[j].
Al doilea
intoarce true
din Moo(i, j) are loc dac˘a v[j] este descendent al lui v[i].
Deci Moo(i, j) returneaz˘a true în ambele cazuri: dac˘a v[j] este descendent al lui v[i], ¸si dac˘a v[i] este
descendent al lui v[j].
Problema 18: Arbori binheap
Un arbore binheap satisface condi¸tiile urm˘atoare: (1) toate nodurile frunz˘a sunt la aceea¸si distan¸t˘a fa¸t˘a de
r˘ad˘acin˘a; (2) toate celelalte noduri au exact doi descenden¸ti; (3) toate nodurile sunt etichetate cu numere;
¸si (4) eticheta oric˘arui descendent y al unui nod x este un num˘ar strict mai mare decât eticheta lui x. Fie hn
num˘arul arborilor binheap de adâncime n cu nodurile etichetate cu toate numerele de la 1 la 2n+1 − 1. De
exemplu, h1 = 2 pentru c˘a sunt doi arbori binheap de adâncime 1:
1
2 3 ¸si
1
3 2

Subiect · pagina 12

12
Care dintre urm˘atoarele afirma¸tii sunt adev˘arate? Alege¸ti toate variantele corecte.
1 hn = Cn
2n · hn−1 · hn−1 pentru to¸ti n > 0. Ciorn˘a, marcat, i 1-3 r˘aspunsuri:
1 2 3 4 5
2 hn = C2n −1
2n+1−2 · hn−1 · hn−1 pentru to¸ti n > 0."
3 hn = n + 1 pentru to¸ti n > 0.
4 h2 = 80."
5 h2 = 24.
Fie Sn mul¸timea arborilor binheap de adâncime n cu noduri etichetate cu numerele de la 1 la 2n+1 − 1.
Orice arbore T din Sn are nodul r˘ad˘acin˘a etichetat cu 1 ¸si doi sub-arbori binheap T1, T2 cu adâncimea n −
1. Sunt C2n −1
2n+1−2 posibilit˘a¸ti s˘a fix˘am mul¸timea etichetelor de noduri din subarborele T1, hn−1 posibilit˘a¸ti
s˘a etichet˘am nodurile lui T1 cu ele, ¸si hn−1 posibilit˘a¸ti s˘a etichet˘am nodurile lui T2 cu numerele r˘amase.
Rezult˘a c˘a Sn are hn = C2n −1
2n+1−2 · hn−1 · hn−1 arbori. În particular, h2 = C3
6 · h1 · h1 = 20 · 2 · 2 = 80.
Problema 19: O func¸tie recursiv˘a
Se consider˘a func¸tia recursiv˘a de mai jos:
funct, ia f(întreg n): întreg
dac˘a n ≤ 3 atunci
întoarce 1
altfel
întoarce f(n − 1)+f(n − 2) + f(n − 3)
Dac˘a primul apel este f(10), de câte ori se calculeaz˘a f(4)? Alege¸ti
toate variantele corecte. Ciorn˘a, marcat, i 1-3 r˘aspunsuri:
1 2 3 4 5
1 De mai pu¸tin de 26 ori "
2 De mai mult de 20 ori "
3 De 25 ori
4 Niciodat˘a
5 O dat˘a
Fie x(n) num˘arul de calcule ale lui F(4) pe durata unui apel F(n). Se observ˘a c˘a x(n) = x(n − 1) + x(n −
2) + x(n − 3) dac˘a n ≥ 5 ¸si c˘a x(4) = 1, x(3) = x(2) = 0. Deci x(5) = 1 + 0 + 0 = 1, x(6) = 1 + 1 + 0 =
2, x(7) = 1 + 1 + 2 = 4, x(8) = 1 + 2 + 4 = 7, x(9) = 2 + 4 + 7 = 13, x(10) = 4 + 7 + 13 = 24. A¸sadar
F(4) se calculeaz˘a de exact 24 ori.
Problema 20: Da sau Nu
Se ¸stie c˘a A este un tablou de dimensiune m × n ale c˘arui elemente A[i][j] sunt numere reale indexate cu
1 ≤ i ≤ m ¸si 1 ≤ j ≤ n. Se presupune c˘a m, n ≥ 1 ¸si se consider˘a algoritmul urm˘ator:
procedura DaSauNu(float A[1..m][1..n], float x)
boolean ok = false

Subiect · pagina 13

admiterefmi@uvt, iulie 2024 13
pentru i = 1, m execut˘a
dac˘a (i == 1) sau (i == m) atunci
pentru j = 1, n execut˘a
dac˘a A[i][j] == x atunci
Tip˘are¸ste "Da"
ok = true
altfel
dac˘a (A[i][1] == x) sau (A[i][n] == x) atunci
Tip˘are¸ste "Da"
ok = true
dac˘a ok == false atunci
Tip˘are¸ste "Nu"
Fie d num˘arul maxim de "Da" ce pot fi afi¸sa¸ti de c˘atre acest algoritm. Care dintre urm˘atoarele afirmat, ii
sunt adev˘arate? Aleget, i toate variantele corecte.
1 d = 2 · m Ciorn˘a, marcat, i 1-3 r˘aspunsuri:
1 2 3 4 5
2 d = 2 · (m + n − 2) "
3 Algoritmul afi¸seaz˘a "Nu" dac˘a x nu se g˘ases, te pe conturul tabloului
A, format din prima linie, ultima linie, prima coloan˘a s, i ultima
coloan˘a. "
4 Algoritmul afi¸seaz˘a cel pu¸tin un "Da" dac˘a x este o valoare de pe
conturul tabloului A, format din prima linie, ultima linie, prima
coloan˘a s, i ultima coloan˘a. "
5 Algoritmul afi¸seaz˘a cel pu¸tin un "Da" dac˘a tabloul A con¸tine un
element egal cu x.
Algoritmul parcurge toate elementele de pe conturul matricii A ¸si afi¸seaz˘a "Da" ori de câte ori observ˘a un
element egal cu x. Num˘arul maxim de "Da" ce pot fi afi¸sa¸ti coincide cu num˘arul de elemente de pe con-
turul lui A. Prima ¸si ultima linie a lui A are n elemente pe contur, iar celelalte m − 2 linii au 2 elemente pe
contur. Deci conturul lui A are 2 · n + 2 · (m − 2) = 2 (m + n − 2) elemente.
Erata:
În urma sesiz˘arilor candidat, ilor s-a constatat c˘a r˘aspunsul 2 nu este corect deoarece se afis, eaz˘a un sin-
gur "Da" chiar dac˘a elementul x apare pe ambele coloane care formeaz˘a conturul.
Ne asum˘am gres, eala s, i prin urmare tot, i candidat, ii vor primi punctaj maxim (7p) pentru aceast˘a întrebare.

Deschide documentul original

Continuă pregătirea

Vezi arhiva completă

Concurs de pregătire · 2024Informatică · Subiect și baremDeschide fișa Concurs de pregătire · 2024Matematică · Clasa a XI-aDeschide fișa Concurs de pregătire · 2024Matematică · Clasa a XII-aDeschide fișa Examen de admitere · 2024Informatică · Sesiunea septembrie; subiect oficialDeschide fișa Examen de admitere · 2024Matematică · Sesiunea iulie; subiect oficialDeschide fișa Examen de admitere · 2024Matematică · Sesiunea septembrie; subiect oficialDeschide fișa

Răspunsuri directe

Ce trebuie să știi despre acest subiect?

Ce document de admitere este acesta?

Pagina prezintă examen de admitere din 2024 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?

Nu există un barem public asociat în inventarul verificat pentru acest document. ProfesorBun nu generează și nu inventează răspunsuri oficiale. Poți folosi subiectul pentru antrenament, dar corectarea trebuie făcută cu metodologia instituției, cu materiale oficiale suplimentare sau împreună cu un profesor.

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.