TESTE-GRIL- METODA BACKTRACKING

V41)Utiliznd metoda backtracking, se genereaz numerele naturale formate din exact3 cifre i care au suma cifrelor egal cu
4, n aceast ordine: 103, 112, 121,130, 202, 211, 220, 301, 310, 400. Dac utilizm acelai algoritm pentru agenera toate
numerele de 4 cifre care au suma cifrelor egal cu 7, precizaicare este numarul generat imediat dup 1222.
a)1231 b)1223 c)1213 d)1321
V42)Utiliznd metoda backtracking se genereaz toate permutrile mulimii {1,2,3,4}.Dac primele trei permutri generate
sunt, n acest ordine: 1234, 1243,1324 precizai care este permutarea generat imediat dup 3412.
a)3421 b)3413 c)4123 d)3214
V43)Utiliznd metoda backtracking se genereaz numerele formate din cte 3 cifredistincte din mulimea {1,3,5,7}. Dac
primele trei numere generate sunt, nacest ordine: 135, 137, 153 care este cel de-al patrulea numr generat
a)157b)173c)315d)357
V44)Utiliznd metoda backtracking se genereaz permutrile cuvntului info. Dacprimele trei soluii generate sunt: fino, fion,
fnio care este cea de-a cinceasoluie?
a) foin b) fnoi c) foni d) Ifon
V45) Utiliznd metoda backtracking se genereaz toate cuvintele de cte 3 litere din mulimea {a,b,c}. Dac primele patru
cuvinte generate sunt, n acest ordine:aaa, aab, aac, aba, care este cel de-al optulea cuvnt generat?a.) acb b) acc c) aca d) bca
V46)Un program genereaz, n ordine cresctoare, numerele naturale de exact 5cifre din mulimea {1, 2, 3, 4, 5}. Fiecare
dintre numerele generate are cifrele distincte dou cte dou. Primele 3 numere astfel generate sunt: 12345, 12354, 12435.
Care este numrul generat imediat dup 12543?
a)15342 b)12534 c)13245 d)13452
V47) ntr-un penar sunt unsprezece creioane cu lungimi diferite, dintre care trei sunt roii iarcelelalte sunt negre Dac scoatem
din penar cinci creioane, cte posibilitiexist ca exact dou dintre ele s fie roii?
V48) Se genereaz prin metoda backtracking mulimile distincte ale crorelemente sunt numere naturale nenule i care au
proprietatea c sumaelementelor fiecrei mulimi este egal cu 7. Astfel, sunt generate, n aceastordine, mulimile: {1,2,4},
{1,6}, {2,5}, {3,4}, {7}. Folosind aceeai metod pentru a genera mulimile distincte ale cror elemente sunt numere
naturalenenule i care au proprietatea c suma elementelor fiecrei mulimi esteegal cu 9, stabilii n ce ordine sunt generate
urmtoarele mulimi:M1={2,3,4}; M2={3,6}; M3 ={2,7}; M4={4,5}.
V49)Se genereaz n ordine strict cresctoare numerele de cte ase cifre care conin: cifra 1 singur dat, cifra 2 de dou ori i
cifra 3 de trei ori. Se obin, naceast ordine, numerele:122333, 123233, 123323, , 333221.
Cte numere generate prin aceast metod au prima cifr 1 i ultima cifr 2?
V50)Se genereaz n ordine strict cresctoare toate numerele de cte ase cifrecare conin: cifra 1 o singur data cifra 2 de dou
ori i cifra 3 de trei ori. Se obin,n aceast ordine, numerele: 122333, 123233, 123323, ,333221. Ce numr se genereaz
imediat dupa 332312 ?
V51) Se consider un numr natural nenul, x, avnd exact 8 cifre, distincte doucte dou; printre cifrele sale se gsete i cifra
0. Permutnd cifrele lui x,se obin alte numere naturale. Cte dintre numerele obinute, inclusiv x, au exact 8 cifre?
V52) Utiliznd metoda backtracking, se genereaz n ordine lexicografic toateanagramele cuvntului caiet( cuvinte formate
din acelea i litere, eventual n alt ordine). Cte cuvinte vor figenerate?
a)60b)100c)200d)120
V53)---- V54)Utiliznd metoda backtracking se genereaz n ordine lexicografic toateanagramele cuvntului caiet ( cuvinte
formate din acelea i litere, eventual n alt ordine). Careeste a asea soluie?
a) catei b) actie c) actei d) catie
V55) Utiliznd metoda backtracking se genereaz toate matricele ptratice de ordinul4 ale cror elementeaparin mulimii
{0,1}, cu proprietatea c pe fiecare linie i pe fiecare coloan exist o singur valoare 1. Primele 3 soluii generate sunt, n
aceast ordine:
1000
1000
1000
0100

