subiecte intensiv

1. Ci frai are nodul 1 din arborele cu rdcin cu 7 noduri, numerotate de la 1 la 7, avndurmtorul vector de tai: (5,1,5,1,0,7,5)? (6p.)

a. 0 b. 1 c. 2 d. 3

2. Care este vectorul "de tai" pentru arborele cu rdcin din figura alturat? (4p.)

a. 0 0 5 7 6 5 1 b. 1 0 0 7 6 5 0c. 7 4 5 0 4 5 4 d. 7 4 5 0 4 5 7

3. Ci frai are nodul 1 din arborele cu rdcin, cu 7 noduri, numerotate de la 1 la 7, avndurmtorul vector de tai: (5,1,5,1,0,7,5)? (4p.)

a. 3 b. 1 c. 0 d. 2

4. Se consider un arbore cu rdcin n care doar 13 dintre nodurile arborelui au exact 2descendeni direci (fii), restul nodurilor avnd cel mult un descendent direct (fiu). Care estenumrul frunzelor arborelui? (6p.)

5. Se consider un arbore cu 11 muchii. Care este numrul de noduri ale arborelui? (6p.)

6. Se consider un arbore cu rdcin n care doar 13 dintre nodurile arborelui au exact 2descendeni direci (fii), restul nodurilor avnd cel mult un descendent direct (fiu). Care estenumrul frunzelor arborelui? (6p.)

7. Care este numrul de muchii ale unui arbore cu 15 noduri? (6p.)

8. Cte frunze are arborele cu 8 noduri i rdcina 1,reprezentat prin matricea de adiacen alturat? (4p.)0 1 0 0 1 0 0 01 0 1 0 0 0 0 00 1 0 1 0 0 0 00 0 1 0 0 0 0 01 0 0 0 0 1 0 10 0 0 0 1 0 1 00 0 0 0 0 1 0 00 0 0 0 1 0 0 0a. 5 b. 4 c. 3 d. 2

9. ntr-un arbore cu rdcin, nivelul unui nod este egal cu lungimea lanului format din noduri distincte care unete rdcina cu acel nod. Care dintre noduri trebuie ales ca rdcin n arborele din figura alturat astfel nct pe fiecare nivel s se gseasc un numr impar de noduri? (6p.)a. 2 b. 3 c. 6 d. 4

10. Un arbore cu 11 noduri, numerotate de la 1 la 11, este memorat cu ajutorul vectorului detai t=(2,5,5,3,0,2,4,6,6,2,3). Mulimea tuturor ascendenilor nodului 8 este: (4p.)

a. {1, 2, 5, 6, 10} b. {6, 2, 5} c. {6} d. {5, 2}

11. Care sunt nodurile de tip frunz din arborele alturat dac se allege ca rdcin nodul 6? (6p.)

12. Care dintre noduri trebuie ales ca rdcin n arborele din figura alturat astfel nct s existe un nod cu 3 descendeni direci (fii)? (6p.)

a. 2 b. 3 c. 6 d. 4

13. Un arbore cu rdcin are nodurile numerotate de la 1 la 18 i este reprezentat prinvectorul de tai t:(8,8,0,3,4,3,4,7,1,2,3,3,7,8,3,5,6,8). Numrul tuturordescendenilor nodului 3 este egal cu: (4p.)a. 3 b. 6 c. 17 d. 18

14. Care dintre vectorii urmtori poate fi vectorul de tai ai unui arbore cu rdcin avnd 10noduri, numerotate de la 1 la 10? (4p.)a. (0,1,2,3,4,5,0,7,8,9) b. (1,2,3,4,5,7,6,8,9,0)c. (10,10,10,10,10,10,10,10,10,0) d. (9,8,7,6,5,4,3,2,1,0)

15. Un arbore cu rdcin are nodurile numerotate de la 1 la 18 i este reprezentat prinvectorul de tai t=(8,8,0,3,4,3,4,7,1,2,3,3,7,8,3,5,6,8). Numrul tuturordescendenilor nodului 3 este egal cu: (4p.)

a. 3 b. 6 c. 17 d. 18

