Pregătire cu un profesor

Universitatea “Alexandru Ioan Cuza” din Ia¸si Admitere - studii de licent¸˘a
Facultatea de Informatic˘a Sesiunea iulie 2016
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 corect.
1. Un num˘ar natural n desemneaz˘a un an bisect dac˘a n este multiplu de 4, dar nu este multiplu de 100,
cu except, ia numerelor multiplu de 400. De exemplu, 1600, 2000, 2004, 2016, 2400 sunt ani bisect, i,
dar 2007, 1700, 1800, 2200 nu sunt ani bisect, i. Care dintre expresiile C/C++ de mai jos testeaz˘a dac˘a
valoarea variabilei n desemneaz˘a un an bisect? (4p.)
a. (n%100 != 0) &&
(n%4 == 0)
c. (n%100 != 0) ||
(n%4 == 0)
b. (n%4 == 0) &&
((n%100 != 0) || (n%400 == 0))
d. (n%4 == 0) &&
((n%100 != 0) && (n%400 == 0))
Scriet¸i pe foaia de examen r˘aspunsul pentru fiecare dintre cerint¸ele urm˘atoare.
2. Se consider˘a subprogramul recursiv F de mai jos, descris ˆın pseudocod. Subprogramul primes, te
ca parametri dou˘a numere naturale u s, i v s, i ˆıntoarce un num˘ar natural. Operat, ia % reprezint˘a restul
ˆımp˘art, irii, iar max(a,b) reprezint˘a maximul dintre a s, i b.
a. Care este valoarea returnat˘a de sub-
program pentru parametrii u = 42
s, i v = 35? (6p.)
b. Dat, i exemplu de dou˘a numere na-
turale u, v distincte s, i nenule astfel
ˆıncˆat F(u, v) s˘a returneze 5. (4p.)
c. Dac˘a u = 14, care este cea mai
mare valoare strict mai mic˘a decˆat
100 pentru v, astfel ˆıncˆat F(u, v) s˘a
returneze 7? (6p.)
d. Scriet, i funct, ia C/C++ cores-
punz˘atoare subprogramului
al˘aturat. (10p.)
subprogram F(u,v) (u, v - numere naturale)
dac˘a u=v sau u=0 sau v=0 atunci
returneaz˘a max(u,v)
altfel dac˘a u%2=0 atunci
dac˘a v%2=0 atunci returneaz˘a 2*F(u/2, v/2)
altfel returneaz˘a F(u/2, v)
altfel
dac˘a v%2=0 atunci returneaz˘a F(u, v/2)
altfel
dac˘a u<v atunci returneaz˘a F(u, (v-u)/2)
altfel returneaz˘a F((u-v)/2, v)
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. Care este ˆın˘alt¸imea maxim˘a a unui arbore cu r˘ad˘acin˘a, avˆand 11 noduri, ¸stiind c˘a fiecare nod
intern (care nu este r˘ad˘acin˘a sau frunz˘a) are mai multe noduri fiu decˆat p˘arintele s˘au? (In˘alt¸imea
arborelui este num˘arul de muchii ale celui mai lung drum de la r˘ad˘acin˘a la o frunz˘a.) (4p.)
a. 2 b. 4 c. 10 d. nu exist˘a un astfel de arbore

Subiect · pagina 2

