TEHNICI AVANSATE DE PROGRAMARE

19 . In lista circulara simplu inlantuita ce contine numerele 1, 2, 3, 2, 3 in aceasta ordine, iar este adresa nodului ce contine primul numar 2 (fiecare nod are un camp nr ce contine numarul intreg si un camp urm care indica adresa elementului urmator din lista). Prin executarea secventei
while (p -> nr > 0) {p -> nr = p -> nr -1; p = p -> urm;}

continutul listei, citit de la adresa de plecare va fi:

d. 0, 1, 0, 1, 0

20.Se considera ca variabilele p si q memoreaza adresa primului, respectiv ultimului element al

unei liste liniare nevide dublu inlantuite. Elementele listei retin in campul urm adresa elementului urmator,

iar in campul prec adresa elementului anterior. Stabiliti care este numarul de noduri din lista daca p -> urm -

> urm si q -> prec -> prec indica acelasi nod al listei.

a. 4

b. 5

21.Se considera lista circulara simplu inlantuita ce contine celulele cu numerele 1, 2, 3, 4 (in

aceasta ordine). Fiecare element memoreaza in campul nr un numar intreg, iar in campul urm adresa

elementului urmator din lista. Variabila prim indica nodul ce contine numarul 1. Cate treceri sunt necesare pentru ca toate elementele din lista sa ajunga egale. Definim prin trecere prelucrarea data de secventa
urmatoare:

p = prim;

do {if(p->nr > prim->nr) p->nr = p->nr -1; p = p -> urm;} while (p != prim);

c. 3

22.Intr-o lista circulara simplu inlantuita, p este adresa unui nod din lista si campul next memoreaza pentru fiecare nod adresa nodului urmator din lista. Pentru a numara elementele listei vom scrie Secventa (variabila q este de acelasi tip cu variabila p):

a. q = p; k = 1; while(q -> next != p) {k++; q = q -> next;}

23 . Se considera o stiva alocata dinamic care are cel putin 10 elemente. Variabila vf memoreaza

adresa de inceput a stivei si orice element al stivei memoreaza in campul info un numar intreg, iar in campul next adresa nodului urmator. Se considera seceventa de program:

while (vf && vf -> info %2 == 0) {

aux = vf;

vf = aux-> next;
free (aux);

}

Daca in urma executarii secventei de program, variabila vf are valoarea NULL, atunci:

a. Primul element memorat in stiva este par, celelalte fiind numere impare.

b. In stiva nu s-a memorat nici un numar impar.

24.Se considera o lista circulara cu 8 elemente numerotate cu 1, 2, 3, 4, 5, 6, 7, 8. Mai intai se

elimina elementul numerotat cu 3, apoi se elimina fiecare al treilea element al parcurgeri, numararea

continuandu-se cu succesorul elementului eliminat, pana cand lista va mai contine un singur element. Care

va fi numarul de ordine al elementului ramas?

b. 7 d. 4

25 .Se considera o lista circulara dublu inlantuita ale carei noduri retin in campul st adresa

nodului anterior, iar in campul dr adresa nodului urmator din lista. Lista are cel putin doua elemente. Stiind ca p retine adresa unui nod din lista, care este numarul de noduri din lista astfel incat relatia
p->st->st == p->dr sa fie adevarata?

b. 3 d. 4

26 . Se considera lista dublu inlantuita cu noduri care contin in campul inf (ce retine un n umar

natural), in aceasta ordine, numerele: 3, 4, 5, 6, 7, 8. In campurile st si dr sunt retinute adresa nodului

precedent, respectiv adresa nodului urmator din lista.Variabilele globale p si sf retin adresele primului si respectiv ultimului element din lista. O variabila ce retine adresa unui element este de tip nod. Care va fi continutul listei la o parcurgere de la st la dr dupa apelul functiei sub(), unde, functia sub este:
void sub(){

nod *man = sf;

while(man->inf > sf -> inf /2) man = man ->st;
nod *q = man;

man -> st -> dr = q -> dr;
q -> dr -> st = man -> st;
free(q);

}

a. 3, 5, 6, 7, 8

