Pregătire cu un profesor

Universitatea de Vest din Timi¸soara
Facultatea de Matematic˘a ¸si Informatic˘a
Admitere - 19 iulie 2018
Concurs de admitere la Facultatea de Matematic˘a ¸si Informatic˘a
Proba: INFORMATIC ˘A
I.(40p)
1. (5p) Se consider˘a suma S = 1 − 1/3 + 1/5 − 1/7 + 1/9 − . . . (primul termen este 1, al doilea termen este −1/3
etc.).
(a) Care este expresia corespunz˘atoare celui de al k-lea termen?
(i) 1/(2k − 1);
(ii) 1/(2k + 1);
(iii) (−1)k/(2k − 1);
(iv) (−1)k+1/(2k − 1);
(v) (−1)k+1/(2k + 1).
(b) Scriet¸i o funct¸ie ˆın C/C++/Pascal care prime¸ste ca parametru un num˘ar natural n ≥ 2 ¸si returneaz˘a
suma primilor n termeni din S.
2. (5p) Un num˘ar natural este considerat tip ”dublu-unu” dac˘a reprezentarea sa ˆın baza 2 cont¸ine exact o
pereche de cifre consecutive egale cu 1 (numerele 3 = (11)2, 6 = (110)2 sunt de tip ”dublu-unu”, dar numerele
5 = (101)2 ¸si 7 = (111)2 nu sunt de acest tip).
(a) Cˆate numere de tip ”dublu-unu” sunt ˆın intervalul (0, 2d)?
(b) Care dintre urm˘atoarele afirmat¸ii este adevarat˘a pentru orice num˘ar n de tip ”dublu-unu” din (0, 2d):
(i) exist˘a 1 ≤ k ≤ d astfel ˆıncˆat n = 2k − 2k−1;
(ii) exist˘a 1 ≤ k < d astfel ˆıncˆat n = 2k + 2k−1;
(iii) exist˘a 0 < k < d astfel ˆıncˆat n = 2k+1 + 2k−1;
(iv) exist˘a 1 ≤ k < d astfel ˆıncˆat n = 2k + 1;
3. (10p) Se consider˘a un serviciu web la care utilizatorii se conecteaz˘a/deconecteaz˘a ¸si se pune problema deter-
min˘arii num˘arului maxim de utilizatori conectat¸i simultan pornind de la o secvent¸˘a de semnale de forma: 1 (s-a
conectat un utilizator), 0 (s-a deconectat un utilizator). De exemplu pentru secvent¸a 1,1,1,0,1,0,1,1,1,0,0,1,0,0,0
num˘arul maxim de utilizatori conectat¸i simultan este 5. Scriet¸i o funct¸ie C/C++/Pascal care prime¸ste un
tablou de semnale precum ¸si num˘arul acestora ¸si returneaz˘a num˘arul maxim de utilizatori conectat¸i simultan.
4. (10p) Pentru un num˘ar natural nenul n se pune problema determin˘arii num˘arului de zerouri finale (de exemplu
304500 cont¸ine dou˘a zerouri finale, 30245 cont¸ine 0 zerouri finale). (a) Scriet¸i o funct¸ie C/C++/Pascal
(nerecursiv˘a) care prime¸ste ca parametru num˘arul n ¸si returneaz˘a num˘arul de zerouri finale. (b) Scriet¸i o
funct¸ie C/C++/Pascal recursiv˘a care efectueaz˘a aceea¸si prelucrare.
5. (10p) Se consider˘a c˘a un text a fost tehnoredactat folosind o tastatur˘a defect˘a care ”multiplic˘a” simbolurile
tastate ¸si se pune problema ”cur˘at¸irii” acestui text prin eliminarea caracterelor ˆın exces (se presupune c˘a textul
cont¸ine doar cuvinte ˆın care nu intervin simboluri consecutive identice). De exemplu textul ”Acccceessttta
eesttte uuun exxeeemmppllluu” trebuie transformat ˆın ”Acesta este un exemplu”. Considerˆand c˘a textul este
stocat ˆıntr-un tablou cu elemente de tip caracter scriet¸i:
(a) o funct¸ie/procedur˘a care construie¸ste un nou tablou de caractere care cont¸ine textul cur˘at¸at (pentru
exemplul de mai sus noul tablou va avea 22 de caractere ¸si va cont¸ine ”Acesta este un exemplu”);
(b) o funct¸ie/procedur˘a care transform˘a tabloul init¸ial astfel ˆıncˆat pe primele pozit¸ii s˘a fie textul curat (ˆın
exemplul de mai sus noul cont¸inut al tabloului este ”Acesta este un exempluuuun exxeeemmppllluu”).
Nu este permis˘a utilizarea unui tablou adit¸ional.

Subiect · pagina 2

