Subiectul al II-lea, 2., toate variantele

Variabilele s și t permit memorarea câte unui șir de maximum 20 de caractere. Scrieți valorile afișate în urma executării secvenței C/C++ alăturate. (6p.)

strcpy(s,"anatoliana"); strcpy(t,"ana"); cout<<strlen(s)<<' '; | printf("%d ",strlen(s)); if(strstr(s,t)==s) cout<<"DA "; | printf("DA "); else cout<<"NU "; | printf("NU "); if(strcmp(strstr(s+1,t),t)==0) cout<<"DA"; | printf("DA"); else cout<<"NU"; | printf("NU");

Utilizând metoda backtracking se generează toate seturile de câte cel mult trei materiale de promovare turistică din mulțimea ordonată {broșură, ghid, pliant, revistă}, astfel încât din același set să nu facă parte simultan un pliant și o revistă. Două seturi sunt distincte dacă diferă prin cel puțin un material. Primele cinci soluții generate sunt, în această ordine, (broșură), (broșură, ghid), (broșură, ghid, pliant), (broșură, ghid, revistă), (broșură, pliant). Scrieți a șasea și a șaptea soluție generată. (6p.)

Un arbore cu 8 noduri, numerotate de la 1 la 8, este reprezentat prin vectorul de „tați” (3, 0, 2, 5, 2, 5, 1, 5). Enumerați două noduri ale arborelui care pot fi alese drept rădăcină (cu excepția rădăcinii curente), astfel încât nodul 4 să aibă aceiași „frați” ca în reprezentarea dată. (6p.)

Un graf neorientat cu 6 noduri, numerotate de la 1 la 6, este reprezentat prin listele de adiacență alăturate. Scrieți mulțimea nodurilor și mulțimea muchiilor unui subgraf al acestuia, fără noduri izolate, care să fie graf eulerian. (6p.)

1: 2, 3, 4, 6 2: 1, 3, 5 3: 1, 2, 5 4: 1, 5, 6 5: 2, 3, 4, 6 6: 1, 4, 5

Subprogramul f este definit alăturat. Scrieți valorile f(3,9) și f(1,1000). (6p.)

int f(int x,int y) { if(x*5>y/5) return x; return f(x*5,y/5); }

Un graf neorientat cu 6 noduri, numerotate de la 1 la 6, are muchiile [1,2], [2,3], [2,4], [2,5], [4,5], [4,6], [5,6]. Scrieți listele de adiacență ale unui graf parțial al său care să fie conex și fără cicluri. (6p.)

Enumerați, în ordinea parcurgerii lor, nodurile celui mai lung lanț elementar care are extremitatea inițială în rădăcină. (6p.)

Utilizând metoda backtracking, se generează toate buchetele formate din câte trei flori distincte din mulțimea ordonată astfel: {trandafir, crin, gerbera, iris, eustoma, orhidee, zambilă}; în același buchet crinul nu poate fi împreună cu eustoma sau cu zambila. Două buchete diferă prin cel puțin o floare. Primele cinci soluții sunt, în ordinea generării: (trandafir, crin, gerbera), (trandafir, crin, iris), (trandafir, crin, orhidee), (trandafir, gerbera, iris), (trandafir, gerbera, eustoma). Scrieți două soluții, una generată imediat înainte, iar cealaltă generată imediat după (crin, gerbera, orhidee). (6p.)

Un arbore cu 8 noduri, numerotate de la 1 la 8, este reprezentat prin vectorul de „tați” (0,1,1,2,2,4,5,1). Enumerați toți descendenții nodului numerotat cu 2. (6p.)

Utilizând metoda backtracking, se generează toate amestecurile de apă provenită din surse distincte din mulțimea {lac, mare, ocean, ploaie, râu}, astfel încât o sursă să fie de apă sărată și una sau două surse să fie de apă dulce. Marea și oceanul sunt surse de apă sărată, iar lacul, ploaia și râul sunt surse de apă dulce. Două amestecuri sunt distincte dacă diferă prin cel puțin o sursă a apei. Primele patru soluții obținute sunt, în această ordine: (lac, mare), (lac, mare, ploaie), (lac, mare, râu) și (lac, ocean). Scrieți soluția generată imediat înainte și soluția generată imediat după (ocean, ploaie). (6p.)

