Pregătire cu un profesor

Universitatea de Vest din Timi¸soara
Facultatea de Matematic˘a ¸si Informatic˘a
Concurs FMI - 19 mai 2018
Concurs FMI
Proba: INFORMATIC ˘A
1. (30p)
(a) (5p) Se consider˘a funct¸ia f : N ∗ × N ∗ → N definit˘a prin:
f (m, n) =
{ m dac˘a m < n
f (m − n, n) dac˘a m ≥ n
(i) Scriet¸i o funct¸ie recursiv˘a ˆın C/Pascal care prime¸ste doi parametri m ¸si n de tip ˆıntreg ¸si returneaz˘a
valoarea f (m, n); (ii) Ce returneaz˘a funct¸ia atunci cˆand este apelat˘a pentru dou˘a valori naturale nenule?
(b) (5p) Se ¸stie c˘a orice num˘ar natural nenul poate fi scris, ˆın mod unic, ca o sum˘a de termeni distinct¸i care
sunt puteri naturale ale lui 2. De exemplu 9 = 23 + 20, 15 = 23 + 22 + 21 + 20, 32 = 25. Scriet¸i o funct¸ie
care prime¸ste ca parametru un num˘ar natural nenul, n, ¸si returneaz˘a num˘arul de termeni distinct¸i din
descompunerea lui n ca sum˘a de puteri ale lui 2.
(c) (5p) Se consider˘a un num˘ar natural mare (ce cont¸ine cel put¸in 100 de cifre) specificat prin secvent¸a
cifrelor sale, (ck, ck−1, ..., c1, c0) (cu ck cifra cea mai semnificativ˘a ¸si c0 cifra cea mai put¸in semnificativ˘a).
Scriet¸i o funct¸ie care prime¸ste ca parametri num˘arul de cifre ¸si un tablou ce cont¸ine cifrele num˘arului ¸si
returneaz˘a 1 dac˘a num˘arul este divizibil cu 15 ¸si 0 ˆın caz contrar.
(d) (5p) Se consider˘a o matrice p˘atratic˘a A cu n linii ¸si n coloane ¸si se presupune c˘a elementele aflate sub
diagonala principal˘a sunt stocate ˆıntr-un tablou prin parcurgerea linie cu linie a matricii. Tabloul va
cont¸ine elementele a21, a31, a32, a41, a42, a43 . . .. Presupunˆand c˘a indicii tabloului pornesc de la 1
stabilit¸i care este indicele ˆın tablou al elementului aij din matrice (i > j): (i) (j − 2)(j − 1)/2 + i; (ii)
(i − 2)(i − 1)/2 + j; (iii) (i − 2)(j − 1)/2 + i; (iv) (j − 2)(i − 1)/2 + j; (v) nici una dintre variante nu e
corect˘a.
(e) (5p) Coeficientul de ”palindromitate” a unui ¸sir de numere naturale (b1, b2, . . . , bk) se define¸ste ca num˘arul
minim de operat¸ii de incrementare care ar trebui aplicate unor elemente din ¸sir astfel ˆıncˆat ¸sirul s˘a
devin˘a palindrom (b1 = bk, b2 = bk−1 etc.). (i) Scriet¸i relat¸ia matematic˘a de calcul a coeficientului
de ”palindromitate”; (ii) Scriet¸i o funct¸ie care prime¸ste ca parametru un tablou cu valori naturale ¸si
returneaz˘a valoarea coeficientului.
(f) (5p) Se consider˘a un graf neorientat cu n = 6 noduri specificat prin lista muchiilor sale: (1, 2), (1, 3),
(2, 3), (2, 4), (3, 6), (4, 5), (4, 6), (5, 6). (i) Desenat¸i graful; (ii) Este graful conex?; (iii) Care este num˘arul
minim de muchii care ar trebui eliminate pentru ca graful s˘a devin˘a neconex? Dat¸i un exemplu de muchii
prin a c˘aror eliminare graful devine neconex.
2. (20p) Se consider˘a un set de n (10 ≤ n ≤ 100) segmente de dreapt˘a specificate prin coordonatele ex-
tremit˘at¸ilor lor care sunt stocate ˆıntr-o matrice A cu n linii ¸si 4 coloane avˆand elemente numere reale.
Fiecare linie din matrice cont¸ine coordonatele a dou˘a puncte ˆın plan: ai1 ¸si ai2 reprezint˘a abscisa respectiv
ordonata primei extremit˘at¸i, iar ai3 ¸si ai4 reprezint˘a abscisa respectiv ordonata cel de a doua extremit˘at¸i.
(a) (5p) Scriet¸i o funct¸ie/procedur˘a care afi¸seaz˘a num˘arul de segmente de dreapt˘a orizontale ¸si num˘arul de
segmente de dreapt˘a verticale.
(b) (5p) S¸tiind c˘a lungimea unui segment determinat de dou˘a puncte avˆand coordonatele (xi, yi) respectiv
(xj , yj ) este √(xi − xj )2 + (yi − yj )2 scriet¸i o funct¸ie care prime¸ste ca parametri coordonatele a dou˘a
puncte ¸si returneaz˘a lungimea segmentului determinat de ele.
(c) (10p) Scriet¸i o funct¸ie/procedur˘a care transform˘a matricea A astfel ˆıncˆat liniile sale s˘a fie ordonate
cresc˘ator dup˘a lungimea segmentului pe care ˆıl reprezint˘a.

Subiect și barem · pagina 2

3. (20p) Pentru un num˘ar natural n definim d(n) ca fiind suma dintre n ¸si suma cifrelor sale. De exemplu,
d(75) = 75 + 7 + 5 = 87. Num˘arul n este considerat generator pentru d(n) (75 este generator pentru 87).
Un num˘ar natural nenul m este considerat auto-num˘ar dac˘a nu exist˘a nici un num˘ar n < m cu proprietatea
c˘a n este generator pentru m (adic˘a m 6 = d(n) pentru orice n < m).
(a) (5p) Scriet¸i o funct¸ie care prime¸ste un num˘ar natural n ¸si returneaz˘a valoarea lui d(n).
(b) (10p) Scriet¸i o funct¸ie care determin˘a num˘arul maxim de generatori pe care ˆıi poate avea un num˘ar cu
k cifre (2 ≤ k ≤ 4).
(c) (5p) Scriet¸i o funct¸ie/procedur˘a care afi¸seaz˘a toate auto-numerele care au cel mult k cifre (2 ≤ k ≤ 4).
4. (20p) Se consider˘a un set S de m ¸siruri de caractere ce cont¸in simboluri din {a, b} ¸si se pune problema
identific˘arii unor sub¸siruri cˆat mai lungi care verific˘a ¸sablonul ”anban” = ” aa...a︸ ︷︷ ︸
n ori
b aa...a︸ ︷︷ ︸
n ori
” (n ≥ 1). De
exemplu ˆın ¸sirul ”abbaaabaaabaab” cel mai lung sub¸sir care respect˘a ¸sablonul este ”aaabaaa” (cu n = 3).
(a) (10p) Scriet¸i o funct¸ie care prime¸ste ca parametru un ¸sir de caractere ¸si returneaz˘a valoarea n core-
spunz˘atoare celui mai lung sub¸sir care respect˘a ¸sablonul. Dac˘a un astfel de sub¸sir nu exist˘a se returneaz˘a
0.
(b) (10p) Declarat¸i o variabil˘a ˆın care se poate stoca setul de ¸siruri de caractere. Scriet¸i o funct¸ie care
afi¸seaz˘a cel mai lung sub¸sir care respect˘a ¸sablonul ¸si este comun tuturor ¸sirurilor din setul S .
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
4. Pentru fiecare dintre funct¸iile/subprogramele 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 nici
preluarea datelor prin citire.

Subiect și barem · pagina 3

Universitatea de Vest din Timi¸soara
Facultatea de Matematic˘a ¸si Informatic˘a
Concurs FMI - 19 mai 2018
Barem de corectare - INFORMATIC ˘A
Start . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10p
1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10p
1a: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5p
(i) descriere corect˘a a funct¸iei recursive - 3p; (ii) funct¸ia determin˘a restul ˆımp˘art¸irii ˆıntregi a lui m la n - 2p
1b: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5p
declararea corect˘a a funct¸iei, a variabilelor locale ¸si returnarea rezultatului - 1p; contorizarea num˘arului de
cifre egale cu 1 din reprezentarea ˆın baza 2 a num˘arului - 4p
1c: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5p
declararea corect˘a a funct¸iei, a variabilelor locale ¸si returnarea rezultatului - 1p; verificare divizibilitate cu 3
(suma tuturor cifrelor este divizibil˘a cu 3) - 2p; verificare divizibilitate cu 5 (cifra cea mai put¸in semnificativ˘a este
0 sau 5) - 2p
1d: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5p
(ii) pozit¸ia elementului aij ˆın tablou este (i − 2)(i − 1)/2 + j - 5p
1e: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5p
(i) ∑[k/2]
i=1 |bi − bk−i+1| - 2p; (ii) declararea corect˘a a funct¸iei, a variabilelor locale ¸si returnarea rezultatului -
1p; calculul corect al coeficientului - 2p
1f: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5p
(i)desen corect al grafului - 1p (ii) da, graful este conex - 1p; (iii) trebuie eliminate minim dou˘a muchii - 2p;
exemplu corect de muchii eliminate (de exemplu (2,4) ¸si (3,6)) - 1p
2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20p
2a: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5p
declararea corect˘a a funct¸iei, a variabilelor locale ¸si afi¸sarea rezultatelor - 1p; contorizarea corect˘a a segmentelor
orizontale (segmentul i este orizontal dac˘a ai2 = ai4, respectiv vertical dac˘a ai1 = ai3) - 4p
2b: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5p
declararea corect˘a a funct¸iei, a variabilelor locale ¸si returnarea rezultatului - 1p; descrierea corect˘a a calculului
lungimii unui segment - 4p
2c: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10p
declararea corect˘a a funct¸iei, a variabilelor locale/globale - 1p; implementarea corect˘a a algoritmului de sortare
folosind funct¸ia de la punctul (b) drept criteriu de sortare - 9p)

