Pregătire cu un profesor

Universitatea “Alexandru Ioan Cuza” din Ia¸si Admitere - studii de licent¸˘a
Facultatea de Informatic˘a Sesiunea iulie 2014
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. Precizat¸i care dintre expresiile C/C++ de mai jos este echivalent˘a cu relat¸ia
a ∈ [-4,-1] ∪ [2,4]. (4p.)
a. !((a < -4 || a > -1) && (a >= 2 || a <= 4))
b. !(a >= -4 && a <= -1 && a >= 2 && a <= 4)
c. (a >= -4 || a <= -1) && (a >= 2 || a <= 4)
d. !(a < -4 || a > -1) || !(a < 2 || a > 4)
2. Se consider˘a algoritmul al˘aturat, des-
cris ˆın pseudocod.
a. Scriet¸i valoarea afi¸sat˘a de algoritm dac˘a
num˘arul n citit este 91. (6p.)
b. Care sunt cea mai mic˘a, respectiv cea mai
mare valoare pe care o poate lua n ˆın in-
tervalul [1,300] astfel ˆıncˆat algoritmul s˘a
afi¸seze valoarea 11? (6p.)
c. ˆInlocuit¸i instruct¸iunea x ← n % y cu o
secvent¸˘a echivalent˘a de instruct¸iuni care
folose¸ste doar adun˘ari/sc˘aderi repetate.
(4p.)
d. Scriet¸i programul C/C++ corespunz˘ator al-
goritmului al˘aturat. (10p.)
cites¸te n
(num˘ar natural nenul)
x ← 1
y ← 2
cˆat timp x ≠ 0 s¸i y*y <= n execut˘a
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
x ← n % y
y ← y + 1
scrie y-1

Subiect · pagina 2

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 un arbore binar cu 15 noduri. Num˘arul nodurilor cu cel put¸in un fiu este cel mult: (4p.)
a. 14 b. 8 c. 7 d. 1
2. Se consider˘a un graf neorientat cu 8 vˆarfuri numerotate de la 1 la 8 ¸si urm˘atoarele muchii:
{1,7},{1,8},{3,4},{3,5},{3,6},{3,7},{4,7},{5,6},{5,8},{6,7},{6,8},{7,8}. Care este
num˘arul minum de culori cu care pot fi colorate vˆarfurile grafului astfel ˆıncˆat oricare dou˘a vˆarfuri
adiacente s˘a aib˘a culori diferite? (6p.)
a. 2 b. 3 c. 4 d. 8
Scriet¸i pe foaia de examen r˘aspunsul pentru fiecare dintre cerint¸ele urm˘atoare.
3. O matrice are proprietatea ParImpar dac˘a fiecare dintre liniile sale este format˘a fie doar din
numere ˆıntregi pare, fie doar din numere ˆıntregi impare. Scriet¸i un program C/C++ care:
a) Cite¸ste de la tastatur˘a un num˘ar natural n ≥ 2 ¸si o matrice p˘atratic˘a A de dimensiune
n × n, calculeaz˘a matricea produs B = A × A ¸si verific˘a dac˘a B are proprietatea ParImpar,
conform definit¸iei de mai sus. (6p.)
b) Justificat¸i faptul c˘a dac˘a matricea A are proprietatea ParImpar, atunci ¸si matricea B are
proprietatea ParImpar. (4p.)
4. Scriet¸i un program C/C++ care:
a) Cite¸ste de la tastatur˘a un num˘ar natural n ≥ 2 ¸si un vector w1, . . . , wn de numere ˆıntregi.
(2p.)
b) Construie¸ste o permutare w′
1, . . . , w′
n a vectorului init¸ial w1, . . . , wn astfel ˆıncˆat oricare dou˘a
elemente aflate pe pozit¸ii consecutive ˆın permutare sunt diferite: w′
i ≠ w′
i+1, ∀i = 1..n − 1.
Dac˘a nu exist˘a o astfel de permutare, atunci algoritmul va afi¸sa nu exist˘a. (8p.)
Exemple:
• pentru vectorul 1, 1, 1, 2, 2, 2, 3, 3, permutarea ar putea fi 3, 2, 1, 3, 2, 1, 2, 1;
• dac˘a vectorul este 1, 1, 1, 2 atunci permutarea nu poate fi creat˘a.

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. La un concurs particip˘a 4 elevi iar concursul se desf˘a¸soar˘a ˆın dou˘a s˘ali: sala A ¸si sala B.
Fiecare sal˘a are capacitatea de maxim 3 locuri. ˆIn cˆate moduri pot fi ˆımp˘art¸it¸i elevii ˆın s˘alile A
¸si B? (ordinea elevilor ˆın cadrul unei s˘ali nu conteaz˘a) (4p.)
a. 8 b. 14 c. 16 d. 18
Scriet¸i pe foaia de examen r˘aspunsul pentru fiecare dintre cerint¸ele urm˘atoare.
2. Pentru funct¸ia C definit˘a al˘aturat, ce
valoare va returna apelul C(5,3)? (6p.)
int C(int n, int k) {
if (k == 0 || n == k) return 1;
return C(n - 1, k - 1) + C(n - 1, k);
}
3. O gril˘a SUDOKU este o matrice 9 × 9 care respect˘a urm˘atoarele propriet˘at¸i:
1. fiecare element al matricii este un num˘ar natural ˆıntre 1 ¸si 9,
2. fiecare linie cont¸ine toate numerele naturale de la 1 la 9,
3. fiecare coloan˘a cont¸ine toate numerele naturale de la 1 la 9,
4. fiecare dintre cele 9 submatrici de dimensiune 3 × 3,
evident¸iate prin linii ˆıngro¸sate ˆın exemplul al˘aturat, cont¸ine
toate numerele de la 1 la 9.
6 2 8 5 3 4 9 1 7
5 1 9 8 7 2 4 3 6
4 3 7 9 1 6 2 5 8
8 6 5 2 4 7 1 9 3
3 9 2 1 8 5 7 6 4
7 4 1 6 9 3 5 8 2
2 5 4 3 6 9 8 7 1
1 7 6 4 5 8 3 2 9
9 8 3 7 2 1 6 4 5
Un puzzle SUDOKU este o matrice 9 × 9 completat˘a part¸ial cu numere naturale de la 1 la 9. Mai
jos este un exemplu de puzzle SUDOKU. O solut¸ie a unui astfel de puzzle este o gril˘a SUDOKU care
coincide cu puzzle-ul pe pozit¸iile precompletate.
2 5 8 7 3 9 4 1
6 9 8 2 4 3 7
4 7 1 5 2 6
3 9 5 2 7 4 6
6 2 4 8 1 5
8 4 6 5 7 2 9
1 8 4 3 6 9 5 7 2
7 1 4 2 9 3
9 2 3 5 8 7 6 1 4
a) G˘asit¸i o solut¸ie pentru puzzle-ul SUDOKU de mai sus. (4p.)
b) Descriet¸i ˆın limbaj natural un algoritm pentru rezolvarea unui puzzle SUDOKU. (6p.)
c) Scriet¸i ˆın limbajul C/C++ o funct¸ie care:
• prime¸ste ca argument o matrice reprezentˆand puzzle-ul SUDOKU (celulele necompletate
ale puzzle-ului sunt reprezentate ˆın matrice de cifra 0);
• returneaz˘a o matrice reprezentˆand solut¸ia puzzle-ului. Dac˘a problema nu are solut¸ie,
matricea returnat˘a va cont¸ine pe toate liniile ¸si coloanele doar cifra 0. (10p.)