Un arbore cu 6 noduri, numerotate de la 1 la 6, are muchiile [1,2], [2,3], [2,6], [3,4], [3,5]. Scrieți nodurile care pot fi desemnate ca rădăcină, astfel încât fiecare dintre arborii obținuți să aibă un număr minim de niveluri. (6p.)

Un graf neorientat cu 6 noduri, numerotate de la 1 la 6, are muchiile [1,2], [1,3], [1,4], [1,5], [2,3], [2,4], [2,5], [3,5], [4,6], [5,6]. Scrieți mulțimea muchiilor unui subgraf al acestui graf, care să fie complet și să aibă un număr maxim de noduri. (6p.)

Subprogramul f este definit alăturat. Scrieți două valori din intervalul [2000,2025] pentru variabila întreagă x, astfel încât, pentru fiecare dintre acestea, f(2022,x) să aibă valoarea 2022. (6p.)

Un arbore cu 9 noduri, numerotate de la 1 la 9, are muchiile [1,8], [2,3], [2,5], [2,7], [4,5], [5,6], [5,8], [8,9]. Scrieți două noduri care pot fi alese drept rădăcină, astfel încât nodul 5 să aibă doi “frați”. (6p.)

Subprogramul f este definit alăturat. Scrieți ce valori au f(2), respectiv f(21). (6p.)

Utilizând metoda bactracking se generează toate grupurile de cel puțin două păsări cântătoare din mulțimea {cinteză, ciocârlie, mierlă, privighetoare, scatiu}, astfel încât mierla și privighetoarea să nu fie în același grup. Două grupuri diferă prin cel puțin o pasăre. Primele patru soluții generate sunt, în această ordine: (cinteză, ciocârlie), (cinteză, ciocârlie, mierlă), (cinteză, ciocârlie, mierlă, scatiu), (cinteză, ciocârlie, privighetoare). Scrieți următoarele două soluții generate imediat după (ciocârlie, privighetoare, scatiu). (6p.)

Scrieți șirul memorat prin intermediul variabilei s în urma executării secvenței alăturate. (6p.)

Un arbore cu 9 noduri, numerotate de la 1 la 9, are muchiile [1,2], [2,8], [2,9], [3,6], [4,6], [5,8], [6,8], [7,8]. Scrieți două noduri care pot fi alese drept rădăcină, astfel încât nodul 8 să aibă doi “frați”. (6p.)

Un graf neorientat, fără cicluri, are 26 de muchii și două componente conexe. Pentru fiecare dintre cele două componente, scrieți un exemplu de număr de noduri, respectiv de număr de muchii. (6p.)

Lacătul unei biciclete are un cifru format din 5 cifre distincte, astfel încât oricare două cifre alăturate au parități diferite. Pentru că a uitat cifrul, Andrei încearcă toate soluțiile posibile, pe care le generează în ordine lexicografică, utilizând metoda backtracking. Două cifruri diferă prin cel puțin o cifră sau prin ordinea acestora, primele șase fiind, în ordinea generării: 01234, 01236, 01238, 01254, 01256, 01258. Scrieți două soluții, una generată imediat înainte, iar cealaltă generată imediat după 16789. (6p.)

Utilizând metoda backtracking, se generează toate numerele formate din cifre distincte, cifre a căror sumă să fie 6. Primele patru soluții generate sunt, în această ordine: 1023, 1032, 105 și 1203. Scrieți cea de a cincea și cea de a șasea soluție generată. (6p.)