II.(25p) Se consider˘a un set de n ora¸se, numerotate de la 1 la n (n ≤ 50), ¸si o ”hart˘a” a conexiunilor aeriene dintre aceste
ora¸se stocat˘a sub forma unei matrici A cu n linii ¸si n coloane ˆın care elementul aij este 1 dac˘a exist˘a conexiune
direct˘a ˆıntre ora¸sele i ¸si j ¸si este 0 dac˘a nu exist˘a conexiune direct˘a (se presupune c˘a aii = 0 ¸si aij = aji pentru
orice i ¸si j din {1, 2, . . . , n}). Exemplu: se consider˘a 5 ora¸se ¸si matricea de conectivitate direct˘a:
A =






0 1 0 0 1
1 0 0 1 1
0 0 0 1 1
0 1 1 0 1
1 1 1 1 0






(a) Scriet¸i o funct¸ie/procedur˘a care construie¸ste tabloul D care cont¸ine pentru fiecare ora¸s num˘arul de conexiuni
directe (D[i] cont¸ine num˘arul de conexiuni directe care pornesc din ora¸sul i). Exemplu: D = [2, 3, 2, 3, 4].
(b) Scriet¸i o funct¸ie/procedur˘a care prime¸ste ca parametru tabloul D ¸si afi¸seaz˘a ora¸sele ˆın ordinea descresc˘atoare
a num˘arului de conexiuni directe. Exemplu: valorile afi¸sate sunt 5, 2, 4, 1, 3.
(c) Scriet¸i o funct¸ie/procedur˘a care prime¸ste ca parametri matricea conexiunilor ¸si indicii a dou˘a ora¸se (i ¸si j) ¸si
afi¸seaz˘a toate variantele de a ajunge din ora¸sul i ˆın ora¸sul j f˘acˆand cel mult o escal˘a. Exemplu: pentru i = 2,
j = 5 se afi¸seaz˘a: (2, 5), (2, 1, 5), (2, 4, 5).
(d) Scriet¸i o funct¸ie/procedur˘a care calculeaz˘a matricea B = A2 = A × A.
(e) ˆIn ipoteza c˘a fiecare ora¸s este conectat direct cu cel put¸in un alt ora¸s care dintre urm˘atoarele afirmat¸ii,
referitoare la elementele matricii B, este adev˘arat˘a? (i) bii = 0 ¸si bij = bji pentru orice i ¸si j din {1, 2, . . . , n};
(ii) bii ≥ 1 pentru orice i din {1, 2, . . . , n} ¸si exist˘a cel put¸in o pereche de (i, j) cu proprietatea c˘a bij 6 = bji;
(iii) bii cont¸ine num˘arul de conexiuni directe ale ora¸sului i. Argumentat¸i r˘aspunsul selectat.
III.(25p) Un lucr˘ator preia pachete (de dimensiuni diferite) de pe o band˘a ¸si le stivuie¸ste astfel ˆıncˆat s˘a nu pun˘a niciodat˘a
un pachet peste unul de dimensiune mai mic˘a (dac˘a un pachet nu poate fi plasat pe nici una dintre stivele existente
este creat˘a o nou˘a stiv˘a). De exemplu, dac˘a dimensiunile pachetelor, ˆın ordinea ˆın care sosesc pe band˘a, sunt [3,
1, 2, 6, 5, 7, 4] atunci stivele constituite sunt [3, 1], [2], [6, 5, 4], [7].
(a) Propunet¸i o structur˘a de date pentru reprezentarea stivelor ¸si scriet¸i o funct¸ie/procedur˘a care prime¸ste ca
parametri num˘arul de pachete ¸si un tablou cu dimensiunile acestora ¸si care distribuie pachetele pe stive astfel
ˆıncˆat num˘arul de stive create s˘a fie cˆat mai mic (fiecare pachet este plasat pe prima stiv˘a pe care este posibil).
(b) Presupunˆand c˘a num˘arul de stive create este k justificat¸i faptul c˘a cel mai lung sub¸sir strict cresc˘ator din
tabloul dimensiunilor are k elemente (elementele din sub¸sir nu sunt neap˘arat consecutive dar trebuie s˘a fie ˆın
aceea¸si ordine ca ˆın ¸sirul init¸ial; de exemplu [1, 2, 6, 7] este un sub¸sir strict cresc˘ator al ¸sirului [3, 1, 2, 6, 5, 7,
4]). Scriet¸i o funct¸ie/procedur˘a care construie¸ste un sub¸sir strict cresc˘ator de lungime maxim˘a.
Not˘a:
1. Timp de lucru: 3 ore
2. Toate subiectele sunt obligatorii
3. Limbajul de programare este la alegere ˆıntre C/C++ ¸si Pascal. Nu este permis˘a utilizarea funct¸iilor din biblioteci
(cu except¸ia funct¸iilor/procedurilor de afi¸sare).
4. Pentru fiecare dintre funct¸iile/procedurile scrise se vor specifica toate declarat¸iile de variabile globale ¸si locale
necesare ¸si se vor pune comentarii explicative. NU este necesar˘a scrierea programului principal ¸si preluarea datelor
prin citire.

