Exerciții SDA

Vectori

1. Realizați un program care să implementeze o listă inteligentă de valori folosind vectori. Scrieți funcții pentru:
   • adăugarea unui element la sfărșitul listei;
   • adăugarea unui element la o poziție specificată din listă;
   • eliminarea unui element de la o poziție specificată din listă;
   • căutarea unui element în listă;
   • sortarea listei cu un algoritm eficient - O(n*logn);
2. Realizați un program care să implementeze o listă inteligentă de valori sortate folosind vectori (lista trebuie menținută sortată la orice modificare). Scrieți funcții pentru:
   • adăugarea unui element folosind un algoritm eficient - O(logn) pentru identificarea poziției corecte;
   • eliminarea unui element de la o poziție specificată din listă;
   • căutarea unui element în listă folosind un algoritm eficient - O(logn);
3. Realizați o structură de tip coadă (FIFO) de șiruri de caractere folosind vectori. Dimensiunea maximă a cozii este specificată inițial și nu se face realocare. Scrieți funcții pentru:
   • adăugarea unui element în coadă;
   • citirea unui element din coadă;
   • interogarea numărului de elemente din coadă;
4. Realizați o structură de tip stivă (LIFO) de valori de tip float folosind vectori. Dimensiunea maximă a stivei este specificată inițial și nu se face realocare. Scrieți funcții pentru:
   • adăugarea unui element în stivă;
   • citirea unui element din stivă;
   • interogarea numărului de elemente din stivă;
5. Realizați o structură de tip mulțime (set) de elemente de tipul unui struct arbitrar ales, folosind vectori. Implementați mulțimea având în vedere faptul că adăugarea de elemente este mult mai rară decât interogarea. Scrieți funcții pentru:
   • adăugarea unui element în mulțime;
   • interogarea mulțimii pentru a afla dacă un element specificat este sau nu conținut în mulțime;
6. Realizați o structură de tip asociativ (map) de elemente de tipul unui struct arbitrar ales, folosind vectori. Implementați mulțimea având în vedere faptul că adăugarea de elemente este mult mai rară decât interogarea. Scrieți funcții pentru:
   • adăugarea unei perechi [cheie, valoare] în map;
   • căutarea unei valori după cheie;
7. Pentru exercițiul 1 de mai sus, realizați funcții pentru toți algoritmii cunoscuți de sortare.
8. Dându-se o imagine memorată într-o matrice de valori pe 16 biți, reprezentând valorile de luminanță pentru fiecare pixel, calculați histograma imaginii (de câte ori apare fiecare valoare de luminanță în imagine). Dimensiunea imaginii și luminanțele pixelilor se citesc din fișier.

Liste simplu și dublu înlănțuite

1. Realizați un program care să implementeze o listă inteligentă de valori folosind înlănțuirea dublă. Scrieți funcții pentru:
   • adăugarea unui element la sfărșitul listei;
   • adăugarea unui element la o poziție specificată din listă;
   • eliminarea unui element de la o poziție specificată din listă;
   • căutarea unui element în listă;
   • sortarea listei cu un algoritm eficient - O(n*logn);
   • printarea valorilor din listă pe ecran folosind o funcție iterativă;
2. Realizați un program care să implementeze o listă inteligentă de valori sortate folosind înlănțuirea simplă (lista trebuie menținută sortată la orice modificare). Scrieți funcții pentru:
   • adăugarea unui element folosind un algoritm eficient - O(logn) pentru identificarea poziției corecte;
   • eliminarea unui element de la o poziție specificată din listă;
   • căutarea unui element în listă;
   • printarea valorilor din listă pe ecran folosind o funcție recursivă;
3. Realizați o structură de tip coadă (FIFO) de șiruri de caractere folosind înlănțuirea simplă. Nu există o dimensiune maximă a cozii. Scrieți funcții pentru:
   • adăugarea unui element în coadă;
   • citirea unui element din coadă;
   • interogarea numărului de elemente din coadă;
4. Realizați o structură de tip stivă (LIFO) de valori de tip float folosind înlănțuirea simplă. Nu există o dimensiune maximă a stivei. Scrieți funcții pentru:
   • adăugarea unui element în stivă;
   • citirea unui element din stivă;
   • interogarea numărului de elemente din stivă;
5. Realizați o structură de tip mulțime (set) de elemente de tipul unui struct arbitrar ales, folosind înlănțuirea simplă. Scrieți funcții pentru:
   • adăugarea unui element în mulțime;
   • interogarea mulțimii pentru a afla dacă un element specificat este sau nu conținut în mulțime;
6. Realizați o structură de tip asociativ (map) de elemente de tipul unui struct arbitrar ales, folosind înlănțuirea simplă. Scrieți funcții pentru:
   • adăugarea unei perechi [cheie, valoare] în map;
   • căutarea unei valori după cheie;

Funcții Hash

1. Definiți un struct arbitrar oarecare și definiți o funcție Hash și o funcție care să compare două variable de tipul acestui struct.
2. Folosind funcțiile de la exercițiul 1, implementați pentru struct-ul de mai sus un hash set care să se încadreze în 512MB de memorie când este gol.
3. Folosind funcțiile de la exercițiul 1, implementați pentru struct-ul de mai sus un hash map care să se încadreze în 512MB de memorie când este gol.

Arbori

1. Folosind un arbore binar, realizați o structură de tip mulțime (tree set) pentru valori de 8 biți, în felul următor:
   • cei doi copii ai unui nod sunt "0" și "1" reprezentând bitul din valoare de pe poziția corespunzatoare nivelului din arbore. Spre exemplu, valoarea 150, care în binar este 10010110, va avea, din rădacină, ruta 0 - 1 - 1 - 0 - 1 - 0 - 0 - 1 (de la cel mai puțin semnificativ bit la cel mai semnificativ - adică de la dreapta la stânga).
2. Folosind conceptul de la punctul 1, realizați, folosind un arbore binar, o structură de tip asociativ (tree map), cu cheia fiind o valore numerică pe 8 biți.

Backtracking

1. Dându-se un număr de N orașe și a drumurilor dintre ele memorate într-o matrice MAT de NxN, astfel încât MAT[i][j] este 1 dacă există drum între orașul i și k și 0 dacă nu există, se cere o rută pentru un comis-voiajor care să treacă prin toate orașele o singură dată.
2. Să se genereze toate perumările de N numere, cu N dat de la tastatură.