7/23/2019 Model Examen Atpa

1/4

Modelul 1 de subiect

1. Se considera algoritmul de unire-rapida a nodurilor 0..9. Care sunt valorile tabloului dupa

urmatoarea secventa de conexiuni p-q: 4-2,-4,2-!,-!, 0-9, "-#,$-1

tab%10& ' ( 0, 1, 2, , 4, !, #, $, ", 9 )

*nitial, in tablou, valoarea +iecarui element va +i egala cu ceia acelui element ex: tab%0& ' 0 tab%1&'1 s.a.m.d.pana la tab%9&'9 /.

pentru conexiunea 4-2/:

index: 0 1 2 4 ! # $ " 9

valori -inainte: 0 1 2 4! # $ " 9 -dupa : 0 1 2 2! # $ " 9

Ce s-a intamplat lementului de pe poitia 4 i-a +ost data valoarea elementului de pe poitia 2 care este tot 2 in

acest ca/. pentru conexiunea -4/

index: 0 1 2 4 ! # $ " 9

valori -inainte: 0 1 2 2! # $ " 9

-dupa : 0 1 2 22 ! # $ " 9

lementului de pe poitia i-a +ost data valoarea elementului de pe poitia 4, adica 2.

index: 0 1 2 4 ! # $ " 9

4-2 0 1 2 2! # $ " 9

-4 0 1 2 22 ! # $ " 9

2-! 0 1 !2 2 ! # $ " 9 -! 0 1 ! !2 ! # $ " 9

0-9 91 ! ! 2 ! # $ " 9

"-# 9 1 ! ! 2 ! # $ #9

$-1 9 1 ! ! 2 ! # 1# 9

