Pregătire cu un profesor

Universitatea Alexandru Ioan Cuza din Ia¸si Admitere - studii de licent¸˘a
Facultatea de Informatic˘a Sesiunea iulie 2019
Test la INFORMATIC ˘A
Se acord˘a 10 puncte din oficiu. Timpul 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. Fie M mult¸imea tuturor numerelor naturale nenule care sunt divizibile cu 5, dar nu sunt divizibile cu 4.
Fie un num˘ar natural n ≥ 1. Care dintre expresiile C/C++ de mai jos este echivalent˘a cu n ∈ M ? (4p.)
A. (n % 20 != 0)
C. !((n % 5 != 0) || (n % 20 == 0))
B. (n % 5 == 0) || (n % 4 != 0)
D. !((n % 5 == 0) || (n % 4 != 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 n s, i ˆıntoarce un num˘ar natural cˆand se opres, te.
a. Care este valoarea returnat˘a de subprogram pen-
tru parametrul n = 37? (6p.)
b. Care este cel mai mare num˘ar natural n mai mic
decˆat 1000 astfel ˆıncˆat F(n) s˘a returneze 0?(6p.)
c. Scriet¸i ˆın pseudocod un subprogram recursiv,
echivalent cu F, care nu folose¸ste instruct¸iuni
repetitive. (4p.)
d. Scriet, i o funct, ie C/C++/Pascal care imple-
menteaz˘a subprogramul F al˘aturat. (10p.)
subprogram F(n)
(n - num˘ar natural nenul)
p ← 0
t ← 1
c^at timp n 6 = 0
dac˘a n este par atunci
p ← p + t
n ← n / 2 (ˆımp˘art, ire ˆıntreag˘a)
t ← t * 2
returneaz˘a p
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. Fie G un graf neorientat conex, cu mult¸imea de vˆarfuri V , avˆand propriet˘at¸ile: (a) fiecare vˆarf are cel
mult 3 vecini ¸si (b) exist˘a un vˆarf u ∈ V astfel ˆıncˆat pentru orice v ∈ V avem d(u, v) ≤ 5, unde d(u, v)
reprezint˘a lungimea celui mai scurt drum dintre vˆarfurile u ¸si v (ca num˘ar de muchii). Care este num˘arul
maxim de vˆarfuri din G? (5p.)
A. 46 B. 94 C. 125 D. 190
2. Care dintre cele patru variante de mai jos nu poate reprezenta secvent¸a gradelor vˆarfurilor unui graf
neorientat? (5p.)
A. (1, 1, 1, 2, 2, 3) B. (1, 1, 3, 3, 3, 5) C. (1, 1, 2, 3, 4, 5) D. (1, 4, 4, 4, 4, 5)
Scriet¸i pe foaia de examen r˘aspunsul pentru fiecare dintre cerint¸ele urm˘atoare.
3. Scriet¸i o funct¸ie C/C++/Pascal cu numele compute care primes, te la intrare un num˘ar natural a ¸si
efectueaz˘a urm˘atoarele operat¸ii:
a) Verific˘a faptul c˘a num˘arul a este format din cel put¸in patru cifre, toate nenule. ˆIn caz contrar, funct¸ia
returneaz˘a −1. (2p.)
b) Construie¸ste num˘arul n format din cifrele de pe pozit¸iile impare ale lui a ¸si num˘arul m format din
cifrele de pe pozit¸iile pare ale lui a. Pozit¸iile cifrelor lui a sunt numerotate de la stˆanga la dreapta,
ˆıncepˆand cu pozit, ia 1. De exemplu, dac˘a a = 73528, n va avea valoarea 758, iar m va avea valoarea
32. (4p.)

Subiect · pagina 2

