Test w formie fiszek Odpowiedzi na podstawie "biblii algorytmów"
Ilość pytań: 73
Rozwiązywany: 4654 razy
Złożoność pesymistyczna wstawienia 100 nowych zdarzeń na listę zdarzeń symulacji zawierającą już 1000 zdarzeń wynosi:
100000
10000
1000
100
1000
Liczba poziomów drzewa turniejowego zawierającego 1000 elementów wynosi:
12
10
11
9
11
Aby skonstruować stóg składający się z n elementów, trzeba wpisać elementy do stogu i wykonać operację:
PushDown, od góry, n/2 razy
PushDown, od dołu, n razy
PushUp, od góry, n razy
PushUp, od dołu, n/2 razy
PushDown, od góry, n/2 razy
W trakcie symulacji zdarzeniowej czas symulacji zmieniamy:
po obsłużeniu zdarzenia, o jedną jednostkę czasu
w momencie wstawienia zdarzenia, na czas tego zdarzenia
w momencie pobrania zdarzenia, na czas tego zdarzenia
po wstawieniu zdarzenia, o jedną jednostkę czasu
w momencie pobrania zdarzenia, na czas tego zdarzenia
Złożoność średnia sortowania prawie posortowanego ciągu n-elementowego algorytmami quicksort i przez wstawianie pozostaje w stosunku:
n / log n
1
log n
log n / n
log n
Złożoność średnia mierzona liczbą zamian przy sortowaniu prawie posortowanego ciągu
n-elementowego algorytmami przez wstawianie i przez wybieranie pozostaje w stosunku:
n
1
1 / n
2
1 / n
Poszukując wśród n elementów k najmniejszych należy wstawić do stogu dokładnie:
n - (k - 1) elementów
k - 1 elementów
k elementów
n - k elementów
n - (k - 1) elementów
Złożoności średnie znalezienia wśród n elementów k najmniejszych przy użyciu stogu i k-tego najmniejszego przy użyciu algorytmu Hoare'a są w stosunku:
k
n
log n
1
1
Poszukując najlżejszego drzewa rozpinającego, konstruowanie drzewa:
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 Prima zaczynamy od najkrótszej krawędzi, a w Kruskala nie
w algorytmie Kruskala zaczynamy od najkrótszej krawędzi, a w Prima nie
w algorytmie Kruskala zaczynamy od najkrótszej krawędzi, a w Prima nie
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)
k
1 / k
n - k
n - k
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(o) < min(l(o), w(e))
l(t) <= min (l(0), w(e))
l(t) < min (l(0), w(e))
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)
n /m
n
1 / n
m / n
n /m
Przy wyszukiwaniu metodą interpolacyjną jednego spośród miliona elementów trzeba wykonać kroków około:
10
50
100
5
5
Stosunek pesymistycznej liczby kroków wymaganych do wyszukania elementu w słowniku 1000 elementów metodami przeszukiwania binarnego i drzewa AVL to:
1 / 100
1 / 10
1 / 1000
1
1
Złożoności pesymistyczne wyszukania elementu w słowniku opartym na drzewie BST i drzewie AVL pozostają w stosunku:
n / log n
1
log n / n
n
n / log n
W haszowaniu otwartym, przy n elementach i m możliwych wartościach kluczy wartości funkcji haszującej powinno być rzędu:
m
n
m / n
n / m
m
W haszowaniu zamkniętym, gdy stosujemy rehasz przy szukaniu elementu, którego nie ma w słowniku, kończymy, gdy:
napotkamy pozycję wolną
funkcja rehaszu zwróci tą samą wartość
napotkamy pozycję zajętą przez inny element
wykonamy rehasz określoną liczbę razy
wykonamy rehasz określoną liczbę razy
Liczba wierzchołków drzewa pozycyjnego struktury słownika (nie licząc korzenia) jest równa:
liczbie liter alfabetu
Żadne z powyższych
liczbie liter najdłuższego słowa
liczbie słów słownika
Żadne z powyższych
W algorytmach znajdowania rozłącznych ścieżek przeplot to:
najkrótsza ścieżka nie korzystająca z krawędzi należących do dotychczasowych ścieżek zgodnie z ich skierowaniem
ścieżka nie korzystająca z krawędzi należących do dotychczasowych ścieżek zgodnie z ich skierowaniem
najkrótsza ścieżka nie korzystająca z krawędzi należących do dotychczasowych ścieżek
ścieżka nie korzystająca z krawędzi należących do dotychczasowych ścieżek
ścieżka nie korzystająca z krawędzi należących do dotychczasowych ścieżek zgodnie z ich skierowaniem
Przy znajdowaniu maksymalnego przepływu, krawędzi nieskierowanej o przepustowości 1 i przepływie 1/2 w grafie resztkowym odpowiada:
krawędź nieskierowana o przepustowości 1/2
krawędź nieskierowana o przepustowości 3/2
krawędź skierowana zgodnie o przepust. 1/2 i krawędź skierowana przeciwnie o przepustowości 3/2
krawędź skierowana przeciwnie do przepływu o przepustowości 1/2
krawędź skierowana zgodnie o przepust. 1/2 i krawędź skierowana przeciwnie o przepustowości 3/2