Utilizând metoda backtracking se generează toate grupele de accesorii pentru înot din mulțimea ordonată astfel: {cască, clipsuri pentru nas, costum de înot, dopuri pentru urechi, înotătoare, ochelari, pantofi acvatici, placă}. Accesoriile au prețurile următoare, exprimate în lei: cască - 20, clipsuri pentru nas - 10, costum de înot - 50, dopuri pentru urechi - 20, înotătoare - 150, ochelari - 50, pantofi acvatici - 100, placă - 150. Într-o grupă accesoriile sunt distincte și costă, în total, 200 de lei. Două soluții diferă prin cel puțin un accesoriu. Primele trei soluții generate sunt, în această ordine: (cască, clipsuri pentru nas, costum de înot, dopuri pentru urechi, pantofi acvatici), (cască, clipsuri pentru nas, dopuri pentru urechi, înotătoare), (cască, clipsuri pentru nas, dopuri pentru urechi, ochelari, pantofi acvatici). Scrieți a patra și a cincea soluție obținute, în ordinea generării acestora. (6p.)

Subprogramul f este definit alăturat. Scrieți valoarea f(2), respectiv valoarea f(17). (6p.)

int f(int x) { if (x<=4) return x; else return x-f(x-2); }

Variabila t memorează simultan, pentru un telefon, următoarele date: producătorul (o literă mare a alfabetului englez), frecvența procesorului (număr natural) și dimensiunea, dată prin trei valori, reprezentând lățimea, grosimea și lungimea, în această ordine, în milimetri (numere reale). Știind că expresiile C/C++ de mai jos au ca valori producătorul și lățimea telefonului, respectiv frecvența procesorului acestuia, scrieți definiția unei structuri cu eticheta telefon, care permite memorarea datelor despre un telefon, și declarați corespunzător variabila t.

t.producator t.dimensiune[0] t.frecventa

(6p.)

Un arbore cu 10 noduri, numerotate de la 1 la 10, este reprezentat prin vectorul de „tați” (8,1,4,5,0,9,4,5,4,3). Enumerați toate nodurile arborelui care au câte un singur descendent direct („fiu”). (6p.)

Variabila c, declarată alăturat, permite accesul la datele fiecăreia dintre cele trei echipe participante la ultima etapă a unui concurs: numele și rezultatul (număr natural din intervalul [0,100]); cele trei echipe au rezultate distincte.

struct echipa { char nume[50]; int rezultat; }; struct echipa c[3];

Scrieți o secvență de instrucțiuni în urma executării căreia să se afișeze pe ecran, separate prin câte un spațiu, numele celor trei echipe, în ordinea descrescătoare a rezultatelor obținute. (6p.)

Un arbore cu 7 noduri, numerotate de la 1 la 7, este reprezentat prin vectorul de „tați” (4,1,1,0,7,4,4). Scrieți trei muchii care i se pot adăuga, astfel încât graful obținut să fie eulerian. (6p.)

Un arbore cu 9 noduri, numerotate de la 1 la 9, este reprezentat prin vectorul de „tați” (3, 5, 2, 2, 0, 5, 3, 3, 8). Scrieți numerele asociate nodurilor care sunt descendenți direcți („fii”) ai nodului cu eticheta 3. (6p.)

Într-un arbore cu rădăcină un nod se află pe nivelul x dacă lanțul elementar care are o extremitate în nodul respectiv și cealaltă extremitate în rădăcina arborelui are lungimea x. Pe nivelul 0 se află un singur nod (rădăcina). Un arbore cu rădăcină are 10 noduri și este reprezentat prin vectorul de „tați” (10,5,5,10,0,10,9,2,5,2). Enumerați trei dintre frunzele situate în arbore pe niveluri impare. (6p.)

Utilizând metoda backtracking se generează toate numerele din intervalul [10⁴,10⁵), cu cifrele în ordine strict crescătoare. Primele trei numere generate sunt 12345, 12346, 12347. Scrieți, în ordinea obținerii, ultimele trei numere generate care au prima cifră 4. (6p.)

Un graf neorientat cu 6 noduri, numerotate de la 1 la 6, este reprezentat prin listele de adiacență alăturate. Pentru acest graf scrieți un lanț care să nu fie elementar, precum și un ciclu elementar. (6p.)

1: 2,6 2: 1,4,6 3: 5,6 4: 2,5 5: 3,4,6 6: 1,2,3,5