Pregătire cu un profesor

UNIVERSITATEA DE VEST DIN TIMIŞOARA
FACULTATEA DE MATEMATICĂ ŞI INFORMATICĂ
Examen de admitere
Informatică, 17 Iulie 2021
Notă: Subprogramele pot fi scrise în limbajele de programare C/C++/ Pascal/Python. Proba de examen durează 3 ore.
Partea I (6p)
1. (0.75p) Un nufăr îşi dublează suprafat, a în fiecare zi.
(a) (0.25p) În a 48-a zi nufărul ocupă toată suprafat, a unui lac. În a câta zi nufărul ocupă un sfert din suprafat, a
lacului? (i) 46 (ii) 22 (iii) 12 (iv) 11
(b) (0.5p) Considerăm un subprogram recursiv care primeşte ca parametri suprafat, a ocupată de nufăr azi, S (număr
real pozitiv), şi un număr natural X. Subprogramul returnează suprafat, a ocupată de nufăr în urmă cu X zile.
Completat, i spat, iile lipsă pentru condit, ia de oprire şi apelul recursiv.
Subprogram f (S, X)
dacă . . . (i) . . . returnează S
altfel returnează . . . (ii) . . .
2. (1p) Se consideră că locurile dintr-un amfiteatru sunt reprezentate sub forma unei matrice de dimensiune m × n (unde
m, n ∈ N, 2 < m < 30, 2 < n < 30). Pentru participarea la un examen se doreşte aranjarea candidat, ilor după modelul
de mai jos (pentru m = 4 şi n = 13), unde 1 reprezintă loc ocupat, iar 0 reprezintă loc liber. Între oricare două locuri
ocupate există un loc liber, între două rânduri ocupate există un rând liber.
1 0 1 0 1 0 1 0 1 0 1 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 1 0 1 0 1 0 1 0 1 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0
(a) (0.5p) Scriet, i un subprogram care primeşte ca parametri numărul de rânduri şi locuri pe rând şi completează o
matrice, declarată ca variabilă globală, cu structura specificată mai sus.
(b) (0.25p) Care este numărul maxim de student, i care pot fi plasat, i într-un amfiteatru reprezentat sub forma unei
matrice de dimensiune n × m ocupată după modelul de mai sus? (b c reprezintă partea întreagă a unui număr
real)
(i) bn/2c · bm/2c; (ii) b(n + 1)/2c · b(m + 1)/2c; (iii) m · n/2
(c) (0.25p) Determinaţi numărul minim de locuri dintr-un amfiteatru ocupat la capacitate maximă cu 91 de studenţi
distribuiţi în felul indicat mai sus.
(i) 13 × 25 (ii) 13 × 26 (iii) 14 × 26 (iv) 14 × 25 (v) 12 × 25
3. (1.25p) Fie T un arbore cu rădăcină care are n noduri.
(a) (0.25p) Câte muchii are arborele T ?
(i) n + 1 (ii) n (iii) n − 1 (iv) n − 2
(b) (0.25p) În câte feluri se pot colora nodurile arborelui T cu roşu şi negru astfel încât orice două noduri învecinate
să aibă culori diferite?
(i) 2 (ii) 1 (iii) n (iv) 2n (v) n − 1
(c) (0.25p) Presupunem că arborele T are 9 noduri numerotate de la 1 la 9, rădăcina 1, şi muchiile [1, 2], [1, 3], [2, 4],
[2, 5], [2, 6], [2, 7], [3, 8], [8, 9]. Care este numărul maxim de noduri roşii în arborele T dacă nodurile sunt colorate
cu roşu şi negru astfel încât oricare două noduri învecinate să aibă culori diferite?
(d) (0.5p) Se consideră că un nod frunză este un nod care nu este tată al altui nod. Definiţi un subprogram care
primeşte ca parametri de intrare vectorul de taţi al unui arbore cu rădăcina 1 şi cu n ≤ 50 noduri numerotate de
la 1 la n, şi numărul n, şi returnează numărul frunzelor din arborele respectiv.
1

Subiect · pagina 2

