Pregătire cu un profesor

Universitatea “Alexandru Ioan Cuza” din Ia¸si Admitere - studii de licent¸˘a
Facultatea de Informatic˘a Sesiunea iulie 2017
Test la INFORMATIC ˘A
Limbajul C/C++
Se acord˘a 10 puncte din oficiu. Timpul efectiv de lucru este de 3 ore.
SUBIECTUL I (30 de puncte)
Pentru itemul 1, scriet¸i pe foaia de examen litera corespunz˘atoare r˘aspunsului co-
rect.
1. Fie x o variabil˘a ˆıntreag˘a care cont, ine cel mai mic num˘ar natural nenul, multiplu de 36,
divizibil cu toate numerele prime mai mici decˆat 10. Precizat¸i care dintre expresiile C/C++ de
mai jos este adev˘arat˘a. (4p.)
A. (x<1000) && (x % 27 == 0)
C. ((x*x) / 16) % 2 == 0
B. (x>1000) && ((x*x*x) % 1000 == 0)
D. (x % 100 == 0) || (x / 100 == 0)
Scriet¸i pe foaia de examen r˘aspunsul pentru fiecare dintre cerint¸ele urm˘atoare.
2. Se consider˘a subprogramul F de mai jos, descris ˆın pseudocod. Subprogramul primes, te un
num˘ar natural nenul ˆın parametrul u s, i ˆıntoarce un num˘ar natural cˆand se opres, te.
a. Care este valoarea returnat˘a de sub-
program pentru parametrul u = 10?(6p.)
b. Dat, i exemplu de un num˘ar natural u astfel
ˆıncˆat F(u) s˘a returneze 7. (4p.)
c. Scriet, i ˆın pseudocod un subprogram re-
cursiv, echivalent cu F, care nu foloses, te
instruct, iuni repetitive. (6p.)
d. Scriet, i o funct, ie C/C++ care implementeaz˘a
subprogramul F al˘aturat. (10p.)
subprogram F(u)
(u - num˘ar natural nenul)
count ← 0
c^at timp u 6 = 1
dac˘a u este par atunci
u ← u / 2
altfel
u ← u * 3 + 1
count ← count + 1
returneaz˘a count
SUBIECTUL al II-lea (30 de puncte)
Pentru fiecare dintre itemii 1 ¸si 2, scriet¸i pe foaia de examen litera corespunz˘atoare
r˘aspunsului corect.
1. O matrice cu 8 linii, format˘a doar din 0 ¸si 1, are urm˘atoarele trei propriet˘at¸i: (i) prima
linie cont¸ine un singur element cu valoarea 1, (ii) linia j cont¸ine de dou˘a ori mai multe elemente
nenule decˆat linia j − 1, pentru orice j ∈ {2, 3, . . . , 8}, (iii) ultima linie cont¸ine un singur element
cu valoarea 0. Care este num˘arul total de elemente cu valoarea 0 din matrice? (5p.)
A. 777 B. 769 C. 528 D. nu exist˘a o astfel
de matrice
2. Fie T un arbore ¸si v un nod al acestuia. Construim un graf G astfel: cre˘am 11 copii distincte
T1, T2, . . . , T11 ale arborelui T ¸si ad˘aug˘am toate muchiile posibile ˆıntre nodurile v1, v2, . . . , v11,
unde vi este copia din arborele Ti corespunz˘atoare nodului ales v. ˆIn graful rezultat, num˘arul
de muchii este dublul num˘arului de noduri. Cˆate noduri are arborele init¸ial T ? (5p.)
A. 6 B. 5 C. 4 D. Niciuna dintre va-
riantele A., B., C.

Subiect · pagina 2

