Karol J. Piczak
  • Kontakt
  • Dydaktyka
    • Prace dyplomowe
    • 2021L-ZZSN - projekty
    • 2020Z-ARKO - ćwiczenia
    • 2020L-AISDI - laboratoria
    • 2019Z-AISDI - ćwiczenia
      • Kolokwium
      • Prezentacje
      • Zadanie domowe #1
      • Zadanie domowe #2
      • Zadanie domowe #3
      • Zadanie domowe #4
    • 2019Z-AISDI - laboratoria
      • Instrukcja - GitLab
  • Linki
    • Zapisy na konsultacje
    • GitLab wydziałowy
    • Materiały na GitHub
  • Admin
    • Edit on GitBook
Powered by GitBook
On this page
  • Ćwiczenia 1
  • 1.1 Tablica, std::array, std::vector
  • 1.2 Lista jedno- i dwukierunkowa
  • 1.3 Kolejka (FIFO), stos (LIFO)
  • 1.4 Binarne drzewo poszukiwań (BST)
  • Ćwiczenia 2
  • 2.1 Algorytmy sortowania
  • Ćwiczenia 3
  • 3.1 Drzewa
  • Ćwiczenia 4
  • 4.1 Kopce
  1. Dydaktyka
  2. 2019Z-AISDI - ćwiczenia

Kolokwium

Zakres materiału obowiązującego na kolokwium

Previous2019Z-AISDI - ćwiczeniaNextPrezentacje

Last updated 5 years ago

Ćwiczenia 1

Przykłady implementacji struktur listowych dostępne są w .

1.1 Tablica, std::array, std::vector

  • podstawowe operacje na tablicy/wektorze i ich złożoność:

    • dostęp,

    • wstawianie elementu (na końcu/w środku),

    • usuwanie elementu (z końca/ze środka),

    • wyszukiwanie elementu o określonej wartości

  • różnica między std::vector::size() a std::vector::capacity(),

  • wykorzystanie iteratorów

1.2 Lista jedno- i dwukierunkowa

  • podstawowe operacje na liście i ich złożoność:

    • dostęp,

    • wstawianie elementu,

    • usuwanie elementu,

    • wyszukiwanie elementu o określonej wartości

  • wyszukiwanie ze strażnikiem

Ogólne:

Wykorzystanie strażnika:

Wizualizacje:

Dany jest następujący szkielet klasy listy jednokierunkowej:

struct Node {
    Node* next;
    int value;
};

class LinkedList {
  public:
    int length;
    Node* head;

    LinkedList();

    void erase_after(int pos);  // usuwa elem. za pozycją pos
    void insert_after(int pos, int value);  // wstawia elem. za pozycją pos
    void pop_front();  // usuwa pierwszy element
    void push_front(int value);  // wstawia element na początek listy
};

Zaimplementuj brakujące metody.

Zaimplementuj metodę, która dla listy jednokierunkowej zwróci trzeci element od końca. Załóż, że długość listy nie jest znana.

Zaimplementuj metodę, która zwróci środkowy element listy jednokierunkowej. Załóż, że długość listy nie jest znana.

Zaproponuj sposób odwracania listy jednokierunkowej w jednym przejściu bez tworzenia kopii wszystkich elementów.

Zaproponuj sposób usuwania węzła mając tylko odwołanie do niego. Załóż, że nie jest to ostatni węzeł listy.

Zaimplementuj uproszczony iterator (tylko operacje -> i ++ ) po elementach listy. Jak wyglądałby taki iterator, gdyby miał zwracać najpierw elementy na rosnących pozycjach nieparzystych listy, a następnie na parzystych?

1.3 Kolejka (FIFO), stos (LIFO)

  • pojęcie abstrakcyjnego typu danych (abstract data type, ADT),

  • kolejka i stos jako przykłady ADT,

  • implementacja funkcjonalności kolejki i stosu na bazie listy dwukierunkowej

ADT:

Wizualizacje:

1.4 Binarne drzewo poszukiwań (BST)

  • drzewo binarne, definicja, podstawowe własności,

  • binarne drzewo poszukiwań (binary search tree, BST):

    • podstawowe operacje i ich złożoność:

      • dostęp,

      • wyszukiwanie elementu,

      • wstawianie elementu,

      • usuwanie elementu

    • przechodzenie po węzłach drzewa:

      • in-order,

      • pre-order,

      • post-order

    • implementacja iteratora dla drzewa

Ogólne:

Przechodzenie drzewa:

Wizualizacje:

Narysuj binarne drzewo poszukiwań utworzone przez wstawienie w kolejności elementów:

31, 72, 23, 44, 85, 106, 17, 28, 9, 30, 41

Zaimplementuj metody wstawiania i wyszukiwania węzła w drzewie BST.

Zaimplementuj rekursywne przechodzenie po węzłach drzewa w kolejności "in-order".