27 . Se considera lista dublu inlantuita cu noduri care contin in campul inf (ce retine un n umar

natural), in aceasta ordine, numerele: 7, 5, 6, 2, 4, 6. In campurile st si dr sunt retinute adresa nodului

nod *man = sf;

while(man->inf > sf -> inf ) man = man ->st;
nod *q = man;

man -> st -> dr = q -> dr;
q -> dr -> st = man -> st;
free(q);

}

d.7, 5, 6, 2, 4

28.Se considera lista dublu inlantuita cu noduri care contin in campul inf (ce retine un n umar

natural), in aceasta ordine, numerele: 9, 7, 8, 3, 2, 4. In campurile st si dr sunt retinute adresa nodului

nod *man = sf;

while(man->inf > sf -> inf ) man = man ->st;
nod *q = man;

man -> st -> dr = q -> dr;
q -> dr -> st = man -> st;
free(q);

}

c.9, 7, 8, 3, 2

29Intr-o lista simplu inlantuita circulara, fiecare element retine in campul adr adresa

elementului urmator din lista. Daca p si q sunt adresele a doua elemente distincte din lista astfel incat sunt

satisfacute conditiile p == q -> adr si q == p -> adr. Atunci lista are

b. exact 2 elemente

30.Se considera o stiva implementata prin intermediul vectorului a cu elementele a[0] = 0, a[1]

= 10, a[2] = 20, a[3] = 30, a[4] = 40, a[5] = 50. Daca cel de-al doilea element, incepand de la baza stivei este

10, atunci primul element care iese din stiva este:

c. a[5]

31 . Intr-o lista circulara simplu inlantuita, cu cel putin un element, fiecare nod retine in campul

adr adresa elementului urmator din lista. Daca p este o variabila care retine adresa primului element din lista, iar q este o variabila care poate sa retina adresa unui element din lista, care dintre urmatoarele secvente de instructiuni calculeaza in variabila nr, de tip int, numarul de elemente al listei?

b. nr = 0; q = p; do {nr ++; q = q -> adr;} while (q != p);

32.Intr-o lista circulara simplu inlantuita fiecare element retine in campul adr adresa

elementului urmator din lista. Daca p reprezinta adresa unui element din lista atunci stabiliti care dintre

urmatoarele expresii are valoarea 1 daca si numai daca lista contine exact doua noduri.

c. p -> adr -> adr == p
33.Se considera urmatoarea functie recursiva apelata numai pentru numere naturale nenule:

int f(int a, int b){

if (a<b) return a; else return f(a-b, b);

}

Care dintre urmatoarele functii este echivalenta cu functia data?

c. int f(int a, int b){return a%b;}

34.Se considera definitia

void f(int n){

int j;

if (n>0) for (j=1; j<=n; j++) {printf(“%d”,j); f(n-1);}

}

Ce se afiseaza ca urmare a apelului f(2)?

b. 112 d. 1121

35.Se considera definitia:

long f(int n){

if (n == 0) return 1;

else if (n == 1) return 4;

else return f(n-1) - f(n-2);

}

Stabiliti ce valoasre returneaza apelul f(7).

d.4

36. Se considera definitia

long f(int n, int k){

if (n == k || k == 1) return 1;
if (n < k) return 0;

long s=0, i;

for (i=1; i<=k; i++) s+=f(n-k,i);
return s;

}

Stabiliti ce valoare returneaza apelul f(6,3).

a. 3

37.Se considera definitia:

long f(int x, int y){

if (x == y || x == 0) return 1;
else return f(x,y-1)+f(x-1,y-1);
}

Ce valoare returneaza apelul f(8,10)?

b. 45

38 . In functia recursiva de mai jos se considera ca tabloul unidimensional v este declarat global.

void star(int i){

if(i<10) {

printf(“*”);

if (v[i] == i+1) star(i+2); else star(i+1);
}

} Pentru care dintre declaratiile urmatoare, apelul star(0) produce 7 asteriscuri (stelute)?

a. int v[] = {1, 4, 3, 2, 1, 6, 5, 4, 3, 10};

39.Pentru o valoare naturala mai mare decat 1 memorata in variabila globala n, subprogramul

urmator afiseaza cel mai mare divizor al lui n, mai mic decat n, la apelul divi(n).