16. ntr-un arbore cu rdcin, cu 10 noduri, numerotate de la 1 la 10, nodul 10 este rdcin,iar ntre celelate noduri exist relaia: nodul cu numrul i+1 este tatl celui cu numrul i,

Vectorul de tai al arborelui astfel definit, este: (4p.)a. (0,1,2,3,4,5,6,7,8,9) b. (1,2,3,4,5,6,7,8,9,0)c. (2,3,4,5,6,7,8,9,10,0) d. (9,8,7,6,5,4,3,2,1,0)

17. Pentru care dintre urmtorii arbori cu rdcin, fiecare avnd 9 noduri, numerotate de la 1la 9, memorai cu ajutorul vectorilor de tai, nodul 3 are cei mai muli descendeni? a. tata=(2,0,2,3,2,3,4,4,3) b. tata=(3,3,4,0,2,3,4,4,4)c. tata=(4,2,4,0,3,3,3,3,3) d. tata=(0,1,1,3,4,3,4,4,3)

18. Pentru arborele cu rdcin, cu 9 noduri, numerotate de la 1 la 9, avnd urmtorul vector detai tata=(8,7,6,6,7,7,8,0,8), care este rdcina arborelui i care sunt descendeniinodului 7?

19. Stabilii care dintre urmtorii vectori este vector de tai pentru 0 1 0 0 1 0 0 arborele cu 7 noduri, numerotate de la 1 la 7, cu rdcina 1 1 0 1 1 0 0 0 reprezentat prin matricea de adiacen alturat: 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0

a. (3, 1, 0, 2, 1, 5, 6) b. (1, 0, 2, 2, 1, 5, 5)c. (0, 1, 2, 2, 1, 5, 5) d. (2, 1, 0, 2, 1, 5, 2)

20. Se consider vectorul de tai" al unui arbore cu rdcin t=(3,4,0,3,3,5) ale cruinoduri sunt numerotate de la 1 la 6. Alegei afirmatia corect:

a. nodurile 1, 2, 6 sunt noduri de tip frunz b. nodul 3 are un singur descendent direct (fiu)c. nodul 6 este tatl nodului 5 d. nodurile 4 i 6 sunt noduri de tip frunz

21. Un arbore cu rdcin are nodurile numerotate de la 1 la 18 i este reprezentat prinvectorul de tai t=(8,8,0,3,4,3,4,7,1,2,3,3,7,8,3,5,6,8). Numrul tuturordescendenilor nodului 3 este egal cu: a. 3 b. 6 c. 17 d. 18

22. ntr-un arbore cu rdcin, cu 10 noduri, numerotate de la 1 la 10, nodul 10 este rdcin,

iar ntre celelate noduri exist relaia: nodul cu numrul i+1 este tatl celui cu numrul i,pentru i= {1,2,3,4,5,6,7,8,9}. Vectorul de tai al arborelui astfel definit, este: a. (0,1,2,3,4,5,6,7,8,9) b. (1,2,3,4,5,6,7,8,9,0)c. (2,3,4,5,6,7,8,9,10,0) d. (9,8,7,6,5,4,3,2,1,0)

23. Cte muchii trebuie eliminate dintr-un graf neorientat complet cu 20 de noduri, pentru cagraful parial obinut s fie arbore?

24.Care este gradul maxim posibil i care este gradul minim posibil pentru un nod dintr-un grafcu n noduri, care este arbore? a. n-1 i 1 b. n i 1c. n i 0 d. n-1 i 0

25. Un arbore binar este un arbore cu rdcin n care fiecare nod are cel mult 2 descendenidireci (fii), iar nlimea arborelui este reprezentat de numrul maxim de muchii ale unuilan elementar ce unete rdcina cu un vrf terminal (frunz). Pentru un arbore binar cuexact 8 noduri, precizai care este nlimea minim posibil?

a. 4 b. 7 c. 3 d. 2

26. Care este numrul de muchii care trebuie eliminate dintr-un graf neorientat, complet, cu 7noduri, astfel nct graful parial obinut s fie arbore? (4p.)

a. 15 b. 1 c. 6 d. 21