Zaimplementuj uproszczony iterator (tylko operacje -> i ++ ), który będzie przechodził węzły drzewa w kolejności "in-order".

Zaimplementuj w klasie drzewa BST funkcjonalność usuwania węzła o zadanej wartości.

Ćwiczenia 2

2.1 Algorytmy sortowania

Algorytmy:

  • sortowanie przez wybieranie (selection sort),

  • sortowanie przez wstawianie (insertion sort),

  • sortowanie bąbelkowe (bubble sort),

  • sortowanie szybkie (quicksort),

  • sortowanie przez scalanie (merge sort),

  • sortowanie przez kopcowanie (heapsort),

  • sortowanie kubełkowe (bucket sort)

Dla przedstawionych algorytmów:

  • implementacja,

  • złożoność czasowa (najlepsza, średnia, najgorsza),

  • złożoność pamięciowa,

  • stabilność

Ogólne:

Algorytmy:

Wizualizacje:

Ćwiczenia 3

3.1 Drzewa

  • drzewa BST zrównoważone i niezrównoważone,

  • rotacje drzew,

  • drzewa splay:

    • implementacja i złożoność obliczeniowa:

      • operacja splay,

      • wyszukiwanie elementu,

      • wstawianie elementu,

      • usuwanie elementu,

    • zastosowania drzewa splay, zalety i wady

  • drzewa AVL:

    • wysokość, współczynnik wyważenia,

    • operacje równoważenia drzewa AVL,

    • implementacja i złożoność obliczeniowa:

      • wyszukiwanie elementu,

      • wstawianie elementu,

      • usuwanie elementu

Zrównoważenie drzewa BST:

Rotacje:

Drzewa splay:

Drzewa AVL:

Wizualizacje:

Stwórz dwa drzewa BST przez wstawianie w kolejności następujących wartości:

A: 40, 20, 60, 10, 30, 50, 70

B: 10, 20, 30, 40, 50, 60, 70

Porównaj złożoność podstawowych operacji dla obydwu drzew.

Następnie dla drzewa niezrównoważonego B wykonaj kolejno operacje rotacji:

  • L(40)

  • L(30)

  • L(20)

  • L(10)

  • L(20)

Zapis L(R) oznacza rotację lewą, dla której korzeniem jest węzeł o wartości R.

Dane jest drzewo splay o takiej samej strukturze jak drzewo A z zadania 1.

Wykonaj w kolejności następujące operacje:

  • znajdź element o wartości 30,

  • znajdź element o wartości 50,

  • wstaw element o wartości 25,

  • wstaw element o wartości 22,

  • usuń element o wartości 50,

  • usuń element o wartości 25.

Stwórz drzewo AVL przez wstawianie kolejno wartości:

10, 20, 30, 40, 50, 60, 70

Na stworzonym drzewie przeprowadź operacje:

  • wstaw element o wartości 55,

  • wstaw element o wartości 52,

  • usuń element o wartości 52,

  • usuń element o wartości 70.

Ćwiczenia 4

4.1 Kopce

  • kolejka priorytetowa (priority queue, ADT),

  • kopiec binarny:

    • własność kopca min-heap, max-heap,

    • reprezentacja tablicowa kopca (implicit data structure),

    • implementacja i złożoność obliczeniowa operacji:

      • dostęp do najmniejszego elementu,

      • wstawianie nowego elementu,

      • usuwanie najmniejszego elementu,

      • budowa kopca:

        • metoda Williamsa (sukcesywne wstawianie elementów),

        • metoda Floyda (przywracanie własności kopca dla tablicy)

  • kopce d-arne:

    • 3-heap (ternary heap) i 4-heap (quaternary heap),

    • zalety i wady zastosowania arności wyższego rzędu,

  • kopiec dwumianowy:

    • kopiec dwumianowy jako przykład kopca złączalnego (mergeable heap),

    • własności kopca dwumianowego,

    • implementacja i złożoność obliczeniowa operacji:

      • dostęp do najmniejszego elementu,

      • wstawianie nowego elementu,

      • usuwanie najmniejszego elementu,

      • scalanie kopców

  • kopiec Fibonacciego:

    • implementacja i złożoność obliczeniowa operacji:

      • dostęp do najmniejszego elementu,

      • wstawianie nowego elementu,

      • usuwanie najmniejszego elementu,

      • scalanie kopców

Ogólne:

Kopiec binarny:

Kopce d-arne:

Kopiec dwumianowy:

Kopiec Fibonacciego:

Wizualizacje:

Zapisz w reprezentacji tablicowej drzewo binarne następującej postaci:

Dla zapisu tablicowego:

[95, 80, 85, 40, 70, 90, 50, 30, 10, 20]

narysuj zupełne drzewo binarne. Czy drzewo to przedstawia kopiec typu max-heap?

