[canonical]: https://grile.online/informatica/subiecte/model-admitere-automatica-si-calculatoare-iasi-066 > Pagina completă: https://grile.online/informatica/subiecte/model-admitere-automatica-si-calculatoare-iasi-066 > 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 Automatică și Calculatoare Iași · Informatică #066 10 grile din Grafuri, Complexitate, Expresii, cu explicații. Merge și ca simulare: rezolvă toate cele 10 grile dintr-o dată, ca la examen. Original, în stilul Admitere Automatică și Calculatoare Iași ## Teaser gratuit, fără cont 1. Căutarea binară într-un vector sortat face cel mult $7$ comparații cu elementul din mijloc. Care este numărul maxim de elemente pe care îl poate avea vectorul? a) $127$ b) $128$ c) $64$ d) $255$ Răspuns corect: a) $127$ Cu $k$ comparații se pot trata cel mult $1+2+4+\dots+2^{k-1}=2^k-1$ elemente. Pentru $k=7$: $2^7-1=127$ (cu $128$ ar fi nevoie de a opta comparație). 2. Un graf neorientat are $10$ noduri și fiecare nod are gradul $3$. Câte muchii are graful? a) $30$ b) $13$ c) $10$ d) $15$ Răspuns corect: d) $15$ Suma gradelor este dublul numărului de muchii: $10\cdot3=30=2m$, deci $m=15$. 3. Un vector sortat are $n$ elemente. Căutarea secvențială are complexitatea $O(n)$. Care este complexitatea căutării binare și de ce e posibilă? a) $O(\log n)$, fiindcă ordinea elimină jumătate din interval la fiecare pas b) $O(\log n)$, fiindcă vectorul este parcurs de la ambele capete c) $O(n)$, fiindcă fiecare element tot trebuie comparat cel puțin o dată d) $O(\sqrt n)$, fiindcă vectorul este împărțit în blocuri egale Răspuns corect: a) $O(\log n)$, fiindcă ordinea elimină jumătate din interval la fiecare pas Vectorul este deja sortat, deci o comparație cu elementul din mijloc elimină jumătate din interval: după $k$ pași rămân $n/2^k$ elemente, adică $O(\log n)$ pași. 4. Ce afișează secvența alăturată? a) `32` b) `01` c) `22` d) `21` Răspuns corect: d) `21` La primul `if`, `x>0` e adevărat, deci `y++` nu se execută: $x=1+1=2$. La al doilea, `x<0` e fals, deci `y++` nu se execută nici acum. Se afișează `21`. 5. Într-o căutare binară pe un vector sortat se folosește `while(st