4. (1p) Se consideră un şir S1 de n caractere (n < 10000). Un subşir, S2, al şirului S1 este format dintr-o succesiune de
caractere, nu neapărat consecutive ale şirului S1, în ordinea în care acestea apar în S1. Scriet, i un subprogram care
primeşte patru parametri: două şiruri S1 şi S2 şi lungimile lor, şi verifică dacă S2 este subşir al lui S1. În caz afirmativ,
subprogramul afişează pozit, iile caracterelor din şirul S1 pe care se află elementele din S2. În cazul în care S1 nu cont, ine
elementele lui S2 se va afişa “Nu este subşir”.
De exemplu, pentru şirurile S1 = “La ce examen primim rezultatul maine?” şi S2 = “La mate?” se va afişa
1 2 3 10 27 28 36 37
5. (1p) Un şir de bit, i este k-special dacă începe cu 1, cont, ine bitul 1 de exact k ori, şi între oricare doi de 1 consecutivi
apare cel mult un 0. De exemplu, şirul 101100 este 3-special, dar şirul 110010 nu este. Fie A un tablou cu 0 şi 1 care
reprezinta un şir de n bit, i, n ≤ 100000.
(a) (0.5p) Definit, i un subprogram care primeşte ca parametru de intrare tabloul A, dimensiunea acestuia n şi re-
turnează true dacă tabloul A reprezintă un şir 6-special, şi false în caz contrar.
(b) (0.5p) Câte şiruri 6-speciale de 12 bit, i există?
(i) 25 (ii) 32 (iii) 5 (iv) 6
6. (1p) Patru prieteni trebuie să treacă un pod şubred pe timp de noapte, înainte ca podul să fie luat de ape. Cei patru
prieteni au diferite condit, ii fizice: Ana poate trece podul într-un minut, Bogdan are nevoie de 2 minute, Cristina de
5 minute, iar Dan de 10 minute. Podul nu poate sust, ine mai mult de două persoane în acelaşi timp, iar aceste două
persoane au nevoie de lanternă pentru a vedea unde păşesc. Drept urmare, după ce doi prieteni trec podul, lanterna
trebuie adusă înapoi de cineva. Timpul în care trec doi prieteni este dat de timpul cel mai lung: dacă Ana şi Dan trec
în acelaşi timp, va dura 10 minute.
(a) (0.5p) Propunet, i o ordine de trecere, astfel încât cei 4 prieteni să treacă podul în 17 minute.
(b) (0.5p) Scriet, i un subprogram care primeşte ca parametri un tablou T, (T1 ≤ T2 ≤ . . . ≤ Tn) reprezentând timpi de
traversare, dimensiunea tabloului n (n ≤ 100) şi calculează timpul necesar trecerii tuturor celor n prieteni pentru
următoarea strategie: prietenul cel mai rapid îi conduce pe fiecare, întorcându-se cu lanterna.
Partea a II-a (3p)
UEFA doreşte realizarea unui sistem de înregistrare a rezultatelor meciurilor din grupele EURO 2020 pentru aflarea echipelor
calificate în faza următoare. Se citeşte de la tastatură indicativul grupei (A, B, ..., F ), urmat de 6 rezultate de forma a X Y
b, semnificând că echipa a a marcat X goluri, iar echipa b a marcat Y goluri. Dacă o echipă câştigă meciul (are mai multe
goluri înscrise), aceasta va acumula 3 puncte. Dacă scorul este egal, atunci fiecare echipă va acumula câte un punct.
Primele două clasate din fiecare grupă se vor califica direct în faza următoare. Dacă două echipe au acelaşi număr de
puncte, vor fi departajate în funct, ie de golaverajul G = GM − GP , GM = goluri marcate, GP = goluri primite.
1. (0.75p) Propunet, i o structură de date pentru memorarea clasamentului,
punctelor şi golaverajului
2. (0.75p) Scriet, i un subprogram citire_rezultate care citeşte datele de intrare
şi care completează structura de date propusă.
3. (0.75p) Scriet, i un subprogram ordonare_clasament care ordonează de-
screscător echipele din fiecare grupă pe baza punctajului. Echipele cu acelaşi
punctaj sunt ordonate descrescător după golaveraj.
4. (0.75p) Scriet, i un subprogram af isare_calif icate, care foloseşte clasamen-
tul ordonat anterior şi afişează echipele calificate direct. Aceste echipe vor
fi afişate în ordinea grupelor, adică A1, A2, B1, B2, . . .. Fiecare echipă va fi
afişată pe o linie, alături de punctaj şi golaveraj.
Exemplu:
A
a 0 3 b
c 1 1 d
a 0 2 c
b 3 0 d
b 1 0 c
d 3 1 a
B
...
Output:
Echipe calificate direct:
b 9 7
c 4 1
...
2