void divi(long i){

if ( ... == 0) printf(“%ld”, ...); else divi(i-1);

}

Cu ce expresii trebuie completate punctele de suspensie?

b. n% (i-1) si i-1

40 . Stiind ca p este un vector (tablou unidimensional) cu 3 componente intregi (tabloul este

declarat global), M este multimea tuturor cifrelor nenule, iar functia tipar afiseaza valorile elementelot p[0], p[1] si p[2], cu ce trebuie inlocuite simbolurile a, b si c in definitia functiei G astfel incat in urma apelului G(0) sa se afiseze toate elementele produsului cartezian MxMxM?

void G(int k){

int i;

for (i = a; i<=b; i++) { p[k] = i; if (k == c) tipar(); else G(k+1);}

}

d. a = 1, b = 9, c = 2

41 . Pentru definitia alaturata a functiei ex(), stabiliti ce se afiseaza la apelul ex(120)?

void ex(int x){

if (x != 0){

printf(“%d”, x %10);
ex(x/10);

} }

c. 021

42.a.2³⁰

b.2²⁰Gasiti elementul f(20) din sirul definit prin relatia (f(n))² = 8(f(n-1))^2,unde f(0) = 2

c. 2¹⁹

d. 2³¹

43.Se considera relatia de recurenbta neomogena de ordinul intai f(n) - f(n-1) = 9n², f(0) = 8,

n>0; Atunci f(n) =

a.c.

b.d.

44.Se considera relatia de recurenta f(n) - 7f(n-1) = 9(5ⁿ), n > 0; f(0) = 3. Atunci f(n) =

a.c.

b.d.

45.Solutia f(n) a relatiei de recurenta f(n) - 7f(n-1) = 9(7ⁿ), n>0, f(0) = 3, este

a.(9n+3)7ⁿc.(9n+9)7ⁿ

b.(3n+9)7ⁿd.(3n+3)7ⁿ

46 Solutia relatiei de recurenta f(n) = 6 f(n-1) - 9 f(n-2), n≥0, f(0) = 1, f(1) = 2 este f(n) =

a. 3ⁿ-n3^n-1

b. 3^n-1-n3ⁿ

c.3ⁿ⁺¹-n3ⁿ

d.3ⁿ⁺¹-n3^n-1

47.Solutia relatiei de recurenta f(n) = 2f(n-1) - 4f(n-2), n>1, f(0)=1, f(1) = 3 este f(n) =

a. c.

b. d.

48.Un algoritm de tip backtracking genereaza in ordine lexicografica, toate sirurile de 5 cifre 0

si 1 cu proprietatea ca nu exista mai mult de doua cifre de 0 consecutive. Primele sase solutii generate sunt:

00100, 00101, 00110, 01001, 01010. Care este cea de-a opta solutie?

a. 01110

b.01100 c.01011 d.01101

49 Un algoritm backtracking genereaza toate sirurile alcatuite din cate 5 cifre binare (0 si 1).

Numarul tuturor solutiilor generate va fi egal cu :

a. 5 c. 10

b. 32 d. 31

50 . Aplicand metoda backtracking pentru a genera toate permutarile celor n elemente ale unei

multimi, o solutie se memoreaza sub forma unui tablou unidimensional x₁, x₂, ..., x_n. Daca sunt deja generate valori pentru componentele x₁, x₂, ..., x_k-1, iar pentru componenta x_k (1 <k<n)au fost testate toate valorile posibile si nu a fost gasita niciuna convenabila, atunci:

a. se incearca alegerea unei noi valori pentru componenta x_k-1.

51.Daca se utilizeaza metoda backtracking pentru a genera toate numerele naturale, in ordine

strict crescatoare, formate din 4 cifre pare distincte, care dintre numerele de mai jos trebuie, eliminate astfel incat cele ramase sa reprezinte o succesiune de numere corect generate?

1) 2068; 2) 2084; 3) 2088; 4) 2468; 5) 2086; 6) 2406

a. numai 3)

b. atat 3) cat si 5)

c. atat 3) cat si 4)

d. numai 4)

52 . Se considera multimea {1, 7, 5, 16, 12}. Se genereaza prin metoda backtracking toate