Scriet¸i pe foaia de examen r˘aspunsul pentru fiecare dintre cerint¸ele urm˘atoare.
3. Consider˘am un alfabet A format dintr-o mult¸ime finit˘a de caractere. Un cuv^ant este o
secvent¸˘a nevid˘a de caractere distincte din A. Lungimea unui cuvˆant este num˘arul de caractere
din care acesta este format. Un p-sistem (p ≥ 1) este definit ca o mult¸ime S de cuvinte, toate
de lungime p, avˆand propriet˘at¸ile: (P1) oricare dou˘a cuvinte din S au exact un caracter comun
¸si (P2) orice caracter din alfabetul A apare ˆın cel put¸in un cuvˆant din S.
Exemplu: Pentru A = {’a’, ’b’, ’c’}, mult¸imea S = {”ab”, ”ac”} este un 2-sistem.
a) Scriet¸i un 3-sistem peste alfabetul A = {’a’, ’b’, ’c’, ’d’, ’e’, ’f’}. (2p.)
b) Scriet¸i un program C/C++ care:
b1) Cite¸ste de la tastatur˘a un ˆıntreg m, 1 ≤ m ≤ 26, ¸si construie¸ste alfabetul A format
din primele m caractere ale alfabetului {’a’, ’b’, . . . , ’z’}. (1p.)
b2) Cite¸ste de la tastatur˘a un ˆıntreg n ≥ 1 ¸si o secvent¸˘a de n ¸siruri de caractere. Se
presupune c˘a fiecare ¸sir citit este format din caractere distincte din A (este un cuvˆant).
Nu este necesar˘a validarea datelor citite. (1p.)
b3) Verific˘a dac˘a exist˘a un p astfel ˆıncˆat mult¸imea de cuvinte citite reprezint˘a un p-sistem.
ˆIn caz afirmativ, va fi afi¸sat mesajul "DA", ˆın caz contrar "NU". (6p.)
4. O ret¸ea de comparatori de tip n (n ≥ 2) ¸si de dimensiune m (m ≥ 1) este o secvent¸˘a
(c1, c2, . . . , cm) ˆın care fiecare element ci, numit comparator, este o pereche de numere ˆıntregi
(j, k) cu proprietatea 1 ≤ j < k ≤ n.
Exemplu: Ret¸eaua R = ((1, 2), (2, 3)) are tipul 3 ¸si dimensiunea 2.
Dac˘a a este un vector de n numere ˆıntregi ¸si R este o ret¸ea, not˘am cu R(a) vectorul obt¸inut
aplicˆand urm˘atoarele transform˘ari lui a: pentru fiecare comparator ci = (j, k), 1 ≤ i ≤ m din
R, ˆın ordinea ˆın care ace¸stia apar ˆın ret¸ea, dac˘a a[j] > a[k] atunci ˆın vectorul a interschimb˘am
valorile de la pozit¸iile j ¸si k.
Exemplu: Pentru R = ((1, 2), (2, 3)) ¸si a = (30, 20, 10) avem R(a) = (20, 10, 30).
a) Fie R = ((2, 4), (1, 2), (3, 4), (2, 3)) ¸si a = (40, 30, 20, 10). Calculat¸i R(a) ¸si scriet¸i valorile
intermediare ale vectorului a corespunz˘atoare transform˘arilor efectuate. (2p.)
b) Dat¸i exemplu de o ret¸ea R de tip 4 cu proprietatea c˘a pentru orice vector a format din 4
numere ˆıntregi distincte, R(a) va avea elementele ordonate cresc˘ator. Justificare. (4p.)
c) Scriet¸i o funct¸ie C/C++ care prime¸ste ca parametri numerele naturale n ¸si m, o matrice R
cu m linii ¸si 2 coloane, reprezentˆand o ret¸ea de comparatori, ¸si un vector a de n numere
ˆıntregi. Funct¸ia va calcula vectorul R(a) ¸si va returna valoarea 1 dac˘a acesta are elementele
ordonate cresc˘ator. ˆIn caz contrar, va returna valoarea 0. (4p.)
SUBIECTUL al III-lea (30 de puncte)
Pentru itemul 1, scriet¸i pe foaia de examen litera corespunz˘atoare r˘aspunsului co-
rect.
1. Se consider˘a toate s, irurile de lungime l ∈ {1, 2, 3} formate din litere din mult, imea {a, b, c, d, e}.
Cˆate dintre aceste s, iruri au un num˘ar par de vocale? (a s, i e sunt vocale) (4p.)
A. 79 B. 80 C. 81 D. 78

Subiect · pagina 3