Subiect · pagina 3

BAREM
Partea I
SUBIECTUL 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0.75p
1a (i) 46 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0.25p
1b (i) X = 0, (ii) f (S/2, X − 1) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0.5p
SUBIECTUL 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1p
2a Variantă de rezolvare (în C++) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0.5p
int A[30][30];
void init(int m,int n) {
for (int i=0;i<m;i++)
for (int j=0;j<n;j++)
if ((i%2==0)&&(j%2==0)) { A[i][j]=1; }
else { A[i][j]=0; }
}
2b (ii) b(n + 1)/2c · b(m + 1)/2c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0.25p
2c (i) 13 × 25 = 325. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0.25p
SUBIECTUL 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.25p
3a (iii) n − 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0.25p
Într-un arbore cu rădăcină, orice muchie este între un nod şi părintele lui. Doar nodul rădăcină nu are părinte. Rezultă
că numărul de muchii conicid cu numărul de noduri diferite de rădăcină, adică n − 1.
3b (i) 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0.25p
Fie d(x) numărul de muchii de la rădacina arborelui la nodul x din arbore, şi c culoarea rădăcinii. Observăm că
• Toate nodurile cu d(x) impar au culoarea diferită de c.
• Toate nodurile cu d(x) par au culoarea c.
Deci, după ce am colorat rădăcina, avem o singură posibilitate să colorăm restul nodurilor din arbore. Rezultă că numărul
de colorări cu roşu şi negru al unui arbore coincide cu numărul de colorări posibile ale rădăcinii cu roşu sau negru, adică 2.
3c Răspuns: Numărul maxim de noduri roşii este 6, în a doua colorare. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .0.25p
Cele două colorări posibile sunt ilustrate mai jos:
1
2
4 5 6 8
3
8
9
1
2
4 5 6 7
3
8
9
3d Variantă de rezolvare (în C++) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0.5p
int nrFrunze(int* tata,int n) {
int nrFii[51];
for (int i=1;i<=n;i++) nrFii[i]=0;
for (int i=2;i<=n;i++) nrFii[tata[i]]++;
int nrFrunze=0;
for (int i=1;i<=n;i++)
if (nrFii[i]==0) nrFrunze++;
return nrFrunze;
}
SUBIECTUL 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1p
Variantă de rezolvare (în C++)
3

Subiect · pagina 4

