Strona 2
AISDE - bank pytań od Komandosa
Pytanie 9
Poszukując najlżejszego drzewa rozpinającego, konstruowanie drzewa:
w algorytmie Prima zaczynamy od najkrótszej krawędzi, a w Kruskalu nie
ani w algorytmie Kruskala ani w Prima nie zaczynamy od najkrótszej krawędzi
w algorytmie Kruskala zaczynamy od najkrótszej krawędzi, a w Prima nie
zarówno w algorytmie Kruskala i Prima zaczynamy od najkrótszej krawędzi
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:
stosunek liczby rozważanych drzew w algorytmie Kruskala i Prima wynosi:
1/k
k
n-k
1/(n-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):
jeżeli (w - waga, l - etykieta):
l(o)< min(l(o),w(e))
l(t)< min(l(o),w(e))
l(t)<=min(l(o),w(e))
l(o)<=min(l(t),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:
między wszystkimi parami wierzchołków przy użyciu algorytmu Floyda w stosunku do algorytmu Dijkstry
wynosi:
m/n
1/n
n/m
n
Pytanie 13
Przy wyszukiwaniu metodą interpolacyjną jednego spośród miliona elementów trzeba wykonać kroków
około:
około:
5
50
100
10
Pytanie 14
Stosunek pesymistycznej liczby kroków wymaganych do wyszukania elementu w słowniku 1000
elementów metodami przeszukiwania binarnego i drzewa AVT to:
elementów metodami przeszukiwania binarnego i drzewa AVT to:
1
1/10
1/1000
1/100
Pytanie 15
Złożoności pesymistyczne wyszukania elementu w słowniku opartym na drzewie BST i drzewie AVT
pozostają w stosunku:
pozostają w stosunku:
logn/n
1
n
n/logn
Pytanie 16
W haszowaniu otwartym, przy n elementach i m możliwych wartościach kluczy wartości funkcji hasz.
powinno być rzędu:
powinno być rzędu:
n/m
n
m/n
m