Exerciții SDA

De la WikiLabs

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ă;

Funcții Hash