0100
0010
0010
0001

0100
0001
0010
0001
Care este a opta soluie?
a)0 1 0 0b)0 1 0 0c)0 1 0 0 d)0 0 1 01 0 0 0 1 0 0 0 0 0 1 01 0 0 00 0 0 1 0 0 1 0 1 0 0 00 1 0 00 0 1 0 0 0 0 1 0 0 0 10 0 0 1
V56) Se genereaz toate numerele naturale cu exact 2 cifre nenule. Cte numerese vor genera n total?
a)100b)81c)90d)9
V57) Se utilizeaz metoda backtracking pentru a genera cuvintele de cte patru litere distincte din mulimea {d,a,n,s}. tiind c
primul cuvnt generat este dans,iar al doilea este dasn, care va fi al treilea cuvnt obinut?
a) dnas b) dsan c) dnsa d) dsna
V58)Se utilizeaz metoda backtracking pentru a genera cuvintele de cte treilitere distincte din mulimea {i,n,f,o}. tiind c
primul cuvnt generat este inf, iar aldoilea este ino, care va fi al treilea cuvnt obinut?
a) ino b) ifo c) ifn d) ion
V59)Se utilizeaz metoda backtracking pentru a genera toate cuvintelecare conin toate literele din mulimea {i,n,f,o}, astfel
nct fiecare liter s apar exact o dat ntr-un cuvnt. tiind c primul cuvnt generat este info , iar al doilea este inof, care va
fi al treilea cuvnt obinut?
a) ionf b) inof c.) ifon d) ifno
V60) Se utilizeaz metoda backtracking pentru a genera toate cuvintele careconin toate literele din mulimea {i,n,f,o}, astfel
nct fiecare liters apar exact o dat ntr-un cuvnt; tiind c primul cuvnt generat este info , iar al doilea este inof, care
este ultimul cuvnt obinut?
a) ofni b) oinf c) onif d) ofin
V61) Se genereaza, utiliznd metoda backtracking, toate modalitile derepartizare a n teme de proiecte, numerotate de la 1 la
n, pentru m elevi(n<m), numerotai de la 1 la m, astfel nct fiecare tem s fie rezolvat decel puin un elev. Care este num
rul total de soluii generate pentru m=3 in=2, dac primele 3 soluii generate sunt, n ordine, 1 1 2, 12 1, 1 2 2? Osolutie este
scris sub forma t1, t2, ...,tm, unde ti reprezint tema repartizatelevului i (1im, 1tin).
a)12 b)6 c)4 d)8
V62) Utiliznd metoda backtracking pentru afiarea tuturor modalitilor dedescompunere a unuinumr natural nenul ca o
sum de numere naturalenenule, pentru n=3, se obin n ordine soluiile: 1+1+1; 1+2; 3. Folosindaceeai metod pentru n=4,
care este soluia generat imediat dup1+1+2?
a)1+3 b)1+2+1 c)1+1+1+1 d)2+2
V63)Se genereaza, prin metoda backtracking, toate partiiile mulimiiA={1,2} obinndu-se urmtoarele soluii: {1}{2};{1,2}.
Se observ cdintre acestea, prima soluie e alctuit din exact dou submulimi. Dac sefolosete aceea i metod pentru a
genera partiiile mulimii {1,2,3} stabiliicte dintre soluiile generate vor fi alctuite din exact dou submulimi.
a.) 2 b)1 c)3 d)4
V64) Se genereaz, utiliznd metoda backtracking, toate modalitile deaezare a n ture pe o tabl de ah cu n linii i n coloane,
astfel nct s nuexiste pe tabl ture care se atac ntre ele (dou ture se atac reciprocdac se afl pe aceeai linie sau pe
aceeai coloan). O soluie generat are forma (c1,c2,,cn), unde ci reprezint coloana pe care se afl tura depe linia i. Dac
primele 2 soluii generate pentru n=5 sunt (1,2,3,4,5) i(1,2,3,5,4), care este prima soluie generat n care primul numr este 4?
a)(4, 1, 3, 2, 5) b)(4, 2, 5, 1, 3) c)(4, 3, 5, 3, 1) d)(4, 1, 2, 3, 5)
V65)Se genereaz , utiliznd metoda backtracking, toate modalitile deaezare a numerelor naturale de la 1 la 5, astfel nct
oricare dou numere deaceeai paritate s nu se afle pe pozi ii alturate. Dac primele 3 solu iigenerate sunt, n ordine:
(1,2,3,4,5), (1,2,5,4,3) i (1,4,3,5,2) care esteprima soluie generat ce ncepe cu 3?
a)(3, 2, 1, 4, 5) b)(3, 2, 5, 4, 1) c)(3, 4, 1, 2, 5) d)(3, 4, 5, 2, 1)
V66) Folosind metoda backtracking, s-au generat toate secvenele formate din 3 cifre,fiecare secven generat avnd numai
cifre din mul imea {1,2,3,4}, oricare dou cifre alturatedin secven fiind fie ambele pare, fie ambele impare. Scrie i
secvena carelipse te din ir 111, 113, 131, 133, 311, 313, 331, 333, 224, 242, 244, 422, 424, 442, 444
V67) Folosind metoda backtracking, s-au generat toate secven ele formate din 3 cifre,fiecare secven generat avnd numai
cifre din mul imea {1,2,3,4} , oricare dou cifre alturate din secven fiind fie ambele pare, fie ambele impare.
Scrieisecvena care lipsete din ir : 111, 113, 131, 133, 311, 313, 331, 333, 222, 224, 242, 244, 424, 442, 444
V70) Folosind metoda backtracking, s-au generat toate secven ele formate din 3 cifre,fiecare secven generat avnd numai
cifre din mul imea {1,2,3,4}, oricare doucifre alturate din secven fiind fie ambele pare, fie ambele impare. Scrieisecvena
care lipsete din ir : 111,113,131,133,311,313,331,333,222,224,242,244,422,424,442
V71) Se genereaz n ordine cresctoare toate numerele de exact 4 cifre care sepot forma cu elementele mul imii {0,1,2,3,4}.
Primele 8 soluii generate sunt, nordine: 1000, 1001, 1002, 1003, 1004, 1010, 1011, 1012. Care sunt primele trei numere cese
vor genera imediat dup numrul 3443? a)4000, 4001, 4002b)3444, 4443, 4444c)3444, 4444, 4000d)3444, 4000, 4001
V72) Se genereaz n ordine cresctoare toate numerele de 4 cifre, cu cifredistincte, astfel nct diferen a n valoare absolut
dintre prima i ultima, respectiv a doua i a treiacifr este egal cu 2. Primele 11 soluii generate sunt, n ordine: 1023,
1203,1243, 1423, 1463, 1573, 1643, 1683, 1753, 1793, 1863. Care dintreurmtoarele numere se va generaimediat naintea
numrului 9317?
a)9247 b)9357 c)9207 d)8976
V73) Se genereaz n ordine cresctoare toate numerele de 4 cifre, cu cifredistincte, astfel nct diferena n valoare absolut
dintre ultimele dou cifreale fiecrui numr generat este egal cu 2. Primele opt soluii generate sunt,n ordine:1024, 1035,
1042, 1046, 1053, 1057, 1064, 1068. Care dintre urm toarele numerese va genera imediat dup num rul 8975?
a)8979 b)9013 c)8957 d)9024
V74) ntr-un spectacol sunt prezentate cinci melodii numerotate cu 1, 2, 3, 4 i 5. Utiliznd metoda backtracking, se genereaz
toate posibilitile de a le prezenta pe toate,tiind c melodia 2 trebuie prezentat dup melodia 3, nu neaprat pe o
poziieconsecutiv, iar melodia 5 va fi prezentat tot timpul prima. Cte asemeneaposibiliti exist?
a)24b)6c)12d)4V75)----------
V76) Dac se utilizeaz metoda backtracking pentru a genera toatepermutrile de 4 obiecte i primele 5 permut ri generate
sunt, n aceast ordine, 4 3 2 1, 4 3 1 2, 4 2 3 1, 4 2 1 3, 4 1 3 2,atunci a 6-a permutare este:a)3 2 1 4b)3 4 2 1c)1 4 3 2d)4 1 2
3V77) La un concurs sportiv sunt 5 echipe, iar n fiecare echip sunt cte 10 [Link] determin rii tuturor grupelor de
cte 5 elevi, cte unul din fiecareechip, este similar cu generarea tuturor:a. elementelor produsului cartezianb. submul imilor
cu 5 elemente ale mulimii AxAxAxAxA, unde A={1,2,,10}{1,2,,10}c. permut rilor mulimii {1,2,3,4,5} d. parti iilor
mulimii {1,2,,10}
V78) Un program construie te i afieaz elementele produsului cartezianAxBxC pentru mul imile A={1,2,3,4}, B={1,2,3},
C={1,2}. Care dintre urm toarele triplete NU va fi afi at?
a)(3,2,1)b)(1,3,2)c)(1,2,3)d)(2,2,2)
V79) Problema gener rii tuturor codurilor formate din exact 4 cifre nenule, cutoate cifrele distincte dou cte dou , este
similar cu generarea tuturor: a) aranjamentelor de 9 elemente luate cte 4b) permut rilor elementelor unei mulimi cu 4
elemente c) elementelor produsului cartezian AxAxAxA unde A este o mul ime cu 9 elemente d) submultimilor cu 4 elemente
ale mul imii {1,2,3,4,5,6,7,8,9}
V80) O clas de 28 de elevi este la ora de educaie fizic i profesorul dorete s formeze o echip de 4 elevi; ordinea elevilor
n cadrul echipei nu areimportan. Algoritmul de generare a tuturor posibilit ilor de a forma o asfel deechip este similar cu
algoritmul de generare a tuturor:a) aranjamentelor de 28 de elemente luate cte 4 b) combin rilor de 28 de elementeluate cte
4c) parti iilor unei mulimi AxAxAxA, A fiind o mul ime cu 28 de elemented) elementelor produsului cartezianV81) Folosind
cifrele {1,2,3} se genereaz , n ordinea cresctoare a valorii, toatenumerele pare formate din trei cifre distincte. Astfel, se ob
in n ordine, numerele: 132, 312. Folosind aceea i metod, se genereaz numerele pare formate din patru cifre distincte din
mul imea {1,2,3,4}. Care va fi al 4-lea num r generat ?
a)2134b)1432c)2314d)1423
V82) Folosind cifrele {1,2,3} se genereaz , n ordinea cresctoare a valorii, toatenumerele pare formate dintrei cifre distincte.
Astfel se ob in, n ordine, numerele: 132, [Link] aceea imetod, se genereaz numerele pare formate din patru cifre
distincte din mul imea {1,2,3,4}. Care va fi al 5-lea numr generat ?
a)1432 b)2134 c)2314 d)1423
V84)Folosind cifrele {2,3,4} se genereaz , n ordinea cresctoare a valorii, toatenumerele pare formate din trei cifre distincte.
Astfel se ob in, n ordine, numerele: 234,324, 342, 432. Folosind aceea i metod , se genereaz numerele pare formate
dinpatru cifre distincte din mul imea {2,3,4,5}. Care va fi al doilea numr generat?
a)2354b)3254c)5432d)2534
V85) Folosind cifrele {1,2,3} se genereaz , n ordinea cresctoare a valorii, toatenumerele impare formate din trei cifre
distincte. Astfel se ob in, n ordine, numerele: 123, 213, 231, 321. Folosind aceea i metod, se genereaz numerele
impareformate din patru cifre distincte din mul imea {1,2,3,4}. Care va fi al 2-lea num rgenerat ?
a)1423b)1243c)4321d)1234
V86)La examenul de bacalaureat, un elev prime te un test format dintr-un subiect detip I, unul de tip II i unul de tip III.
Stiind c pentru fiecare tip de subiect suntelaborate exact 100 de variante, algoritmul de generare a tuturor posibilit ilor de a
formaun test este similar cu algoritmul de generare a:a) elementelor produsului cartezian b) aranjamentelor c) permut rilor d)
submul imilor
V87) Trei elevi vor s nfiineze o trup de rock format dintr-un chitarist solo, unbasist i un baterist. To i trei tiu s cnte
att la chitar solo, ct i la chitarbas, i se pricep cu toii i la baterie. Algoritmul de generare a tuturor posibilitilor de
aforma trupa estesimilar cu algoritmul de generare a:a) aranjamentelor b) permut rilor c) elementelor produsului cartezian d)
submul imilor
V88) Ionel dore te s ofere cadouri membrilor familiei sale, format din cei doi prini i o sor. Decide s le ofere stilouri de
diferite culori. La magazin existstilouri de 5culoridiferite. Algoritmul de generare a tuturor posibilit ilor de a atribui cte un
stilou fiecruia dintre cei trei membri ai familiei,f r s se repete vreo culoare, este similar cu algoritmul de generare aa)
aranjamentelor b) elementelor produsuluicartezianc) permut rilor d) submul imilor
V89) O clas format din 28 de elevi dorete s trimit la consftuireareprezentanilor claselor colii o delegaie format din 3
elevi. Algoritmul de generare atuturorposibilitilor de a forma o delega ie este similar cu algoritmul de generare a:a) permut
rilor b) aranjamentelor c.) combin rilor d) submul imilor
V90) La un bal mascat magazia colii pune la dispoziia elevilor 10 pelerine, 10mti i 10 p lrii. Algoritmul de generare a
tuturor posibilitilor de a formaun costum format dintr-o p lrie, o masc i o pelerin este similar cualgoritmul de generare
a :a) elementelor produsului cartezian b) aranjamentelor c) permut rilor d) submul imilor
V91)Se genereaz , utiliznd metoda bactracking, numerele cu exact 3 cifredistincte din mul imea {5,1,3}. Dac primele 3
numere generate sunt, n ordine, 513, 531, 153 , care esteurm torul numr generat?
a)351 b) 155 c) 315 d) 135
V92) Avnd la dispozi ie cifrele 0, 1 i 2 se pot genera, n ordine cresctoare,numere care au suma cifrelor egal cu 2. Astfel,
primele 6 soluii sunt 2, 11, 20,101, 110, 200. Folosind acela i algoritm, se genereaz numere cu cifrele 0, 1, 2 i 3 care au
suma cifrelor egal cu 4. Care va fi al 7-lea num r din aceastgenerare?
a) 130 b) 301 c) 220 d) 103
V93) n cte dintre permut rile elementelor mulimii {I,N,F,O} vocala I aparepe prima pozi ie? a)1b)24c)6d)12
V94)Un elev realizeaz un program care citete o valoare natural pentru ovariabil n i apoiafi eaz n fi ierul [Link],
pe prima linie, valoarea lui n, apoi toatepermut rile mulimii {1,2,...,n}, cte o permutare pe cte o linie a [Link]
programul pentru n=3, coninutul fiierului este cel [Link] varula din nou programul i va introduce pentru variabila n
valoarea 5 linii va con inefiierul?
a) 25 b) 24 c) 121 d)721
V95) Un program cite te o valoare natural nenul pentru n i apoi genereaz iafieaz, n ordine cresc toare lexicografic,
toate combinaiile formate din n cifre care aparin mulimii {0,1}. Astfel, pentru n=2, combina iile sunt afiate nurmtoarea
ordine: 00, 01, 10, 11. Dac se ruleaz acest program i se citetepentru n valoarea 6, imediat dup combinaia 011011 va fi afi
at combinaia:
a)100100b)011100c)011111d)100000
V96)Un program cite te o valoare natural nenul pentru n i apoi genereaz iafieaz, ordine descresc lexicografic, toate
combinaiile de n cifrecare aparin mulimii {0,1}. Astfel, pentru n=2, combina iile sunt afiate nurmtoarea ordine: 11, 10,
01, [Link] se ruleaz acest program i se citetepentru n valoarea 8, imediat dup combinaia 10101000 va fi afi at
combinaia:
a)01010111b)10100111c)01010100d)10100100
V97)Se genereaz , utiliznd metoda bactracking, cuvintele cu exact 3litere din mulimea {a,x,c,f,g}. Dac primele patru
cuvinte generate sunt, n ordine, aaa,aax, aac, aaf, scrie i ultimele trei cuvinte care ncep cu litera a , n ordinea n care vor
figenerate. V98) Utiliznd metoda backtracking se genereaz toate submuimile mulimii{3,6,2,5}.Primele ase submulimi
generate sunt, n ordine: {3}, {3,6}, {3,6,2},{3,6,2,5}, {3,6,5}, {3,2}. Care sunt, n ordinea ob inerii, ultimele trei
submulimi,generate dup aceast regul?
V99)Se utilizeaz metoda backtracking pentru a genera toate cuvi ntele formate dindou litere distincte din mu imea
{w,x,z,y} astfel nct niciun cuvnt s nunceap cu litera x i niciun cuvnt s nu conin litera w lng litera [Link] vor
fi generate n ordinea wx , wy, zx, zy, yw, yx, yz. Folosind aceea imetod se gene reaz toate cuvintele de dou litere distincte
din mul imea{w,x,z,y,t} astfel nct niciun c uvnt s nu nceap cu litera x i niciun cuvnt s nuconin litera w lng litera
z. Care este a treia i a patra soluie generat?
V100)Aplicnd metoda backtracking pentru a genera toate permut rile celor n elementeale unei mulimi, o soluie se
memoreaz sub forma unui tablouunidimensional x1,x2,,xn. Dac sunt deja generate valori pentrucomponentele x1,x2,
,xk-1, iar pentru componentacurent , xk (1<k<n), a fost gsit ovaloare convenabil, atunci se ncearc alegerea a) unei noi
valori pentru componenta xk-1 b) unei valori pentru componenta xk+1 c) unei noi valori pentru componenta xk d) unei noi
valori pentru componenta x1