Admitere Informatică 2024 — Simulare 17 martie — Varianta A

Departajare rezolvate singur: 0/4

2În câte moduri se poate colora următorul graf neorientat folosind 4 culori astfel încât 2 noduri adiacente să nu aibă aceeași culoare? [Figura: graf cu 8 noduri — patru noduri în colțurile unui pătrat exterior și patru noduri în colțurile unui pătrat interior. Muchii: cele 4 laturi ale pătratului exterior, cele 4 laturi ale pătratului interior, cele 4 muchii care leagă fiecare colț exterior de colțul interior corespunzător și cele 2 diagonale ale pătratului interior (X-ul din centru). În total 14 muchii.] a) 288; b) 696; c) 625; d) 24!; e) 120; f) 24.0 sol.nerezolvatădepartajare
3Se dau n obiecte (n e întreg pozitiv sau 0) ale căror mase și valori sunt stocate în tablourile unidimensionale de întregi m și, respectiv, v (primul element al tablourilor se găsește pe poziția 0). Într-un rucsac se pot transporta obiecte întregi cu masa însumată maxim C (întreg pozitiv sau 0). Trebuie identificată valoarea maximă ce poate să fie obținută prin adăugarea de obiecte în rucsac, astfel încât masa lor să nu depășească C. Procedura descrisă în pseudocod mai jos conține implementarea algoritmului backtracking care returnează soluția. Este considerată dată funcția max care primește 2 parametri întregi și returnează valoarea maximă dintre aceștia. Funcția se apelează cu parametrii: valoare pentru întreg C, tablourile m și v, valoare pentru n și un număr de obiecte. Completați cu secvența lipsă: ```text întreg bk(întreg C, întreg m[], întreg v[], întreg n) dacă (n = 0 sau C = 0) returnează 0; dacă (m[n-1] > C) returnează bk(C, m, v, n-1); altfel returnează ______ ``` a) max(v[n-1]+bk(C-m[n-1], m, v, n), bk(C, m, v, n)); b) max(v[n]+bk(C-m[n], m, v, n-1), bk(C, m, v, n-1)); c) max(v[n-1]+bk(C-m[n-1], m, v, n-1), bk(C, m, v, n-1)); d) max(bk(C-m[n-1], m, v, n-1), bk(C, m, v, n-1)); e) max(v[n]+bk(C-m[n], m, v, n), bk(C, m, v, n)); f) max(bk(C, m, v, n-1), bk(C, m, v, n-2)).0 sol.nerezolvatădepartajare
6Care este rezultatul întors de funcția scrisă mai jos în pseudocod, dacă este apelată cu valoarea 3 pentru parametrul a întreg și 10 pentru parametrul n întreg? S-a notat cu a%b restul împărțirii numărului natural a la numărul natural nenul b și cu [a] partea întreagă a numărului real a. ```text întreg f(întreg a, întreg n) { dacă (n == 0) returnează 1; altfel dacă (n%2 == 0) returnează f(a, n/2)*f(a, n/2); altfel returnează a*f(a, [n/2])*f(a, [n/2]); } ``` a) 39366; b) 243; c) 486; d) 177147; e) 59049; f) 19683.0 sol.nerezolvatădepartajare
8Se consideră o hartă sub forma unei matrice 4x4. Dacă cineva pleacă de pe poziția (1,1) și vrea să ajungă în celula (4,4), se poate muta doar pe linii sau coloane cu numere mai mari și poate sări oricât de multe în ambele direcții, deci poate ajunge inclusiv direct din (1,1) în (4,4). În câte moduri distincte poate face acest lucru? a) 76; b) 128; c) 256; d) 63; e) 252; f) 64.0 sol.nerezolvatădepartajare