Do pustego kopca binarnego max-heap wstaw w kolejności elementy o wartościach klucza:

43, 24, 11, 47, 13, 67, 59, 95, 29, 17, 54, 40

Następnie trzykrotnie wykonaj operację usunięcia największego elementu z kopca.

Zilustruj stan kopca po każdym kroku.

Z podanej tablicy stwórz kopiec binarny typu max-heap metodą Floyda (przywracanie własności kopca kolejnym poddrzewom):

[2, 7, 26, 25, 19, 17, 1, 90, 3, 36]

Zlicz ilość wykonanych operacji, porównaj z metodą tworzenia kopca przez wstawianie.

Do pustego kopca 3-arnego (ternary heap) typu max-heap wstaw w kolejności elementy o wartościach klucza:

43, 24, 11, 47, 13, 67, 59, 95, 29, 17, 54, 40

Następnie trzykrotnie wykonaj operację usunięcia największego elementu z kopca.

Zilustruj stan kopca po każdym kroku.

Do pustego kopca dwumianowego typu min-heap wstaw w kolejności elementy o wartościach klucza:

43, 24, 11, 47, 13, 67, 59, 95, 29, 17, 54, 40

Następnie trzykrotnie wykonaj operację usunięcia najmniejszego elementu z kopca.

Zilustruj stan kopca po każdym kroku.

Do pustego kopca Fibonacciego typu min-heap wstaw w kolejności elementy o wartościach klucza:

43, 24, 11, 47, 13, 67, 59, 95, 29, 17, 54, 40

Następnie trzykrotnie wykonaj operację usunięcia najmniejszego elementu z kopca.

Zilustruj stan kopca po każdym kroku.

Porównaj stany przejściowe kopca stworzonego na bazie poniższego ciągu operacji:

  • push(43),

  • push(24),

  • push(11),

  • push(47),

  • pop(),

  • push(13),

  • push(67),

  • pop(),

  • push(59),

  • push(95),

  • pop(),

  • push(29),

  • push(17),

  • pop(),

  • push(54),

  • pop(),

  • push(40).

Przykładowe implementacje omawianych algorytmów sortowania dostępne są w .

Przykładowe implementacje omawianych kopców dostępne są w .

Arkusz odpowiedzi dla wersji A kolokwium
Arkusz odpowiedzi dla wersji B kolokwium
Arkusz odpowiedzi dla wersji C kolokwium
Arkusz odpowiedzi dla wersji D kolokwium
Arkusz oceniania dla wersji A/B kolokwium
Arkusz oceniania dla wersji C/D kolokwium
repozytorium z materiałami do przedmiotu
Linked list data structure (Geeks for Geeks)
Sentinel node (Wikipedia)
Using sentinel nodes (Stack Overflow)
List (VisuAlgo)
Queue ADT (Wikipedia)
Stack ADT (Wikipedia)
Queue (VisuAlgo)
Stack (VisuAlgo)
Binary tree (Wikipedia)
Binarne drzewo poszukiwań (Wikipedia)
Binary search tree (Programiz)
Tree traversal (Wikipedia)
Binary search tree iterator (LeetCode)
BST (VisuAlgo)
repozytorium z materiałami do przedmiotu
Sorting algorithm (Wikipedia)
Sorting stability (Wikipedia)
Sorting algorithms (O'Reilly)
Selection sort (w3resource)
Bubble sort (w3resource)
Insertion sort (w3resource)
Quicksort (w3resource)
Merge sort (101computing)
Heapsort (HackerEarth)
Bucket sort (Programiz)
Sorting (sorting.at)
Sorting (VisuAlgo)
Comparison sorting (USF)
Sorting algorithms (toptal)
Bucket sort (USF)
Wyważanie drzewa (Wikipedia)
Tree rotation (Wikipedia)
Drzewo splay (Wikipedia)
Splay tree rotation (Stack Exchange)
Self-Adjusting Binary Search Trees paper (CMU)
Splay trees lecture notes (Berkeley)
AVL tree (Wikipedia)
AVL trees (CodesDope)
Splay tree (USF)
AVL (VisuAlgo)
repozytorium z materiałami do przedmiotu
Priority queue ADT (Wikipedia)
Heap (Wikipedia)
Implicit data structure (Wikipedia)
Binary heap (Wikipedia)
Building a heap in O(n) time (Stack Overflow)
Binary heap (Brilliant)
D-ary heap (Wikipedia)
Binary heap vs d-ary heap (Stack Overflow)
Ternary and quaternary heaps (Stack Overflow)
Binomial heap (Wikipedia)
Binomial heap (Brilliant)
Binomial heap (Growing with the Web)
Fibonacci heap (Wikipedia)
Fibonacci heap (Brilliant)
Fibonacci heap lecture notes (Princeton)
Heap (VisuAlgo)
Heap (USF)
Binomial heap (USF)
Fibonacci heap (USF)