27.Care este gradul maxim posibil i care este gradul minim posibil pentru un nod dintr-unarbore cu n noduri (n>1)?

28.Un arbore binar este un arbore cu rdcin n care fiecare nod are cel mult 2 descendenidireci (fii). nlimea unui arbore este reprezentat de numrul maxim de muchii ale unuilan elementar ce unete rdcina cu un vrf terminal (frunz).Pentru un arbore binar cu exact 8 noduri, care este nlimea minim posibil i care poate fi

numrul maxim de noduri terminale (frunze) ale arborelui n acest caz?

29. Pentru reprezentarea unui arbore cu rdcin cu 9 noduri, etichetate cu numere naturale de la 1 la 9, se utilizeaz vectorul de tai: T=(2,0,1,7,3,1,2,4,1). Care suntdescendenii direci (fiii) ai rdcinii i cte frunze are arborele dat? (6p.)

30. Care sunt nodurile de tip frunz ale arborelui cu rdcin, cu 9 noduri, numerotate de la 1 la 9,al crui vector de tai este (6, 6, 8, 8, 7, 7, 0, 7, 7)? (6p.)

31. Care dintre urmtorii vectori NU poate reprezenta vectorul de tai al unui arbore cu

rdcin, cu 5 noduri, numerotate de la 1 la 5? (4p.)a.3 1 0 1 2 b. 2 0 1 1 2 c. 3 4 0 2 3 d. 4 1 1 0 2

32. Care sunt nodurile care au exact 2 descendeni pentru un arbore cu rdcin, cu 7 noduri,numerotate de la 1 la 7, dat de vectorul de tai: (3,3,0,1,2,2,4)?

33. Fie T un arbore cu rdcin. Arborele are 8 noduri numerotate de la 1 la 8 i este descrisprin urmtorul vector de tai: (4,1,6,0,1,1,4,7). Care sunt frunzele arborelui? (6p.)

34. Se consider arborele din figura alturat.Care este vectorul cu legturi de tip tat pentru acest arbore? Care sunt descendenii nodului 3?

35. Se consider arborele cu 13 noduri, numerotate de la 1 la 13, i mulimea muchiilor{[1,4], [2,5], [3,8], [4,7], [4,9], [4,11], [6,3], [6,10], [6,12], [5,6],[13,2], [2,9]}. Dac se alege nodul numerotat cu 2 drept rdcin, care este vectorulde tai pentru acest arbore? (6p.)

36. Care sunt noduri de grad 1 din arborele cu rdcin, cu 7 noduri, numerotate de la 1 la 7,descris prin urmtorul vector de tai: (5,1,4,5,0,4,3) (6p.)

37. Se consider arborele cu rdcin avnd 10 noduri, numerotate de la 1 la 10 dat prinvectorul Tata=(6, 0, 2, 2, 3, 3, 2, 7, 7, 9). Care este nodul rdcin i care sunt nodurileterminale ale arborelui? (6p.)

38. Care dintre nodurile arborelui din figura alturat pot fi considerate ca fiind rdcin astfel nct astfel nct n arborele cu rdcin rezultat fiecare nod s aib cel mult doi descendeni direci (fii)? (6p.)

39. Se consider un arborele cu rdcin, cu 11 vrfuri numerotate de la 1 la 11, descris prin urmtorul vector de tai: (6,5,5,2,0,3,3,3,8,7,7). Care sunt descendenii direci ai rdcinii i cte frunze are arborele dat?

40. Un arbore cu rdcin, cu 9 noduri, numerotate de la 1 la 9, este memorat cu ajutorul vectorului de tai t=(9,3,4,7,3,9,0,7,2). Mulimea tuturor nodurilor de tip frunzeste:

a. {8, 6, 1, 5} b. {1, 6} c. {8} d. {1, 6, 8}

41. Un arbore cu 9 noduri, numerotate de la 1 la 9, este memorat cu ajutorul vectorului de tait=(9,3,4,7,3,9,0,7,2). Numrul tuturor descendenilor nodului 2 este: a. 3 b. 1 c. 0 d. 2

