Structuri de date - probleme

Structuri de date - probleme

1. O lista L=(e1, . en) se zice ca este sortata  crescator daca e1 . en. Sa se construiasca o lista sortata pe masura ce se citesc elementele ei de la tastatura. Sa se calculeze functia de operatii f si sa se arate ca f(n)O(n).

2. Scrieti o functie care inverseaza o lista simplu inlantuita dintr-o singura trecere.

3. Scrieti o functie care separa o lista simplu inlantuita in doua liste inlantuite astfel incat nodurile primei liste sa mearga alternant in cele doua liste.

4. Scrieti o functie care sterge un nod dintr-o lista circulara.

5. Scrieti o functie care concateneaza doua liste circulare creand o noua lista circulara.

6. Scrieti o functie care separa o lista circulara in doua subliste circulare continand nodurile ei alternante.

7. Dezvoltati un proiect care implementeaza principalele operatii cu polinoame memorate sub forma de lista:

Adaugare/ scadere a doua polinoame;

Inmultire a doua polinoame;

Inmultire polinom cu scalar

Derivata/integrala unei polinom

Calculul radacinilor reale

Evaluarea polinomului intr-un punct dat

8. Scrieti o functie care numara cate elemente sunt intr-o lista. Care este ordinul functiei de operatii?

Int List_Length(LinkedList*);

Fie X=(x1,..,xn) si Y=(y1, . ,ym) doua liste simplu inlantuite. Scrieti un algoritm care interclaseaza cele doua liste intr-una singura. Care este ordinul functiei de operatii?

10. Dezvoltati un proiect care implementeaza principalele operatii cu liste dublu inlantuite: creare, adaugare, stergere, modificare, cautare, afisare.

11. Consideram operatia XOR (sau exclusiv) definita la nivel binar astfel:

ij=

Sa se arate ca

a (a b)=(a a) b=b

(a b) b=a (b b)=a

Aceste relatii ne ofera o idee de a salva memoria necesara atat legaturii stangi cat si celei drepte (prev si next) din lista dublu inlantuita. Nodurile vor avea doar doua campuri: info si link. Daca L1 este la stanga nodului X si R1 este la dreapta nodului X atunci link(X)=L1R1. Pentru cel mai din stanga nod L1 si pentru cel mai din dreapta nod R1

a) scrieti un algoritm care, pentru o lista dublu inlantuita cu campurile info si link ca mai sus, traverseaza lista de la stanga la dreapta;

b) aceeasi problema pt traversarea inversa.