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

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

10 grile din Combinatorică, Algoritmi elementari, Șiruri de caractere, 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ă algoritmul $p(s, n)$, unde $s$ este un șir de $n$ litere mici $s[1], \dots, s[n]$ ($1 \le n \le 100$). Care dintre următoarele afirmații sunt adevărate?

a) Pentru `abba`, bucla While se execută de $3$ ori.
b) Pentru `ab`, $p$ returnează adevărat.
c) Pentru `abca`, $p$ returnează fals.
d) Pentru `rotor`, $p$ returnează adevărat.

Răspunsuri corecte: c), d)

Algoritmul verifică dacă șirul este palindrom, comparând caracterele simetrice de la capete spre mijloc. `abba` face $2$ pași ($i=1,2$), după care $i>j$. `ab` se oprește imediat, cu $i<j$, deci fals.

2. Despre arbori (grafuri neorientate conexe și fără cicluri), care dintre următoarele afirmații sunt adevărate?

a) Un arbore cu $10$ noduri are $9$ muchii.
b) Adăugând o muchie nouă într-un arbore, se formează exact un ciclu.
c) Un graf neorientat cu $n$ noduri și $n - 1$ muchii este întotdeauna arbore.
d) Orice arbore cu cel puțin $2$ noduri are cel puțin două noduri de grad $1$.

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

Un arbore cu $n$ noduri are $n-1$ muchii; capetele unui lanț de lungime maximă au grad $1$; o muchie nouă $[u,v]$ închide un ciclu cu unicul lanț dintre $u$ și $v$. Reciproca nu ține fără conexitate: un triunghi plus un nod izolat are $4$ noduri și $3$ muchii.

3. Trei cupluri (șase persoane) se așază la o masă rotundă cu locuri nenumerotate, astfel încât fiecare persoană să stea lângă partenerul său. Două așezări care diferă doar printr-o rotație sunt considerate identice. În câte moduri se pot așeza?

a) $48$
b) $16$
c) $8$
d) $12$

Răspunsuri corecte: b)

Fiecare cuplu formează un bloc; $3$ blocuri se așază la o masă rotundă în $(3-1)!=2$ moduri, iar în fiecare bloc cei doi parteneri pot schimba locurile: $2 \cdot 2^3 = 16$. $48=3! \cdot 2^3$ ar număra rotațiile ca așezări distincte.

4. Se consideră algoritmul $h(n)$, unde $n$ este număr natural ($1 \le n \le 10^9$). Ce returnează $h(36)$?

a) $9$
b) $6$
c) $10$
d) $8$

Răspunsuri corecte: a)

$h$ numără divizorii lui $n$ în perechi $(d, n/d)$ cu $d<\sqrt{n}$: $(1,36), (2,18), (3,12), (4,9)$ dau $8$, iar $d=6=\sqrt{36}$ se numără o singură dată: $9$ divizori.

5. Se consideră algoritmul $f(n)$, unde $n$ este număr natural ($0 \le n \le 90$), iar $m$ este un tablou global inițializat cu $0$ pe toate pozițiile. Care dintre următoarele afirmații sunt adevărate?

a) $f(10)$ returnează $55$.
b) Fără tabloul $m$ (adică recalculând mereu), numărul de apeluri ar rămâne liniar în $n$.
c) Complexitatea timp a apelului $f(n)$ este $\Theta(2^n)$.
d) Apelul $f(10)$ determină, cu totul (inclusiv apelul inițial), $19$ apeluri ale lui $f$.

Răspunsuri corecte: a), d)

$f$ calculează numerele Fibonacci cu memoizare: fiecare valoare se calculează o singură dată, apoi se citește din $m$. $f(10)$ face apelurile $f(10), f(9), \dots, f(1)$ pe ramura stângă și câte un apel de citire pe cea dreaptă: $19$ apeluri — timp $\Theta(n)$. Fără memoizare, numărul de apeluri ar crește exponențial.