Se încarcă profesorii disponibili…

Subiect și barem

PDF

Sursa: Facultatea de Informatică UVT – arhiva admiterii

Subiect — acces direct

Acest subiect nu are un barem public asociat.

Examen de admitere · Informatică · 2024

Facultatea de Informatică · UVT

Înapoi la arhivă

Subiectul în format text

Text extras automat din documentul original. Pentru formule, tabele, imagini și așezarea răspunsurilor, verifică întotdeauna PDF-ul.

Subiect · 16 pagini

Subiect · pagina 1

Concurs de admitere, Varianta 1
Facultatea de Matematic˘a s, i Informatic˘a
Universitatea de Vest din Timis, oara
Sesiunea Septembrie, 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 49 de puncte, inclusiv punctele de start, pentru nota 10 sunt necesare cel put, in
98 de puncte, inclusiv punctele de start.

Subiect · pagina 2

2
Partea I
Problema 1: Factorial sau nu?
Se consider˘a func¸tiile f1 ¸si f2 definite în modul ilustrat mai jos:
funct, ia f1(întreg n) : întreg
dac˘a n == 0 atunci
întoarce 1
altfel
întoarce n*f1(n-1)
funct, ia f2(întreg n) : întreg
dac˘a n != 1 atunci
întoarce n*f2(n-1)
altfel
întoarce 0
Care din func¸tiile f1 sau f2 returneaz˘a 120 când este apelat˘a cu Ciorn˘a, marcat, i exact un r˘aspuns:
1 2 3 4parametrul de intrare n = 5?
1 atât f1 cât ¸si f2 2 numai f1 " 3 numai f2 4 nici f1 nici f2
Explicat, ii
Se observ˘a us, or c˘a, dac˘a n ≥ 0 atunci f1(n) returneaz˘a valoarea lui n!, iar f2(n)
returneaz˘a 0. Întrucât 120 = 5!, rezult˘a c˘a r˘aspunsul corect este "numai f1".
Problema 2: Grafuri par¸tiale
Ciorn˘a, marcat, i exact un r˘aspuns:
1 2 3 4
Determinat, i num˘arul grafurilor part, iale
distincte cu num˘ar impar de arce pen-
tru graful orientat dat prin matricea de
adiacent, ˘a al˘aturat˘a:







0 1 0 0 0
1 0 1 1 1
0 0 0 1 0
0 1 0 0 1
0 0 0 0 0







1 8 2 128" 3 120 4 2
Explicat, ii
Graful descris cu aceast˘a matrice de adiacen¸t˘a are num˘arul de arce egal cu num˘arul de
elemente 1 din matrice, adic˘a 8. Num˘arul grafurilor par¸tiale distincte cu num˘ar impar de
arce este N1 + N3 + N5 + N7, unde fiecare Nk este num˘arul grafurilor par¸tiale distincte
cu k arce. Un graf par¸tial cu k arce se ob¸tine selectând k arce din cele 8 arce ale grafului
nostru. Deci Nk = Ck
8.
Prin urmare, num˘arul c˘autat este C1
8 + C3
8 + C5
8 + C7
8 = 9 + 56 + 56 + 8 = 128.
Problema 3: Mister dezlegat
Într-o pung˘a sunt 10 jetoane numerotate de la 1 la 10. Anca, Bianca, C˘alin, Daniela ¸si Eugen extrag câte
dou˘a jetoane din pung˘a, f˘ar˘a s˘a le arate celorlal¸ti numerele de pe acestea. Între aceste persoane are loc
urm˘atoarea discu¸tie:

Subiect · pagina 3

admiterefmi@uvt, septembrie 2024 3
Anca: - Suma numerelor de pe jetoanele mele este 16.
Bianca: - Suma numerelor de pe jetoanele mele este 11.
C˘alin: - Suma numerelor de pe jetoanele mele este 17.
Daniela: - Eu nu v˘a spun nimic despre jetoanele mele.
Eugen, care a extras jetoanele cu numerele 1 ¸si 3, spune, dup˘a un timp de gândire:
- Nu-i nimic, v˘a spun eu care sunt numerele de pe jetoanele Danielei.
Care sunt numerele de pe jetoanele extrase de Daniela? Ciorn˘a, marcat, i exact un r˘aspuns:
1 2 3 4
1 4, 6. 2 5, 9. 3 2, 5. " 4 2, 6
Explicat, ii
Fie xA, yA numerele Anc˘ai, xB, yB numerele Bianc˘ai, xC, yC numerele lui C˘alin, ¸si xD, yD
numerele Danielei. Presupunem c˘a xA < yA, xB < yB, xC < yC ¸si xD < yD.
¸Stim c˘a Eugen a extras jetoanele 1 ¸si 3, deci:
1. xA, yA, xB, yB, xC, yC, xD, yD sunt numere distincte din mul¸timea
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10} − {1, 3} = {2, 4, 5, 6, 7, 8, 9, 10}.
2. (xA, yA) ∈ {(6, 10), (7, 9)} pentru c˘a xA + yA = 16.
3. (xC, yC ) ∈ {(7, 10), (8, 9)} pentru c˘a xC + yC = 17.
Singura posibilitate s˘a satisfacem simultan 2 ¸si 3 este (xA, yA) = (6, 10) ¸si (xC, yC ) =
(8, 9). Deducem c˘a xB, yB, xD, yD ∈ {2, 4, 5, 7} ¸si c˘a
4. (xB, yB) = (4, 7) pentru c˘a xB + yB = 11.
Prin urmare (xD, yD ) = (2, 5).
Problema 4: C˘autare binar˘a
Fie tabloul unidimensional cu elementele (20, 15, 12, 8, 4, 2, 1), în aceast˘a ordine. Pentru a verifica dac˘a
num˘arul 5 se afl˘a printre elementele tabloului, se aplic˘a metoda c˘aut˘arii binare.
Care este succesiunea corect˘a de elemente cu care se compar˘a Ciorn˘a, marcat, i exact un r˘aspuns:
1 2 3 4num˘arul c˘autat?
1 20, 15, 12, 8, 4.
2 8, 4, 2.
3 20, 12, 4.
4 8, 2, 4. "

