Pregătire cu un profesor

Universitatea Alexandru Ioan Cuza din Ia¸si Admitere - studii de licent¸˘a
Facultatea de Informatic˘a Sesiunea iulie 2018
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. Variabilele u, v, z, t memoreaz˘a valori ˆıntregi astfel ˆıncˆat u < v ¸si z < t. Precizat¸i care
dintre expresiile C/C++ de mai jos, atunci cˆand este adev˘arat˘a, implic˘a faptul c˘a intersect¸ia
intervalelor [u, v) ¸si (z, t] este nevid˘a. (4p.)
A. (u > t) && (v > z)
C. (u <= t) && (v == z)
B. !((u > t) || (v > z))
D. !((u > t) || (t > u))
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 dou˘a
numere naturale nenule ˆın parametrii x s, i y s, i ˆıntoarce un num˘ar natural cˆand se opres, te.
a. Care este valoarea returnat˘a de subprogram pen-
tru parametrii x = 52 ¸si y = 5? (6p.)
b. Care este cel mai mare num˘ar prim y astfel ˆıncˆat
F(x,y) s˘a returneze 231? (6p.)
c. ˆInlocuit¸i instruct¸iunea x ← x / 2 cu o secvent¸˘a
de pseudocod echivalent˘a ¸si care folose¸ste
ca operat¸ii aritmetice doar adun˘ari/sc˘aderi
repetate. (4p.)
d. Scriet, i o funct, ie C/C++ care implementeaz˘a sub-
programul F al˘aturat. (10p.)
subprogram F(x, y)
(x, y - numere naturale nenule)
acc ← 0
c^at timp x 6 = 0
dac˘a x este impar atunci
acc ← acc + y
x ← x / 2
y ← y * 2
returneaz˘a acc
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 V mult¸imea tuturor secvent¸elor de lungime 8, formate doar din cifrele 0 s, i 1. Graful
neorientat G are drept vˆarfuri elementele lui V ¸si muchii doar ˆıntre vˆarfuri reprezentˆand secvent¸e
care difer˘a exact ˆıntr-una dintre cele 8 pozit¸ii. Care este num˘arul total de muchii din G? (5p.)
A. 896 B. 1024 C. 1792 D. 2048
2. Un graf este p-colorabil dac˘a p este cel mai mic num˘ar pentru care putem colora (eticheta)
vˆarfurile sale cu culori din mult¸imea {1, . . . , p}, astfel ˆıncˆat oricare dou˘a vˆarfuri adiacente s˘a fie
colorate diferit. Care este num˘arul minim de muchii ale unui graf 10-colorabil? (5p.)
A. 45 B. 50 C. 90 D. 100

Subiect · pagina 2

Scriet¸i pe foaia de examen r˘aspunsul pentru fiecare dintre cerint¸ele urm˘atoare.
3. Consider˘am o matrice A de dimensiune n × m (n, m ∈ N, n, m ≥ 2) care cont, ine numere
naturale distincte. Matricea reprezint˘a terenul de joac˘a al unei broscut, e. Elementul de la linia i
s, i coloana j din matrice este ˆın˘alt, imea terenului la acea pozit, ie. Broscut, a viziteaz˘a o succesiune
de pozit, ii din teren ˆın felul descris ˆın continuare. Broscut¸a se afl˘a init¸ial la linia L s, i coloana C
(1 ≤ L ≤ n, 1 ≤ C ≤ m). ˆIn orice pozit, ie s-ar afla la un moment dat, broscut, a efectueaz˘a un
salt pe una dintre pozit, iile vecine pe orizontal˘a sau vertical˘a (fiecare pozit, ie are cel mult patru
pozit, ii vecine: deasupra, dedesubt, la dreapta, la stˆanga).
Dintre acestea, broscut¸a va alege pozit, ia care are ˆın˘alt¸imea cea mai apropiat˘a de ˆın˘alt¸imea de
la pozit, ia curent˘a (diferent¸a ˆın modul dintre cele dou˘a ˆın˘alt, imi s˘a fie minim˘a). ˆIn cazul ˆın care
sunt mai multe pozit, ii vecine cu aceast˘a proprietate, ea alege s˘a sar˘a pe cea cu ˆın˘alt¸imea cea
mai mic˘a dintre acestea. Broscut, a nu se opres, te niciodat˘a.
a) ˆIn exemplul de mai jos dimensiunea terenului este 4 × 5. Broscut¸a se afl˘a init¸ial la coordo-
natele (L, C) = (2, 4), unde ˆın˘alt¸imea este 66. Scriet, i ˆın˘alt, imile primelor 10 pozit, ii vizitate
de broscut, ˘a, ˆın ordinea vizit˘arii acestora. (4p.)




