Fiszki

AiSDE Egzamin

Test w formie fiszek Odpowiedzi na podstawie "biblii algorytmów"
Ilość pytań: 73 Rozwiązywany: 3863 razy
Złożoność pesymistyczna wstawienia 100 nowych zdarzeń na listę zdarzeń symulacji zawierającą już 1000 zdarzeń wynosi:
1000
10000
100000
100
1000
Liczba poziomów drzewa turniejowego zawierającego 1000 elementów wynosi:
12
9
11
10
11
Aby skonstruować stóg składający się z n elementów, trzeba wpisać elementy do stogu i wykonać operację:
PushUp, od góry, n razy
PushUp, od dołu, n/2 razy
PushDown, od dołu, n razy
PushDown, od góry, n/2 razy
PushDown, od góry, n/2 razy
W trakcie symulacji zdarzeniowej czas symulacji zmieniamy:
po wstawieniu zdarzenia, o jedną jednostkę czasu
w momencie pobrania zdarzenia, na czas tego zdarzenia
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
Złożoność średnia sortowania prawie posortowanego ciągu n-elementowego algorytmami quicksort i przez wstawianie pozostaje w stosunku:
log n
n / log n
1
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:
1
2
n
1 / n
1 / n
Poszukując wśród n elementów k najmniejszych należy wstawić do stogu dokładnie:
n - k elementów
k - 1 elementów
n - (k - 1) elementów
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
1
log n
n
1
Poszukując najlżejszego drzewa rozpinającego, konstruowanie drzewa:
zarówno w algorytmie Kruskala jak i Prima zaczynamy od najkrótszej krawędzi
ani w algorytmie Kruskala ani Prima nie zaczynamy od najkrótszej
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 / k
k
1 / (n - 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(o) < min(l(o), w(e))
l(t) <= min (l(0), 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)
1 / n
m / n
n
n /m
n /m
Przy wyszukiwaniu metodą interpolacyjną jednego spośród miliona elementów trzeba wykonać kroków około:
5
50
10
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 / 10
1 / 1000
1 / 100
1
Złożoności pesymistyczne wyszukania elementu w słowniku opartym na drzewie BST i drzewie AVL pozostają w stosunku:
log n / n
n / log n
1
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:
n
m / n
m
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ę zajętą przez inny element
funkcja rehaszu zwróci tą samą wartość
napotkamy pozycję wolną
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
liczbie liter najdłuższego słowa
liczbie liter alfabetu
Żadne z powyższych
Żadne z powyższych
W algorytmach znajdowania rozłącznych ścieżek przeplot to:
ś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
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
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 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
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

Powiązane tematy

Inne tryby