Subiect și barem · pagina 4

3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20p
3a: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5p
(declararea corect˘a a funct¸iei, a variabilelor locale ¸si returnarea rezultatului - 1p; calcul suma cifre - 3p; calcul
corect d(n) - 1p)
3b: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10p
declararea corect˘a a funct¸iei, a variabilelor locale ¸si afi¸sarea rezultatelor - 1p; construirea unui tabel de frecvent¸e
corespunz˘ator valorilor de tip d(i) calculate pentru valori ale lui i cuprinse ˆıntre 1 ¸si 10k − 1 - 7p; determinarea
valorii maxime din tabelul de frecvent¸e - 2p
3c: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5p
declararea corect˘a a funct¸iei, a variabilelor locale ¸si afi¸sarea rezultatelor - 1p; generarea corect˘a a auto-numerelor
(de exemplu parcurgˆand tabelul de frecvent¸e construit la punctul anterior) - 4p
4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20p
4a: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .10p
declararea corect˘a a funct¸iei, a variabilelor locale ¸si returnarea rezultatului - 1p; analiza tuturor sub¸sirurilor
care respect˘a ¸sablonul (de exemplu pornind de la un sub¸sir de forma ”aba” ¸si extinzˆandu-l ˆınspre stˆanga ¸si dreapta
cˆat este posibil) - 6p; determinarea corect˘a a parametrului n corespunz˘ator ¸sablonului de lungime maxim˘a - 3p
4b: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10p
declararea unei variabile care stocheaz˘a setul cu ¸siruri de caractere - 2p; declararea corect˘a a funct¸iei ¸si
a variabilelor locale - 1p; determinarea pentru fiecare ¸sir din set a lungimii maxime a unui sub¸sir care respect˘a
¸sablonul (folosind funct¸ia de la punctul (a)) - 3p; determinarea valorii minime dintre lungimile maxime determinate
- 2p; afi¸sarea corect˘a a ¸sablonului comun - 2p
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 · 2018Matematică · Clasa a XI-aDeschide fișa Concurs de pregătire · 2018Matematică · Clasa a XII-aDeschide fișa Examen de admitere · 2018Informatică · Sesiunea iulie; subiect oficialDeschide 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ă concurs de pregătire 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

Concurs de pregătire · Informatică · 2018

Despre acest subiect

Subiectul și baremul în format text

Subiect și barem · pagina 1

Subiect și barem · pagina 2

Subiect și barem · pagina 3

Subiect și barem · pagina 4

Alte subiecte de la aceeași facultate

Ce trebuie să știi despre acest subiect?