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

> Pagina completă: https://grile.online/informatica/subiecte/model-admitere-ubb-cluj-mate-info-091
> 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ă #091

10 grile din Tablouri, Grafuri, Expresii, 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. Se consideră secvența de mai jos, care prelucrează șirul $v[1], \dots, v[n]$ ($1 \le n \le 1000$). Care dintre următoarele afirmații sunt adevărate?

a) Pentru $n = 7$, se efectuează $4$ interschimbări, câte una pentru fiecare $i \le 4$.
b) Cu limita $n$ în loc de $n \operatorname{DIV} 2$, șirul ar rămâne neschimbat.
c) Pentru $v = (1, 2, 3, 4, 5)$, după execuție $v = (5, 4, 3, 2, 1)$.
d) Pentru $n$ impar, elementul din mijloc ajunge pe prima poziție.

Răspunsuri corecte: b), c)

Se interschimbă $v[i]$ cu simetricul său $v[n-i+1]$ pentru $i=1,\dots,n \operatorname{DIV} 2$, deci șirul se inversează ($3$ interschimbări pentru $n=7$), iar elementul din mijloc rămâne pe loc. Mergând până la $n$, fiecare pereche ar fi interschimbată de două ori, deci șirul ar reveni la forma inițială.

2. Se generează prin backtracking toate numerele de $3$ cifre formate doar cu cifre din mulțimea $\{1, 2, 3, 4\}$, în care fiecare cifră este mai mare sau egală cu cifra din stânga ei (de exemplu $113$ sau $244$). Câte numere se generează?

a) $64$
b) $4$
c) $20$
d) $24$

Răspunsuri corecte: c)

Un astfel de număr este determinat de alegerea a $3$ cifre din $4$, cu repetiție, ordinea fiind impusă: combinări cu repetiție, $\binom{4+3-1}{3}=\binom{6}{3}=20$. $64=4^3$ ar număra toate numerele cu aceste cifre, $24=A_4^3$ pe cele cu cifre distincte în orice ordine, iar $4=\binom{4}{3}$ doar pe cele strict crescătoare.

3. Un copil urcă o scară cu $n$ trepte, făcând la fiecare pas $1$ sau $2$ trepte. Fie $d[n]$ numărul de moduri distincte de a urca scara (ordinea pașilor contează). Care dintre următoarele afirmații sunt adevărate?

a) Dacă se permit și pași de $3$ trepte, numărul de moduri pentru $n = 4$ este $8$.
b) $d[n] = d[n-1] + d[n-2]$ pentru $n \ge 2$, cu $d[0] = d[1] = 1$.
c) $d[5] = 10$.
d) $d[10] = 89$.

Răspunsuri corecte: b), d)

Ultimul pas are $1$ sau $2$ trepte, de unde recurența de tip Fibonacci: $d = 1, 1, 2, 3, 5, 8, \dots$, deci $d[5]=8$ și $d[10]=89$. Cu pași de $1$, $2$ sau $3$: $d=1,1,2,4,7$, deci $7$ moduri pentru $n=4$.

4. Se consideră graful neorientat cu $6$ noduri și muchiile $[1,2]$, $[1,3]$, $[2,3]$, $[3,4]$, $[4,5]$, $[5,6]$, $[4,6]$. Care este numărul minim de muchii care trebuie eliminate pentru ca graful rămas să fie arbore?

a) $3$
b) $2$
c) $1$
d) $7$

Răspunsuri corecte: b)

Graful este conex, are $6$ noduri și $7$ muchii; un arbore cu $6$ noduri are $5$ muchii, deci trebuie eliminate $7-5=2$ muchii — câte una din fiecare ciclu, $1\text{-}2\text{-}3$ și $4\text{-}5\text{-}6$.

5. Fie $\oplus$ operatorul SAU-exclusiv pe biți, iar $x$, $y$ numere naturale. Care dintre următoarele afirmații sunt adevărate?

a) $x \leftarrow x \oplus y$; $y \leftarrow y \oplus x$; $x \leftarrow x \oplus y$ interschimbă $x$ și $y$.
b) $x \oplus y = x + y$ pentru orice $x$ și $y$, chiar dacă au biți de $1$ pe aceleași poziții.
c) $x \oplus x = 0$ pentru orice $x$.
d) $(x \oplus y) \oplus y = x$ pentru orice $x$ și $y$.

Răspunsuri corecte: a), c), d)

SAU-exclusiv este asociativ, comutativ și $y \oplus y=0$, de unde $(x \oplus y) \oplus y = x$ și corectitudinea interschimbării. $x \oplus y$ este adunarea fără transport: $3 \oplus 1 = 2 \ne 4$.