57 51 70 72 75
56 58 60 66 77
59 54 93 90 76
88 52 61 79 68




b) Scriet¸i o funct, ie C/C++ care primes, te ca parametri matricea A, dimensiunile acesteia n s, i
m s, i numerele naturale L s, i C. Funct, ia trebuie s˘a returneze cea mai mic˘a ˆın˘alt, ime a unei
pozit, ii vizitate de broscut, ˘a de cel put, in dou˘a ori. Nu este necesar˘a validarea parametrilor
de intrare. (6p.)
4. Definim un cuvˆant ca fiind un ¸sir nevid format din cel mult 5 caractere ale alfabetului latin,
{’a’, ’b’, . . . , ’z’}.
a) Scriet¸i o funct¸ie C/C++ cu numele value, care are ca argument de intrare un cuvˆant ¸si
returneaz˘a un num˘ar natural. Pentru orice dou˘a cuvinte s1 ¸si s2, funct, ia trebuie s˘a satisfac˘a
proprietatea: s1 = s2 ⇔ value(s1) = value(s2). ˆIn cazul ˆın care argumentul primit nu
este cuvˆant, funct¸ia va returna 0. (6p.)
b) Justificat¸i faptul c˘a implementarea funct¸iei value este corect˘a. (4p.)
SUBIECTUL al III-lea (30 de puncte)
Pentru itemul 1, scriet¸i pe foaia de examen litera corespunz˘atoare r˘aspunsului
corect.
1. Cˆate s, iruri distincte formate din exact o liter˘a A, dou˘a litere B, trei litere C s, i patru litere D
exist˘a? (5p.)
A. 151200 B. 7560 C. 12600 D. 1024

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(53)? (5p.)
int F(int u) {
if (u == 0) {
return 0;
}
if (u % 2 != 0) {
return 2 * F(u / 2);
} else {
return 1 + F(u / 2);
}
}
3. Spunem c˘a o matrice p˘atratic˘a a, de dimensiune n ≥ 2, avˆand elemente numere naturale,
are proprietatea T dac˘a ˆındepline¸ste urm˘atoarele condit¸ii: (i) pentru orice 2 ≤ p ≤ n, num˘arul
de elemente nenule din submatricea format˘a din primele p linii ¸si p coloane ale lui a este 2p − 2;
(ii) pentru orice 1 ≤ j ≤ i ≤ n, fie a[i][j] = a[j][i] = 0, fie a[i][j] = a[j][i] + 1; (iii) pe orice linie
a matricii elementele nenule au aceea¸si valoare.
Exemplu: Matricea p˘atratic˘a de mai jos, de dimensiune 5, are proprietatea T :






0 1 1 0 1
2 0 0 0 0
2 0 0 2 0
0 0 3 0 0
2 0 0 0 0






