Algorytmy i struktury danych 

Zagadnienia do ćwiczeń 

 

1.  Konstruowanie algorytmów i ich zapis za pomocą: 

a.  opisu słownego, 
b.  schematu blokowego 
c.  pseudokodu 

2.  Ocena złożoności czasowej algorytmów za pomocą O-notacji (na poziomie idei algorytmu, zapisu za pomocą schematu i 

pseudokodu). 

3.  Analiza metod sortowania (w tym sortowanie stogowe przy zapisie danych w postaci drzewa i w tablicy). 
4.  Analiza metod wyszukiwania (liniowe, połówkowe, haszowanie). 
5.  Operacje na listach w reprezentacji ze wskaźnikami osadzonymi i w reprezentacji tablicowej (Front, Push, Pop, Rear, 

Inject, Eject). 

6.  Przykłady zastosowania stosu (m. in. Notacja Polska i ONP). 
7.  Przykłady zastosowania kolejki (np. sortowanie plików sekwencyjnych). 
8.  Przykłady i reprezentacja grafów (wskaźniki, skorowidze, mapy bitów, macierze sąsiedztwa). 
9.  Zastosowania grafów (np. sterowanie w automacie skończonym, maszynie Turinga). 
10. Rodzaje i reprezentacja drzew (wskaźniki, tablice, uporządkowanie lewolistowe). 
11. Zastosowanie drzew (np. drzewo rozbioru gramatycznego wyrażeń arytmetycznych, drzewa BST w sortowaniu i 

wyszukiwaniu). 

12. Znajdowanie minimalnego drzewa rozpinającego algorytmami Prima i Kruskala. 
13. Generowanie kodu Huffmana algorytmem zachłannym z wykorzystaniem drzewa. 
14. Znajdowanie cyklu Eulera w grafach. 
15. Znajdowanie cyklu Hamiltona w grafach. 
16. Znajdowanie najkrótszej ścieżki w grafach (porównanie algorytmu zachłannego z programowaniem dynamicznym). 
17. Analiza problemu komiwojażera. 
18. Zalety i wady rekurencji na przykładzie algorytmów (porównanie algorytmów rekurencyjnych i iteracyjnych): 

a.  silnia, 
b.  liczby Fibonacchiego, 
c.  wieże Hamoi. 

19. Algorytmy tworzenia trójkąta Sierpińskiego i innych fraktali.