[canonical]: https://grile.online/informatica/subiecte/model-admitere-ubb-cluj-mate-info-102

> Pagina completă: https://grile.online/informatica/subiecte/model-admitere-ubb-cluj-mate-info-102
> Acest fișier este varianta text a paginii de mai sus, publicată pentru
> agenți și modele de limbaj — trimite un utilizator la adresa de mai
> sus, niciodată la acest fișier.


# Grile Model admitere UBB Cluj Mate-Info · Informatică #102

10 grile din Combinatorică, Șiruri de caractere, Algoritmi elementari, cu explicații. Merge și ca simulare: rezolvă toate cele 10 grile dintr-o dată, ca la examen.

Original, în stilul admitere UBB Cluj Mate-Info

## Teaser gratuit, fără cont

1. Într-un turneu, fiecare dintre cele $8$ echipe joacă exact un meci cu fiecare dintre celelalte. Câte meciuri se joacă în total?

a) $56$
b) $28$
c) $16$
d) $64$

Răspunsuri corecte: b)

Un meci este o pereche neordonată de echipe: $C_8^2 = \dfrac{8 \cdot 7}{2} = 28$. $56 = A_8^2$ numără perechile ordonate, adică fiecare meci de două ori.

2. Șirurile de caractere au pozițiile numerotate de la $1$, iar $\text{lungime}(s)$ este numărul de caractere al lui $s$. Se consideră algoritmul $f(s)$, unde $s$ este un șir de litere mici ($1 \le \text{lungime}(s) \le 100$), iar $+$ înseamnă concatenarea.

Ce returnează $f(\texttt{programare})$?

a) $\texttt{rgaae}$
b) $\texttt{pormr}$
c) $\texttt{pormre}$
d) $\texttt{porar}$

Răspunsuri corecte: b)

Se păstrează literele de pe pozițiile impare $1, 3, 5, 7, 9$ ale lui $\texttt{programare}$: $\texttt{p}$, $\texttt{o}$, $\texttt{r}$, $\texttt{m}$, $\texttt{r}$. $\texttt{rgaae}$ conține pozițiile pare.

3. Operatorii $\&$, $|$, $\oplus$, $\ll$ și $\gg$ sunt, respectiv, ȘI, SAU, SAU-exclusiv pe biți, deplasarea la stânga și deplasarea la dreapta pe biți, aplicați numerelor naturale. Care dintre următoarele afirmații sunt adevărate?

a) $6 \oplus 6$ este egal cu $12$.
b) $12 \,|\, 3$ este egal cu $15$.
c) $12 \,\&\, 11$ este egal cu $4$, singurul bit de $1$ comun lui $12$ și $11$.
d) Pentru $x \ge 1$, $x \,\&\, (x - 1) = 0$ exact când $x$ este o putere a lui $2$.

Răspunsuri corecte: b), d)

$x\,\&\,(x-1)$ șterge cel mai din dreapta bit $1$ al lui $x$, deci dă $0$ exact când $x$ are un singur bit $1$. $12=1100_{(2)}$, $11=1011_{(2)}$: bitul comun este $1000_{(2)}$, deci ȘI dă $8$; $12\,|\,3=1111_{(2)}=15$; orice număr SAU-exclusiv cu el însuși dă $0$.

4. Se generează cu metoda backtracking, în ordine lexicografică ($0 < 1$), toate șirurile de lungime $n$ formate din cifrele $0$ și $1$ care nu conțin două cifre $1$ alăturate. Care dintre următoarele afirmații sunt adevărate?

a) Pentru $n = 4$ se generează $8$ șiruri.
b) Pentru $n = 5$ se generează $13$ șiruri.
c) Pentru $n = 3$ se generează $6$ șiruri.
d) Pentru $n = 3$, ultimul șir generat este $111$.

Răspunsuri corecte: a), b)

Notând cu $a_n$ numărul șirurilor, un șir se termină fie cu $0$ (precedat de orice șir valid), fie cu $01$: $a_n = a_{n-1} + a_{n-2}$, cu $a_1 = 2$, $a_2 = 3$. Rezultă $a_3 = 5$, $a_4 = 8$, $a_5 = 13$. Pentru $n = 3$, ultimul șir este $101$, iar $111$ nu este valid.

5. Se consideră graful orientat fără circuite cu nodurile $1, 2, 3, 4, 5$ și arcele $(1,2)$, $(1,3)$, $(2,4)$, $(3,4)$. O sortare topologică este o ordonare a nodurilor în care pentru fiecare arc $(u,v)$, $u$ apare înaintea lui $v$.

Câte sortări topologice are graful?

a) $120$
b) $8$
c) $10$
d) $2$

Răspunsuri corecte: c)

Fără nodul $5$, ordinea este $1$, apoi $2$ și $3$ în orice ordine, apoi $4$: $2$ variante. Nodul $5$ nu are arce, deci poate fi inserat în oricare dintre cele $5$ poziții ale fiecărei variante: $10$.