42. Pentru reprezentarea unui arbore cu rdcin, cu 10 noduri, etichetate cu numerelenaturale de la 1 la 10, se utilizeaz vectorul de tai: TATA=(4, 8, 8, 0, 10, 4, 8,6, 2, 6). Care sunt frunzele arborelui? (6p.)

43. Pentru reprezentarea unui arbore cu rdcin, cu 9 noduri, etichetate cu numerele naturalede la 1 la 9, se utilizeaz vectorul de tai: T=(5,0,2,7,3,3,2,4,7). Din cte muchiieste format un lan elementar de lungime maxim, n arborele dat? (6p.)

44. Pentru reprezentarea unui arbore cu rdcin, cu 10 noduri, etichetate cu numerelenaturale de la 1 la 10, se utilizeaz vectorul de tai: TATA=(4, 8, 8, 0, 10, 4, 8,6, 2, 6). Care este rdcina arborelui i cte frunze are acesta? (6p.)

45. Pentru reprezentarea unui arbore cu rdcin, cu 9 noduri, etichetate cu numerele naturalede la 1 la 9, se utilizeaz vectorul de tai: T=(7,0,2,7,6,2,3,6,5). Care sunt nodurilearborelui ce au exact 2 descendeni direci (fii)? (6p.)

46. Fie T un arbore cu rdcin. Arborele are 8 noduri numerotate de la 1 la 8 i este descrisprin urmtorul vector de tai:(3,5,0,3,3,5,5,5). Care este nodul cu cei mai mulidescendeni direci (fii)?

47. Fie T un arbore cu rdcin. Arborele are 8 noduri numerotate de la 1 la 8 i este descrisprin urmtorul vector de tai: (4,5,0,3,4,5,4,5). Care sunt frunzele arborelui? (6p.)

48. Dac T este un arbore cu rdcin cu 100 de noduri, care este numrul minim de frunze pe care le poate avea T?

49. Un arbore cu rdcin, cu 8 noduri, numerotate de la 1 la 8, este memorat cu ajutorul vectorului de tai T=(0,1,1,1,3,5,3,3).Care sunt fraii nodului 7?

50. Un arbore cu rdcin avnd 9 noduri, numerotate de la 1 la 9, este memorat cu ajutorul vectorului de tai t=(2,5,5,3,0,2,4,1,1). Scriei toi ascendenii nodului 4.

51. Un arbore cu rdcin avnd 8 noduri, numerotate de la 1 la 8, este memorat cu ajutorul vectorului de tai t=(8,8,0,3,4,3,4,6). Scriei care sunt descendenii nodului 4?

52. Care este vectorul de tai asociat arborelui cu rdcin din figura alturat n care nodul 5 este nodulrdcin?

53. Care este numrul de noduri ale unui arbore cu 100 de muchii?

54.Care este vectorul de tati asociat arborelui cu radacina din figura alaturata? (6p.) 1 / \ 2 3 / \ 4 5 / \ 6 7

55.Care este vectorul de tati asociat arborelui cu radacina din figura alaturata? 2 /|\ 3 5 1 | 4

56.Determinai ultima valoare (notat cu ?) din vectorului de tai (0, 1, 1, 2, 3, 3, ?) astfel

nct arborele cu 7 noduri, numerotate de la 1 la 7, descris de acest vector, s aib pe

fiecare nivel n exact 2n noduri, nodul rdcin fiind pe nivelul n=0, i fiecare nod s aib cel

mult doi descendeni. Scriei matricea de adiacen a unui arbore astfel definit.

57.Se consider un arbore cu 6 noduri, numerotate de la 1 la 6,reprezentat prin matricea de adiacen dat alturat. Scriei toatenodurile care pot fi alese ca rdcin a arborelui astfel nct acestas aib un numr par de frunze. (6p.)0 1 0 0 0 11 0 1 1 1 00 1 0 0 0 00 1 0 0 0 00 1 0 0 0 01 0 0 0 0 0

58.Un arbore cu 11 noduri, numerotate de la 1 la 11, este memorat cu ajutorul vectorului detai t=(2,5,5,3,0,2,4,6,6,2,3). Descendenii direci (fiii) ai nodului 2 sunt: (4p.)