2. Fie un graf neorientat ˆın care fiecare nod are un num˘ar par s, i nenul de vecini, astfel ˆıncˆat nu exist˘a
dou˘a noduri avˆand acela¸si num˘ar de vecini. Care dintre urm˘atoarele variante ar putea reprezenta
num˘arul de muchii ale unui astfel de graf? (6p.)
a. 10 b. 15 c. 16 d. nu exist˘a un astfel de graf
Scriet¸i pe foaia de examen r˘aspunsul pentru fiecare dintre cerint¸ele urm˘atoare.
3. Consider˘am un ¸sir oarecare format doar din caractere din mult¸imea { a, b }. Mult¸imea R = { r1:
aab → aaa, r2: aba → aab, r3: abb → aba, r4: baa → abb, r5: bab → aba, r6: bba → baa, r7:
bbb → bab} define¸ste regulile de transformare care pot fi aplicate unui astfel de ¸sir. Fiecare dintre
aceste transform˘ari, aplicat˘a unui ¸sir de caractere oarecare, va ˆınlocui prima aparit¸ie a sub¸sirului de
trei caractere din partea stˆang˘a a regulii, cu sub¸sirul din partea dreapt˘a. Pornind de la s, irul init¸ial,
vom aplica ˆın mod repetat oricare dintre transform˘arile din mult¸imea R, atˆat timp cˆat acest lucru
este posibil.
Exemplu: Pentru ¸sirul de caractere "abba", o secvent¸˘a posibil˘a de aplicare a regulilor este:
abba r3
Ð→ abaa r4
Ð→ aabb r1
Ð→ aaab r1
Ð→ aaaa.
a) Demonstrat¸i c˘a, indiferent de ¸sirul considerat init¸ial ¸si indiferent de ordinea de aplicare a regulilor
de transformare, dup˘a un num˘ar finit de pa¸si se va obt, ine un ¸sir ce cont¸ine pe fiecare pozit¸ie
doar caracterul a. (3p.)
b) Scriet¸i un program C/C++ care:
i) Cite¸ste de la tastatur˘a un ¸sir s format doar din caracterele a ¸si b. ˆIn cazul ˆın care ¸sirul
cont¸ine ¸si alte caractere, va fi afi¸sat mesajul "Date invalide". (1p.)
ii) Pornind de la s, irul s, aplic˘a regulile de transformare din mult¸imea R atˆat timp cˆat este
posibil ¸si afi¸seaz˘a num˘arul de aplic˘ari ale acestor reguli. (5p.)
iii) Verific˘a faptul c˘a ¸sirul rezultat ˆın final este format doar din caractere egale cu a. (1p.)
4. Fie S ¸si T dou˘a mult¸imi de simboluri, ambele avˆand acela¸si num˘ar de elemente n, unde n este un
num˘ar natural impar. Un (S,T)-p˘atrat este o matrice p˘atratic˘a de dimensiune n × n ce ˆındepline¸ste
urm˘atoarele condit¸ii:
(C1) fiecare element al matricii este o pereche (s,t) unde s∈S ¸si t∈T;
(C2) pentru orice dou˘a elemente (s,t) s, i (s’,t’) aflate pe pozit, ii diferite ˆın matrice dar pe aceea¸si
linie sau pe aceea¸si coloan˘a, avem s ~= s’ ¸si t ~= t’;
(C3) pentru orice dou˘a elemente (s,t) s, i (s’,t’) aflate pe pozit¸ii diferite ˆın matrice, avem s ~= s’
sau t ~= t’.
Exemplu: Pentru n=3, S={a,b,c} ¸si T={0,1,2}, un (S,T)-p˘atrat posibil este:
⎛
⎜
⎝
(a, 0) (b, 1) (c, 2)
(c, 1) (a, 2) (b, 0)
(b, 2) (c, 0) (a, 1)
⎞
⎟
⎠
a) Dat¸i un exemplu de (S,T)-p˘atrat pentru n=5, S={a,b,c,d,e} ¸si T={0,1,2,3,4}. (2p.)
b) Scriet¸i o funct¸ie C/C++ care prime¸ste ca argumente num˘arul natural impar n ¸si dou˘a tablouri de
caractere, reprezentˆand mult¸imile S ¸si T, ¸si construieste un (S,T)-p˘atrat. (6p.)
c) Argumentat¸i faptul c˘a p˘atratul construit de funct¸ia de la punctul b) ˆındepline¸ste condit¸iile (C1),
(C2) ¸si (C3). (2p.)

Subiect · pagina 3