c) Returneaz˘a 1 dac˘a num˘arul nm − n! − 1 este multiplu de 10 ¸si 0 ˆın caz contrar. Solut¸ia trebuie s˘a t¸in˘a
cont de precizia limitat˘a a reprezent˘arii numerelor ˆın C/C++/Pascal. Nu este permis˘a utilizarea unor
biblioteci ajut˘atoare. (4p.)
4. O ret¸ea de transport este format˘a din m + n noduri. Nodurile numerotate de la 0 la m − 1 reprezint˘a
garaje, iar nodurile numerotate de la m la m + n − 1 reprezint˘a locat¸ii. Fiecare garaj cont¸ine exact o ma¸sin˘a.
Fiecare ma¸sin˘a parcurge 0 sau mai multe drumuri. Un drum porne¸ste dintr-un garaj, trece printr-o serie de
locat¸ii distincte ¸si se termin˘a ˆın acela¸si garaj. Se s, tie c˘a prin fiecare locat¸ie trece exact un drum. Mult¸imea
drumurilor parcurse de ma¸sini este reprezentat˘a printr-o matrice p˘atratic˘a D, de dimensiune m + n, format˘a
din elemente 0 ¸si 1, unde D[i][j] = 1 dac˘a ¸si numai dac˘a nodurile i ¸si j apar succesiv, ˆın aceast˘a ordine, ˆın
cadrul unui drum.
a) Pentru o ret¸ea de transport cu m = 2 ¸si n = 5, scriet¸i matricea D corespunz˘atoare drumurilor:
0 → 2 → 3 → 0, 1 → 4 → 5 → 1, 1 → 6 → 1. (2p.)
b) Scriet¸i ˆın C/C++/Pascal o funct¸ie prev care primes, te la intrare o matrice D corespunz˘atoare unei
mult¸imi de drumuri, valorile m, n ¸si o locat¸ie i ¸si returneaz˘a num˘arul nodului care ˆıl precede pe i pe
drumul ce cont¸ine locat¸ia i. (3p.)
c) Scriet¸i ˆın C/C++/Pascal o funct¸ie garages care primes, te la intrare o matrice D corespunz˘atoare unei
mult¸imi de drumuri, valorile m, n ¸si afi¸seaz˘a, pentru fiecare locat¸ie, num˘arul garajului din care porne¸ste
drumul care trece prin acea locat¸ie. (5p.)
SUBIECTUL al III-lea (30 de puncte)
Scriet¸i pe foaia de examen r˘aspunsul pentru itemul 1.
1. Se consider˘a funct, ia recursiv˘a F de mai jos. Ce valoare va returna apelul F(36)? (5p.)
int F(int n)
{
int m = 1;
int i;
for (i = 2; i < n; ++i) {
if (n % i == 0) {
break;
}
}
while (n % i == 0) {
n /= i;
m *= i;
}
if (n == 1) {
return m * (i - 1) / i;
}
return F(n) * F(m);
}
Pentru itemul 2, scriet¸i pe foaia de examen litera corespunz˘atoare r˘aspunsului corect.
2. Care este cel mai mic num˘ar ˆıntreg strict pozitiv pentru care funct, ia F de mai sus ˆıntoarce 10? (5p.)
A. 11 B. 22 C. 36 D. 40
Scriet¸i pe foaia de examen r˘aspunsul pentru fiecare dintre cerint¸ele urm˘atoare.
3. Fie graful neorientat G = (V, E) cu vˆarfurile V = {0, 1, . . . , n − 1} (unde n ≥ 1) ¸si muchiile E. Fiecare
vˆarf v ∈ V are asociat˘a o culoare col(v) ∈ {0, 1, . . . , c − 1} (unde c ≥ 1). Culorile accesibile dintr-un vˆarf
v ∈ V sunt culorile vˆarfurilor w ∈ V pentru care exist˘a un drum de la v la w ˆın G, inclusiv culoarea lui v.
a) Fie V = {0, 1, 2, 3, 4, 5, 6} ¸si E = {{0, 2}, {0, 4}, {0, 5}, {1, 3}, {2, 4}, {2, 5}, {3, 6}}. Culorile sunt:
col(0)=3, col(1)=4, col(2)=3, col(3)=2, col(4)=2, col(5)=2, col(6)=0. G˘asit¸i un vˆarf v ∈ V astfel
ˆıncˆat num˘arul de culori distincte accesibile din v este maxim. (5p.)
b) Funct¸ia maxColor are ca parametri numerele naturale n ¸si c (unde n, c ≥ 1), mult¸imea de muchii E
¸si culorile vˆarfurilor. Mult, imea de muchii este reprezentat˘a prin matricea de adiacent¸˘a, iar culorile
printr-un vector. Funct¸ia maxColor g˘ase¸ste un vˆarf v ∈ V astfel ˆıncˆat num˘arul de culori distincte acce-
sibile din v este maxim ¸si returneaz˘a acest maxim. Implementat¸i funct¸ia maxColor ˆın C/C++/Pascal.
(10p.)
c) Funct¸ia maxConnect are aceia¸si parametri ca funct¸ia maxColor. Aceasta alege dou˘a vˆarfuri neadiacente
v ¸si w astfel ˆıncˆat, dup˘a ad˘augarea muchiei {v, w}, num˘arul returnat de funct¸ia maxColor pe noul graf
s˘a fie maxim. Dac˘a exist˘a o astfel de muchie, atunci funct¸ia returneaz˘a valoarea ˆıntoars˘a de maxColor
pe noul graf. Altfel funct, ia returneaz˘a −1. Implementat¸i funct¸ia maxConnect ˆın C/C++/Pascal. (5p.)

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 2019
Proba scris˘a la INFORMATIC ˘A
BAREM DE EVALUARE S¸I NOTARE
● Se puncteaz˘a oricare alte modalit˘at¸i de rezolvare corect˘a a cerint¸elor.
● ˆIn cazul ˆın care la o ˆıntrebare cu r˘aspuns scurt (o liter˘a, un num˘ar) pe foaia de examen sunt mai
multe r˘aspunsuri (exemplu: ’A’, ’B’; sau: 11, 12), niciunul dintre ele nu se puncteaz˘a.
● ˆIn cazul ˆın care la o ˆıntrebare cu r˘aspuns scurt (o liter˘a, un num˘ar) r˘aspunsul nu este clar
(exemplu: se scrie un caracter similar s, i cu ’a’ s, i cu ’d’, sau o cifr˘a similar˘a s, i cu ’1’ s, i cu ’7’),
r˘aspunsul nu se puncteaz˘a.
● 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 C 4p.
2. a. Valoarea returnat˘a este 26. 6p. ☀
dac˘a r˘aspunsul nu este corect, punctaj part, ial maxim pentru
descrierea calculului
4p.
b. R˘aspunsul este 511. 6p. ☀
dac˘a rezultatul nu este corect, punctaj part, ial maxim pentru
descrierea calculului ¸si a rat¸ionamentului
4p.
c. R˘aspunsul corect. 4p. ☀
dac˘a r˘aspunsul nu este corect, punctaj part, ial pentru:
1. tratarea corect˘a a cazului de baz˘a 1p.
2. identificarea celor dou˘a cazuri recursive (ˆın funct, ie de
paritatea lui n)
1p.
3. invocarea recursiv˘a a subprogramului 1p.
d. Pentru funct, ia C/C++/Pascal corect˘a 10p. ☀
dac˘a r˘aspunsul nu este corect, punctaj part, ial pentru:
1. declararea corect˘a a funct, iei 3p.
2. declararea corect˘a a variabilelor locale 2p.
3. folosirea corect˘a a instruct, iunii repetitive 4p.
4. ˆıntoarcerea rezultului corect 1p.

