[WikiDyd] [TitleIndex] [WordIndex

Algorytmy i struktury danych

Lista pytań i problemów egzaminacyjnych

Spisane tu zagadnienia sa (jak na razie) nieuporządkowaną, zapisaną w kolejności losowej listą pytań, zadań i problemów do rozwiązania, które (być może w nieco zmodyfikowanej postaci) moga pojawić się na egzaminach - tak pisemnych, jak i ustnych. Zostały tu zestawione jako pomoc dla osób przygotowujących się do egzaminu.

Lista

  1. Co to jest algorytm?

  2. Co to jest dziedzina algorytmiczna?

  3. Co to jest struktura danych?

  4. Co to jest abstrakcyjny typ danych?

  5. Co to jest: tablica, lista liniowa (jdno-, dwukierunkowa), multilista, kopiec, drzewo (binarne), graf, hash, drzewo poszukiwań binarnych - BST, drzewo AVL, drzewo czerwono-czarne?

  6. Co to jest: kontener (kolekcja), zbiór, kolejka (LIFO,FIFO, priorytetowa), stos, słownik (mapa)?

  7. Jak formalnie określamy działanie algorytmu? Co to jest warunek początkowy (alfa) i końcowy (beta)?

  8. Jakie własności algorytmu sprawdzamy przy jego dowodzeniu; w jaki sposób to robimy?

  9. Co to jest niezmiennik pętli? Jak i do czego go wykorzystujemy?

  10. Jak formalnie określamy złożoność obliczeniową algorymu? Notacje wielkiego O, Omega, Theta?

  11. Co to jest najgorszy przypadek? Proszę podać przykład.
  12. Algorytm o złożoności f(n) przetwarza dane o wielkości N w czasie T, jak długo będzie ten algorytm przetwarzał dane o długości k*N? (Zadanie będzie uszczegółowione prze podanie np. f(n) = n^2, N = 10000, T=1 sekunda, k=10)
  13. Proszę podać algorytm wyszukiwania sekwencyjnego. Proszę formalnie udowodnic jego poprawność.

  14. Proszę podać algorytm wyszukiwania metodą bisekcji. Proszę formalnie udowodnic jego poprawność.

  15. Proszę podać algorytm sortowania przez wstawianie. Proszę formalnie udowodnic jego poprawność.

  16. Proszę podać algorytm sortowania szybkiego. Proszę formalnie udowodnic jego poprawność.

  17. Proszę podać algorytm sortowania przez mieszanie. Proszę formalnie udowodnic jego poprawność.

  18. Proszę podać algorytm sortowania przez kopcowanie. Proszę formalnie udowodnic jego poprawność.

  19. Proszę podać algorytm dodawania elementu do kopca. Proszę formalnie udowodnic jego poprawność.

  20. Proszę podać algorytm usuwania elementu z kopca. Proszę formalnie udowodnic jego poprawność.

  21. Proszę podać algorytm wstawiania (usuwania, wyszukiwania) działający na liście liniowej.

  22. Proszę podać algorytm wstawiania (usuwania, wyszukiwania) działający na drzewie poszukiwań binarnych.

  23. Proszę podać koszt obliczeniowy operacji wykonywanych na zbiorze (ADT) zaimplementowanym za pomocą drzewa poszukiwań binarnych

  24. Dlaczego tak nam zależy na wyważaniu BST?
  25. Co to znaczy, że BST jest ściśle wyważone, AVL wyważone, czerwono-czarne?

  26. Na czym polega operacja (lewej/prawej) rotacji węzła BST?

  27. Na czym polega haszowanie (kodowanie kluczy, mieszanie)?

  28. Co to jest funkcja haszująca?

  29. Na czym polega haszowanie modularne, haszowanie przez mnożenie, haszowanie uniwersalne?

  30. Co to jest kolizja (w haszowaniu)?

  31. Na czym polega łańcuchowa metoda rozwiązywania kolizji?

  32. Na czym polega adresowanie otwarte?

  33. Jakie metody haszowania stosujemy w połączeniu z adresowaniem otwartym?
  34. Dlaczego w bibliotece standardowej Javy istnieją dwie implementacje interfejsu Set (Map): HashSet i TreeSet (HashMap i TreeMap)?

  35. Jaka jest złożoność obliczeniowa operacji wykonywanych na zbiorze (słowniku) zaimplementowanym za pomocą hasza (drzewa czerwono-czarnego)?
  36. W jaki sposób możemy zaimplementować kolejkę priorytetową? Proszę podać dwie różne implementacje i porównać je.
  37. Czy drzewo (np. BST) może być zaimplementowane przy pomocy tablicy? Jeśli tak, to dlaczego drzewo jest strukturą danych (skoro może być implementowane w różny sposób)?
  38. Proszę podać najlepszy sposób implementacji następujących ATD: zbiór (posortowany), kolejka (LIFO,FIFO, priorytetowa), stos, słownik (mapa)?

  39. Jaka jest różnica pomiędzy stochastycznym, a słownikowym algorytmem kompresji?

  40. Proszę podać algorytm Huffmana i oszacować jego złożonosć obliczeniową.

  41. Proszę opisać algorytm LZ77 (LZSS, LZ78, LZW, LZC)

  42. Na czym polega algorytm move to front?

  43. Na czym polega transformata Burrowsa-Wheelera?
  44. Proszę omówić algorytm bzip2.
  45. W jaki sposób przechowujemy w pamięci grafy?
  46. Co to jest minimalne drzewo rozpinające (MDR) dla grafu?

  47. Na czym polega algorytm Prima, Kruskala'? Dlaczego są to algorytmy zachłanne?

  48. Proszę podać algorytm przeszukiwania grafu wszerz (w głąb).

  49. Proszę podać algorytm Dijkstry i oszacować jego złożoność obliczeniową.

  50. Proszę podać algorytm Rabina-Karpa, Knutha-Morrisa-Pratta, Booyera-Moore'a, wykorzystujący się automat skończony do wyszukiwania wzorca w napisie.
  51. Co to jest funkcja postfiksowa, prefiksowa?
  52. Dlaczego algorytm Rabina-Karpa jest szybszy od wyszukiwania naiwnego?
  53. Co to jest problem NP-zupełny?

CDN


2015-09-23 06:32