Pregătire cu un profesor

Universitatea “Alexandru Ioan Cuza” din Ia¸si Admitere - studii de licent¸˘a
Facultatea de Informatic˘a Sesiunea iulie 2015
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. Numerele reale x, y, z s, i t satisfac inegalit˘at, ile x < y s, i z < t. Precizat, i care dintre expresiile
C/C++ de mai jos este echivalent˘a cu faptul c˘a intervalele ˆınchise [x, y] s, i [z, t] au intersect, ia
nevid˘a ([x, y] ⋂ [z, t] ≠ ∅). (4p.)
a. !((z > y) || (t < x))
c. !((x < z) && (t < y))
b. (x <= z) || (y >= t)
d. !((x > t) || (y > z))
2. Se consider˘a algoritmul al˘aturat, des-
cris ˆın pseudocod.
a. Scriet, i valoarea afis, at˘a de algoritm dac˘a
num˘arul n citit este 213521. (6p.)
b. Care este cel mai mic num˘ar natural for-
mat din patru cifre distincte care poate fi
citit ˆın varabila n astfel ˆıncˆat algoritmul s˘a
afis, eze valoarea 1? (6p.)
c. Scriet, i o secvent, ˘a de instruct, iuni care
s˘a foloseasc˘a doar operat, ii de adunare
s, i sc˘adere s, i care s˘a fie echivalent˘a cu
instruct, iunea n ← [n / 10]. (4p.)
d. Scriet, i programul C/C++ corespunz˘ator al-
goritmului al˘aturat. (10p.)
cites¸te n (num˘ar natural)
x ← n % 10; m ← 1; s ← 1
cˆat timp n > 9 execut˘a
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
n ← [n / 10]; y ← n % 10
dac˘a (y-x)*m < 0 atunci
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
dac˘a m > 0 atunci m ← -1
altfel s ← 0
x ← y
scrie s
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 num˘arul maxim de noduri de grad 3 ˆıntr-un graf neorientat cu 5 noduri? (4p.)
a. 2 b. 3 c. 4 d. 5
2. Fie un graf neorientat cu mult, imea nodurilor {1, 2, ..., 2015}. Dou˘a noduri i s, i j sunt unite
printr-o muchie dac˘a s, i numai dac˘a max(i,j) = 2*min(i,j) sau max(i,j) = 2*min(i,j)+1. Care
este num˘arul de muchii ale acestui graf? (6p.)
a. 2015 b. 2016 c. 2014 d. (2014×2015)/2

Subiect · pagina 2