Barem · pagina 2

SUBIECTUL al II-lea (30 de puncte)
1. R˘aspuns corect B (94) 5p. ☀
dac˘a r˘aspunsul nu este corect, punctaj part, ial pentru:
1. identificarea grafului (arbore) care respect˘a cerint, ele s, i
are num˘ar maxim de vˆarfuri
2p.
2. scrierea num˘arului maxim de vˆarfuri aflate la distant, a k,
0 ≤ k ≤ 5
2p.
3. efectuarea calculului 1 + 3 + 3 ⋅ 2 + 3 ⋅ 22 + 3 ⋅ 23 + 3 ⋅ 24 = 94 1p.
2. R˘aspuns corect C (1, 1, 2, 3, 4, 5) 5p. ☀
dac˘a r˘aspunsul nu este corect, punctaj part, ial pentru:
1. pentru punctul C, conectarea vˆarfului de grad maxim
cu celelalte vˆarfuri s, i observarea faptului c˘a gradele r˘amase,
(0, 0, 1, 2, 3), nu pot reprezenta secvent, a gradelor unui graf
4p.
2. pentru fiecare dintre punctele A, B, D, scrierea unui graf
cu secvent, a gradelor de la punctul respectiv
1p.
3. a. R˘aspuns corect. 2p. ☀
dac˘a r˘aspunsul nu este corect, punctaj part, ial pentru:
1. verificarea fapului c˘a num˘arul a are cel put, in 4 cifre 1p.
2. verificarea fapului c˘a cifrele lui a sunt nenule 1p.
b. R˘aspuns corect. 4p. ☀
dac˘a r˘aspunsul nu este corect, punctaj part, ial pentru:
1. iterarea prin cifrele num˘arului a 1p.
2. identificarea pozit, iilor pare s, i impare 1p.
3. construirea corect˘a a num˘arului n 1p.
4. construirea corect˘a a num˘arului m 1p.
c. R˘aspuns corect. 4p. ☀
dac˘a r˘aspunsul nu este corect, punctaj part, ial pentru:
1. calculul numerelor nm s, i n! f˘ar˘a a t, ine cont de precizia
limitat˘a a reprezent˘arii numerelor
1p.
2. calculul lui u(n!) sau observat, ia faptului c˘a u(n!) = 0
dac˘a n ≥ 5 (u(x) este ultima cifr˘a a num˘arului x)
1p.
3. calculul lui u(nm) sau identificarea situat, ilor ˆın care
u(nm) = 1: u(n) = 1 sau (u(n) = 9 s, i m par) sau ((u(n) = 3
sau u(n) = 7) s, i m multiplu de 4))
1p.
4. a. R˘aspuns corect. 2p.
0010000
0000101
0001000
1000000
0000010
0100000
0100000
b. R˘aspuns corect. 3p. ☀
dac˘a r˘aspunsul nu este corect, punctaj part, ial pentru:
1. declararea corect˘a a funct, iei 1p.
2. parcurgerea coloanei i din matrice 1p.
c. R˘aspuns corect. 5p. ☀
dac˘a r˘aspunsul nu este corect, punctaj part, ial pentru:
1. declararea corect˘a a funct, iei 1p.
2. iterarea prin mult, imea locat, iilor 1p.
3. invocarea repetat˘a a funct, iei prev 2p.
4. identificarea corect˘a a garajului 1p.