Subiect · pagina 3

Universitatea de Vest din Timi¸soara
Facultatea de Matematic˘a ¸si Informatic˘a
Admitere - 19 iulie 2018
Barem de corectare - INFORMATIC ˘A
Start . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .10p
I.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5p
I.1a: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2p
(R˘aspuns corect: (iv) )
I.1b: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3p
(declararea corect˘a a funct¸iei, a variabilelor locale ¸si returnarea rezultatului - 1p; descrierea corect˘a a calculului sumei
- 2p)
I.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5p
I.2a: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3p
R˘aspuns corect: d − 1
I.2b: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2p
R˘aspuns corect: (ii)
I.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10p
(declararea corect˘a a funct¸iei, variabilelor de lucru ¸si returnarea rezultatului - 1p; parcurgerea corect˘a a tabloului cu
semnale - 2p; actualizarea corect˘a a num˘arului de utilizatori activi - 3p; determinarea valorii maxime - 4p)
I.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10p
I.4a: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5p
(declararea corect˘a a funct¸iei, a variabilelor de lucru ¸si returnarea rezultatului - 1p; calculul corect al num˘arului de
zerouri finale - 4p;)
I.4b: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5p
(declararea corect˘a a funct¸iei, a variabilelor de lucru ¸si returnarea rezultatului - 1p; condit¸ie corect˘a pentru ie¸sirea
din apelul recursiv - 1p; apel recursiv corect - 1p; calculul corect al num˘arului de zerouri finale - 2p)
I.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10p
5a: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5p
(declararea funct¸iei/procedurii ¸si a variabilelor utilizate - 1p; construirea corect˘a a noului tablou - 4p)
5b: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5p
(declararea funct¸iei/procedurii ¸si a variabilelor utilizate - 1p; transformarea corect˘a a tabloului - 4p)

Subiect · pagina 4

II . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25p
II.a: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5p
(declararea corect˘a a funct¸iei/procedurii ¸si a variabilelor utilizate - 1p; calculul sumei elementelor de pe fiecare linie
(sau determinarea num˘arului de valori egale cu 1 de pe fiecare linie) ¸si stocarea corect˘a ˆın tabloul D - 4p.)
II.b: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8p
(declararea corect˘a a funct¸iei/procedurii ¸si a variabilelor utilizate - 1p; implementarea corect˘a a unei metode de sortare
- 5p; asigurarea concordant¸ei dintre elementele tabloului D ¸si numerele de ordine ale ora¸selor - 1p; afi¸sarea numerelor de
ordine ale ora¸selor ˆın ordinea cerut˘a - 1p)
II.c: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5p
(declararea corect˘a a funct¸iei/procedurii ¸si a variabilelor utilizate - 1p; afi¸sarea traseului direct (dac˘a exist˘a) - 1p;
afi¸sarea tuturor traseelor cu o escal˘a - 3p)
II.d: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5p
(declararea corect˘a a funct¸iei/procedurii ¸si a variabilelor utilizate - 1p; calculul corect al produsului - 4p)
II.e: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2p
(r˘aspuns corect: (iii) - 1p; argumentare: bii = ∑n
k=1 aik · aki reprezint˘a num˘arul de ora¸selor k conectate direct cu
ora¸sul i (aik = 1) - 1p)
III . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25p
III.a: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15p
(definirea unei structuri de date adecvate - 5p; declararea corect˘a a funct¸iei/procedurii ¸si a variabilelor utilizate - 1p;
parcurgerea tabloului cu dimensiuni ¸si completarea structurii - 9p)
III.b: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10p
(justificarea faptului c˘a un sub¸sir strict crsc˘ator nu poate avea mai mult de un element ˆın aceea¸si stiv˘a - 2p; declararea
corect˘a a funct¸iei/procedurii ¸si a variabilelor utilizate - 1p; construirea unui sub¸sir strict cresc˘ator - 7p)
TOTAL: 100
Observat¸ie: Se puncteaz˘a corespunz˘ator orice variant˘a corect˘a de rezolvare.

Deschide documentul original

Continuă pregătirea

Vezi arhiva completă

Concurs de pregătire · 2018Informatică · Clasele a XI-a și a XII-aDeschide fișa Concurs de pregătire · 2018Matematică · Clasa a XI-aDeschide fișa Concurs de pregătire · 2018Matematică · Clasa a XII-aDeschide fișa Examen de admitere · 2018Matematică · Sesiunea iulie; subiect oficialDeschide fișa Concurs de pregătire · 2019Matematică · Clasa a XI-aDeschide fișa Concurs de pregătire · 2019Matematică · Clasa a XII-aDeschide 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?

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

Despre acest subiect

Subiectul în format text

Subiect · pagina 1

Subiect · pagina 2

Subiect · pagina 3

Subiect · pagina 4

Alte subiecte de la aceeași facultate

Ce trebuie să știi despre acest subiect?