Test
Toate secvențele de cod C++ din subiect folosesc variabile anterior declarate de tipul corespunzător.
1. Ştiind că în variabila întreagă x este memorat un număr natural de exact 4 cifre, stabiliţi care dintre următoarele expresii este adevărată dacă şi numai dacă x este palindrom.
A) x/100 == x%100
B) (x%10 == x/1000) && (x%100 == x/100)
C) x/100 == x%10*10 + x%100/10
D) x%100 == x/100%10 + x/1000
2. Se consideră următoarea secvenţă de cod, în care variabilele k şi n sunt de tip întreg.
k=0;
while(n>0)
{
if(n%2==0)
{k++; n=n/10; }
else k–;
n=n/10;
}
Ştiind că n memorează un număr natural de 4 cifre, care dintre următoarele valori nu poate fi valoarea memorată
de variabila k după execuţia acestei secvenţe de cod?
A)2 B) -1 C) -4 D) 0
3. Se consideră următoarea secvenţă de cod, în care variabilele i,j,x,k sunt de tip întreg.
k=0; x=1;j=1;
for(i=1;i<=105;i++)
{ k++;
if (k == j)
{x++; k=0;j++;}
}
Care este valoarea variabilei x după execuţia acestei secvenţe de cod?
A)10 B) 14 C)15 D) 105
- Se dau matricele A și B de numere întregi. A are m linii și n coloane, B are n linii și p coloane. Numărul de
înmulţiri elementare între elementele matricelor A și B realizate de algoritmul clasic de înmulţire a celor două
matrice (bazat pe definiţia produsului a două matrice) este:
A)m + n + p B) m*n + n*p C) m*n*p D) m + 2*n + p
5.În următoarea secvență de cod a este un vector ordonat crescător cu n elemente(primul element este pe pozitia 1).
i = 1 ; s = 0 ;
while (i<=n)
{
j = i + 1 ;
while (j<=n && a[i] == a[j]) j++;
s++ ;
i = j ;
}
Stabiliţi ce reprezintă valoarea memorată în variabila s şi ce tip de algoritm este din punct de vedere al complexităţii.
A) numărul de elemente distincte din a / algoritm liniar
B) numărul de elemente distincte din a / algoritm pătratic
C) numărul de valori consecutive din a / algoritm pătratic
D) numărul de valori consecutive din a / algoritm liniar
6. Utilizând metoda backtracking se generează toate permutările mulțimii {1, 2, 3, 4, 5} în ordine lexicografică.
Primele cinci soluții generate sunt 12345, 12354, 12435, 12453, 12534. Spunem că o permutarea p a mulțimii
{1, 2, 3, 4, 5} are numărul de ordine k dacă este a k-a permutare generată astfel. Permutarea 12354 are numărul
de ordine 2, iar permutarea 12534 are numărul de ordine 5. Care este numărul de ordine al permutării 51423?
a. 101 b.100 c.103 d. 105
7. Fie n>1 număr natural. Care este numărul minim de muchii ale unui graf neorientat cu 2n noduri care are exact
două componente conexe, cele 2 componente conexe fiind grafuri complete?
a.n(n-1) b. n(n-1)/2 c. 2n(n-1) d.(2n-1)(n-1)
8. Într-un graf neorientat conex, distanța dintre două noduri u și v se definește ca fiind lungimea minimă a unui lanț
de la u la v. Statusul unui nod v se definește ca fiind suma distanțelor de la v la celelalte noduri. Care este
valoarea maximă pe care o poate avea statusul unui nod într-un graf conex neorientat cu n>1 noduri?
a. n b. (n-1)^2 c. n(n-1)/2 d. n(n+1)/2
9. Fie doi vectori a și b ordonați crescător cu na respectiv nb elemente. Prin algoritmul de interclasare se obține
vectorul ordonat care conține toate elementele din a și b. Pe cazul cel mai favorabil, numărul minim de
comparații între elementele celor doi vectori este:
a. min(na,nb) b. max(na, nb) c. na + nb d. (na + nb)/2
10. Se consideră următoarea secvenţă de cod, în care variabilele i și j sunt de tip întreg şi variabila s poate memora
un şir de cel mult 20 de caractere:
strcpy(s,”calculatoare”);
i=0; j=strlen(s);
while(j>i) {j=j-i ;i++;}
i=strchr(s,s[i])-s+1;
Care este valoarea memorată în variabila i după executarea secvenţei de cod?
a.1 b.2 c.3 d.5
11. Se consideră o stivă şi o coadă iniţial vide. Se introduc pe rând în coadă primele 5 pătrate perfecte nenule, în
ordine crescătoare. Se extrag apoi din coadă două elemente și se adaugă în stivă, în ordinea în care au fost
extrase. Care este elementul din vârful stivei după executarea acestor operaţii?
a.1 b.4 c.25 d. 9
12. În următoarea secvență de cod, x este o variabilă care memorează un număr întreg, st, dr, mijl și gasit sunt
variabile de tip întreg, iar v este un vector cu 20 elemente numere întregi, primul element fiind pe poziția 1.
Vectorul v are elementele ordonate crescător. Secvența de cod caută numărul memorat în x în vectorul v,
folosind metoda căutării binare.
st=1; dr=20;gasit=0;
while((st<=dr) && (gasit==0)){
mijl=(st+dr)/2;
printf(“%d “, v[mijl]); | cout<<v[mijl]<<” „;
if(v[mijl]==x) gasit=mijl;
else
if(v[mijl]>x) dr=mijl-1;
else st=mijl+1;
}
Care dintre următoarele variante nu poate fi rezultatul afişat de această secvenţă de cod?
a.10 20 30 b.10 15 20 16 18 c.10 25 17 d.11 25 10
13. Fie v un vector de n elemente întregi, pe poziții numerotate de la 1 la n și secvența de cod de mai jos care
realizează ordonarea crescătoare a elementelor acestuia.
for (i = 1; i<n;i++)
for (j = i+1; j<=n; j++)
if (v[i] > v[j]) {
aux = v[i]; v[i] = v[j]; v[j] = aux;
}
Numărul de comparații între elementele lui v realizat de algoritmul de mai sus pe cazul cel mai favorabil este:
a.n b.0 c. n-1 d.n(n-1)/2
14. Care este numărul maxim de frunze ale unui arbore binar (fiecare nod are cel mult 2 fii) cu 67 de noduri?
a.8 b.36 c.34 d. 66
15. Se consideră următoarea funcţie:
int calc(int n,int d)
{
if(n<=2) return d;
if(n%d==0) return calc(n/d,d);
else return calc(n,d+1);
}
Ce returnează apelul calc(n,2), unde n este un număr natural cu n > 1 ?
a.cel mai mare divizor al lui n
b.cel mai mare divizor prim al lui n
c. puterea la care apare 2 în descompunerea în factori primi a lui n
d. n – 1
1 C 2D 3C 4C 5A
6 A 7A 8C 9A 10 C
11 B 12D 13D 14C 15B
ScoalaMultimedia 