Barem · pagina 3

SUBIECTUL al III-lea (30 de puncte)
1. R˘aspuns corect (12) 5p. ☀
dac˘a r˘aspunsul nu este corect:
punctaj part, ial pentru calculul lui n = 4 si m = 9 ˆın expresia
F(4) * F(9)
3p.
calculul corect al expresiei F(4) 1p.
calculul corect al expresiei F(9) 1p.
2. R˘aspuns corect A (11) 5p. ☀
descrierea unui calcul corect care duce la rezultatul 10 3p.
3. a. R˘aspuns corect: oricare dintre 1, 3, 6. 5p. ☀
1. identificarea celor dou˘a componente conexe 3p.
2. pentru fiecare dintre cele dou˘a componente conexe,
calculul num˘arului de culori distincte
1p.
b. Implementare corect˘a. 10p. ☀
1. declararea corect˘a a funct¸iei 2p.
2. parcurgerea vˆarfurilor grafului 1p.
3. determinarea componentei conexe pentru fiecare vˆarf 4p.
4. determinarea num˘arului de culori distincte accesibile
vˆarfului
2p.
5. alegerea num˘arului maxim de culori distincte accesibile 1p.
c. Implementare corect˘a. 5p. ☀
1. parcurgerea tuturor perechile neordonate de noduri nea-
diacente {v, w}.
1p.
2. determinarea num˘arului maxim de culori accesibile ˆın
graful modificat
3p.
3. determinarea corect˘a a r˘aspunsului 1p.

Deschide documentul original

Continuă pregătirea

Vezi arhiva completă

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

Despre acest subiect

Subiectul și baremul în format text

Subiect · pagina 1

Subiect · pagina 2

Barem · pagina 1

Barem · pagina 2

Barem · pagina 3

Alte subiecte de la aceeași facultate

Ce trebuie să știi despre acest subiect?