Algorytmy i struktury danych - przykładowe zadania egzaminacyjne

1. Podaj definicję algorytmu

2. Podaj podstawowe elementy analizy algorytmów

3. Podaj definicję algorytmu poprawnego semantycznie

4. Podaj definicje i wyjaśnij pojęcia czasowej złożoności obliczeniowej: pesymistycznej, optymistycznej i oczekiwanej

5. Podaj oszacowania następujących funkcji używając notacji O:

1. f(n) = .....................

6. Podaj sposoby rozwiązywania rekurencji

7. Rozwiąż następujące równania rekurencyjne: ....................

8. Udowodnij przez indukcję poprawność następującego rozwiązania: ................. dla rekurencji ............

9. Dla algorytmu sortowania ..............(przez wstawianie, przez scalanie, szybkie):

1. zapisz algorytm (wraz z procedurami pomocniczymi: ....................(scalanie, dzielenie)) w pseudojęzyku (lub wybranym języku programowania)

2. przeprowadź analizę złożoności obliczeniowej (czasowej i pamięciowej)

3. zilustruj działanie dla przykładowej tablicy 10-cio elementowej

10. Podaj algorytmy operacji push i pop dla tablicowej realizacji stosu

11. Podaj algorytmy operacji dequeue, enqueue dla tablicowej realizacji kolejki

12. Podaj algorytmy dla operacji wstawiania na listę, usuwania z listy i wyszukiwania na liście dla realizacji za pomocą:

1. listy powiązanej pojedynczej liniowej

2. listy powiązanej pojedynczej cyklicznej (z wartownikiem)

3. listy powiązanej podwójnej liniowej

4. listy powiązanej podwójnej cyklicznej (z wartownikiem)

13. Podaj definicje grafów:

1. skierowanych

2. nieskierowanych

3. spójnych

4. acyklicznych

14. Dla podanego grafu przedstaw jego reprezentacje za pomocą:

1. list sąsiedztwa

2. macierzy sąsiedztwa

15. Podaj algorytm przechodzenia grafu wszerz i zilustruj jego działanie na podanym przykładzie, tworząc drzewo przechodzenia grafu wszerz

16. Podaj algorytm przechodzenia grafu w głąb i zilustruj jego działanie na podanym przykładzie, wypisując wierzchołki w kolejności „przed”-preorder i „po”-postorder

17. Podaj definicję drzewa i drzewa binarnego

18. Podaj własności drzew charakteryzujące liczbę wierzchołków i krawędzi drzewa

19. Wyjaśnij pojęcia:

1. wierzchołek wewnętrzny

2. głębokość wierzchołka

3. wysokość wierzchołka i wysokość drzewa

20. Podaj definicję drzewa przeszukiwań binarnych (BST) oraz algorytm (wraz z objaśnieniami poszczególnych kroków) wstawiania elementu do drzewa BST

21. Przedstaw algorytm przeszukiwania drzewa BST w wersji:

1. rekurencyjnej

2. iteracyjnej

22. Zanalizuj złożoność obliczeniową podstawowych operacji na drzewach BST

23. Podaj definicję słownika

24. Podaj algorytm wyszukiwania:

1. liniowego

2. binarnego

25. Przedstaw sposób działania tablicy pomieszanej:

1. z łańcuchowym rozwiązywaniem kolizji

2. z adresowaniem otwartym

26. Zanalizuj złożoność obliczeniową podstawowych operacji dla tablicy pomieszanej:

1. z łańcuchowym rozwiązywaniem kolizji

2. z adresowaniem otwartym

27. Podaj przykłady funkcji mieszających i krótko je scharakteryzuj

---