Model-Informatica-Admitere-2019-RO.pdf

Please download to get full document.

View again

All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
 0
 
  Description:
Share
Transcript
  1 UNIVERSITATEA BABEŞ -BOLYAI FACULTATEA DE MATEMATICĂ ŞI INFORMATICĂ   Admitere Mate-Info - model Proba scrisă la Informatică   În atenția concurenților:   1.   Se consideră că indexarea șirurilor începe de la 1.   2.   Problemele tip grilă (Partea A) pot avea unul sau mai multe răspunsuri corecte. Răspunsurile trebuie scrise de candidat  pe foaia de concurs (nu pe foaia cu enunțuri). Obținerea punctajului aferent problemei este condiționată de identificarea tuturor varian telor de răspuns corecte și numai a acestora. 3.   Pentru problemele din Partea B se cer rezolvări complete pe foaia de concurs.   a.   Rezolvările se vor scrie în  pseudocod   sau într-un limbaj de programare  (  Pascal/C/C++). b.   Primul criteriu în evaluarea rezolvărilor va fi corectitudinea  algoritmului, iar apoi  performanța   din punct de vedere al timpului de executare   ș i al  spațiului de memorie utilizat  . c.    Este obligatorie descrierea și justificarea   (sub) algoritmilor înaintea rezolvărilor. Se vor scrie, de asemenea, comentarii   pentru a u ș ura în țelegerea detaliilor tehnice ale soluției date, a semnificaț iei identificatorilor, a structurilor de date folosite etc. Neîndeplinirea acestor cerințe duce la pierderea a 10% din punctajul aferent subiectului. d.    Nu se vor folosi funcții sau biblioteci predefinite (de exemplu: STL , func ț ii predefinite pe ș iruri de caractere). Partea A (60 puncte) A.1.   Oare ce face? (6 puncte) Subalgoritmul generare(n)    prelucrează un număr natural n  (0 < n  < 100). Subalgoritm  generare(n): nr   0 Pentru  i   1, 1801 execută  folosit i       fals   SfPentru CâtTimp nu  folosit n   execută   suma ←  0, folosit n      adevărat   CâtTimp  (n ≠  0) execută   cifra ←  n  MOD  10, n ←  n DIV  10 suma ←  suma + cifra * cifra * cifra SfCâtTimp n ←  suma, nr ←  nr + 1 SfCâtTimp returnează  nr SfSubalgoritm Precizați  care este efectul acestui subalgoritm. A.   calculează, în mod repetat, suma cuburilor cifrelor numărului n    până când suma egalează numărul n   ș i returnează numărul repetărilor   efectuate B.   calculează suma cuburilor cifrelor numărului n   și returnează această sumă  C.   calculează suma cuburilor cifrelor număr  ului n , înlocuiește numărul n  cu suma obținută   și returnează această sumă  D.   calculează numărul înlocuirilor lui n  cu suma cuburilor cifrelor sale  până când se obține o valoare calculată anterior sau numărul însuși și returnează acest număr    A.2.   Ce valori sunt necesare? (6 puncte) Se consideră subalgoritmul prelucreaza(v, k), unde v    este un șir cu k    numere naturale (1 ≤ k    ≤ 1 000).   Subalgoritm  prelucreaza(v, k) i ←  1, n ←  0 CâtTimp   i ≤ k și v i   ≠  0 execută  y ←  v i, c ←  0   CâtTimp  y > 0 execută   Dacă  y MOD  10 > c atunci  c   y MOD  10 SfDacă   y ← y DIV  10 SfCâtTimp n ←  n * 10 + c i ← i + 1   SfCâtTimp returnează  n SfSubalgoritm Precizați pentru care valori ale lui v    ș i k   subalgoritmul returneaz ă  valoarea 928. A.   v    = (194, 121, 782, 0) și k   = 4  2 B.   v    = (928) și k   = 1 C.   v    = (9, 2, 8, 0) și k   = 4 D.   v    = (8, 2, 9) și k   = 3 A.3.   Evaluare logică ( 6 puncte) Fie  s   un șir cu k   elemente de tip b oolean și subalgoritmul evaluare(s, k, i) , unde k    ș i i   sunt numere naturale (0 ≤ i    ≤ k    ≤ 100) . Subalgoritm  evaluare(s, k, i) Dacă   i ≤ k atunci   Dacă  s i   atunci   returnează  s i   altfel returnează  (s i   sau  evaluare(s, k, i + 1)) SfDacă  altfel r eturnează    fals   SfDacă  SfSubalgoritm   Precizați   de câte ori se autoapelează subalgoritmul evaluare(s, k, i)   în urma execu ț iei următoare i secvenț e de instrucțiuni: s ← (  fals ,  fals ,  fals ,  fals ,  fals ,  fals , adev ărat ,  fals ,  fals ,  fals ) k ← 10, i ← 3 evaluare(s, k, i)   A.   de 3 ori B.   de același număr de ori ca în   următoarea   secvență de instrucțiuni   s ← (  fals ,  fals ,  fals ,  fals ,  fals ,  fals ,  fals , a dev ărat ) k ← 8, i ← 4 evaluare(s, k, i)  C.   de 6 ori D.   niciodată   A.4.   Reuniune (6 puncte) Se consideră dat subalgoritmul aparține(x, a, n)   care verifică dacă un număr natural  x    aparține mulțimii a  cu n  elemente; a   este un șir cu n   elemente și reprezintă o mulțime de numere naturale (1 ≤ n   ≤ 200, 1 ≤  x    ≤ 1000). Fie subalgoritmii reuniune(a, n, b, m, c, p ) și calcul(a, n, b, m, c, p ), descri și  mai jos, unde a , b   și  c    sunt șiruri care reprezintă mulțimi de numere naturale cu n , m   și respectiv  p  elemente ( 1 ≤ n   ≤ 200, 1 ≤ m   ≤ 200, 1 ≤  p   ≤ 4 00). Parametrii de intrare sunt a , n , b , m   și  p , iar parametrii de ieșire sunt c    și  p . 1.   Subalgoritm  reuniune(a, n, b, m, c, p): 2.   Dacă  n = 0 atunci  3.   Pentru i   ←  1, m execută  4.   p ←  p + 1, c p   ←  b i  5.   SfPentru  6.   altfel  7.   Dacă nu   aparține(a n , b, m) atunci 8.   p ←  p + 1, c p   ←  a n  9.   SfDacă   10.   reuniune(a, n - 1, b, m, c, p) 11.   SfDacă  12.   SfSubalgoritm  1.   Subalgoritm calcul(a, n, b, m, c, p):   2.   p ←  0 3.   reuniune(a, n, b, m, c, p)   4.   SfSubalgoritm Precizați care dintre afirmațiile de mai jos sunt întotdeauna adevărate:  A.   când mulțimea   a   conține un singur element , apelul subalgoritmului calcul(a, n, b, m, c, p)  provoacă apariția unui ciclu infinit B.   când mulțimea   a   conține 4 elemente, apelul subalgoritmului calcul(a, n, b, m, c, p)  provoacă executarea instrucțiunii de pe linia 10 a subalgoritmului reuniune de 4 ori C.   când mulțimea   a   conține 5 elemente, apelul subalgoritmului calcul(a, n, b, m, c, p)  provoacă executarea instrucțiunii de pe linia 2 a subalgoritmului reuniune de 5 ori D.   când mulțimea a   are aceleași elemente ca și mulțimea b , în urma execuției subalgoritmului calcul(a, n, b, m, c, p) mulțimea c    va avea același număr de elemente ca și mulțim ea a   A.5.   Exponențiere ( 6 puncte) Care dintre următorii algoritmi calculează corect  valoarea a b , a   ș i b  fiind două numere naturale ( 1 ≤ a   ≤ 11, 0 ≤ b   ≤ 11) . A.   Subalgoritm  expo(a, b): rezultat ←  1 B.   Subalgoritm expo(a, b):   Dacă b ≠ 0  atunci  3 CâtTimp  b > 0 execut ă   Dacă  b MOD  2 = 1 atunci  rezultat ←  rezultat * a SfDacă   b ←  b DIV  2 a ←  a * a SfCâtTimp returnează  rezultat SfSubalgoritm Dacă b MOD  2 = 1  atunci returnează expo(a * a, b / 2) * a  altfel returnează   expo(a * a, b / 2)   SfDacă  altfel returnează   1   SfDacă  SfSubalgoritm C.   Subalgoritm  expo(a, b): rezultat ←  1 CâtTimp  b > 0 execută  rezultat ←  rezultat * a b ←  b - 1 SfCâtTimp returnează  rezultat SfSubalgoritm D.   Subalgoritm  expo(a, b): Dacă  b = 0 atunci   returnează  1 SfDacă   returnează  a * expo(a, b - 1) SfSubalgoritm A.6.   Cel mai mare multiplu (6 puncte) Care dintre subalgoritmii de mai jos returnează cel mai mare multiplu al numărului natural a , multiplu care este mai mic sau egal cu numărul natural b   (0 < a  < 10 000, 0 < b  < 10 000, a  < b )? A.   Subalgoritm  f(a, b): c   b CâtTimp  c MOD  a = 0 execută  c   c –  1 SfCâtTimp   returnează  c SfSubalgoritm   B.   Subalgoritm  f(a, b): Dacă  a < b atunci   returnează  f(2 * a, b) altfel Dacă  a = b atunci   returnează  a altfel returnează  b SfDacă   SfDacă   SfSubalgoritm C.   Subalgoritm  f(a, b): returnează  (b DIV  a) * a SfSubalgoritm D.   Subalgoritm  f(a, b): Dacă  b MOD  a = 0 atunci   returnează  b SfDacă   returnează  f(a, b - 1) SfSubalgoritm A.7.   Tip de date (6 puncte) Un tip de date întreg reprezentat pe  x     biți (  x    este număr natural str  ict pozitiv) va putea reține valori întregi din:  A.   [0, 2 x ] B.   [0, 2 x-1 -1] C.   [-2 x-1 ,2 x-1 -1] D.   [-2 x ,2 x -1] A.8.   Număr apeluri  (6 puncte) Se d ă subalgoritm ul f(a, b) : Subalgoritm  f(a, b): Dacă  a > 1 atunci   returnează  b * f(a - 1, b) altfel returnează  b * f(a + 1, b) SfDacă  SfSubalgoritm   Precizați de c âte ori se auto apelează subalgoritmul f(a, b)  în urma execuției   următoarei secvențe de instrucțiuni : a   4 b   3 c   f(a, b)   A.   de 4 ori B.   de 3 ori C.   de o infinitate de ori D.   niciodată   A.9.   Ș iruri (6 puncte)  4 Se consideră toate șirurile de lungime l   ϵ   {1, 2, 3} formate din litere din mulțimea { a , b , c , d  , e }. Câte dintre aceste șiruri au elementele ordonate strict descrescător și un număr impar de vocale? ( a   ș i e  sunt vocale) A.   14 B.   7 C.   81 D.   78 A.10.   Numere pozitive (6 puncte) Se dă subalgoritmul numerePozitive(m, a, n, b) . void numerePozitive(int m,int a[], int &n, int b[]){ n = 0; for(int i = 1; i <= n; i++){ if (a[i] > 0){ n = n + 1; b[n] = a[i]; } } } procedure numerePozitive(m:integer; a:sir; var n:integer; var b:sir) begin n := 0; for i := 1 to n do if (a[i] > 0) then begin n := n + 1; b[n] := a[i]; end; end; Care este rezultatul execuției apelului   numerePozitive(k, x, p, y)  pentru k = 4 , șirul  x  =(-1, 2, -3, 4),  p  = -1 și șirul vid  y   = (). A.    p   = 3 și  y   = (2, 4); B.    p   = 0 și  y   = (2, 4); C.    p   = 0 și  y   = (); D.   Depinde de valoarea lui k  . Partea B (30 puncte) B.1.   Numere magice (15 puncte) Se consideră două numere naturale  p   și q  (2 ≤  p ≤ 10  ,   2 ≤   q   ≤ 10). Un număr natural se numește magic dacă   mulțimea cifrelor utilizate în scrierea lui în sistemul de numeraţie având baza  p   este identică cu mulțimea cifrelor folosite în scrierea lui în sistemul de numeraţie având baza q . De exemplu, pentru  p   = 9 și q  = 7, (31) 10 este număr magic    pentru că  (34) 9  = (43) 7 , iar pentru  p   = 3 și q  = 9, (9) 10 este număr magic    pentru că  (100) 3  = (10) 9 . Se consideră și subalgoritmul cifr eBază (x, b, c)    pentru determinarea cifrelor numărului  x   în  baza b (memorate în șirul c  ): Subalgoritm cifr eBază (x, b, c):  CâtTimp x >  0   execută   c[x MOD  b]     1 x   x DIV  b  SfCâtTimp SfSubalgoritm Cerințe:  a.   Scrieți o variantă recursivă   (fără structuri repetitive) a subalgoritmului cifr eBază (x, b, c)   care are același antet și același efect cu acesta. ( 5 puncte )  b.   Scrieți modelul matematic al variantei recursive a subalgoritmului cifr eBază (x, b, c)   (dezvoltat la  punctul a). ( 3 puncte ) c.   Scrieți un subalgoritm care, folosind subalgoritmul   cifreBază(x, b, c) ,  pentru două baze  p   și q  date determină șirul a  al tuturor numerelor magice   strict mai mari ca 0 și strict mai mici decât un număr natural n  dat (1 < n   ≤ 10   000). Parametrii de intrare ai subalgoritmului sunt  p   și q (cele două baze) și valoarea n . Parametrii de ieșire vor fi șirul a   și lungimea k    a șirului a . ( 7 puncte ) Exemplu:   dacă  p  = 9, q  = 7 și n  = 500 , șirul a  va avea k   = 11 elemente: (1, 2, 3, 4, 5, 6, 31, 99, 198, 248, 297).
Related Search
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks
SAVE OUR EARTH

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...

Sign Now!

We are very appreciated for your Prompt Action!

x