1. Dana jest struktura algebraiczna dwusortowa 
                                   <{1,2,...,n}+ P({1,2,...,n}); add, supr; empty, mb>,

w której operacje są określone  następująco: dla dowolnego zbioru XÎP({1,2,...,n}) oraz dowolnego i Î{1,2,...,n}

•  add(i,X) = X È {i}

•  supr(X) = zbiór, który powstaje z X przez usunięcie elementu najstarszego, ze względu na porządek w jakim zostały dołączone do zbioru X

•  empty(X) = true wttw X jest pusty

•  mb(i,X)=true wttw i należy do X

    Zaproponuj taką implementację tej struktury, by wszystkie operacje mogły być zrealizowane z kosztem stałym O(1).

Wskazówka: Tablica booleowska + lista .

2. Zaproponuj implementację struktury danych   <E+L; add,supr,min,cut>,  która pozwala na wykonywanie następujących operacji na listach

•  add - dołącz element na początek listy, add: L × E ® L

•  supr - usuń pierwszy element listy, supr: L ® L

•  min - podaj najmniejszy element listy,  min: L  ® E

•  cut - usuń element najmniejszy i wszystkie elementy dołączone po nim do listy, cut : L ® L,

tak by wszystkie operacje były wykonywane z kosztem stałym O(1).

Wskazówka: Dwa stosy: stos elementów listy + stos elementów minimalnych

3. Zaproponuj strukturę danych, która pozwala wykonywać następujące operacje z kosztem stałym:

• new - utworzyć pustą listę

• add – dołączyć nowy element na początku  danej listy, add : L × E ® L

• inject  -  dołączyć nowy element na końcu danej listy, inject : L × E ® L

• pop – usunąć pierwszy element listy, pop : L  ® L

• eject  – usunąć ostatni element listy, eject: L ® L

• merge – połączenie dwóch list, merge: L × L ® L

• inverse – utworzyć listę z odwrotnym porządkiem elementów, inverse:  L ® L

Wskazówka: Lista dwukierunkowa z dwoma wskaźnikami na początek i koniec oraz parametrem kierunek listy.

4. Zaproponuj implementację struktury kolejek FIFO w strukturze stosów, tzn.  podaj algorytmy wykonywania operacji na kolejkach, jeśli do dyspozycji mamy tylko stosy i operacje na nich (top, pop, push, empty) oraz możliwość utworzenia nowego pustego stosu.
    

5. Zaproponuj implementację struktury stosów w strukturze kolejek FIFO, tzn.  podaj algorytmy wykonywania operacji na stosach posługując się jedynie obiektami typu kolejka i operacjami in, out, first, empty  charakterystycznymi dla struktury FIFO.
    

6. „Koło graniaste”. Dzieci stoją w kole i wypowiadają kolejno słowa pewnej wyliczanki. Dziecko, które wypowiada ostatnie słowo, odchodzi z koła. Zabawa jest kontynuowana począwszy od następnego w kolejności dziecka.

   • Zaproponuj strukturę danych pozwalającą opisać sytuację w tej zabawie.
   • Napisz algorytm, który dla danego zbioru dzieci i wyliczanki wyznacza kolejność ich odchodzenia z koła.

    

    

    

    

 

« poprzedni punkt

następny punkt »