O companie organizează cursuri de programare în limbaje din mulțimea {PHP, Java, Python, C#, SQL}
, astfel încât o persoană poate opta pentru un curs în care se studiază un număr par de limbaje, dar nu poate alege Java și Python în același curs.
Utilizând metoda backtracking se generează toate posibilitățile unei persoane de a opta pentru un curs în cadrul ofertei companiei. Două cursuri sunt distincte dacă diferă prin cel puțin un limbaj sau prin ordinea în care se studiază limbajele. Primele cinci soluții generate sunt, în această ordine: (PHP,Java)
, (PHP,Java,C#,SQL)
, (PHP,Java,SQL,C#)
, (PHP,Python)
, (PHP,Python,C#,SQL)
.
Soluția generată imediat după (Java,PHP,SQL,C#)
este:
Varianta 1 |
|
Varianta 2 |
|
Varianta 3 |
|
Varianta 4 |
|
Un graf orientat este complet dacă pentru oricare două vârfuri i
și j
ale sale există fie ambele arce (i,j)
și (j,i)
, fie doar unul dintre acestea.
Un graf orientat are 5
vârfuri și 20
de arce. Pentru a obține un graf parțial al său cu două componente tare conexe, fiecare dintre acestea fiind grafuri complete, unul cu 3
vârfuri, iar celălalt cu 2
vârfuri, numărul minim de arce care pot fi eliminate este:
Varianta 1 |
2 |
Varianta 2 |
3 |
Varianta 3 |
6 |
Varianta 4 |
10 |
Un arbore cu 8
noduri, numerotate de la 1
la 8
, este reprezentat prin matricea de adiacență de mai jos.
0 1 1 1 0 0 0 0 1 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0
Care dintre următoarele mulțimi conține doar noduri care pot fi alese drept rădăcină astfel încât fiecare nod să admită cel mult doi descendenți direcți (fii).
Varianta 1 |
|
Varianta 2 |
|
Varianta 3 |
|
Varianta 4 |
|
Utilizând metoda backtracking, se generează toate posibilitățile de a forma seturi de câte 5
instrumente de scris distincte din mulțimea {stilou, pană, toc, creion, pensulă}
, astfel încât în fiecare set creionul precede stiloul și pana. Două seturi sunt distincte dacă instrumentele sunt dispuse în altă ordine.
Primele cinci soluții generate sunt, în această ordine, (toc, creion, stilou, pană,
pensulă)
, (toc, creion, stilou, pensulă, pană)
, (toc, creion, pană, stilou,
pensulă)
, (toc, creion, pană, pensulă, stilou)
, (toc, creion, pensulă, stilou,
pană)
.
Care dintre următoarele reprezintă cea de a șasea și cea de a șaptea soluție, în ordinea generării acestora?
Varianta 1 |
|
Varianta 2 |
|
Varianta 3 |
|
Varianta 4 |
|
Utilizând metoda backtracking, se generează toate posibilitățile de a forma seturi de câte 5
instrumente de scris distincte din mulțimea {stilou, pană, toc, creion, pensulă}
, astfel încât în fiecare set creionul precede stiloul și pana. Două seturi sunt distincte dacă instrumentele sunt dispuse în altă ordine.
Primele cinci soluții generate sunt, în această ordine, (toc, creion, stilou, pană, pensulă)
, (toc, creion, stilou, pensulă, pană)
, (toc, creion, pană, stilou, pensulă)
, (toc, creion, pană, pensulă, stilou)
, (toc, creion, pensulă, stilou, pană)
.
Care dintre următoarele reprezintă ultima soluție generată?
Varianta 1 |
|
Varianta 2 |
|
Varianta 3 |
|
Varianta 4 |
|
Care este numărul minim de arce pe care trebuie să le conțină un graf orientat cu 5 noduri astfel încât, oricum ar fi acestea plasate, să existe cel puțin un drum între oricare două noduri?
Varianta 1 |
20 |
Varianta 2 |
13 |
Varianta 3 |
17 |
Varianta 4 |
5 |
Care este numărul minim de muchii pe care trebuie să le conțină un graf neorientat cu 9 vârfuri astfel încât, indiferent de modul în care acestea sunt dispuse, graful să fie conex?
Varianta 1 |
35 |
Varianta 2 |
29 |
Varianta 3 |
36 |
Varianta 4 |
8 |
Utilizând metoda backtracking, se generează toate drapelele formate din câte 3
culori distincte din mulțimea {alb, galben, negru, roșu, verde}
. Două drapele sunt distincte dacă diferă prin cel puțin o culoare sau prin ordinea culorilor. Primele patru soluţii obţinute sunt, în această ordine: (alb, galben, negru)
, (alb, galben, roșu)
, (alb, galben, verde)
și (alb, negru, galben)
.
Indicați soluția generată imediat înainte de (galben, verde, alb)
.
Varianta 1 |
|
Varianta 2 |
|
Varianta 3 |
|
Varianta 4 |
|
Un graf neorientat cu 8
noduri, numerotate de la 1
la 8
, are muchiile [1,2]
, [1,6]
, [4,6]
, [3,6]
, [6,5]
, [5,3]
, [3,4]
, [7,8]
, [8,2]
. Trei noduri care nu aparţin niciunui ciclu în acest graf pot fi:
Varianta 1 |
|
Varianta 2 |
|
Varianta 3 |
|
Varianta 4 |
|
Un arbore cu 19
noduri, numerotate de la 1
la 19
, are ca rădăcină nodul numerotat cu 1
; nodul 1
are un singur fiu, și anume nodul 2
, iar fiecare nod i
(i≥2
) fie este frunză, fie are drept fii (descendenți direcți) noduri numerotate cu valori din intervalul [i+1,2·i-1]
. Numărul maxim de frunze ale arborelui este:
Varianta 1 |
|
Varianta 2 |
|
Varianta 3 |
|
Varianta 4 |
|