submultimile sale formate din exact 3 elemente: primele patru solutii generate sunt, in ordine: {1, 7, 5}, {1, 7, 16}, {1, 7, 12}. Care dintre solutii trebuie eliminate din sirul urmator astfel incat cele ramase sa apara in sir in ordinea generarii lor:

{1, 16, 12}, {5, 16, 12}, {7, 5, 16}, {7, 5, 12}

a. {1, 16, 12}

b. {5, 16, 12}

53.Se considera algoritmul care genereaza in ordine strict crescatoare toate numerele formate cu

5 cifre distincte alese din multimea {1, 0, 5, 7, 9} in care cifra din mijloc este 0.Selectati numarul care

precede si numarul care urmeaza secventei de numere generate:

19075; 51079; 51097

a. 19057, 57019

54.Daca pentru generarea tuturor submultimilor unei multimi A = {1, 2, ..., n} cu 1 ≤ n ≤ 10, se

utilizeaza un algoritm backtracking astfel incat se afiseaza in ordine, pentru n=3, submultimile {}, {1}, {2},

{3}, {1, 2}, {1,3}, {2,3}, {1, 2, 3}, atunci, utilizand exact acelasi algoritm pentr n = 4, in sirul submultimilor

generate, solutia a 7-a va fi:

a. {1,3}

b. {4}

c. {1,2,3}

d. {1,4}

55.Produsul cartezia {1,2,3}x{2,3} este obtinut cu ajutorul unui algoritm backtracking care

genereaza perechile (1,2), (1,3), (2,2), (2,3), (3,2) si (3,3). Care este numarul perechilor obtinute prin

utilizarea aceluiasi algoritm la generarea produsului cartezian {1, 2, 3, 4}x{2, 3, 4}?

a. 12 c. 81

b. 10 d. 6

56 . Se genereaza toate sirurile strict crescatoare de numere naturale nenule mai mici sau egale cu

4, avand primul termen 1 sau 2, ultimul termen 4 si cu diferenta dintre oricare doi termeni aflati pe pozitii consecutive cel mult 2, obtinandu-se solutiile (1, 2, 3,4), (1, 2, 4), (1, 3, 4), (2, 3, 4), (2, 4). Folosind aceeasi metoda generam toate sirurile strict crescatoare de numere naturale nenule mai mic sau egale cu 6, avand primul termen 1 sau 2, ultimul termen 6 si diferenta dintre oricare doi termeni aflati pe pozitii consecutive cel mult 2, care dintre afirmatiile urmatoare este adevarata:

a. imediat dupa solutia (1, 3, 4, 5, 6) se genereaza solutia (2, 3, 4, 5, 6)

b. penultima solutie generata este (2, 3, 5, 6)

c. imediat dupa solutia (1, 2, 4, 6) se genereaza solutia (1, 3, 4, 6)

d. in total sunt generate 13 solutii.

57.Avand la dispozitie cifrele 0, 1 si 2 putem genera, in ordine crescatoare, numerele care au

suma cifrelor egala cu 2 astfel: 2, 11, 20, 101, 110, 200, etc. Folosind acest algoritm generati numerele cu

cifrele 0, 1 si 2 care au suma cifrelor egala cu 3. Care va fi al saptelea numar din aceasta generare?

a. 120

b. 1002

c. 201

d. 210

58.Generarea tuturor cuvintelor de 4 litere, fiecare litera putand fi orice element din multimea

{a, c, e, m, v, s}, se realizeaza cu ajutorul unui algoritm echivalent cu algoritmul de generare a:

a. produsului cartezian c. partitiilor unei multimi

b. combinarilor d. permutarilor

59.Folosind un algoritm de generare putem obtine numere naturale de k cifre care au suma

cifrelor egala cu un numar natural s introdus de la tastatura, unde s si k sunt numere naturale nenule. Astfel

pentru valorile k = 2 si s = 6 se genereaza numerele: 15, 24, 33, 42, 51, 60. Care vor fi primele 4 numere ce

se vor genera pentru k = 3 si s=8?

a. (a, b, c) c. (a, b, b)

b. (a, c, b) d. (a, c, d)