Scriet¸i pe foaia de examen r˘aspunsul pentru fiecare dintre cerint¸ele urm˘atoare.
2. Se consider˘a funct, ia recursiv˘a F de mai jos. Ce valoare va returna apelul F(0,63,64)?(6p.)
int F(int u, int v, int t) {
int m = (u + v) / 2;
if (u >= v) { return u; }
else if (m * m > t) { return F(u, m - 1, t); }
else if (m * m < t) { return F(m + 1, v, t); }
else { return m; }
}
3. O cas˘a are n × m camere (n, m ∈ N, n, m ≥ 2) s, i este reprezentat˘a ca o matrice cu n
linii (numerotate de la 0 la n − 1) s, i m coloane (numerotate de la 0 la m − 1). Camera de
la linia i (0 ≤ i ≤ n − 1) s, i coloana j (0 ≤ j ≤ m − 1) este identificat˘a prin perechea de
numere (i, j). Toate camerele, cu except, ia celor situate pe prima linie (i = 0) s, i a celor situate
pe prima coloan˘a (j = 0), au cˆate un comutator. Act, ionarea comutatorului din camera (i, j)
(unde 1 ≤ i ≤ n − 1, 1 ≤ j ≤ m − 1) conduce la urm˘atorul rezultat: ˆın fiecare dintre camerele
(i, j), (i − 1, j), (i, j − 1), (i − 1, j − 1) (camera cu comutatorul, cea de deasupra, cea de la stˆanga
s, i cea de deasupra s, i la stˆanga), dac˘a lumina era aprins˘a, ea se stinge, iar dac˘a era stins˘a, se
aprinde.
a) Matricea de mai jos reprezint˘a starea luminilor din fiecare camer˘a dintr-o cas˘a cu n = 5
linii s, i m = 4 coloane. Pozit, iile (0, 1), (0, 2), (1, 1), (1, 3), (2, 2), (2, 3) cont, in valoarea
1, reprezentˆand faptul c˘a luminile sunt aprinse ˆın camerele respective, iar celelalte pozit, ii
cont, in valoarea 0, reprezentˆand faptul c˘a luminile sunt stinse. Comutatoarele din care
camere trebuie act, ionate pentru a stinge luminile din toate camerele? (4p.)






0 1 1 0
0 1 0 1
0 0 1 1
0 0 0 0
0 0 0 0






b) Scriet¸i o funct, ie C/C++ care primes, te 5 parametri de intrare: o matrice A de 0 s, i de
1, reprezentˆand starea luminilor din camere, dimensiunile n (n ≥ 2) s, i m (m ≥ 2) ale
acesteia, precum s, i dou˘a numere naturale i, j (1 ≤ i ≤ n − 1, 1 ≤ j ≤ m − 1), reprezentˆand
o camer˘a (i, j) cu comutator. Funct, ia trebuie s˘a modifice matricea primit˘a ca parametru,
astfel ˆıncˆat aceasta s˘a cont, in˘a starea luminilor dup˘a act, ionarea comutatorului din camera
(i, j). Nu este necesar˘a validarea parametrilor de intrare. (6p.)
c) Scriet¸i o funct, ie C/C++ care primes, te ca parametri de intrare o matrice A de 0 s, i de 1,
reprezentˆand starea luminilor din camere, precum s, i dimensiunile n (n ≥ 2) s, i m (m ≥ 2)
ale acesteia. Funct, ia trebuie s˘a returneze 1 dac˘a exist˘a o mult, ime de camere astfel ˆıncˆat,
act, ionˆand comutatorul ˆın fiecare camer˘a din mult, ime o singur˘a dat˘a, s˘a se obt, in˘a stingerea
luminilor din toate camerele. Altfel, funct, ia va returna 0. ˆIn rezolvare, putet, i utiliza
funct, ia de la punctul b). Nu este necesar˘a validarea parametrilor de intrare. Se va folosi
un algoritm cˆat mai eficient din punct de vedere al timpului de executare; solut, iile de tip
backtracking vor primi cel mult 2p. (10p.)

Deschide documentul original

Barem · 3 pagini

Barem · pagina 1

Universitatea “Alexandru Ioan Cuza” din Ias, i Admitere – studii de licent, ˘a
Facultatea de Informatic˘a Sesiunea iulie 2017
Proba scris˘a la INFORMATIC ˘A
BAREM DE EVALUARE S¸I NOTARE
comun pentru limbajele C/C++ ¸si Pascal
● Se puncteaz˘a oricare alte modalit˘at¸i de rezolvare corect˘a a cerint¸elor.
● Se acord˘a 10 puncte din oficiu. Nota final˘a se calculeaz˘a prin ˆımp˘art¸irea punctajului total
acordat pentru lucrare la 10.
☀ ˆIn cazul ˆın care r˘aspunsul final la o ˆıntrebare care nu necesit˘a justificare nu este corect dar exist˘a
justific˘ari part¸ial corecte, punctajul se calculeaz˘a conform baremului afi¸sat.
SUBIECTUL I (30 de puncte)
1. R˘aspuns corect B 4p.
2. a. Valoarea returnat˘a este 6. 6p. ☀
1. descrierea calculului 4p.
2. obt¸inerea rezultatului corect 2p.
b. Orice num˘ar din mult, imea {3, 20, 21, 128} 4p. ☀
1. descrierea calculului 2p.
2. obt¸inerea unui exemplu corect 2p.
c. Pentru subprogram recursiv corect, f˘ar˘a instruct, iuni
repetitive.
6p.
1. structura corect˘a a subprogramului 1p.
2. folosirea corect˘a a instruct, iunii condit, ionale 1p.
3. folosirea corect˘a a recursiei 2p.
4. echivalent, a subprogramelor 2p.
d. Pentru funct, ia C/C++ corect˘a 10p.
1. structura corect˘a a funct, iei 2p.
2. folosirea corect˘a a instruct, iunii de decizie 2p.
3. folosirea corect˘a a instruct, iunii repetitive 3p.
4. sintaxa corect˘a 3p.