Subiect · pagina 4

4
Explicat, ii
C˘autarea binar˘a se poate face într-un vector v numai dac˘a elementele acestuia sunt ordo-
nate.
În cazul nostru, elementele sunt ordonate descresc˘ator, prin urmare pseudocodul c˘aut˘arii
binare este
procedura cautareBinara(întreg x, întreg v[1..n])
întreg st = 1, dr = n, poz = 0, m
cât timp st ≤ dr S, I poz == 0 execut˘a
m = (st + dr) % 2
dac˘a v[m] == x atunci
poz = m
altfel
dac˘a v[m] > x atunci
st = m + 1
altfel
dr = m − 1
dac˘a poz̸ = 0 atunci
x apare în v la pozi¸tia poz
altfel
x nu apare în v
Vectorul v = (20, 15, 12, 8, 4, 2, 1) are lungimea n = 7 iar c˘autarea binar˘a îl instan¸tiaz˘a
pe m cu valorile 4, 6, 5, în aceast˘a ordine. Prin urmare, x = 5 este comparat cu elementele
v[4], v[6], v[5], adic˘a cu 8, 2, 4 în aceast˘a ordine.
Problema 5: Cuvinte speciale
Utilizând metoda backtracking se genereaz˘a în ordine lexicografic˘a cuvintele de câte patru litere din
mul¸timea A = {a, b, c, d, e}, cuvinte care nu con¸tin dou˘a vocale al˘aturate. Primele opt cuvinte generate
sunt, în ordine: abab, abac, abad, abba, abbb, abbc, abbd, abbe.
Câte dintre cuvintele generate încep cu litera b ¸si se termin˘a cu e? Ciorn˘a, marcat, i exact un r˘aspuns:
1 2 3 4
1 0 2 15 " 3 12 4 20
Explicat, ii
Cuvintele de acest fel sunt de forma bxye cu x ∈ A ¸si y consoan˘a. x este una din 5 litere
posibile iar y este una din 3 consoane posibile. Rezult˘a c˘a num˘arul de astfel de ¸siruri este
5 · 3 = 15.
Problema 6: Ce face?
Se consider˘a algoritmul al˘aturat, reprezentat în pseudocod:
cite¸ste n (num˘ar natural)

Subiect · pagina 5

admiterefmi@uvt, septembrie 2024 5
m = 0
p = 1
cât timp n > 0 execut˘a
dac˘a n%2̸ = 0 atunci
n = n − 1
m = m + (n%10) ∗ p
n = [n/10]
p = 10 ∗ p
scrie m
S-a notat cu x%y restul împ˘ar¸tirii num˘arului natural x la num˘arul natural nenul y ¸si cu [z] partea întreag˘a
a num˘arului real z.
Câte numere naturale, fiecare având exact patru cifre, pot fi citite Ciorn˘a, marcat, i exact un r˘aspuns:
1 2 3 4pentru variabila n astfel încât, în urma execut˘arii algoritmului, pentru
fiecare dintre acestea s˘a se afi¸seze valoarea 40?
1 Nici unul. 2 6 3 8" 4 24
Explicat, ii
Pentru orice num˘ar natural cu reprezentarea zecimal˘a a1a2 . . . an, programul afi¸seaz˘a
num˘arul cu reprezentarea zecimal˘a b1b2 . . . bn unde fiecare bi este cea mai mare cifr˘a par˘a
astfel încât bi ≤ ai.
Dac˘a num˘arul afi¸sat este m = 40 atunci reprezentarea zecimal˘a a lui n este de forma 1xyz
unde x ∈ {0, 1}, y ∈ {4, 5}, ¸si z ∈ {0, 1}. Sunt 23 = 8 astfel de numere.
Problema 7: Opera¸tii aritmetice
Se consider˘a func¸tia F descris˘a în pseudocod
funct, ia F(întreg x, întreg y)
întreg acc = 0
cât timp x̸ = 0 execut˘a
dac˘a x % 2 > 0 atunci
acc = acc + y
x = x/2
y = y ∗ 2
întoarce acc
S-a notat cu x % y restul împ˘ar¸tirii num˘arului natural x la num˘arul Ciorn˘a, marcat, i exact un r˘aspuns:
1 2 3 4natural nenul y, ¸si cu x/y câtul împ˘ar¸tirii num˘arului natural x la
num˘arul natural nenul y. Care este cel mai mare num˘ar prim y astfel
încât F(x, y) s˘a returneze 231?
1 3 2 7 3 11 " 4 21

