Jaki będzie stan stosu po wykonaniu następujących operacji:
push(3), pop(), push(1), pop(), push(7), push(4), push(2), pop(), pop(), push(4), push(3) - 1pkt
podaj optymalny algorytm wyszukiwania elementu o podanej wartości w dwukierunkowej liście wiązanej - 2pkt
narysuj drzewo bst utworzone przez dodanie kolejno następujących liczb: 38,73,42,17,25,20,11,65,72,16 - 1,5pkt
wypisz węzły drzewa w porządku inorder - 1pkt
wypisz węzły grafu w kolejności odwiedzania, od 1 dla algorytmu BFS - 1,5pkt, G: 1→4;; 2→1,4 ;; 3→1 ;; 4→3,5 ;; 5→3
wymień dwa sposoby rozwiązywania problemu kolizji w tablicy z haszowaniem - 1pkt
czy graf nieskierowany, który nie zawiera węzłów izolowanych jest zawsze spójny? uzasadnij odp - 2pkt
podaj złożoność (w notacji O ) operacji push i pop dla stosu reprezentowanego w postaci tablicy - 1pkt
klucze zamieszczone w węzłach bst zostaną wypisane w porządku malejącym, jeśli zostanie zastosowany algorytm przechodzenia przez drzewo w porządku:
preorder
inorder
postorder
żadna z w/w
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
jeśli drzewo binarne jest zapisane w postaci tablicy i korzeń znajduje się w komórce o indeksie 0 to lewy potomek węzła o indeksie „i” znajduje się w komórce o indeksie… ?
minimalne drzewo rozpinające to graf, w którym
każda para węzłów jest połączona minimalną liczbą krawędzi
liczba krawędzi jest równa liczbie węzłów
każdy węzeł jest co najmniej stopnia 2,
żadna z w/w
w przeszukiwaniu w głąb grafu skierowanego nie istnieją krawędzie:
w tył
w przód
poprzeczne
żadna z w/w
wykonanie algorytmu Dijkstry wymaga aby graf
był skierowany
nie posiadał cykli
nie posiadał ujemnych wag
żadna z w/w
podaj algorytm 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