Strona 2
AiSDE Egzamin
Pytanie 9
Poszukując najlżejszego drzewa rozpinającego, konstruowanie drzewa:
w algorytmie Prima zaczynamy od najkrótszej krawędzi, a w Kruskala nie
ani w algorytmie Kruskala ani Prima nie zaczynamy od najkrótszej
zarówno w algorytmie Kruskala jak i Prima zaczynamy od najkrótszej krawędzi
w algorytmie Kruskala zaczynamy od najkrótszej krawędzi, a w Prima nie
Pytanie 10
Przy poszukiwaniu najlżejszego drzewa rozpinającego w grafie z n wierzchołkami, po k iteracjach stosunek liczby rozważanych drzew w algorytmie Kruskala i Prima wynosi:
1 / (n - k)
1 / k
n - k
k
Pytanie 11
W algorytmie znajdowania najgrubszej ścieżki od źródła, węzeł t krawędzi e=(o,t) jest cechowany z o, jeżeli (w - waga, l - etykieta):
l(o) < min(l(o), w(e))
l(t) < min (l(0), w(e))
l(t) <= min (l(0), w(e))
l(o) <= min(l(o), w(e))
Pytanie 12
Stosunek złożoności wyszukania w grafie o n wierzchołkach i m krawędziach najkrótszych ścieżek między wszystkimi parami wierzchołków przy użyciu algorytmu Floyda w stosunku do algorytmu Dijkstry
wynosi: (Komandos zdaje się nie dostrzegać lepszych implementacji Dijkstry)
1 / n
n
n /m
m / n
Pytanie 13
Przy wyszukiwaniu metodą interpolacyjną jednego spośród miliona elementów trzeba wykonać kroków około:
10
5
100
50
Pytanie 14
Stosunek pesymistycznej liczby kroków wymaganych do wyszukania elementu w słowniku 1000 elementów metodami przeszukiwania binarnego i drzewa AVL to:
1 / 1000
1 / 100
1 / 10
1
Pytanie 15
Złożoności pesymistyczne wyszukania elementu w słowniku opartym na drzewie BST i drzewie AVL pozostają w stosunku:
log n / n
1
n / log n
n
Pytanie 16
W haszowaniu otwartym, przy n elementach i m możliwych wartościach kluczy wartości funkcji haszującej powinno być rzędu:
n
m / n
m
n / m