Scriet¸i pe foaia de examen r˘aspunsul pentru fiecare dintre cerint¸ele urm˘atoare.
3. Consider˘am codificarea binar˘a a caracterelor, ˆın care fiec˘arui simbol ˆıi revine reprezentarea pe
8 bit¸i a codului s˘au ASCII. De exemplu, caracterului ’A’, avˆand codul ASCII 65, ˆıi va corespunde
reprezentarea binar˘a 01000001. Scriet¸i un program C/C++ care s˘a cont¸in˘a urm˘atoarele funct¸ii:
a) Funct¸ia convert char prime¸ste ca argument un caracter ¸si construie¸ste un tablou cu 8 elemente
0 sau 1, reprezentˆand codificarea binar˘a a caracterului primit. (2p.)
b) Funct¸ia convert string prime¸ste ca argument un ¸sir de caractere s ¸si construie¸ste o matrice cu
n linii ¸si 8 coloane (unde n este lungimea ¸sirului s), linia i a matricii reprezentˆand codificarea
binar˘a a caracterului de pe pozit¸ia i din ¸sir. (2p.)
c) Funct¸ia submatrix size prime¸ste ca argument o matrice m format˘a doar din elemente 0 ¸si 1
(precum ¸si dimensiunile sale) ¸si determin˘a dimensiunea celei mai mari submatrici p˘atratice a lui
m cont¸inˆand elemente avˆand toate aceea¸si valoare (fie 0, fie 1). (5p.)
(Observat¸ie: funct¸iile pot avea ¸si alte argumente fat¸˘a de cele specificate mai sus.)
Programul va citi de la tastatur˘a un ¸sir de caractere s ¸si va afi¸sa rezultatul determinat de funct¸ia
submatrix size aplicat˘a pe matricea construit˘a de convert string aplicat˘a ¸sirului s. (1p.)
Exemplu: Pentru ¸sirul de caractere s="IDEEA", programul va afi¸sa 3, matricea corespunz˘atoare fiind:
m =
⎛
⎜
⎜
⎜
⎜
⎜
⎜
⎝
0 1 0 0 1 0 0 1
0 1 0 0 0 1 0 0
0 1 0 0 0 1 0 1
0 1 0 0 0 1 0 1
0 1 0 0 0 0 0 1
⎞
⎟
⎟
⎟
⎟
⎟
⎟
⎠
.
4. Fie mult¸imea S = {1,2,. . . ,n}, unde n ≥ 4 este un num˘ar natural multiplu de 4.
Scriet¸i un program C/C++ care:
a) Cite¸ste de la tastatur˘a num˘arul n ≥ 4 precum ¸si un num˘ar natural p (1 ≤ p ≤ n/2). ˆIn cazul ˆın
care condit¸iile impuse nu sunt ˆındeplinite, va fi afi¸sat mesajul ”date invalide”. (2p.)
b) Partit¸ioneaz˘a mult¸imea dat˘a S ˆın dou˘a submult¸imi disjuncte A ¸si B (S = A ∪ B, A ∩ B = ∅)
astfel ˆıncˆat suma elementelor din A s˘a fie egal˘a cu suma elementelor din B. (3p.)
c) Elimin˘a elementul p din mult¸imea S ¸si creeaz˘a o nou˘a partit¸ie A′, B′ (eventual, modificˆand partit¸ia
creat˘a la punctul b) astfel ˆıncˆat S ∖ {p} = A′ ∪ B′, A′ ∩ B′ = ∅ ¸si suma elementelor din A′
este egal˘a cu suma elementelor din B′. ˆIn cazul ˆın care acest lucru nu este posibil, va fi afi¸sat
mesajul ”partit¸ie inexistent˘a”. (5p.)
Exemplu: Pentru n=8, S = {1,2,3,4,5,6,7,8}, partit¸ia init¸ial˘a este A = {1,3,6,8}, B =
{2,4,5,7}. Dac˘a p=1 sau p=3, va afi¸sa ”partit¸ie inexistent˘a”. Dac˘a p=2, partit¸ia modificat˘a este
A′ = {3,6,8}, B′ = {1,4,5,7}. Dac˘a p=4, partit¸ia modificat˘a este A′ = {2,6,8}, B′ = {1,3,5,7}.
SUBIECTUL al III-lea (30 de puncte)
Pentru itemul 1, scriet¸i pe foaia de examen litera corespunz˘atoare r˘aspunsului corect.
1. ˆIntr-o urn˘a se afl˘a 4 bile de culoare alb˘a ¸si 3 bile de culoare neagr˘a. Se extrag bilele pe rˆand ¸si se
ret¸ine secvent¸a de 7 culori obt¸inut˘a. Cˆate astfel de secvent¸e distincte sunt? (4p.)
a. 210 b. 35 c. 70 d. 840

Subiect · pagina 3