Barem · pagina 2

SUBIECTUL al II-lea (30 de puncte)
1. R˘aspuns corect A 5p. ☀
1. calculul num˘arului de coloane (129) 2p.
2. calculul num˘arului de elemente cu valoarea 1 (255) 2p.
3. identificarea r˘aspunsului corect 1p.
2. R˘aspuns corect C 5p. ☀
1. folosirea propriet˘at, ii: num˘ar muchii = num˘ar noduri − 1 2p.
2. calculul num˘arului de noduri s, i a num˘arului de muchii
din graful rezultat
2p.
3. identificarea r˘aspunsului corect 1p.
3. Pentru solut, ie corect˘a 10p.
a Orice 3-sistem corect (de exemplu, S = {abc, ade, bdf } sau
S = {abc, cde, adf }).
2p.
b1 citirea datelor de intrare s, i construirea alfabetului 1p.
b2 citirea corect˘a a datelor de intrare 1p.
b3 rezolvarea corect˘a 6p.
1. verificarea faptului c˘a toate cuvinte au aceeas, i lungime 1p.
2. verificarea propriet˘at, ii P1 3p.
3. verificarea propriet˘at, ii P2 2p.
4. Pentru solut, ie corect˘a 10p.
a r˘aspuns corect 2p.
1. calculul vectorilor intermediari 1p.
2. obt, inerea vectorului R(a) ((10, 20, 40, 30)) 1p.
b orice ret, ea corect˘a, cu justificare 4p.
1. ret, ea corect˘a 2p.
2. justificarea 2p.
c funct, ie corect˘a 4p.
1. structura funct, iei 1p.
2. aplicarea corect˘a a transform˘arilor 2p.
3. verificarea faptului c˘a vectorul este sortat 1p.

Barem · pagina 3

SUBIECTUL al III-lea (30 de puncte)
1. R˘aspuns corect A (79) 4p. ☀
1. analiza corect˘a a cazurilor posibile 2p.
2. rezultatul corect 2p.
2.
R˘aspuns corect 8 6p.
1. observarea faptului c˘a funct, ia face o c˘autare prin bisect, ie
(c˘autare binar˘a).
2p.
2. calculul recursiv (lista tuturor apelurilor recursive) 3p.
3. obt¸inerea rezultatului corect 1p.
3.
a. R˘aspuns corect (de exemplu, act, ionarea comutatoa-
relor {(1, 2), (2, 3)})
4p.
b. Pentru solut, ie corect˘a 6p.
1. structura corect˘a a funct, iei 3p.
2. aplicarea corect˘a a transform˘arii 3p.
c. Pentru orice solut, ie corect˘a s, i eficient˘a 10p.
c. Pentru orice solut, ie corect˘a, dar ineficient˘a 2p.

Deschide documentul original

Continuă pregătirea

Vezi arhiva completă

Examen de admitere · 2017Matematică · Sesiunea iulieDeschide fișa Examen de admitere · 2018Informatică · Sesiunea iulieDeschide fișa Examen de admitere · 2018Matematică · Sesiunea iulieDeschide fișa Examen de admitere · 2016Informatică · Sesiunea iulieDeschide fișa Examen de admitere · 2019Informatică · Sesiunea iulieDeschide fișa Examen de admitere · 2019Matematică · Sesiunea iulieDeschide fișa

Răspunsuri directe

Ce trebuie să știi despre acest subiect?

Ce document de admitere este acesta?

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

Examen de admitere · Informatică · 2017

Despre acest subiect

Subiectul și baremul în format text

Subiect · pagina 1