Fiszki
AiSDE Egzamin
Test w formie fiszek Odpowiedzi na podstawie "biblii algorytmów"
Ilość pytań: 73
Rozwiązywany: 3888 razy
Złożoność pesymistyczna wstawienia 100 nowych zdarzeń na listę zdarzeń symulacji zawierającą już 1000 zdarzeń wynosi:
100000
1000
100
10000
1000
Liczba poziomów drzewa turniejowego zawierającego 1000 elementów wynosi:
12
10
9
11
11
Aby skonstruować stóg składający się z n elementów, trzeba wpisać elementy do stogu i wykonać operację:
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
PushDown, od góry, n/2 razy
W trakcie symulacji zdarzeniowej czas symulacji zmieniamy:
w momencie wstawienia zdarzenia, na czas tego zdarzenia
po obsłużeniu zdarzenia, o jedną jednostkę czasu
po wstawieniu zdarzenia, o jedną jednostkę czasu
w momencie pobrania zdarzenia, na czas tego zdarzenia
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:
1
log n / n
n / log n
log 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
2
1 / n
1
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 elementów
n - k elementów
k - 1 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:
1
n
log n
k
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 Kruskala zaczynamy od najkrótszej krawędzi, a w Prima nie
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
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)
n - k
1 / k
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(t) < min (l(0), w(e))
l(o) < min(l(o), 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
n /m
m / n
1 / n
n /m
Przy wyszukiwaniu metodą interpolacyjną jednego spośród miliona elementów trzeba wykonać kroków około:
5
10
50
100
5
Stosunek pesymistycznej liczby kroków wymaganych do wyszukania elementu w słowniku 1000 elementów metodami przeszukiwania binarnego i drzewa AVL to:
1
1 / 100
1 / 1000
1 / 10
1
Złożoności pesymistyczne wyszukania elementu w słowniku opartym na drzewie BST i drzewie AVL pozostają w stosunku:
1
log n / n
n / log 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
n / m
m / n
m
W haszowaniu zamkniętym, gdy stosujemy rehasz przy szukaniu elementu, którego nie ma w słowniku, kończymy, gdy:
funkcja rehaszu zwróci tą samą wartość
napotkamy pozycję wolną
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 słów słownika
Żadne z powyższych
liczbie liter najdłuższego słowa
liczbie liter alfabetu
Ż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
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
ś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
Przy znajdowaniu maksymalnego przepływu, krawędzi nieskierowanej o przepustowości 1 i przepływie 1/2 w grafie resztkowym odpowiada:
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ź nieskierowana o przepustowości 3/2
krawędź nieskierowana o przepustowości 1/2
krawędź skierowana zgodnie o przepust. 1/2 i krawędź skierowana przeciwnie o przepustowości 3/2