Subiect · pagina 6

6
Explicat, ii
Se observ˘a c˘a dac˘a x, y sunt numere naturale atunci F(x, y) calculeaz˘a produsul x · y
în timp logaritmic fa¸t˘a de x. Întrucât descompunerea în factori primi a lui 231 este
231 = 3 · 7 · 11, r˘aspunsul este 11: valoarea 231 este returnat˘a de apelul F(21, 11).
Partea a II-a
Problema 8: O matrice simetric˘a
Se s, tie c˘a a este un tablou bidimensional cu 5 linii s, i 5 coloane, numerotate de la 1 la 5, având init, ial toate
elementele nule. Not˘am cu x % y restul împ˘ar¸tirii num˘arului natural x la num˘arul natural nenul y.
Pentru ca algoritmul urm˘ator s˘a instant, ieze elementele tabloului a cu valorile din tabloul al˘aturat
condit, iile (A) s, i (B) trebuie înlocuite în felul urm˘ator Ciorn˘a, marcat, i 1-2 r˘aspunsuri:
1 2 3 4 5
procedura Instant, iaz ˘a()
întreg i, j
pentru i = 1 to 5 execut˘a
pentru j = 1 to 5 execut˘a
dac˘a ( A) atunci (B)
0 3 0 5 0
3 0 5 0 7
0 5 0 7 0
5 0 7 0 9
0 7 0 9 0
1 ( A) se înlocuies, te cu (i + j) % 2 == 0
2 ( A) se înlocuies, te cu (i + j) % 2 > 0 "
3 ( A) se înlocuies, te cu (i − j) % 2 == 0
4 (B) se înlocuies, te cu a[i][ j] = i + j "
5 (B) se înlocuies, te cu a[i][ j] = 2 ∗ i + 1
Explicat, ii
Se observ˘a c˘a tabloul a este instan¸tiat astfel încât a[i][ j] = i + j pentru to¸ti 1 ≤ i, j ≤ n
care satisfac condi¸tia c˘a i + j este num˘ar impar, adic˘a (i + j)%2 > 0.
Problema 9: Trunchieri
Definim operat, ia de trunchiere a unui num˘ar natural cu reprezentarea în baza 10, c1c2 . . . ck, ca fiind
trunc(c1c2 . . . ck) =
(
0 dac˘a k < 2,
c1c2 în caz contrar.
Presupunem c˘a x este un tablou de n numere naturale mai mici decât 1000000, ¸si c˘a opera¸tia div(a, b) re-
turneaz˘a câtul împ˘ar¸tirii num˘arului natural a la num˘arul natural nenul b.
Precizat, i care dintre urm˘atorele funct, ii calculeaz˘a suma trunchierilor elementelor lui x. De exemplu,
dac˘a n = 4 ¸si x = {213, 7, 78347, 22} atunci suma trunchierilor este 21 + 0 + 78 + 22 = 121.Ciorn˘a, marcat, i 1-2 r˘aspunsuri:
1 2 3 4 51 Niciuna dintre funct, iile de mai jos

Subiect · pagina 7

admiterefmi@uvt, septembrie 2024 7
2 "
funct, ia t1(întreg n, întreg x[1..n]): întreg
întreg s = 0, m = n
cât timp m > 0 execut˘a
dac˘a x[m] > 9 atunci
cât timp x[m] > 99 execut˘a
x[m] = div(x[m], 10)
s = s + x[m]
m = m − 1
întoarce s
3 funct, ia t2(întreg n, întreg x[1..n]): întreg
întreg s = n, m = n
cât timp m > 0 execut˘a
dac˘a x[m] > 9 atunci
cât timp x[m] > 99 execut˘a
x[m] = div(x[m], 10)
s = s + x[m]
m = m − 1
întoarce s
4 funct, ia t3(întreg n, întreg x[1..n]): întreg
întreg s = 0, m = n
cât timp m > 0 execut˘a
dac˘a x[m] > 9 atunci
cât timp x[m] > 99 execut˘a
x[m] = div(x[m], 10)
s = s + x[m]
m = m − 1
întoarce s
5 "
funct, ia t4(întreg n, întreg x[1..n]): întreg
întreg s = 0, m = 1
cât timp m ≤ n execut˘a
dac˘a x[m] > 9 atunci
cât timp x[m] > 99 execut˘a
x[m] = div(x[m], 10)
s = s + x[m]
m = m + 1
întoarce s
Explicat, ii
T1(n, x) însumeaz˘a trunchierile lui x[n], .., x[1] în aceast˘a ordine.
T4(n, x) însumeaz˘a trunchierile lui x[1], .., x[n] în aceast˘a ordine.
Problema 10: Swap
Se s, tie c˘a n este un num˘ar întreg mai mare ca 1, s, i c˘a v este un vector de n numere indexate de la 1 la n.
Care dintre urm˘atoarele afirmat, ii referitoare la tabolul v sunt adev˘arate dup˘a rularea algoritmului par-
curge(), oricare ar fi valorile stocate în tabloul v? Ciorn˘a, marcat, i 1-2 r˘aspunsuri:
1 2 3 4 5Aleget, i toate variantele corecte.
procedura parcurge()
întreg tmp, i = 1
pentru i = 1, n − 1 execut˘a
dac˘a (v[i] < v[i + 1]) atunci
tmp = v[i]
v[i] = v[i + 1]
v[i + 1] = tmp
1 v[1] < v[i] pentru to¸ti 1 < i ≤ n.
2 v[n] ≤ v[i] pentru to¸ti 1 ≤ i < n. "
3 v[n − 1] ≥ v[n]. "
4 v[i] ≥ v[i + 1] pentru to¸ti 1 ≤ i ≤ n.
5 v[1] ≥ v[2].

Subiect · pagina 8

8
Explicat, ii
Prin permut˘ari repetate de elemente consecutive în vector, algoritmul mut˘a pe ultima
pozi¸tie elementul cel mai mic din v. În final, v[n] va con¸tine cea mai mic˘a valoare din
tablou. Altfel spus, v[n] ≤ v[i] pentru to¸ti 1 ≤ i < n.
Problema 11: Un graf orientat
Într-un graf orientat G cu 7 vârfuri numerotate de la 2 la 8, pentru oricare dou˘a vârfuri ale sale i s, i j exist˘a
arcul (i, j) fie dac˘a i < j ¸si i este divizor al lui j, fie dac˘a i > j s, i i − j este num˘ar par.
Care dintre urm˘atoarele afirmat, ii sunt adev˘arate pentru graful G? Ciorn˘a, marcat, i 1-2 r˘aspunsuri:
1 2 3 4 5Aleget, i toate variantele corecte.
1 Num˘arul de arce ale lui G este 12.
2 G are 3 noduri cu grad interior 3. "
3 G are 3 noduri cu grad exterior 3.
4 G are un nod cu grad interior 0. "
5 Num˘arul de arce ale lui G este 13.
Explicat, ii
Dac˘a presupunem c˘a V+(i) = {j | (i, j) este arc în G} s, i c˘a V−(i) = {j | (j, i) este arc în
G} atunci avem situat, ia urm˘atoare:
nod i V+(i) V−(i)
2 {4, 6, 8} {4, 6, 8}
3 {6} {5, 7}
4 {2, 8} {2, 6, 8}
5 {3} {7}
6 {2, 4} {2, 3, 8}
7 {3, 5} ∅
8 {2, 4, 6} {2, 4}
Deci G are 14 arce; trei noduri cu grad interior 3: {2, 4, 6}; dou˘a noduri cu grad exterior
3: {2, 8}; un nod cu grad interior 0: {7}.
Problema 12: O problem˘a de c˘autare
Presupunem c˘a c este un vector de n numere naturale nenule de cel mult 9 cifre fiecare, indexate începând
de la 1. Se pune problema g˘asirii celui mai mare num˘ar a de exact 3 cifre care nu apare în v ¸si pentru care
exist˘a un num˘ar b care apare în v, astfel încât a + b = 1000. Observa¸ti c˘a este posibil ca num˘arul a s˘a nu
existe. Alex ¸si Bogdan au propus rezolv˘arile urm˘atoare:
procedura cautaA(întreg v[1..n], întreg n)
întreg i, x, ok = 0
întreg f [1..999]
pentru i = 1, 999 execut˘a f [i] = 0
pentru i = 1, n execut˘a
dac˘a v[i] < 1000 atunci f [v[i]] = f [v[i]] + 1
x = 999
cât timp (x ≥ 100) S, I (ok == 0) execut˘a
dac˘a ( f [x] == 0) S, I ( f [1000 − x]̸ = 0)
atunci

Subiect · pagina 9

admiterefmi@uvt, septembrie 2024 9
ok = 1
altfel
x = x − 1
dac˘a (ok == 1) atunci
afi¸seaz˘a x
altfel
afi¸seaz˘a "Nu exista"
procedura cautaB(întreg v[1..n], întreg n)
întreg i, x, ok = 0
întreg f [1..999]
pentru i = 1, n execut˘a f [i] = 0
pentru i = 1, n execut˘a
dac˘a v[i] < 1000 atunci f [i] = f [i] + 1
x = 999
cât timp (x ≥ 100) S, I (ok == 0) execut˘a
dac˘a ( f [x] == 0) S, I ( f [1000 − x]̸ = 0)
atunci
ok = 1
altfel
x = x − 1
dac˘a (ok == 1) atunci
afi¸seaz˘a x
altfel
afi¸seaz˘a "Nu exista"
Care dintre urm˘atoarele afirmat, ii referitoare la aceste proceduri sunt Ciorn˘a, marcat, i 1-2 r˘aspunsuri:
1 2 3 4 5adev˘arate? Aleget, i toate variantele corecte.
1 Doar procedura cautaA(v) este corect˘a."
2 Ambele proceduri sunt corecte.
3 Doar procedura cautaB(v) este corect˘a.
4 cautaA(v) are ordinul de complexitate O(log n).
5 cautaA(v) are ordinul de complexitate O(n). "
Explicat, ii
cautaA(v) instan¸tiaz˘a fiecare element f [i] al lui f cu o valoare nenul˘a dac˘a ¸si numai
dac˘a i apare în v.
Prin urmare ok devine 1 dac˘a ¸si numai dac˘a exist˘a 100 ≤ k ≤ 999 astfel încât x nu apare
în v ¸si 1000 − x apare în v. Deci procedura cautaA(v) este corect˘a.
Procedura cautaB(v) este incorect˘a pentru c˘a, dac˘a elementele lui v sunt (499, 501)
atunci c˘autarea ar trebui s˘a raporteze "nu exista", dar cautaB(v) g˘ase¸ste valoarea in-
corect˘a x = 999:
• se instan¸tiaz˘a f [1] = f [2] = 1 ¸si f [i] = 0 pentru to¸ti 3 ≤ i ≤ 1000.
• ok devine 1 când x = 999 pentru c˘a f [999] = 0 ¸si f [1000 − 999] = f [1] = 1 > 0.
Valoarea 999 este incorect˘a fiindc˘a egalitatea 999 + b = 1000 nu are loc pentru nici un ele-
ment b din v.
Ordinul de complexitate al lui cautaA(v) este O(n).
Problema 13: Rezultat simplu
Se consider˘a funct, ia RunMe, de mai jos Ciorn˘a, marcat, i 1-2 r˘aspunsuri:
1 2 3 4 5Cerint, e: k ∈ N
funct, ia RunMe(k)
i, rezultat = 0
pentru i = 0 to k execut˘a

Subiect · pagina 10

10
dac˘a i mod 3 == 1 atunci
rezultat = rezultat + i
altfel
rezultat = rezultat + 1
întoarce rezultat
Precizat, i care dintre urm˘atoarele afirmat, ii sunt adev˘arate:
1 Pentru apelul RunMe(5), funct, ia va returna 8
2 Pentru apelul RunMe(0), funct, ia va returna 1 "
3 Pentru apelul RunMe(5), funct, ia va returna 5
4 Pentru apelul RunMe(9), funct, ia va returna 18
5 Pentru apelul RunMe(4), funct, ia va returna 8 "
Problema 14: Zigzag
Robotul Robi poate fi ghidat s˘a execute una din urm˘atoarele 4 comenzi de a înainta 1 metru: N spre nord,
V spre vest, E spre est, ¸si S spre sud. Din cauza unui defect de fabrica¸tie, Robi nu poate efectua aceea¸si co-
mand˘a succesiv ¸si s˘a mearg˘a mai mult de 1 metru în aceea¸si direc¸tie. De pild˘a, secven¸ta NVN îl deplaseaz˘a
pe Robi 2 metri spre nord si 1 metru spre vest, dar secven¸ta NNV nu poate fi executat˘a fiindc˘a comanda N
apare consecutiv. Alex, elev în clasa a XII-a, este preocupat s˘a rezolve dou˘a probleme:
1. Pentru orice valori întregi x, y, s˘a g˘aseasc˘a o secven¸t˘a cât mai scurt˘a de comenzi πx,y care s˘a-l ghideze pe
Robi s˘a ajung˘a x metri mai la sud ¸si y metri mai la est.
2. S˘a g˘aseasc˘a o formul˘a de calcul pentru num˘arul sn de secven¸te de comenzi care-l ghideaz˘a pe Robi s˘a se
deplaseze n metri.
Pentru g˘asirea lui πx,y, Alex folose¸ste metoda de parcurgere în l˘a¸time respectând urm˘atoarele reguli:
(1) vizitarea locurilor se face în ordinea N,E,S,V; ¸si
(2) se evit˘a secven¸te de comenzi ce provoac˘a cicluri, adic˘a vizitarea aceluia¸si loc de mai multe ori.
Care dintre urm˘atoarele afirmat, ii sunt adev˘arate? Aleget, i toate Ciorn˘a, marcat, i 1-2 r˘aspunsuri:
1 2 3 4 5variantele corecte.
1 π2,1 este o secven¸t˘a de 3 comenzi. "
2 În general πx,y este o secven¸t˘a de |x| + |y| comenzi.
3 sn = 2n−1 pentru to¸ti n ≥ 1.
4 sn = 4 · 3n−1 pentru to¸ti n ≥ 1. "
5 Ultima comand˘a din π0,2 este N.

Subiect · pagina 11

admiterefmi@uvt, septembrie 2024 11
Explicat, ii
Fiecare comand˘a îl ghideaz˘a pe robot s˘a avanseze 1 metru. Deci secven¸tele de comenzi
care îl ghideaz˘a s˘a parcurg˘a n metri sunt cele de forma c1c2 . . . cn, unde c1 ∈ {N, E, S, V}
¸si ci ∈ {N, E, S, V} − {ci−1} pentru to¸ti 1 < i ≤ n. Deci sn = 4 · 3n−1 pentru to¸ti n ≥ 1.
Arborele de c˘autare pentru parcurgerea în l˘a¸time a lui Robi este
•
N1
N1E1
N2E1
N2E2 N2
. . .
E1
E2
N1V1
N2V1 V1
. . .
E1
N1E1
N1E2 N1
. . .
S1E1
S1E2 S1
. . .
S1
S1E1
E1 S2E1
. . .
S1V1
V1 S2V1
. . .
V1
N1V1
N1 N1V2
. . .
S1V1
S1 S1V2
. . .
de unde ob¸tinem secven¸ta π2,1 = SES pentru calea la nodul S2E1, ¸si secven¸ta π0,2 =
NESE pentru calea la nodul E2. Deci
• π2,1 este o secven¸t˘a de 3 comenzi
• Afirma¸tia c˘a πx,y are |x| + |y| comenzi este fals˘a fiindc˘a π0,2 = NESE are 4 comenzi, ¸si
4̸ = |0| + |2|
• Ultima comand˘a din π0,2 nu este N.
Problema 15: Rela¸tii de prietenie
Se consider˘a o matrice de adiacen¸t˘a, M, care reprezint˘a prieteniile dintre n persoane (unde M[i][j] = 1
înseamn˘a c˘a persoana i este prieten˘a cu persoana j, iar M[i][j] = 0 înseamn˘a c˘a nu sunt prieteni, iar
M[i][i] = 1, ∀i ∈ {1, 2, . . . , n}).
Care dintre urm˘atoarele metode determin˘a corect dac˘a exist˘a cel Ciorn˘a, marcat, i 1-2 r˘aspunsuri:
1 2 3 4 5pu¸tin dou˘a persoane cu acelas, i num˘ar de prieteni?
1 Pentru fiecare persoan˘a i se calculeaz˘a num˘arul de prieteni, Ni, adunând valorile de pe rândul i al ma-
tricei s, i stocând aceste valori într-un tablou. Dac˘a tabloul cont, ine cel put, in dou˘a valori identice, se re-
turneaz˘a True; altfel, se returneaz˘a False. "
2 Pentru fiecare persoan˘a i din grup, se calculeaz˘a num˘arul de prieteni adunând valorile din rândul i al
matricei. Dac˘a num˘arul de prieteni este mai mare decât n
2 , se returneaz˘a True, iar altfel, False.
3 Pentru fiecare persoan˘a i se calculeaz˘a num˘arul de prieteni, Ni, adunând valorile de pe rândul i al
matricei s, i se incrementeaz˘a valoarea A[Ni], unde A este un vector de frecvent, ˘a init, ializat cu 0. Dac˘a
A[Ni] = 2 se va returna True. Dac˘a se termin˘a execut, ia f˘ar˘a a întâlni acest caz, se returneaz˘a False. "
4 Pentru fiecare persoan˘a i din grup, se calculeaz˘a num˘arul de prieteni adunând valorile de pe rândul i al
matricei. Dac˘a vreo persoan˘a are 0 prieteni, se returneaz˘a True, altfel se returneaz˘a False.

Subiect · pagina 12

12
5 Pentru fiecare persoan˘a i din grup, se calculeaz˘a num˘arul de prieteni adunând valorile de pe rândul i al
matricei. Dac˘a vreo persoan˘a are 0 prieteni, se returneaz˘a False, altfel se returneaz˘a True.
Explicat, ii
R˘aspunsul 1 va calcula num˘arul de prieteni pentru fiecare persoan˘a iar apoi verific˘a dac˘a
exist˘a dou˘a persoane cu acelas, i num˘ar de prieteni.
R˘aspunsul 3 va calcula num˘arul de prieteni, Ni pentru o persoan˘a s, i verific˘a dac˘a acest
Ni a mai fost întâlnit.
R˘aspunsurile 2, 4, 5 nu garanteaz˘a c˘a exist˘a dou˘a persoane cu acelas, i num˘ar de prieteni
Partea a III-a
Problema 16: Pune ’T’
Se consider˘a o matrice p˘atratic˘a mat de dimensiune n × n (n num˘ar impar, 3 ≤ n ≤ 100) ¸si subalgoritmul
puneT(mat, n, i, j) care pune caracterul ’T’ pe anumite pozi¸tii în matricea mat. Parametrii i, j sunt numere
naturale (1 ≤ i ≤ n ¸si 1 ≤ j ≤ n), iar pseudocodul subalgoritmului este
procedura puneT(char mat[1..n][1..n], întreg n, întreg i, întreg j)
dac˘a i ≤ div(n, 2) atunci
dac˘a j ≤ n − i atunci
mat[i][j] = ′T′
puneT(mat, n, i, j + 1)
altfel
puneT(mat, n, i + 1, i + 2)
unde div(n, 2) returneaz˘a câtul împ˘ar¸tirii întregi a lui n la 2.
Precizat, i de câte ori se autoapeleaz˘a subalgoritmul puneT(mat, n, i, j) Ciorn˘a, marcat, i 1-3 r˘aspunsuri:
1 2 3 4 5dac˘a se evalueaz˘a puneT(mat, 7, 2, 4) (Apelul ini¸tial nu se ia în con-
siderare). Alege¸ti toate variantele corecte.
1 de 5 ori."
2 de 12 ori.
3 de o infinitate de ori.
4 de 0 ori.
5 de acela¸si num˘ar de ori ca s, i în cazul apelului puneT(mat, 9, 3, 5).
"

Subiect · pagina 13

admiterefmi@uvt, septembrie 2024 13
Explicat, ii
Secven¸ta de auto-apeluri ale lui puneT(mat, 7, 2, 4) este
→puneT(mat, 7, 2, 5) →puneT(mat, 7, 2, 6) →puneT(mat, 7, 3, 4) →puneT(7, 3, 5) →puneT(7, 4, 5)
iar secven¸ta de auto-apeluri ale lui puneT(mat, 9, 3, 5) este
→puneT(mat, 9, 3, 6) →puneT(mat, 9, 3, 7) →puneT(mat, 9, 4, 5) →puneT(9, 4, 6) →puneT(9, 5, 6)
Deci num˘arul de autoapeluri ale lui puneT(mat, n, i, j) dac˘a se evalueaz˘a
puneT(mat, 7, 2, 4) este 5,
care este acela¸si dac˘a se evalueaz˘a puneT(mat, 9, 3, 5).
Problema 17: ¸Siruri magice
Presupunem c˘a A este un alfabet de n > 1 litere. Spunem c˘a s este un ¸sir magic dac˘a s are lungimea n + 2 ¸si
fiecare liter˘a din A apare cel pu¸tin o dat˘a în s. Fie xn num˘arul ¸sirurilor magice cu litere din alfabetul A.
Care dintre urm˘atoarele afirma¸tii referitoare la xn sunt adev˘arate? Ciorn˘a, marcat, i 1-3 r˘aspunsuri:
1 2 3 4 5Alege¸ti toate variantele corecte.
1 xn = n! · (n + 2) · (3 n + 1)
24 "
2 xn = (n + 2)! · (3 n + 1)
4! · (n + 1) "
3 xn = (n + 1)! + n!
4 x2 = 14"
5 x3 = 30

Subiect · pagina 14

14
Explicat, ii
Fie s un ¸sir magic. Distingem 2 cazuri distincte:
1. s are 2 litere L1, L2 distincte care apar de câte 2 ori în s, iar restul literelor din A apar o
singur˘a dat˘a.
• Sunt C2
n posibilit˘a¸ti s˘a alegem {L1, L2} din alfabetul A.
• Sunt C2
n+2 posibilit˘a¸ti s˘a alegem pozi¸tiile unde apare L1 în ¸sirul s.
• Sunt C2
n posibilit˘a¸ti r˘amase s˘a alegem pozi¸tiile unde apare L2 în s.
• Sunt (n − 2)! posibilit˘a¸ti s˘a aranj˘am literele lui A − {L1, L2} pe cele n − 2 pozi¸tii r˘a-
mase din s.
Conform regulii produsului, avem C2
n · C2
n+2 · C2
n · (n − 2)! = C2
n · (n + 2)!
4 ¸siruri magice
în acest caz.
2. s are o liter˘a L care apare de 3 ori în s, iar restul literelor din A apar o singur˘a dat˘a.
• Sunt n posibilit˘a¸ti de a alege litera L din A.
• Sunt C3
n+2 moduri s˘a alegem pozi¸tiile unde apare L în s.
• Sunt (n − 1)! posibilit˘a¸ti s˘a aranj˘am literele lui A − {L} pe cele n − 1 pozi¸tii r˘amase
din s.
Conform regulii produsului, avem n · C3
n+2 · (n − 1)! = n · (n + 2)!
6 ¸siruri magice în acest
caz.
Deducem c˘a
xn = C2
n · (n + 2)!
4 + n · (n + 2)!
6 = (n + 2)!n(3 n + 1)
24 .
Problema 18: 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) + 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 10 ori
3 De 6 ori "
4 Niciodat˘a
5 O dat˘a

