Wyjaśnij krótko (słownie) na czym polega wyszukiwanie binarne -1pkt
podaj optymalny algorytm (w języku C) usuwania dwukierunkowej listy wiązanej - 2pkt
Węzły drzewa BST utworzonego kolejno z liczb: 48, 73, 42, 17, 25, 20, 11, 65, 72 wypisane w porządku postorder (lub inorder)
wymień dwa sposoby rozwiązywania problemu kolizji w tablicy z haszowaniem - 1pkt
wymień po jednym algorytmie sortowania o podanych złożonościach obliczeniowych: O(n), O(nlogn), O(n^2)
jak wyznaczyć spójne składowe w grafie nieskierowanym za pomocą algorytmu BFS
kolejka priorytetowa reprezentowana za pomocą kopca binarnego min po następujących operacjach : insert (7), insert (4) insert (2), insert (8), insert(1), erase () będzie miała postać:
kopiec jest drzewem binarnym, w którym:
klucz lewego syna jest zawsze mniejszy od klucza prawego syna
wszystkie poziomy są zapełnione w całości
klucz prawego syna jest mniejszy od klucza ojca
żadna z w/w
w przeszukiwaniu w głąb grafu skierowanego nie istnieją krawędzie:
w tył
w przód
poprzeczne
wszystkie powyższe istnieją
podaj algorytm (kod w C)umożliwiający wypisanie wszystkich węzłów najkrótszej ścieżki od wybranego węzła s do wybranego węzła t w grafie G, jeśli ścieżka od węzła s do t została wyznaczona przy pomocy algorytmu Dijkstry wszystkich oszacuj jego złożoność - 2pkt
algorytm Boyera-Moore'a:jeśli symbol nie występuje we wzorcu to s=j, jeśli symbol występuje na prawo od j to s=1, jeśli symbol występuje na lewo od j to s=j
Drzewo dwumianowe 4rtego stopnia będzie miało … węzłów.
Kopiec dwumianowy o 11 węzłach składa się z drzew dwumianowych o wagach: ………….. .
Do wyważenia następującego drzewa należy zastosować rotacje: a)LL b)RR c) LR d)RL