61.Pentru a determina toate modalitatile de a scrie numarul 8 ca suma de numere naturale

nenule distincte (abstractie facand de ordinea termenilor) se foloseste metoda backtracking obtinandu-se, in

ordine, toate solutiile 1+2+5, 1+3+4, 1+7, 2+6, 3+5. Aplicand exact acelasi procedeu, se determina solutiile

pentru scrierea numarului 10. Cate solutii de forma 1+ ... exista?

a. 3 c. 5

b. 4 d. 6

62.Se considera multimile A = {1, 2, 3}, B = {1}, C = {2, 3, 4}. Elementele produsului

cartezian AxBxC se genereaza, folosind metoda backtracking, in ordinea (1, 1, 2), (1, 1, 3), (1, 1, 4), (2, 1,

2), (2, 1, 3), (2, 1, 4), (3, 1, 2), (3, 1, 3), (3, 1, 4). Daca prin acelasi algoritm se genereaza produsul cartezian

al multimilor AxBxC unde A = {x, y}, B = {x}, c = {x, y, z}, atunci cel de-al treilea element generat este:

a. (x, x, y) c. (x, x, z)

b. (x, y, x) d. (x, y, z)

63.Generarea tuturor sirurilor formate din trei elemente, fiecare element putand fi oricare numar

din multimea {1, 2, 3}, se realizeaza cu ajutorul unui algoritm echivalent cu algoritmul de generare a:

a. permutarilor

b. combinarilor

c. produsului cartezian

d. aranjamentelor

64 In utilizarea metodei backtracking pentru a genera toate cuvintele alcatuite din doua litere

ale multimii {a, c, e, q}, astfel incat sa nu existe doua consoane alaturate, cuvintele se genereaza in

urmatoarea ordine: aa, ac, ae, aq, ca, ce, ea, ec, ee, eq, qa, qe. Daca se utilizeaza exact aceeasi metoda pentru a genera cuvinte formate din 4 litere ale multimii {a, b, c, d, e, f}, astfel incat sa nu existe doua consoane alaturate in cuvant, care este penultimul cuvant generat?

a. fefa c. feef

b. fafe d. fefe

65 . Utilizand metoda backtracking se genereaza toate numerele formate doar din trei cifre astfel

incat fiecare numar sa aiba cifrele distincte. Cifrele fiecarui numar sunt din multimea {12, 2, 3, 4}. acest

algoritm genereaza numerele, in aceasta ordine: 123, 124, 132, 134, 213, 214, 231, 234, 312, 314, 321, 324, 412, b413, 421, 423, 431, 432. Daca utilizam acelasi algoritm pentru a genera toate numerele de 4 cifre,
fiecare numar fiind format din cifre distincte din multimea {1, 2, 3, 4, 5}, precizati care este numarul generat imedia dupa 4325.

a. 4351 c. 4521

b. 5123 d. 4321

66 . Utilizand metoda backtracking se genereaza toate numerele palindrom formate din 4 cifre.

Fiecare numar contine cifre din multimea {1, 3, 5}. Elementele sunt generate in urmatoarea ordine: 111, 1331, 1551, 3113, 3333, 3553, 5115, 5335, 5555. Daca se utilizeaza exact aceeasi metoda pentru a genera toate numerele palindrom formate din 4 cifre, fiecare element avand cifre din multimea {1, 2, 3, 4, 5, 6, 7, 8, 9}. Sa se precizeze cate numere pare se vor genera.

a. 99 c. 36

67.Utilizand metoda backtracking se genereaza elementele produsului cartezian a n multimi A₁,

A₂, ..., A_n. Daca utilizam acest algoritm pentru a genera elementele produsului cartezian a 3 multimi: M = {1,

2, 3}, N = {1, 2} si P = {1, 2, 3, 4} atunci care din urmatoarele secvente nu reprezinta o solutie acestui

algoritm, pentru produsul cartezian PxNxM?

a. (4, 2, 3) c. (3, 2, 1)

b. (3, 3, 3) d. (1, 1, 1)

68.Utilizand metoda backtracking se genereaza toate numerele de cate 3 cifre astfel incat

fiecare numar generat are cifrele distincte si suma lor este un numar par. Precizati care dintre urmatoarele