Deschide documentul original

Barem · 3 pagini

Barem · pagina 1

Universitatea “Alexandru Ioan Cuza” din Ia¸si Admitere - studii de licent¸˘a
Facultatea de Informatic˘a Sesiunea iulie 2014
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 la 10 a punctajului total
acordat pentru lucrare.
● ˆ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. d 4p.
2. a. Valoarea returnat˘a este 7 6p.
1. descrierea calculului 4p.
2. obt¸inerea rezultatului corect 2p.
b. Cea mai mic˘a valoare a lui n este 121 3p.
Cea mai mare valoare a lui n este 253 3p.
c. Pentru algoritm corect 4p.
1. folosirea unei structuri repetitive
cˆat timp sau repet˘a
2p.
2. scrierea corect˘a a algoritmului 2p.
d. Pentru program corect 10p.
1. structura corect˘a a programului 3p.
2. citirea corect˘a a parametrului n 1p.
3. instruct¸iunea repetitiv˘a corect˘a 5p.
4. afi¸sarea expresiei y-1 1p.

Barem · pagina 2

SUBIECTUL al II-lea (30 de puncte)
1. a 4p.
2. b 6p.
3. a. Pentru solut¸ie corect˘a 6p.
1. citirea datelor de intrare 1p.
2. calculul matricii produs B 2p.
3. verificarea propriet˘at¸ii ParImpar 3p.
b. Pentru r˘aspuns corect 4p.
4. a. Pentru solut¸ie corect˘a 2p.
b. Pentru solut¸ie corect˘a 8p.
1. crearea corect˘a a permut˘arii ˆın cazul
ˆın care exist˘a
5p.
2. descrierea cazului ˆın care nu exist˘a
solut¸ie
3p.

Barem · pagina 3

SUBIECTUL al III-lea (30 de puncte)
1. b 4p.
2.
R˘aspuns corect: 10 6p.
1. observarea faptului c˘a funct¸ia C este
recursiv˘a
1p.
2. calculul lui C(5,3) 3p.
3. obt¸inerea rezultatului corect 2p.
3.
a. Pentru r˘aspuns corect 4p.
2 5 8 7 3 6 9 4 1
6 1 9 8 2 4 3 5 7
4 3 7 9 1 5 2 6 8
3 9 5 2 7 1 4 8 6
7 6 2 4 9 8 1 3 5
8 4 1 6 5 3 7 2 9
1 8 4 3 6 9 5 7 2
5 7 6 1 4 2 8 9 3
9 2 3 5 8 7 6 1 4
b. Pentru solut¸ie corect˘a 6p.
1. descrierea structurii de date 2p.
2. descrierea structurii unui algoritm
de tip backtracking
3p.
3. testarea validit˘at¸ii unei configurat¸ii
part¸iale
1p.
c. Pentru funct¸ie corect˘a 10p.
1. structura funct¸iei (argumente, tip
returnat)
1p.
2. validarea unei grile part¸iale 2p.
3. implementarea unui algoritm valid 5p.
4. returnarea solut¸iei 1p.
5. determinarea inexistent¸ei solut¸iei 1p.

Deschide documentul original

Continuă pregătirea

Vezi arhiva completă

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

Despre acest subiect

Subiectul și baremul în format text

Subiect · pagina 1