3upa realiarea conexiunilor, tabloul tab va avea valorile ( 9, 1, !, !, 2, !, #, 1, #, 9).

2. entru care dintre problemele de mai 5os nu se poate implementa o +unctie recursiva a. calculul sumei intregilor de la ! la !!

b. calculul sumei a cinci intregi

c. calculul produsului intregilor de la ! la !!

d. calculul unui sir 6ibonacci

7aspuns: b.

6unc8ia recursiv este o +unc8ie n corpul creia exist apeluri la ea ns;i. < +unctie care sa calculee suma a

cinci numere intregi primite ca argumente nu are de ce sa se apelee recursiv =t+>/. x: int +int a, int b, int c, int d, int e/ (

return a?b?c?d?e

)

a va +i apelata o singura data ex: +1, 2, , 4, !/ / si va returna un @@t de int. 3esi sunt mai multe operatii de adunare, +iindca operanii adunarii nu sunt predictibili nu o poti +ace recursiva.

x: calculul sumei intregilor de la ! la !!

int + int a, int b/ ( i+ a A b /

return a ? + a?1, b/

return a

) int suma ' +!, !!/

7/23/2019 Model Examen Atpa

2/4

*n acest ca + este o +unctie recursiva>

. 6ie +unctia recursiva cu urmatoarea lege de +ormare:

+0, B/ ' B +,/ ' +-1,?1/

Con+orm de+initiei, +2, 4/ va +i: #

7eolvare: Con+orm legii de +ormare,

+2, 4/ ' + 2-1, 4?1/ adica +1, !/ DD +,/ ' +-1,?1/

E-F +1,!/ ' +1-1, !?1/ adica +0, #/

E-F+0,#/ ' # DD+0, B/ ' B

4.6ie +unctia recursiva cu urmatoarea lege de +ormare:

+B/ ' + B?1/D2 / ? + BD2 /

+1/ ' 1 3e cate oriva +i invocata +unctia recursiva in caul +4/

7eolvare:

+4/ ' + !D2 / ? +2/

entru +4/ +unctia se va apela recursiv: +!D2/ si +2/ entru +iecare apel in parte, +unctia va +i executata din noucu parametrul primit si daca este caul se va apela recursiv din nou pana va +i indelinita conditia de oprire in acest

ca, B sa +ie 1/.

Gtat antru + !D2/ cat si pentru +2/ nu va +i indeplinita niciodata conditia de oprire.

Gsta inseamna ca, teoretic, +unctia se va apela de un numar in+init de ori. ractic ea se va apela pana cand vor +iepuiate resursele alocate programului.

!. 6ie +unctia recursiva + in care BF'0 si HF0, cu urmatoarea lege de +ormare:

+B, H/ ' B, daca B A H +B, H/ ' +B-H, H/, daca BF'H

Care este valoarea +2, !/:

+2, !/ ' 2 , +iindca 2A!.

3aca nu era indeplinita conditia ciar de la primul apel, +unctia se apela recursiv cu alti parametrii, con+orm legii

de +ormare. entru +iecare apel in parte, trebuiau analiati parametrii si se e+ectua actiunea corespunatoare,

con+orm legii dupa care este de+inita +unctia legea de +ormare/.

#. 3eavanta5ul unei liste inlantuite este:

c. +oloseste mai multa memorie decat un tablou cu valori similare

xplicatie:

< lista +oloseste mai multa memorie decat un tablou +iindca pentru +iecare element al listei, pe langa

in+ormatia ce +ace obiectul listei, mai contine cate o re+erinta catre elementul urmator, resectiv anterior.

Iabloului ii este alocata o ona continua de memorie egala cu numarul de elementeJdimensiuneaelementului a tipului de data ce +ace obiectul tabloului/. Bu sunt necesare alte campuri.

C*ISI I>>

$. 3aca teste o re+erinta catre nodul cap al listei, care este secventa corecta pentru a+isarea valorii ultimului nod dinlista:

t. a a+isa valoarea ultimului nod, trebuie parcursa lista pana se a5unge la ultimul nod:

*. Bod x ' t DD x este un nod cursor +olosit la parcurgere

7/23/2019 Model Examen Atpa

3/4

=ile x >' null / (

i+ x.urmator '' null / DD daca urmatorul element este nul, inseamna ca x este ultimul element

SKstem.out.print x.valoare /

x ' x.urmator )

**. Bod x ' t =ile x.urmator >' null / ( DD cat tim urmatorul element nu este nul, se merge mai dearte

DD cand urmatorul element este nul, se intrerupe bucla si x va avea val. ultimului element

al listei

x ' x.urmator )

SKstem.out.print x.valoare/

9. Care dintre urmatoarele coduri permite inserarea in lista simplu inlantuita a nodului cu valoare 10 dupa nodulre+erit prin p:

Bod ' ne= Bod10/

.urmator ' p.urmator

p.urmator '

C*ISI I>>

10. >

11. Considerand ca t este re+erinta catre capul listei, codul urmator: Bod x't

=ilex>'null/ (x.urmator ' x.urmator.urmator)

are ca reultat:

< eroare in timul rularii. Gici trebuie analiat codul, sa vei ce +ace. Bu ai ce invata, trebuie doar sa +ii atenta. Bu este greu :/

x.urmator = x.urmator.urmatorsterge elementul a+lat dupa x. x ia valoarea lui t dar nu ii este scimbata valoarea niciodata, asa ca nu va +i niciodata nul. Gsta inseamna ca sevor sterge elemente din lista pana vor ramane doua noduri, x si nodul urmator lui x.urmator/. La urmatoarea

stergere va +i returnata o eroare +iindcax.urmator = x.urmator.urmatorincearca sa accesee un nod inexistent un

camp al unui obiect nul, de +apt/. Gsta va intrerupe executia programului si va returna o excetie

Bullointerxception parca.../.

12. Se introduce secventa:

# " 1 9 !

intr-o coada. Capul coii este #. lementele sunt introduse si extrase intr-o stiva. Gpoi sunt extrase din stiva sireintroduse in coada. Cum va arata coada: ! 9 1 " #

lementele vor +i in ordine inversa +iindca au +ost introduse si extrase intr-o stiva.

3in stiva, elementele sunt extrase in ordinea inversa introducerii lor. o secventa de elemente ce este introdusa

printr-o stiva, dupa extragere va +i in ordine inversa/. Coada nu scimba ordinea elementelor.

1. entru implementarea unui bu++er tampon/ de date se +oloseste o structura de tip:

b. coada

14. Care sunt valorile tabloului

1 ! " $ # 2

la pasul 4, in caul sortarii prin insertie: 1 ! $ " # 2

7/23/2019 Model Examen Atpa

4/4

7eolvare:

Se ia elementul de pe poi8ia de indice i;i se caut la stMnga lui, de la dreapta la stMnga, poi8ia pe care trebuie

plasat, ast+el ncMt s se respecte ordinea impus.

N 0 1 2 4 ! #

1 ! " $ # 2

N1 1! " $ # 2N2 1 ! " $ # 2N 1 ! " $ # 2

N4 1 ! $ "# 2

Glt exemplu: 0 1 2 4 ! #

9 1 2 ! " $ #

N1 1 92 ! " $ # DD 1A9, se deplaseaa 9 in dreapta cu o po. si se insereaa 1 la locul lui po. 0/

N2 1 2 9! " $ # DD 2A9,N 1 2 ! 9" $ # DD !A9,

N4 1 2 ! " 9$ # DD "A9

1!. Care sunt valorile tabloului

1 2 ! # 4 9 la pasul 4,in caul sortarii prin selectie:

Se caut n tablou cel mai mic element ;i se scimb cu cel de pe prima poi8ie. Se caut apoi cel mai mic

element dintre cele rmase ;i se aduce n tablou pe poi8ia a doua ;i a;a mai departe.

1 2 ! # 4 9pas 1 12 ! # 4 9 DD1 cel mai mic elem., se scimb cu cel de pe prima poi8ie, ramane tabloul 2 ! # 4 9

pas 2 1 2 ! # 4 9 DDdin 2 ! # 4 9,2a5unge pe prima poitie ramane tabloul ! # 4 9

pas 1 2 ! # 4 9

pas 4 1 2 4# !9

1#. Se considera un arbore binar complet. Considerand radacina arborelui ca +iind situata pe nivelul

ero, cate noduri se a+la la nivelul 4: 24'1#

1$ On arbore este considerat arbore binar de cautare daca:

valorile subarborelui din stanga sunt mai mici decat valoarea radacinii, care este mai mica decat valorile

subarborelui din dreapta

1". 3aca radacina unui arbore binar complet se considera nivelul 0, cate noduri sunt pe nivelul 1#: 21#'#!#

19. 3aca un arbore binar complet este repreentat printr-un tablou, copilul din dreapta al nodului

de pe poitia ! din tablou se va a+la pe poitia:

stanga@ ' 2J@ ? 1

dreapta@' 2J@ ? 2 7asuns: 2J! ?2 ' 12