An1

Name: ________________________ Class: ___________________ Date: __________

wshgtr Multiple Choice Identify the letter of the choice that best completes the statement or answers the question. A ____

B ____

A ____

D ____

1. Se consideră declaraŃiile:

var f:file of char; c:char; Ce conŃine fişierul f după execuŃia secvenŃei următoare: rewrite(f); for c: =’z’ downto ‘a’ do write(f,c); a. zyxwvutsrqponmlkjihgfedcba; b. za; c. nimic d. abcdefghijklmnopqrstuvwxyz. 2. FuncŃia de mai jos determină termenul Fibonacci de rang n. E corectă? function fib(n:integer):integer; begin fib=fib(n-1)+fib(n-2) end; a. da, pentru că respectă formula de calcul a şirului lui Fibonacci; b. nu, pentru ca se autoapelează la nesfârşit. 3. FuncŃia de mai jos implementează recursiv calculul sumei S(n)=1+2+...+n. E corectă? int S(int n){ if(n<=0) return 0; else return (S(n+1)-(n+1)); } a. nu, pentru că, deşi are condiŃie de ieşire din autoapelare, nu se ajunge la ea; b. da, pentru că respectă matematic relaŃia şi are condiŃie de oprire din autoapelare. 4. Dacă există declaraŃia FILE f; şi se apelează funcŃia fopen() astfel: f=fopen(“fisier.txt”,”w”); care afirmaŃie e adevărată? a. fişierul fisier.txt a fost deschis pentru scriere; conŃinutul său se păstrează; b. fişierul fisier.txt a fost deschis pentru scriere, dar numai dacă exista pe disc; c. fisierul fisier.txt a fost deschis pentru scriere/citire; d. fisierul fisier.txt a fost deschis pentru scriere; dacă exista, conŃinutul lui se pierde, iar dacă nu exista, fisierul va fi creat în momentul executării instrucŃiunii de mai sus.

1

ID: A

Name: ________________________ C ____

ID: A

5. Se consideră problema căutării unui element într-un vector ordonat cu n elemente (căutare binară).

Care este complexitatea algoritmului (câŃi paşi se execută) în cazul cel mai defavorabil, adică atunci când elementul nu este în vector? a) b) c) O(n), pentru că verificăm fiecare element; O(1), căutarea efectuându-se in timp constant; O(log2n), la fiecare pas înjumătăŃindu-se intervalul de căutare. 6. În fişierul numere.txt, aflat pe disc, sunt scrise, pe linie, numerele: 1 2 3 4 5 6 Ce se afişează în urma execuŃiei programului următor: #include<stdio.h> #include<stdlib.h> a. b. c.

C ____

FILE f; int n,i;

B ____

void main(){ f=fopen(”numere.txt”,”r”); for(i=1;i<4;i++) {fscanf(”%d”,&n);printf(”%d”,n);} rewind(f); for(i=1;i<4;i++) {fscanf(”%d”,&n);printf(”%d”,n);} FCLOSE f } a. 123456 b. 123 c. 123123 d. 123456123 7. Streamurile standard (adică streamurile care sunt deschise automat când un program C îşi începe execuŃia) sunt: a. stdin,stdout; b. stdin,stdout,stderr; c. nu există strem-uri standard.

2

Name: ________________________ ____ A

ID: A

8. Se consideră următorul arbore binar, reprezentat mai jos:

4 1

6

3

B ____

9

7

2

10

11

8

5

Este arborele binar complet? a. da b. nu 9. Se consideră următorul arbore binar, reprezentat mai jos:

4 1

6

3

9

7

10

2

11

Care este înălŃimea arborelui binar? a. 1 b. 3 c. 4 d. 5 e. 11

3

8

5

Name: ________________________

ID: A

A ____ 10. Se consideră următorul arbore binar, reprezentat mai jos:

4 1

6

3

9

7

2

10

11

8

5

Este arborele binar strict? a. da b. nu C ____ 11. Se consideră următorul arbore binar, reprezentat mai jos:

4 1

6

3

9

7

10

2

11

Parcurgerea in inordine este: a. 4,1,9,6,7,2,8,3,10,11,5 b. 3,6,1,4,9,8,10,7,2,5,11 c. 3,6,10,1,7,4,11,2,5,9,8

4

8

5

Name: ________________________

ID: A

C ____ 12. Se consideră următorul arbore binar, reprezentat mai jos:

4 1

6

3

9

7

2

10

11

8

5

Parcurgerea in preordine este: a. 4,1,9,6,7,2,8,3,10,11,5 b. 4,3,6,1,9,8,10,7,2,5,11 c. 4,1,6,3,10,7,9,2,11,5,8 B ____ 13. Se consideră următorul arbore binar, reprezentat mai jos:

4 1

6

3

9

7

10

2

11

8

5

Parcurgerea in postordine este: a. 4,1,9,6,7,2,8,3,10,11,5 b. 3,10,6,7,1,11,5,2,8,9,4 c. 3,6,8,10,7,4,1,11,2,5,9 B ____ 14. Un arbore binar cu n vârfuri este plin. PrecizaŃi ce valoare poate avea n, dintre cele de mai jos: a. 5 b. 7 c. 8 d. 9

5

Name: ________________________

ID: A

B ____ 15. Pentru implementarea unei stive, se folosesc funcŃiile:

