Sprawdzian ze struktur danych

Poprawna odpowiedź: C

Kolejka działa według zasady FIFO: element dodany najwcześniej wychodzi pierwszy. Pierwsze było 7, więc to ono zostanie pobrane. Odpowiedź 9 pasowałaby do stosu (LIFO), z którego zdejmuje się element dodany jako ostatni.

Poprawna odpowiedź: P, F, F, F

Każdy węzeł ma najwyżej dwoje dzieci, więc liczba węzłów może się podwajać z poziomu na poziom: 1, 2, 4, …, $2^h$. W BST jest odwrotnie: mniejsze wartości idą w lewo, większe w prawo. Kolejka priorytetowa wydaje element o najwyższym priorytecie. Przy wielu kolizjach wyszukiwanie w tablicy haszującej spada nawet do $O(n)$.

Poprawna odpowiedź: (1) stos; (2) 3+4

Algorytm czyta wyrażenie od lewej: liczby odkłada na stos, a po napotkaniu operatora zdejmuje dwie ostatnie, wykonuje działanie i odkłada wynik. Dla 3 4 + zdejmuje 4 i 3 i liczy 3 + 4 = 7. ONP nie potrzebuje nawiasów ani reguł kolejności działań.

Poprawna odpowiedź: 1–D, 2–C, 3–B, 4–A

• 1. Preorder → D. korzeń, lewe poddrzewo, prawe poddrzewo
• 2. Inorder → C. lewe poddrzewo, korzeń, prawe poddrzewo
• 3. Postorder → B. lewe poddrzewo, prawe poddrzewo, korzeń
• 4. Level-order → A. poziom po poziomie od korzenia (BFS)

Przedrostek mówi, kiedy odwiedzamy korzeń: pre- przed poddrzewami, in- pomiędzy nimi, post- po nich. W drzewie BST przejście inorder daje wartości w kolejności rosnącej. Przejście poziomami realizuje się kolejką, tak jak BFS w grafie.

Poprawna odpowiedź: A, B, D, E

Krawędź między u i v wpisuje się w dwóch miejscach macierzy, stąd symetria. Sprawdzenie krawędzi to odczyt jednej komórki. Macierz ma zawsze $V^2$ pól, nawet przy kilku krawędziach, dlatego dla grafów rzadkich oszczędniejsza jest lista sąsiedztwa. Jedynki w wierszu to sąsiedzi danego wierzchołka.