numere reprezinta o solutie a algoritmului?

a. 235 c. 281

b. 986 d. 455

69 . Utilizand metoda backtracking se genereaza in ordine lexicografica toate posibilitatile de

aranjare a 8 dame pe tabla de sah astfel incat aceastea sa nu se atace. fiecare solutie se exprima sub forma

unui vector c = (c1, c2, ..., c8) unde c1 reprezinta coloana pe care se afla dama de pe linia i. Stiind ca primele doua solutii generate sunt (1, 5, 8, 6, 3, 7, 2, 4), (1, 6, 8, 3, 7, 4, 2, 5) sa se determine solutia generata de
algoritm imediat dupa solutia (8, 2, 4, 1, 7, 5, 3, 6).

a. teica c. ticae

b. tieac d. tiace

73 . O singura statie de servire (procesor, pompa de benzina etc) trebuie sa satisfaca cererile a n

clienti. Timpul de servire necesar fiecarui client este cunoscut in prealabil: pentru clientul i este necesar un timp t_i, 1 ≤ i ≤ n. Daca dorim sa minimizam timpul total de asteptare atunci

a. selectam intotdeauna clientul cu timpul maxim de servire din multimea de clienti ramasa

b. selectam intotdeauna clientul cu timpul minim de servire din multimea de clienti ramasa

74 . Se considera graful ponderat din imaginea alaturata.

Ordinea de selectare a muchiilor in vederea obtinerii unui arbore partial de cost minim, prin utilizarea strategiei Greedy de tip Kruskal, este:

a. (1, 2), (2, 3), (4, 5), (6, 7), (1, 4), (4, 7)

75 . Managerul artistic al unui festival trebuie sa selecteze o multime cat mai ampla de spectacole

care pot fi jucate in singura sala pe care o are la dispozitie. Stiind ca i s-au propus 8 spectacole si pentru fiecare spectacol i-a fost anuntat intervalul in care se va desfasura:

1: [10, 15)

2: [2, 4)
3: [7, 9)
4: [21, 25)
5: [10, 12)
6: [12, 15)
7: [7, 8)
8: [20, 27)

Care spectacole trebuie selectate pentru a permite spectatorilor sa vizioneze un numar cat mai mare de spectacole?

a. 2, 3, 5, 6, 8

76.Se considera ca trebuie transportate cu ajutorul unui rucsac de capacitate 10kg, obiecte cu

greutatile 8kg, 6kg si 4kg. Pentru fiecare kg transportat castigul obtinut este 1 LEU.

Stiind ca obiectele se incarca integral in sac si ca se poate alege cel mult un obiect din fiecare tip, atunci

solutia optima este (se noteaza prin 1 - selectarea obiectului, iar prin 0 - neselectarea acestuia):

a. (1, 0, 0) c. (1, 1, 1)

b. (0, 1, 1) d. (1, 1, 0)

77 . Se doreste planificarea optimala (penalizarea totala sa fie minima) a 7 lucrari, fiecare lucrare

i fiind data prin termenul de predare t[i] si penalizarea p[i] care se plateste in cazul in care lucrarea nu este finalizata la timp. Se presupune ca pentru executarea unei lucrari este necesara o unitate de timp si ca nu se pot executa doua lucrari in acelasi timp.

Se considera datele de intrare:

i t[i] p[i]

1 4 50

2 3 40

3 2 60

4 3 20

5 4 70

6 2 10

7 1 130

Care este penalizarea totala minima ce se poate obtine?

a. 10 c. 20

b. 130 d. 70

78.Fie tabloul unidimensional a in care elementele sunt, in ordine 1, 3, 5, 7, 10, 16, 21. Pentru a

verifica daca numarul x = 4 se afla printre elementele tabloului, se aplica metoda cautarii binare. Care este

succesiunea corecta de elemente cu care se compara x?

c. 7, 3, 5

d. 21, 16, 10, 7, 5, 3

79.Se considera doua tablouri unidimensionale A si B: A = (1, 3, 5, 9, 10), respectiv B = (2, 4,

6, 7). In urma interclasarii lor in ordine crescatoare se obtine tabloul cu elementele: