Subiecte propuse pentru Colocviu SDA

1. Elementele unei mulimi M sunt notate cu litere mici din alfabet. Se citesc perechi de elemente x, y (x, y aparin mulimii M) cu semnificaia c elementul x precede elementul y. S se afieze elementele mulimii M ntr-o anumit ordine, astfel nct pentru oricare elemente x, y cu proprietatea c x precede pe y, elementul x s fie afiat naintea lui y. 2. S se scrie programul care creeaz dou liste ordonate cresctor dup o cheie numeric i apoi le interclaseaz. 3. S se conceap o stuctur dinamic eficient pentru reprezentarea matricelor rare. S se scrie operaii de calcul a sumei i produsului a dou matrici rare. Afiarea se va face in form natural. 4. S se conceap o structur dinamic eficient pentru reprezentarea n memorie a polinoamelor. Se vor scrie funcii de calcul a sumei, diferenei, produsului i mpririi a dou polinoame. 5. Se citete de la tastatur o expresie postfixat corect sintactic. S se scrie programul de evaluare a sa. Expresia conine variabile formate dintr-o liter i operatorii binari +, -, *, /. 6. S se evalueze un arbore care conine n noduri constantele 0 i 1 i operatorii AND, OR, NOT. S se scrie o funcie care determin dac doi arbori binari sunt echivaleni (arborii binari sunt echivaleni dac sunt structural echivaleni i datele corespunztoare nodurilor sunt aceleai). 7. S se scrie un program care transform un arbore binar ntr-o list dublu nlnuit i care folosete funcii de pretty-print (tiprire frumoas) pentru afiare. 8. Arborele genealogic al unei persoane se reprezint astfel: numele persoanei este cheia nodului rdcin i pentru fiecare nod cheia descendentului stng este numele tatlui, iar a descendentului drept este numele mamei. Se citesc dou nume de la tastatur. Ce relaie de rudenie exist ntre cele dou persoane? Se presupune c o familie are doar un singur fiu. 9. S se scrie un program care pentru un arbore binar: interschimb subarborele drept cu cel stng pentru un nod dat; determin nlimea; determin numrul de frunze. 10. S se verifice dac operaia de tergere a unui nod dintr-un arbore de cutare este comutativ (tergerea nodurilor x i y se poate face n orice ordine). 11. S se implementeze operaia de interclasare a doi arbori de cutare. 12. S se scrie o funcie care s verifice dac exist o cale ntre dou noduri date (v, w) ale unui graf orientat G = (V, E). 13. Pentru un graf neorientat dat G = (N, R), s se scrie o funcie care s verifice dac graful este conex sau nu.

albastru nota 8 verde nota 9 rosu nota 10

Subiecte propuse pentru Colocviu SDA

14. S se implementeze algoritmul lui Floyd de gsire a cilor de cost minim din oricare vrf al unui graf neorientat. Se vor afia cile de cost minim ntre dou vrfuri, date de la tastatur. 15. S se afieze frecvena de apariie a literelor dintr-un text utiliznd o tabel de dispersie. 16. Se dau m vectori V1, V2, ... Vm, care conin n1, n2, ... nm elemente, ordonate cresctor dup o cheie. Se interclaseaz vectorii dai, obinndu-se un vector de lungime n1+n2+...+nm elemente, ordonate cresctor. Se tie c interclasarea a doi vectori care conin n1, respectiv n2 elemente necesit un timp proporional cu suma lungimilor lor. S se determine ordinea optim n care trebuie efectuat interclasarea tuturor vectorilor dai. 17. Problema activitilor. Exist o mulime S=1, 2, 3, ..., n de n activiti care doresc s foloseasc o aceeai resurs (de exemplu o sal de clas). Aceast resurs poate fi folosit de o singur activitate la un anumit moment de timp. Fiecare activitate i are un timp de pornire tpi i un timp de terminare tfi (tpi < tfi). Dac este selectat activitatea i, ea se desfoar pe durata [tpi, tfi). Spunem c activitile i i j sunt compatibile dac duratele lor nu se intersecteaz. S se selecteze o mulime maximal de activiti mutual compatibile. 18. Colorarea grafurilor. Fiind dat un graf neorientat G =(X, ), unde X este mulimea format din n noduri, iar este mulimea muchiilor i un numr de m culori, se cere s se determine toate colorrile posibile ale nodurilor grafului folosind cele m culori, astfel nct oricare dou noduri adiacente s fie colorate n mod diferit. 19. Problema ciclului hamiltonian. Se d un graf conex neorientat G =(X, ) prin matricea costurilor pozitive. Se cere s se determine ciclul hamiltonian de cost minim (ciclul hamiltonian este un ciclu simplu care trece prin toate nodurile). 20. Fiind dat o matrice A de n n elemente numere naturale, s se determine cea mai mic sum de n elemente luate din linii diferite i coloane diferite. 21. Un labirint este codificat printr-o matrice de n m elemente ale crui culoare sunt reprezentate prin elemente egale cu 1, situate n poziii consecutive pe o aceeai linie sau coloan, celelalte elemente fiind 0. O persoan se gsete n poziia (i, j) din interiorul labirintului. Se cere afiarea tuturor traseelor de ieire din labirint care nu trec de mai multe ori prin acelai loc. 22. Se consider o mulime format din n elemente numere ntregi. S se genereze toate submulimile acestei mulimi avnd proprietatea c suma elementelor lor este egal cu S. 23. Exist urmtorul joc: pe o linie de cale ferat se afl n vagoane unul lng altul, numerotate cu valori distincte din mulimea 1...n. O macara poate lua k vagoane de pe linie i le poate aeza n partea dreapt, la sfritul irului de vagoane, care apoi prin mpingere ajung din nou unul lng altul, n noua ordine creat dup operaia respectiv. Dndu-se ordinea iniial a vagoanelor, se cere s se determine (dac este posibil) numrul minim de operaii pe care trebuie s le efectueze macaraua pentru ca n final vagoanele s se afle n ordine cresctoare 1, 2, ..., n .

albastru nota 8 verde nota 9 rosu nota 10

Subiecte propuse pentru Colocviu SDA

24. Pe malul unui ru se afl 2n btinai din care n sunt canibali. Acetia doresc s traverseze rul utiliznd o barc care poate transporta cel mult k persoane. Dac pe un mal sau n barc sunt mai muli canibali dect ceilali, atunci canibalii i vor mnca. Cum vor reui s treac toi pe malul opus fr s se mnnce i fr a apela la alte persoane. 25. Pe un pod se afl n capre care vin dintr-un sens, cu n capre care vin din sens opus. Acestea nu se pot ocoli, ns fiecare capr poate sri peste o singur capr din grupul opus i desigur poate avansa dac n faa sa este un spaiu liber. Cum reuesc aceste capre s traverseze podul doar prin cele dou micri posibile (avans i sritur). 26. Fiind dat un vector ce conine elemente de tip ntreg ordonate cresctor, s se scrie o funcie de cutare a unui element dat n vector, returnndu-se poziia sa. 27. Problema turnurilor din Hanoi. Se dau trei tije. Pe una dintre ele sunt aezate n discuri de mrimi diferite, discurile de diametre mai mici fiind aezate peste discurile cu diametre mai mari. Se cere s se mute aceste discuri pe o alt tij, utiliznd tija a treia ca intermediar, cu condiia mutrii a cte unui singur disc i fr a pune un disc de diametru mai mare peste unul cu diametru mai mic. 28. Se dau dou numere naturale A i B i un vector v care conine n numere naturale. S se determine dac se poate trece din A n B, tiind c singurele operaii permise sunt: a) Adunarea la A a oricte numere din vectorul v; a) Scderea din A a oricte numere din vectorul v. Fiecare numr poate fi adunat, respectiv sczut de mai multe ori. Dac rspunsul la ntrebare este afirmativ, se cere numrul minim de operaii prin care se poate trece din A n B. 29. Pe o creang de mr, se afl n mere, fiecare caracterizat prin distana hi n cm de la pmnt pn la poziia n care se afl i prin greutatea sa gi n grame. Un culegtor dorete s culeag o cantitate exprimat n grame ct mai mare de mere. Dup ce este cules un mr ntreaga creang devine mai uoar i se ridic n sus cu x cm. Culegtorul ajunge doar la merele aflate la o nlime mai mic sau egal cu d cm. S se determine greutatea maxim de mere care poate fi culeas i ordinea n care sunt culese merele. Se citesc: n, x, d i (gi, hi) i=1...n. 30. S se gseasc maximul unei funcii f(x) n intervalul [a, b]. 31. Se d un graf neorientat cu n noduri. Se cere s se determine numrul minim de culori necesare pentru a colora nodurile grafului dat, astfel nct dou vrfuri legate printr-o muchie s fie colorate cu culori diferite. 32. Se d un graf neorientat cu n noduri. Se cere s se determine o submulime maxim de noduri cu proprietatea c oricare dou noduri din ea nu sunt legate printr-o muchie. 33. Descriei algoritmul de sortare prin inserare, la care modificai cutarea liniar cu o cutare binar (n cadrul subtabloului din stnga elementului curent). Devine acest algoritm mai performant?

albastru nota 8 verde nota 9 rosu nota 10

Subiecte propuse pentru Colocviu SDA

34. Adaptai algoritmul quick-sort pentru a determina ntr-un ir de lungime n cu elemente ntregi, al mlea mai mic element. 35. S se sorteze un numr de n elemente numerotate de la 1 la n caracterizate prin anumite relaii de preceden notate (j, k), avnd semnificaia c elementul j precede ca ordine elementul k. Sortarea trebuie s aib ca rezultat o list n care oricare element k este devansat de predecesorul su (sortarea topologic). 36. S se descrie algoritmul care realizeaz urmtoarele aciuni specifice unui examen de admitere: - efectuarea calculului mediilor candidailor la examenul de admitere; - repartizarea celor admii dup opiuni (se consider c exist m opiuni, fiecare cu un numr dat de candidai admii) i afiarea listei; - afiarea n ordinea descresctoare a mediilor a tuturor candidailor neadmii. Se consider c examenul const din dou probe, la medii egale (calculate cu dou zecimale, prin trunchiere), departajarea se face dup nota la prima prob (dac egalitatea se menine, se ia n considerare a doua), admindu-se depirea numrului de locuri n caz de egalitate i dup acest criteriu. 37. Exist n puncte: p 1, p 2, ..., p n, toate localizate pe axa X, iar xi este coordonata lui p i. Se presupune ca x1=0 i punctele sunt numerotate de la stnga la dreapta. Aceste n puncte determin n*(n-1)/2 distane (de valori nu neaparat unice), d 1, d 2, ...., d m ntre oricare 2 puncte distincte xi si xj. Problema reconstruciei este urmtoarea: se dau m valori, (sortate n ordine cresctoare), care reprezint setul de distane ntre m=n*(n-1)/2 perechi de puncte. Se cere s se reconstituie coordonatele celor n puncte. 38. S se scrie un program care s gseasc toate variantele, precum i cea optim pentru tierea unui fir de lungime L n pri de lungimi L1, L2, ..., Ln date, n condiiile: a) nu exist nici un fel de restricie n ce privete numrul de buci din fiecare lungime; b) se taie cel mult o bucat de fiecare lungime; c) numrul de buci de fiecare lungime s difere prin cel mult o unitate. 39. Se consider urmtoarea problem de formatare a textului unui paragraf, care este o secven de n cuvinte, c1, c2, ..., cn, de lungimi a1, a2, ..., an, care trebuie afiate pe linii de lungime L. Cuvintele trebuie separate prin spaii, a cror lungime ideal este b, dar spaiile pot fi extinse sau comprimate (dupa comprimare trebuie s rmn totui > 0), astfel nct o linie ce conine cuvintele ci ci+1 ... cj s ocupe exact lungimea L. Pentru fiecare spaiu b' care este este mai mare sau mai mic dect lungimea ideal b, se definete un "grad de urenie" ca fiind |b' - b|. Pentru ntregul paragraf, este de dorit ca suma acestor grade de urenie s fie minim. Se cere s se scrie programul care determin valorile lungimilor spaiilor separatoare astfel nct s se obin o formatare ct mai estetic a textului. 40. S se scrie cte o procedur recursiv pentru: a) transformarea unui ntreg din baza 10 n alt baz dat; b) tiprirea nodurilor unei liste n ordine invers; c) analog cu b), dar pentru elementele unui tablou; d) copierea n ordine invers a liniilor dintr-un fiier text, n altul. 41. Se consider un set de N ntrebri, fiecare avnd un punctaj Pi. S se genereze toate chestionarele coninnd un numr de ntrebri ntre A i B i avnd un punctaj total ntre C i D.

albastru nota 8 verde nota 9 rosu nota 10

Subiecte propuse pentru Colocviu SDA

42. Se consider un triunghi format din n linii, pe fiecare linie i sunt i numere ntregi pozitive, ca n exemplul de mai jos: 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 S se scrie un program care calculeaz cea mai mare sum a numerelor aflate pe un drum care leag vrful de sus al triunghiului cu baza. Drumul este astfel construit nct la fiecare pas se coboar pe diagonal, spre stnga sau spre dreapta. Exemplu: pentru triunghiul de mai sus, drumul cutat este: 7 - 3 - 8 - 7 5 43. Se consider o suprafa caroiat de dimensiune n x n, n care fiecare ptrat are una din culorile: galben, rou, albastru sau verde. Configuraia suprafeei se citete de la tastatur (sau dintr-un fiier). S se determine i s se tipreasc dac exist drumuri (minime) ntre colurile opuse - un drum trebuie s cuprind doar ptrate de aceeai culoare; deplasarea dintr-un ptrat se poate face n oricare din cei opt vecini. 44. Pe un circuit electric trebuie plasate n componente. Plasarea lor se face n n poziii bine determinate, identificate cu numerele 1.. n. Se d o matrice c n care c[i,j] reprezint numrul de conexiuni care trebuie fcute ntre componentele i i j, precum i o matrice d, cu d[p,q] reprezentnd distana ntre punctele p i q. Cablarea const n plasarea fiecrei componente ntr-o anumit poziie. Nu se pot aeza 2 componente n aceeai poziie. Costul cablarii este suma valorilor c[i,j]*d[p,q], unde componenta i a fost plasat n poziia p iar componenta j n poziia q. Se cere s se determine o plasare a componentelor pe poziii astfel nct costul total al cablrii s fie minim. 45. ntre n orae exist o reea de drumuri care permite ca dintr-un ora s se ajung n oricare din celelalte. ntre 2 orae exist cel mult un drum direct, de lungime cunoscut, iar timpul necesar pentru parcurgerea unui drum este proporional cu lungimea sa. Se cere s se realizeze programul pentru determinarea traseului pe care se poate merge ntre dou orae date, ntr-un timp minim. 46. S se scrie un program care s vin n sprijinul alctuirii orarului cursurilor facultative. Exist un numr de N=20 cursuri si M=100 studeni. La nceputul anului, fiecare student i exprim opiunea privind cursurile la care dorete s participe. Un student poate alege un numr oarecare de cursuri (0 ..N), dar n medie numarul cursurilor alese este de 2-3. Problema responsabilului cu alctuirea orarului este de a identifica care sunt cursurile care pot fi programate a se desfura n paralel. Se pot desfura n paralel 2 sau mai multe cursuri, cu condiia s nu existe suprapuneri n orarul nici unui student. Exemplu: N=5, M=6 studentul 1 alege cursurile 1,2 studentul 2 nu alege nimic studentul 3 alege cursurile 1,3 studentul 4 alege cursul 4 studentul 5 alege cursul 4 studentul 6 alege cursul 5 Cursurile care se pot desfura n paralel sunt: (1,4,5) (2,3)albastru nota 8 verde nota 9 rosu nota 10

Subiecte propuse pentru Colocviu SDA

47. S se implementeze un TDA "numere mari". Un "numr mare" este un ntreg care poate avea pn la 200 de cifre. Pentru reprezentarea intern a numerelor se vor folosi iruri de caractere. Asupra acestor numere se definesc operaiile aritmetice (adunare, scdere, nmulire). S se scrie un program care citete 2 numere i realizeaz operaiile aritmetice asupra lor. 48. Un participant la un joc de noroc pornete avnd la start o sum de bani A. La fiecare tur a jocului, juctorul poate pierde sau ctiga o sum n valoare fix B. S se gseasc toate posibilele variante de desfurare a jocului(secvene pierdere - ctig), astfel nct dup N runde, juctorul s aib aceeai sum de bani, A, ca la start. 49. Un ofer dorete s conduc din oraul A n oraul B, ntre care distana este de n * 10 km (n numr ntreg >=1). ncepnd cu punctul de plecare A (inclusiv) exist benzinrii (numerotate ncepnd cu 0) la fiecare 10 km. Maina oferului consum 1 litru de benzin la fiecare 10 km i are o capacitate a rezervorului de c litri (c numr ntreg >=1). oferul are la dispoziie o hart n care este trecut preul la fiecare benzinrie. S se scrie un program care s indice de unde i n ce cantitate trebuie s cumpere oferul benzin pentru a parcurge drumul cu cost minim, i care este acest cost. Programul va afia o singur soluie. Iniial maina nu are benzin n rezervor, iar de la o benzinrie oferul poate cumpra orice cantitate de benzin, n limitele capacitii rezervorului. Exemplu: Fiierul de intrare: 52 2.9 3.1 2.8 3.3 2.9 Ieirea programului: Cumpr 2 l de la benzinria 0 Cumpr 2 l de la benzinria 2 Cumpr 1 l de la benzinria 4 Cost total: 14.3 50. Imaginea unui mozaic se afl ntr-un fiier text, fiecare caracter desemnnd culoarea unei plcue din mozaic. Pentru simplitate, toate plcuele sunt de form ptrat, de aceeai dimensiune, i nu sunt dect dou culori, reprezentate n fiier prin caracterele 0 i 1. Toate liniile fiierului au aceeai lungime i nu depesc 250 caractere. Figurile din imaginea mozaicului sunt formate din grupe de 1 sau mai multe ptrele adiacente, de culoare 1. Plcuele adiacente au cel puin o latur comun cu restul grupului. Scriei un program care s cear, prin dialog de la consol, numele unui fiier (dimensiunea fiierului poate fi orict de mare - peste 100 de linii), i s afieze numrul figurilor gsite n acel fiier. 51. La orele serii, piaa central n form de hexagon regulat a oraului X abund de vizitatori. Atracia o constituie statuile plasate la distane egale i luminate fiecare de un reflector. La ncheierea programului de vizitare, sarcina lui Gogu este de a stinge toate reflectoarele, astfel nct pierderea de energie s fie minim. El pornete din cabina sa, notat 0, aflat lng colul din stnga-sus al pieii, revenind n acelai punct dup stingerea tuturor reflectoarelor. Se poate deplasa numai pe aleile ce leag cabina de prima statuie, respectiv statuile ntre ele. Aleile sunt de lungimi egale, iar parcurgerea uneia se face ntr-o unitate de timp. Poate s treac de mai multe ori pe lng aceeai statuie, la primaalbastru nota 8 verde nota 9 rosu nota 10

Subiecte propuse pentru Colocviu SDA

trecere stingnd reflectorul. Pregtii traseul lui Gogu! Dac exist dou variante cu aceeai energie minim consumat, se va considera soluia care se parcurge ntr-un timp mai scurt. Ca date de intrare, se citesc din fiierul IN.TXT ntregii: pe prima linie numrul N al statuilor de pe o latur a pieii, inclusiv colurile, iar pe linia urmatoare consumurile de energie pe unitatea de timp ale reflectoarelor, in ordinea parcurgerii lor pe linii, de la stanga la dreapta. Se vor afia: timpul T de parcurgere a traseului, pierderea de energie E i traseul urmat (succesiunea statuilor pe lng care se trece).

albastru nota 8 verde nota 9 rosu nota 10