init(): iniŃializarea stivei (vârful stivei devine -1) empty(): returnează 1 daca stiva e goală şi 0 în caz contrar push(val): adauga item-ul val în stivă pop(): returnează (ştergându-l din stivă) elementul din vârful stivei top(): returnează elementul din vârful stivei, fără a-l şterge însă Ce apare la ieşire, dacă asupra stivei se execută prelucrările de mai jos (presupunem ca functia scrie afişează pe ecran parametrul ei, urmat de un spatiu): init(); push(100); push(54); scrie(top()); pop(); scrie(top()); push(60); push(630); scrie(top()); pop(); scrie(top()); pop(); scrie(top()); a. 54 100 60 630 60 b. 54 100 630 60 100 c. 54 60 100 630 100 C ____ 16. Care este timpul în cazul cel mai defavorabil pentru algoritmul lui Kruskal, aplicat unui graf complet cu n vârfuri? a. O(n2) b. O(nlog2n) c. O(n2log2n)

6

Name: ________________________

ID: A

B ____ 17. Fie graful de mai jos:

3

2

1

1 4

3

3 1

2

5

4

3

Din câte muchii e format arborele parŃial de cost minim? a. 3 b. 4 c. 5 d. 7 B ____ 18. Fie graful de mai jos:

3

2

1

1 3

4 1

3 2

5

3

4

PrecizaŃi ordinea muchiilor care se adaugă pentru determinarea arborelui parŃial de cost minim, folosind algoritmul lui Kruskal: a. (2,3),(3,5),(3,4),(1,2),(1,4),(4,5),(2,5) b. (2,3),(3,5),(3,4),(1,2) c. (2,3),(3,5),(2,5),(3,4)

7

Name: ________________________

ID: A

C ____ 19. Fie graful de mai jos:

3

2

1

1 4

3

3 1

2

5

4

3

Care este distanŃa minimă de la 1 la 5, conform algoritmului lui Dijkstra? a. b. c. d.

3 4 5 6

____ C 20. Se consideră arborele de căutare de mai jos:

12

5

2

18

9

15

19

17 Valoarea 13 va fi inserată în arbore: a. ca fiu drept al lui 2 b. ca fiu drept al lui 9 c. ca fiu stâng al lui 15 d. ca fiu stâng al lui 19 e. ca fiu stâng al lui 17

8

Name: ________________________

ID: A

D ____ 21. Se consideră arborele de căutare de mai jos:

12

5

2

18

9

15

19

17 Dacă ştergem rădăcina (12), ce nod va ajunge în locul ei ? a. b. c. d. e.

5 18 9 15 17

A ____ 22. Metoda de sortare rapidă (Quicksort) găseşte pivotul (printr-un algoritm de partiŃie) şi se

autoapelează pentru cele două porŃiuni din vectorul iniŃial. Algoritmul de partiŃie de mai jos e corect? Presupunem că a este un tablou de întregi, i şi j sunt indicele de start, respectiv de sfârşit ale elementelor pe care le sortează. De asemenea, funcŃia swap(x,y) interschimbă x şi y. FuncŃia întoarce poziŃia (finală) a lui a[i]. int partitie(a,i,j){int val,h,k; val=a[i]; h=i; for(k=i+1;i<=j;i++) if(a[k]<=val){ h=h+1; swap(a[h],a[k]); } swap(a[i],a[h]); return h; } a. b.

da nu

9

Name: ________________________

ID: A

A ____ 23. Se consideră implementarea unei liste simplu înlănŃuite sub forma: typedef struct nod{ int info; struct nod *adr; }lista; lista *c /*capul listei*/ ,*p,*q;

Pentru inserarea unui elementului 3 în capul unei liste înlănŃuite (dat de c), se fac următorii paşi: a. p=(lista*)malloc(sizeof(lista)); p->info=3;p->adr=c;c=p; b. p=(lista*)malloc(sizeof(lista)); p->info=3; c=p;p->adr=c; B ____ 24. Se consideră implementarea unei liste simplu înlănŃuite sub forma: typedef struct nod{ int info; struct nod *adr; }lista; lista *c /*capul listei*/ ,*p,*q;

Dacă vrem să ştergem capul listei, se fac paşii: a. free(c); b. p=c;c=c->adr;free(p); B ____ 25. Se consideră implementarea unei liste simplu înlănŃuite sub forma: typedef struct nod{ int info; struct nod *adr; }lista; lista *c /*capul listei*/ ,*p,*q;

Presupunând că vrem să ştergem elementul imediat următor celui pe care punctează p, se fac paşii: a. q=p->adr;free(q);p->adr=q->adr; b. q=p->adr;p->adr=q->adr;free(q); B ____ 26. Se consideră implementarea unei liste simplu înlănŃuite sub forma: typedef struct nod{ int info; struct nod *adr; }lista; lista *c /*capul listei*/ ,*p,*q;

Presupunând că vrem să inserăm un element după cel punctat de p, se fac paşii: a. q=(lista*)malloc(sizeof(lista));p->adr=q;q->adr=p->adr; b. q=(lista*)malloc(sizeof(lista));q->adr=p->adr; p->adr=q; 10

Name: ________________________

ID: A

B ____ 27. Se consideră implementarea unei liste simplu înlănŃuite sub forma: typedef struct nod{ int info; struct nod *adr; }lista; lista *c /*capul listei*/ ,*p,*q;

Ce efect are următoarea funcŃie, dacă se apelează scriu(c)? void scriu(lista* p) { if(p) {scriu(p->adr);printf(“%d “,p->info);} } a. afişează lista de la primul la ultimul element b. afişează lista de la ultimul element la primul A ____ 28. Coada de priorităŃi este: a. o structură de date care conŃine o mulŃime S de elemente, fiecare având asociată o valoare numită cheie; inserarea adaugă un element, iar extragerea unui element returnează elementul cu prioritatea maximă b. o structură de date care conŃine o mulŃime S de elemente, în care intrările se fac la un capăt al ei, iar ieşirile la celălalt capăt c. o structură de date care conŃine o mulŃime S de elemente,în care intrările şi ieşirile se fac la un singur capăt.

11