a. 1, 6 i 10 b. 5 c. 6, 8 i 9 d. 3

59.Scriei vectorul de tai corespunztor arborelui cu 8 noduri,numerotate de la 1 la 8, dat prin lista alturat adescendenilor direci (fiilor)? (6p.)

1: 4,6,72: -3: 1,84: -5: -6: 27: -8: 5

60. Se consider arborele din figura alturat.

a) Care este nodul care trebuie ales ca rdcin astfel nct aceasta s aib 4 descendeni direci (fii)? (3p.)b) Care sunt cei patru fii ai nodului ales ca rdcin n acest caz? (3p.)

61.Un graf neorientat cu 5 noduri, numerotate de la 1 la 5, conine urmtoarele muchii: [1,2],[1,3], [2,3], [2,5], [3,4], [3,5], [4,5]. Eliminai din acest graf numrul necesar demuchii astfel nct graful parial rezultat s fie arbore. Considernd c acest arbore are cardcin vrful 5, care este vectorul cu legturi de tip tat corespunztor ? (6p.)

62. Cte valori nule pot s apar ntr-un vector cu legturi de tip tat asociat unui arbore curdcin care conine 10 noduri? (4p.)a. niciuna b. exact unac. depinde de configuraia arborelui d. exact dou

63. Care este numrul maxim de valori egale care pot s apar ntr-un vector cu legturi de tiptat asociat unui arbore cu rdcin care conine 10 noduri? (4p.)a. cel mult 2 b. 10c. nu pot s apar valori egale ntr-un vectorcu legturi de tip tatd.9

64. Se consider un arbore cu rdcin memorat cu ajutorul vectorului de taiT=(2,0,1,1,1,2). Stabilii care dintre nodurile arborelui sunt situate pe nivelul 3, dacrdcina este situat pe nivelul 1? (4p.)a. 3 4 5 b. 1 c. 2 6 d. 1 2 6

65. Scriei vectorului de tai al unui arbore cu rdcin, tiind c: nodurile arborelui sunt numerotate cu numerele naturale distincte 1,2,3,...; numrul nodurilor este 4 sau 6; nodul 1 este desemnat ca rdcin; numrul nodurilor de tip frunz este egal cu jumtate din numrul total de noduri dinarbore; numrul de nivele pe care sunt dispuse nodurile arborelui este egal cu numrul nodurilorde tip frunz.

66. Se consider arborele cu 6 noduri, numerotate de la 1 la 6, cu muchiile [2,1], [2,4],

[4,5], [6,2], [6,3]. Scriei toate nodurile desemnate ca rdcin astfel nct fiecarearbore cu rdacin obinut s aib exact 3 frunze. (6p.)

67. Care este nodul ce poate fi ales ca rdcin a arborelui din figura de mai jos,astfel nct rdcina s aib 3 descendeni direci(fii)? a. 3 b. 4 c. 6 d. 1

68. Care este numrul nodurilor de tip frunz din arborele cu rdcin,cu 8 noduri,numerotate de la 1 la 8,reprezentat prin vectorul "de tai" (2,0,6,2,4,4,5,5)?

a. 3 b. 4 c. 5 d. 2

69. ntr-un arbore cu rdcin fiecare nod neterminal are exact 2 descendeni direci (fii).Care este numrul de noduri din arbore dac acesta are 8 frunze?

a. 8 b. 7 c. 15 d.10

70. Care este nodul ce poate fi ales ca rdcin a arborelui din figura de mai jos,astfel nct fiecare nod care nu este de tip frunz s aib un numr impar de descendeni direci (fii)?

a. 3 b.4 c. 6 d. 1

71. Intr-un arbore cu radacina nivelul unui nod este egal cu lungimea lantului format din noduri distincte care uneste radacina cu acel nod. Radacina se afla pe nivelul 0. Daca toate frunzele se afla pe nivelul 3 si oricare nod neterminal aflat pe un nivel k are exact k+1 descendenti directi (fii),care este numarul de noduri din acest arbore?

a. 8 b. 9 c. 10 d. 6