Subiect · pagina 15

admiterefmi@uvt, septembrie 2024 15
Explicat, ii
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) = x(1) = 0.
Deci x(5) = x(4) + x(2) = 1, x(6) = x(5) + x(3) = 1, x(7) = x(6) + x(4) = 2, x(8) =
x(7) + x(5) = 2 + 1 = 3, x(9) = x(8) + x(6) = 3 + 1 = 4, x(10) = x(9) + x(7) = 4 + 2 = 6.
A¸sadar F(4) se calculeaz˘a de exact 6 ori.
Problema 19: G˘ase¸ste arborele
Presupunem c˘a T este un arbore cu 6 noduri, numerotate de la 1 la 6, în care nodul 1 este r˘ad˘acin˘a. Deaseme-
nea, presupunem c˘a V este vectorul de „tat, i” ai nodurilor din T, adic˘a V[i] este nodul „tat˘a” al lui i pentru
to¸ti 1 < i ≤ 6. Se consider˘a urm˘atoarea operat, ie prin care se transform˘a arborele T: se elimin˘a din ar-
bore nodul „frunz˘a” numerotat cu valoarea minim˘a, marcându-se nodul „tat˘a” al acestuia. Se ¸stie c˘a dac˘a
asupra arborelui T se efectueaz˘a de patru ori succesiv operat, ia de transformare ment, ionat˘a mai sus, atunci
se marcheaz˘a, în aceast˘a ordine, nodurile 5, 1, 1, 1. Ciorn˘a, marcat, i 1-3 r˘aspunsuri:
1 2 3 4 5Care dintre urm˘atoarele afirma¸tii referitoare la arborele T sunt
adev˘arate?
Alege¸ti toate variantele corecte.
1 T are 3 noduri „frunz˘a”.
2 T are 4 noduri „frunz˘a”. "
3 V[5] = 6.
4 V[6] = 1."
5 V[4] = 1."
Explicat, ii
Din faptul c˘a transformarea ment, ionat˘a marcheaz˘a nodurile în ordinea 5, 1, 1, 1 rezult˘a c˘a
T este 1
5
a
b c d unde a < min{b, c, d}.
Rezult˘a c˘a a = 2 ¸si {b, c, d} = {3, 4, 6}, deci V[2] = 5, V[3] = V[4] = V[5] = V[6] = 1.
Arborele T are 4 noduri „frunz˘a”: 2, 3, 4, 6.
Problema 20: Detec¸tia elementelor minimale ale unei matrici
Presupunem c˘a a este un tablou bidimensional cu m linii ¸si n coloane numerotate începând de la 1, ale
c˘arui elemente sunt numere întregi. Programul urm˘ator trebuie s˘a ia ca argumente de intrare numerele
m, n ¸si tabloul a, ¸si s˘a afi¸seze pozi¸tiile elementelor din tablou care sunt strict mai mici decât toate elemente-
le cu care se învecineaz˘a direct (aflate pe aceea¸si linie dar pe o coloan˘a al˘aturat˘a sau pe aceea¸si coloan˘a dar
pe o linie al˘aturat˘a).
procedura PozitiiMinimale(întreg m, întreg n, întreg a[1..m][1..n])
întreg i, j, b