Scriet¸i pe foaia de examen r˘aspunsul pentru fiecare dintre cerint¸ele urm˘atoare.
2. Pentru funct¸iile F1 ¸si F2 definite mai jos, ce valoare va returna apelul F1(34)? (6p.)
int F2(int x);
int F1(int x) {
if (x < 7) { return 3 + x; }
else { return 2 + F2(x - 2); }
}
int F2(int x) {
if (x < 10) { return 3 * x; }
else { return 2 * F1(x / 2); }
}
3. Un puzzle Minesweeper este o matrice de n linii ¸si m coloane care cont¸ine la fiecare pozit¸ie num˘arul
0 (reprezentˆand un loc liber) sau −1 (reprezentˆand o min˘a). Pozit¸iile adiacente pozit¸iei (i, j) sunt:
{(i − 1, j − 1), (i − 1, j), (i − 1, j + 1), (i, j − 1), (i, j + 1), (i + 1, j − 1), (i + 1, j), (i + 1, j + 1)} ⋂ {0, . . . , n − 1} × {0, . . . , m − 1}.
O pozit¸ie (i, j) din matrice este periculoas˘a dac˘a cel put¸in o pozit¸ie din cele maxim 8 pozit¸ii adiacente
cont¸ine o min˘a. Fie (l, c) o pozit¸ie ˆın matrice. Zona sigur˘a este compus˘a din toate pozit¸iile accesibile
din (l, c) urmˆand un drum format din pozit¸ii nepericuloase adiacente.
Zona activ˘a cont¸ine toate pozit¸iile zonei sigure ¸si pozit¸iile adiacente zonei sigure. Matricea rezultat
are acelea¸si dimensiuni cu puzzle-ul ¸si este definit˘a astfel:
• Dac˘a (l, c) cont¸ine o min˘a, matricea rezultat va fi chiar puzzle-ul init¸ial.
• Dac˘a (l, c) nu cont¸ine o min˘a dar este periculoas˘a, matricea rezultat cont¸ine −2 peste tot cu
exceptia pozit¸iei (l, c), care cont¸ine num˘arul de mine vecine.
• Altfel, matricea rezultat cont¸ine pe fiecare pozit¸ie (i, j) din zona activ˘a num˘arul de mine adia-
cente pozit¸iei (i, j) ¸si −2 ˆın celelalte pozit¸ii.
Exemplu (I) (II) (III) (IV )
Puzzle
⎛
⎜
⎜
⎜
⎜
⎝
-1 0 0 -1
0 0 -1 0
0 0 0 0
0 -1 0 0
⎞
⎟
⎟
⎟
⎟
⎠
⎛
⎜
⎜
⎜
⎜
⎝
0 0 0 0
0 -1 -1 0
0 0 0 0
0 0 0 0
⎞
⎟
⎟
⎟
⎟
⎠
⎛
⎜
⎜
⎜
⎜
⎝
-1 0 0 0
0 0 0 0
0 0 -1 -1
0 -1 0 -1
⎞
⎟
⎟
⎟
⎟
⎠
⎛
⎜
⎜
⎜
⎜
⎝
-1 0 0 0
0 0 0 0
0 0 0 0
0 0 0 -1
⎞
⎟
⎟
⎟
⎟
⎠
Pozit, ia (l, c) (1, 2) (2, 1) (0, 2) (1, 3)
Rezultat
⎛
⎜
⎜
⎜
⎝
-1 0 0 -1
0 0 -1 0
0 0 0 0
0 -1 0 0
⎞
⎟
⎟
⎟
⎠
⎛
⎜
⎜
⎜
⎝
-2 -2 -2 -2
-2 -2 -2 -2
-2 2 -2 -2
-2 -2 -2 -2
⎞
⎟
⎟
⎟
⎠
⎛
⎜
⎜
⎜
⎝
-2 1 0 0
-2 2 2 2
-2 -2 -2 -2
-2 -2 -2 -2
⎞
⎟
⎟
⎟
⎠
a) Scriet¸i matricea rezultat pentru exemplul (IV ). (5p.)
b) Scriet¸i ˆın limbajul C/C++ o funct, ie care, primind la intrare un puzzle, calculeaz˘a o matrice
(de aceleas, i dimensiuni cu puzzle-ul) care cont, ine 0 pe pozit, iile nepericuloase s, i 1 pe pozit, iile
periculoase. (5p.)
c) Scriet¸i ˆın limbajul C/C++ o funct¸ie care:
– prime¸ste ca argument o matrice reprezentˆand puzzle-ul Minesweeper ¸si pozit¸ia (l, c);
– construie¸ste matricea rezultat dup˘a cum este descris mai sus. (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 2015
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. a 4p.
2. a. Valoarea returnat˘a este 0 6p.
1. descrierea calculului 4p.
2. obt¸inerea rezultatului corect 2p.
b. Cel mai mic num˘ar natural con-
form cu cerint¸a este 1230.
6p.
1. identificarea propriet˘at¸ii de
munte
2p.
2. utilizarea a patru cifre distincte 2p.
3. obt¸inerea valorii 1230 2p.
c. Pentru algoritm corect 4p.
1. folosirea unei structuri repetitive
cˆat timp sau repet˘a
2p.
2. scrierea corect˘a a secvent¸ei 2p.
d. Pentru program corect 10p.
1. structura corect˘a a programului 2p.
2. citirea corect˘a a parametrului n 1p.
3. instruct¸iune repetitiv˘a corect˘a 3p.
4. instruct¸iuni de decizie corecte 3p.
5. afi¸sarea corect˘a a valorii s 1p.

Barem · pagina 2

SUBIECTUL al II-lea (30 de puncte)
1. c 4p.
2. R˘aspuns corect c 6p.
1. stabilirea propriet˘at¸ii de arbore 2p.
2. un arbore cu n noduri are n-1 muchii 2p.
3. obt¸inerea valorii 2014 2p.
3. Pentru solut¸ie corect˘a 10p.
1. citirea datelor de intrare 1p.
2. alocarea memoriei 1p.
3. lucrul cu ¸siruri de caractere 1p.
4. structura corect˘a convert char 1p.
5. structura corect˘a convert string 1p.
6. funct¸ia (secvent¸a de cod) care de-
termin˘a cea mai mare submatrice avˆand
colt¸ul stˆanga-sus la o anumit˘a pozit¸ie a
matricii
3p.
7. parcurgerea pozit¸iilor matricii date 1p.
8. structura corect˘a submatrix size 1p.
4. Pentru solut¸ie corect˘a 10p.
1. citirea datelor de intrare 1p.
2. validarea datelor de intrare 1p.
3. observat¸ia c˘a exist˘a un num˘ar par de
perechi de forma (k, (n+1)-k)
1p.
4. crearea corect˘a a partit¸iei init¸iale,
mult¸imea A avˆand elemente impare pe
primele n/4 pozit¸ii iar B elemente pare
pe primele n/4 pozit¸ii
2p.
5. observat¸ia c˘a dac˘a p este num˘ar im-
par, S ∖ {p} nu poate fi partit¸ionat˘a
1p.
6. observat¸ia c˘a dac˘a p este par, p ∈ B,
suma(B) scade cu p/2
1p.
7. observat¸ia c˘a dac˘a p/2 este im-
par, p/2 ∈ A, partit¸ia modificat˘a este
A′ = A ∖ {p/2}, B′ = B ∪ {p/2}
1p.
8. observat¸ia c˘a dac˘a p/2 este par, 1 +
p/2 ∈ A, A′ = A ∖ {1+p~2} ∖ {1} ∪ {2},
B′ = B ∪ {1+p~2} ∪ {1} ∖ {2}
1p.
9. crearea corect˘a a partit¸iilor A′,B′ 1p.

Barem · pagina 3

SUBIECTUL al III-lea (30 de puncte)
1. b 4p.
2.
R˘aspuns corect: 74 6p.
1. observarea faptului c˘a funct¸iile
F1 ¸si F2 sunt mutual recursive
1p.
2. calculul recursiv (lista tuturor
apelurilor recursive)
3p.
3. obt¸inerea rezultatului corect 2p.
3.
a. Pentru r˘aspuns corect 5p.
-2 1 0 0
1 1 0 0
0 0 1 1
0 0 1 -2
5p.
b. Pentru solut¸ie corect˘a 5p.
1. parcurgerea tuturor pozit, iilor
matricii
1p.
2. parcurgerea tuturor vecinilor
pentru pozit, ia curent˘a
2p.
3. determinarea corect˘a a faptului
ca pozit, ia curent˘a este periculoas˘a
sau nu
2p.
c. Pentru solut¸ie corect˘a 10p.
1. identificarea s, i tratarea corect˘a
a cazului particular ˆın care (l, c)
cont, ine o min˘a
2p.
2. identificarea s, i tratarea corect˘a
a cazului particular ˆın care (l, c) nu
cont, ine min˘a s, i este periculoas˘a
2p.
3. g˘asirea zonei sigure printr-un al-
goritm de tip flood-fill (bfs, dfs sau
ad-hoc)
3p.
4. identificarea pozit, iilor adiacente
zonei sigure
1p.
5. calculul num˘arului de vecini care
cont, in mine pentru fiecare pozit, ie
din zona activ˘a (sigur˘a + pozit, ii ad-
iacente zonei sigure)
1p.
6. determinarea rezultatului corect
pentru cazul general
1p.

Deschide documentul original

Continuă pregătirea

Vezi arhiva completă

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

Despre acest subiect

Subiectul și baremul în format text

Subiect · pagina 1