SUBIECTUL al III-lea (30 de puncte)
Pentru itemul 1, scriet¸i pe foaia de examen litera corespunz˘atoare r˘aspunsului corect.
1. Se consider˘a toate s, irurile de lungime 10 formate din 0 s, i 1. Cˆate dintre acestea au proprietatea
c˘a suma oric˘aror 5 elemente de pe pozit¸ii consecutive este 3? (4p.)
a. 10 b. 100 c. 120 d. 1024
Scriet¸i pe foaia de examen r˘aspunsul pentru fiecare dintre cerint¸ele urm˘atoare.
2. John McCarthy, unul dintre fondatorii domeniului inteligent, ˘a artificial˘a, a propus funct, ia F91,
definit˘a mai jos s, i numit˘a “funct, ia 91 a lui McCarthy”. Ce valoare va returna apelul F91(91)?(6p.)
int F91(int x) {
if (x > 100) { return x - 10; }
else { return F91(F91(x + 11)); }
}
3. Fie A o matrice de numere naturale cu N≥2 linii ¸si M≥2 coloane. O secvent, ˘a (i1,j1), (i2,j2),
..., (ik,jk) de pozit¸ii din A se nume¸ste progresiv˘a dac˘a s, irurile
– i1, i2, ..., ik
– j1, j2, ..., jk
– A[i1][j1], A[i2][j2], ..., A[ik][jk]
sunt progresii aritmetice cu rat¸ii nenule. De exemplu, ˆın matricea
⎛
⎜
⎜
⎜
⎜
⎝
22 35 30 37 25 34
26 8 44 23 41 10
38 23 14 20 49 11
35 20 3 2 24 13
⎞
⎟
⎟
⎟
⎟
⎠
este evident¸iat˘a secvent¸a progresiv˘a (1,2), (2,4), (3,6): indicii liniilor (1, 2, 3) sunt ˆın progresie
aritmetic˘a de rat, ie nenul˘a, indicii coloanelor (2, 4, 6) sunt ˆın progresie aritmetic˘a de rat, ie nenul˘a,
iar valorile (35, 23, 11) sunt ¸si ele ˆın progresie aritmetic˘a de rat, ie nenul˘a.
a) Pentru matricea de mai jos, scriet, i care este cea mai lung˘a secvent¸˘a progresiv˘a. Dac˘a sunt mai
multe astfel de secvent, e, aleget, i oricare dintre ele. (4p.)
⎛
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎝
1 1 1 9 1
1 1 6 1 1
1 3 7 1 1
1 1 2 1 1
1 5 1 1 9
1 1 1 1 1
3 1 1 3 1
⎞
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎠
b) Scriet¸i o funct¸ie C/C++ care prime¸ste ca parametri dimensiunile N s, i M ale matricii, matricea A
¸si primele dou˘a pozit, ii (i1,j1), (i2,j2) dintr-o secvent¸˘a progresiv˘a din A. Funct¸ia va returna
lungimea secvent¸ei progresive din A ce ˆıncepe cu (i1,j1), (i2,j2) s, i care are un num˘ar maxim
de elemente. (8p.)
c) Scriet¸i o funct¸ie C/C++ care prime¸ste ca parametri dimensiunile N s, i M ale matricii s, i matricea A.
Funct, ia va returna lungimea secvent¸ei progresive din A, care are un num˘ar maxim de elemente.
ˆIn rezolvare, putet, i apela funct, ia de la punctul b). (8p.)

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 2016
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.
● Nu se acord˘a punctaje intermediare, altele decˆat cele precizate explicit prin barem. Nu se acord˘a
fract¸iuni de punct.
● 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. b 4p.
2. a. Valoarea returnat˘a este 7. 6p. ☀
1. descrierea calculului 4p.
2. obt¸inerea rezultatului corect 2p.
b. Orice dou˘a numere naturale u s, i v, nenule s, i diferite
ˆıntre ele, al c˘aror cmmdc este 5 (exemplu: u = 10,
v = 5).
4p. ☀
1. identificarea propriet˘at¸ii de cmmdc 3p.
2. obt¸inerea unui exemplu corect 1p.
c. Valoarea v = 91. 6p. ☀
1. utilizarea propriet˘at, ilor de divizor/multiplu 3p.
2. obt¸inerea rezultatului corect 3p.
d. Pentru funct, ia C/C++ corect˘a 10p.
1. structura corect˘a a funct, iei 3p.
2. folosirea corect˘a a instruct, iunilor de decizie 4p.
3. sintaxa corect˘a 3p.