72. Un arbore cu 9 noduri, numerotate de la 1 la 9, estememorat cu ajutorulvectorului de tai

t=(9,3,4,7,3,9,0,7,2). Lungimeaceluimai lung lanelementar care pornete dinrdcineste: (4p.)

a. 1 b. 5 c. 3 d. 4

73. Scriei matricea de adiacen a arborelui cu 6 noduri, numerotate de la 1 la 6, definit prinurmtorul vector "de tai": (0, 1, 1, 1, 3, 3).

74. Se considerun arbore cu 6 noduri, numerotate de la 1 la 6,reprezentatprinmatricea de adiacendatalturat. Scrieitoatenodurile care pot fi alesecardcin a arboreluiastfelnctacestasaib un numr minim de frunze. (6p.)0 1 0 0 0 11 0 1 1 1 00 1 0 0 0 00 1 0 0 0 00 1 0 0 0 01 0 0 0 0 0

75. Un arbore cu rdcin, cu 9 noduri, numerotate de la 1 la 9, estememorat cu ajutorulvectorului de tai t=(9,3,4,7,3,9,0,7,2). Care estenumrul minim de noduricetrebuie eliminate pentrucalungimeaceluimai lung lanelementar, cu o extremitatenrdcin, s fie 3 isubgrafulobinuts fie tot arbore? (4p.)

a. 4 b. 3 c. 2 d. 5

76. Scriei matricea de adiacen a arborelui cu rdcin, cu 6 noduri, numerotate de la 1 la 6,definitprinurmtorul vector "de tai": (0, 1, 1, 1, 3, 3).

77. Se considerun arbore cu 6 noduri, numerotate de la 1 la 6,reprezentatprinmatricea de adiacendatalturat. Scrieitoatenodurile care pot fi alesecardcin a arboreluiastfelnctacestasaib un numr maxim de frunze. (6p.)0 1 0 0 0 11 0 1 1 1 00 1 0 0 0 00 1 0 0 0 00 1 0 0 0 01 0 0 0 0 0

78. Se considerun arbore cu 6 noduri, numerotate de la 1 la 6,reprezentatprinmatricea de adiacendatalturat. Scrieitoatenodurile care pot fi alesecardcin a arboreluiastfelnctacestasaib un numr minim de frunze. (6p.)0 1 0 0 0 11 0 1 1 1 00 1 0 0 0 00 1 0 0 0 00 1 0 0 0 01 0 0 0 0 0

79. Se considerun arbore G, cu rdcin, memorat cu ajutorulvectorului de tai urmtor:

T=(2,0,4,2,4,7,2). Care dintreurmtoareleafirmaiiesteadevrat? (4p.)

80. Se considerun arbore cu rdcin, cu 100 noduri, numerotate de la 1 la 100.a) Care este numrul de muchii din arbore? (3p.)b) Care este numrul maxim de cicluripe care acestalpoateconine? (3p.)

subiecte neintensiv

1. Pentru reprezentarea unui arbore cu radacin cu 9 noduri, etichetate cu numere naturale dela 1 la 9, se utilizeaz vectorul de tai: T=(5,0,2,7,3,3,2,4,7).a) Care este lungimea maxim a unui lan elementar care leag dou noduri oarecare dinacest arbore? (3p.)b) Care sunt extremitile acestui lan?

2.Care este vectorul de tati asociat arborelui curadacina din figura alaturata n care nodul 1 este nodul radacina?

1 / \ 2 3 / \ 4 5 / \ 6 7

3.Care este vectorul de tati asociat arborelui cu radacina dinfigura alaturata n care nodul 5 este nodul radacina? 2 / |\ 3 5 1 | 4

4. Se considera arborele cu 12 noduri, numerotate de la 1 la 12, definit prin urmatorul vectoride tati: (4, 8, 0, 3, 10, 1, 8, 3, 2, 4, 7, 10). Care dintre nodurile arborelui au exact undescendent direct (fiu)? (4p.)a. 6, 9, 11 b. 1, 2, 7 c. 5, 12, 6, 9, 11 d. 10, 1, 2, 7