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