a) Scriet¸i o funct¸ie C/C++ care prime¸ste ca parametri un ˆıntreg n ≥ 2 ¸si o matrice p˘atratic˘a
de dimensiune n. Funct¸ia va returna 1 dac˘a matricea satisface proprietatea T , 0 ˆın caz
contrar. (6p.)
b) Demonstrat¸i c˘a ˆıntr-o matrice p˘atratic˘a de dimensiune n ≥ 2 ce satisface proprietatea T
exist˘a cel put¸in dou˘a linii avˆand un singur element nenul. (6p.)
c) Scriet¸i o funct, ie C/C++ care prime¸ste ca argumente un ˆıntreg n ≥ 2 ¸si o matrice p˘atratic˘a
de dimensiune n care satisface proprietatea T . Funct, ia va afi¸sa cea mai lung˘a secvent¸˘a
de indec¸si (ik, . . . , i2, i1 = 1) care satisface relat¸ia a[ij+1][ij ] = a[ij ][ij+1] + 1, pentru orice
1 ≤ j < k. Nu este necesar˘a validarea parametrilor de intrare. Justificat¸i corectitudinea
algoritmului. Pentru exemplul de mai sus, funct, ia va afi¸sa: (4, 3, 1). Nu se acord˘a puncte
pentru solut, ii de tip backtracking. (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 2018
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.
● ˆ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 D 4p.
2. a. Valoarea returnat˘a este 260. 6p. ☀
dac˘a r˘aspunsul nu este corect, punctaj part, ial maxim pentru
descrierea calculului
4p.
b. R˘aspunsul este 11. 6p. ☀
dac˘a rezultatul nu este corect, punctaj part, ial maxim pentru
descrierea calculului
3p.
c. R˘aspuns corect. 4p.
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 variabilei locale 2p.
3. folosirea corect˘a a instruct, iunii repetitive 4p.
4. ˆıntoarcerea corect˘a a unei valori 1p.

Barem · pagina 2

SUBIECTUL al II-lea (30 de puncte)
1. R˘aspuns corect B (1024) 5p. ☀
dac˘a r˘aspunsul nu este corect, se acord˘a punctaj part, ial:
1. pentru calculul num˘arului de noduri 2p.
2. pentru calculul num˘arului de vecini ai unui nod 2p.
3. pentru calculul num˘arului de muchii 1p.
2. R˘aspuns corect A (45) 5p. ☀
dac˘a r˘aspunsul nu este corect, se acord˘a punctaj part, ial pen-
tru:
1. observat, ia faptului c˘a G trebuie s˘a aiba cel put, in 10
noduri/10 mult, imi nevide de noduri, fiecare mult, ime colo-
rat˘a cu aceeas, i culoare
2p.
2. observat, ia faptului c˘a, pentru orice dou˘a culori, trebuie
s˘a existe cel put, in o muchie ˆıntre dou˘a noduri colorate cu
cele dou˘a culori
2p.
3. a. R˘aspuns corect 66, 60, 58, 56, 57, 56, 57, 56, 57, 56 (se ac-
cept˘a s, i 60, 58, 56, 57, 56, 57, 56, 57, 56, 57 – cazul ˆın care
nu se consider˘a prima pozit, ie ca fiind vizitat˘a).
4p. ☀
dac˘a r˘aspunsul nu este corect, punctaj part, ial maxim pentru
descrierea calculului
2p.
b. R˘aspuns corect. 6p. ☀
dac˘a r˘aspunsul nu este corect, punctaj part, ial pentru:
1. declararea corect˘a a funct, iei. 1p.
2. calculul corect al vecinilor. 1p.
3. identificarea corect˘a a vecinului ales. 2p.
4. identificarea corect˘a a pozit, iilor care se repet˘a. 2p.
4. a. Pentru solut, ie corect˘a. 6p. ☀
dac˘a r˘aspunsul nu este corect, punctaj part, ial pentru:
1. declararea corect˘a a funct, iei 2p.
2. implementarea unei funct, ii injective pe cuvinte, care t, ine
cont de lungimea s, irului s, i de toate caracterele sale
4p.
b. R˘aspuns corect. 4p. ☀
dac˘a r˘aspunsul nu este corect, punctaj part, ial pentru:
1. ˆıncadrarea ˆın dimensiunea tipului rezultat 1p.
2. tratarea cazului cˆand lungimile s, irurilor s1 s, i s2 sunt
diferite
1p.
3. tratarea cazului cˆand s, irurile s1 s, i s2 au aceeas, i lungime 2p.

Barem · pagina 3

SUBIECTUL al III-lea (30 de puncte)
1. R˘aspuns corect C (12600) 5p. ☀
dac˘a r˘aspunsul nu este corect:
punctaj part, ial pentru g˘asirea unei expresii matematice co-
recte (e.g., C1
10 × C2
9 × C3
7 × C4
4 )
3p.
2.
R˘aspuns corect 6 5p.
dac˘a r˘aspunsul nu este corect:
punctaj part, ial maxim pentru descrierea calculului. 3p.
3. a. Pentru solut, ie corect˘a. 6p. ☀
dac˘a r˘aspunsul nu este corect, punctaj part, ial pentru:
1. declararea corect˘a a funct, iei s, i calculul valorii returnate 1p.
2. testarea propriet˘at, ii i. 2p.
3. testarea propriet˘at, ii ii. 1p.
4. testarea propriet˘at, ii iii. 2p.
b. Demonstrat, ie corect˘a. 6p.
c. Rezolvare corect˘a (f˘ar˘a backtracking). 8p. ☀
dac˘a rezolvarea nu este corect˘a s, i nu se foloses, te metoda
backtracking, punctaj part, ial pentru:
1. declararea corect˘a a funct, iei/procedurii. 1p.
2. utilizarea faptului c˘a matricea reprezint˘a matricea de
adiacent, ˘a a unui arbore.
4p.
3. parcurgerea dinspre frunze spre r˘ad˘acin˘a pentru g˘asirea
drumului maxim.
3p.

Deschide documentul original

Continuă pregătirea

Vezi arhiva completă

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

Despre acest subiect

Subiectul și baremul în format text

Subiect · pagina 1