void subsir(char* S1,char* S2, int m, int n) {
int p=0; // poziţia curentă în şirul S2
int subsir[n]; // poziţiile unde apare S2 în S1
for (int i=0;i<m;i++) { // presupun că m este lungimea lui S1
if (S1[i]==S2[p]) {
subsir[p++]=i+1; // pentru că indexăm caracterele lui S1 începând de la 1
if (p==n) {
for (int j=0;j<n;j++) cout << subsir[j] << ’ ’;
return;
}
}
cout<<"Nu este subşir";
}
SUBIECTUL 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1p
5a Variantă de rezolvare (în C++) 0.5p
bool special6(int *A, int n) {
int pos; // variabilă locală care reţine poziţia ultimului bit 1 găsit în A
int n; // variabilă locală care reţine numărul de biţi 1 găsiţi în A
if (A[0]!=1) return false;
else { n=1; p=0; }
for (int i=1;i<n;i++)
if (A[i]==1) {
n++;
if (n>6||(i-pos>2)) return false;
pos=i;
}
return (n==6);
}
5b (ii) 25 = 32 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0.5p
Orice şir 6-special de 12 biţi este unic determinat de poziţiile i1, i2, i3, i4, i5, i6 unde apare 1 în şir. P¸ rimul bit este 1, deci
i1 = 1. Ştim că i2 ∈ {2, 3}, i3 ∈ {i2 + 1, i2 + 2}, i4 ∈ {i3 + 1, i3 + 2}, i5 ∈ {i4 + 1, i4 + 2} şi i6 ∈ {i5 + 1, i5 + 2}. Deci avem
2 posibilităţi pentru valoarea fiecărei poziţii i2, i3, i4, i5, i6. Rezultă că sunt 25 = 32 posibilităţi, adică 32 de şiruri 6-speciale
de 12 biţi.
SUBIECTUL 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1p
6a Modul de traversare al podului este următorul: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . (0.5p)
Ana, Bogdan −→ (2)
←− Ana (1)
Cristina, Dan −→ (10)
←− Bogdan (2)
Ana, Bogdan −→ (2)
Total: 17
6b Orice implementare care efectuează calculul T1 · (n − 2) + ∑n
i=2 Ti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .(0.5p)
Partea a II-a
În cele ce urmează se consideră că prima echipă se află pe pozit, ia 0 în tabloul numit clasament.
1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0.75p
Varianta A: Folosirea unui tablou de structuri abstracte de date în care se ret, in indicativul echipei, punctajul s, i golaverajul.
struct echipa {
int indicativ, punctaj, golaveraj;
}
echipa clasament[24];
4

Subiect · pagina 5

Varianta B: O matrice în care pe prima coloană se stochează indicativul echipei (a = 0, b = 1, . . .), pe a doua coloană
numărul de puncte, iar pe a treia golaverajul.
int clasament[24][3];
2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0.75p
Citirea tuturor liniilor (6 indicative de grupă şi 36 de meciuri) (0.25p), calcularea punctelor s, i golaverajului pe baza unui
meci (0.25p), actualizarea clasamentului (0.25p)
3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0.75p
Parcurgerea per grupe a clasamentului s, i ordonarea echipelor din fiecare grupă după punctaj s, i golaveraj folosind orice
algoritm de sortare.
Variantă de rezolvare în C++:
void ordonare_clasament(echipa clasament[24]) {
for(int gr = 0; gr < 6; gr++){
int start = gr*4;
int end = start+4;
//ordonare între start si end
}
}
4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0.75p
Parcurgerea similar cu exemplul de la punctul 3, afişarea clasament[start], clasament[start + 1]
OBS: Orice variantă corectă de rezolvare va fi luată în considerare.
5

Deschide documentul original

Continuă pregătirea

Vezi arhiva completă

Concurs de pregătire · 2021Informatică · Etapa 1Deschide fișa Concurs de pregătire · 2021Informatică · Etapa 2Deschide fișa Concurs de pregătire · 2021Matematică · Clasa a XI-a, etapa 1Deschide fișa Concurs de pregătire · 2021Matematică · Clasa a XII-a, etapa 1Deschide fișa Examen de admitere · 2021Matematică · Sesiunea iulie; subiect oficialDeschide fișa Concurs de pregătire · 2022Informatică · Etapa 1Deschide fișa

Răspunsuri directe

Ce trebuie să știi despre acest subiect?

Ce document de admitere este acesta?

Pagina prezintă examen de admitere din 2021 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?

Nu există un barem public asociat în inventarul verificat pentru acest document. ProfesorBun nu generează și nu inventează răspunsuri oficiale. Poți folosi subiectul pentru antrenament, dar corectarea trebuie făcută cu metodologia instituției, cu materiale oficiale suplimentare sau împreună cu un profesor.

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ă · 2021

Despre acest subiect

Subiectul în format text

Subiect · pagina 1

Subiect · pagina 2

Subiect · pagina 3

Subiect · pagina 4

Subiect · pagina 5

Alte subiecte de la aceeași facultate

Ce trebuie să știi despre acest subiect?