Barem · pagina 2

SUBIECTUL al II-lea (30 de puncte)
1. R˘aspuns corect b 4p. ☀
1. arbore care respect˘a condit, iile 2p.
2. identificarea r˘aspunsului corect 2p.
2. R˘aspuns corect d 6p. ☀
1. folosirea propriet˘at, ii: suma gradelor = 2 × num˘ar muchii 2p.
2. calculul num˘arului maxim de muchii ˆıntr-un graf cu n
noduri
2p.
3. identificarea r˘aspunsului corect 2p.
3. Pentru solut, ie corect˘a 10p.
a. 1. Identificarea faptului c˘a s, irul descres, te lexicografic s, i ˆıs, i
p˘astreaz˘a lungimea.
2p.
2. Identificarea faptului c˘a pentru orice s, ir care cont, ine cel
put, in un b poate fi aplicat˘a o regul˘a.
1p.
b.i citirea s, i validarea datelor de intrare 1p.
b.ii 1. identificarea unei reguli care poate fi aplicat˘a s, irului
curent
2p.
2. transformarea s, irului conform regulii 2p.
3. num˘ararea transform˘arilor 1p.
b.iii verificarea faptului c˘a s, irul cont, ine doar caractere a 1p.
4. Pentru solut, ie corect˘a 10p.
a construirea unui exemplu corect 2p.
b 1. structura funct, iei 1p.
2. folosirea unei structuri de date adecvate pentru repre-
zentarea p˘atratului
2p.
3. algoritm corect pentru construirea p˘atratului 3p.
c argumentare corect˘a 2p.

Barem · pagina 3

SUBIECTUL al III-lea (30 de puncte)
1. R˘aspuns corect a 4p. ☀
1. observarea faptului c˘a s, irul este determinat ˆın mod unic
de oricare 5 elemente situate pe pozit, ii consecutive
3p.
2. calculul corect al num˘arului de combin˘ari 1p.
2.
R˘aspuns corect 91 6p. ☀
1. observarea faptului c˘a funct, ia este recursiv˘a 1p.
2. calculul recursiv (lista tuturor apelurilor recursive) 3p.
3. obt¸inerea rezultatului corect 2p.
3.
a. R˘aspuns corect (7,1), (5,2), (3,3), (1,4) sau
(1,4), (3,3), (5,2), (7,1)
4p. ☀
1. identificarea unei secvent, e progresive de lungime i ip.
b. Pentru solut, ie corect˘a 8p.
1. structura corect˘a a funct, iei 2p.
2. folosirea unei instruct, iuni repetitive pentru parcugerea
secvent, ei progresive
3p.
3. verificarea corect˘a a condit, iilor 3p.
c. Pentru solut, ie corect˘a 8p.
1. structura corect˘a a funct, iei 2p.
2. folosirea unor instruct, iuni repetitive pentru parcugerea
tutoror perechilor de pozit, ii care pot reprezenta ˆınceputul
unei secvent, e progresive
3p.
3. apelul corect al funct, iei de la punctul b. 2p.
4. tratarea cazului cˆand r˘aspunsul este 1 1p.

Deschide documentul original

Continuă pregătirea

Vezi arhiva completă

Examen de admitere · 2017Informatică · Sesiunea iulieDeschide fișa Examen de admitere · 2017Matematică · Sesiunea iulieDeschide fișa Examen de admitere · 2015Informatică · Sesiunea iulieDeschide fișa Examen de admitere · 2018Informatică · Sesiunea iulieDeschide fișa Examen de admitere · 2018Matematică · Sesiunea iulieDeschide fișa Examen de admitere · 2014Informatică · 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 2016 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ă · 2016

Despre acest subiect

Subiectul și baremul în format text

Subiect · pagina 1