Subiect · pagina 16

16
pentru i = 1, m execut˘a
pentru j = 1, n execut˘a
b = 1
dac˘a ((i − 1 ≥ 1) S, I (A)) SAU ((i + 1 ≤ n) S, I (B)) atunci
b = 0
dac˘a ((j − 1 ≥ 1) S, I (C)) SAU ((j + 1 ≤ n) S, I (D)) atunci
b = 0
dac˘a b == 1 atunci
Tip˘are¸ste i, j
Pentru ca acest program s˘a func¸tioneze corect, condi¸tille (A), (B), Ciorn˘a, marcat, i 1-3 r˘aspunsuri:
1 2 3 4 5(C) ¸si (D) trebuie înlocuite cu expresii corespunz˘atoare. Care dintre
urm˘atoarele afirmat, ii sunt adev˘arate? Aleget, i toate variantele corecte.
1 (A) = (a[i][j] ≥ a[i + 1][j]) ¸si (B) = (a[i][j] ≥ a[i − 1][j])
2 (A) = (a[i][j] ≥ a[i − 1][j]) ¸si (B) = (a[i][j] ≥ a[i + 1][j]) "
3 (A) = (a[i][j] < a[i − 1][j]) ¸si (B) = (a[i][j] < a[i + 1][j])
4 (C) = (a[i][j] ≥ a[i][j − 1]) ¸si (D) = (a[i][j] ≥ a[i][j + 1]) "
5 (C) = (a[i][j] < a[i][j − 1]) ¸si (D) = (a[i][j] < a[i][j + 1])
Explicat, ii
Pentru ca acest program s˘a func¸tioneze corect trebuie ca b s˘a fie setat s˘a fie 0 dac˘a a[i][j]
se învecineaz˘a direct cu o valoare mai mare sau egal˘a. Deci b devine 0 dac˘a una din
condi¸tiile urm˘atoare este satisf˘acut˘a:
• i − 1 ≥ 1 ¸si (A) = (a[i][j] ≥ a[i − 1][j])
• i + 1 ≤ n ¸si (B) = (a[i][j] ≥ a[i + 1][j])
• j − 1 ≤ 1 ¸si (C) = (a[i][j] ≥ a[i][j − 1])
• j + 1 ≤ n ¸si (D) = (a[i][j] ≥ a[i][j + 1])
Rezult˘a c˘a variantele corecte sunt
• (A) = (a[i][j] ≥ a[i − 1][j]) ¸si (B) = (a[i][j] ≥ a[i + 1][j])
• (C) = (a[i][j] ≥ a[i][j − 1]) ¸si (D) = (a[i][j] ≥ a[i][j + 1])
Deschide documentul original
Continuă pregătirea

Alte subiecte de la aceeași facultate

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 iulie; 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.