Test w formie fiszek Wrzucam pytania z odpowiedziami(tymi prawdopodobnie dobrymi).
1-25 pyt. z 1KolosaSem11Z
26-47 pyt. z EgzaminuSem10Z
48-55 pyt. z 1EgzaminuSem11Z(z pamięci)
56-79 pyt. z Kolos2_Szczatki
Fiszki
AISDE - bank pytań od Komandosa
Ilość pytań: 79
Rozwiązywany: 5680 razy
Złożoność pesymistyczna wstawienia 100 nowych zdarzeń ma listę zdarzeń symulacji zawierającą 1000
zdarzeń wynosi:
zdarzeń wynosi:
10000
1000
100000
100
100000
Liczba poziomów drzewa turniejowego zawierającego 1000 elementów to:
11
9
12
10
11
Aby skonstruować stóg składający się z n elementów, trzeba wpisać elementy do stogu i wykonać
operację:
operację:
PushDown, od góry, n/2 razy
PushUp, od dołu, n/2 razy
PushUp, od góry, n razy
PushDown, od dołu, n razy
PushDown, od góry, n/2 razy
W trakcie symulacji zdarzeniowej czas symulacji zmieniamy:
w momencie wstawienia zdarzenia, na czas tego zdarzenia
w momencie pobrania 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
Złożoność średnia sortowania prawie posortowanego ciągu n-elementowego algorytmami quicksort i
przez wstawianie pozostaje w stosunku:
przez wstawianie pozostaje w stosunku:
1
n / log n
log n / 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-elementowego algorytmami przez wstawianie i przez wybieranie pozostaje w stosunku:
1
n
2
1/n
1
Poszukując wśród n elementów k najmniejszych należy wstawić do stogu dokładnie:
k elementów
n-k elementów
k-1 elementów
n-(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:
najmniejszego przy użyciu algorytmu Hoare'a są w stosunku:
k
n
1
log n
log n
Poszukując najlżejszego drzewa rozpinającego, konstruowanie drzewa:
w algorytmie Prima zaczynamy od najkrótszej krawędzi, a w Kruskalu nie
zarówno w algorytmie Kruskala i Prima zaczynamy od najkrótszej krawędzi
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
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:
stosunek liczby rozważanych drzew w algorytmie Kruskala i Prima wynosi:
1/k
n-k
1/(n-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):
jeżeli (w - waga, l - etykieta):
l(t)<=min(l(o),w(e))
l(t)< min(l(o),w(e))
l(o)< min(l(o),w(e))
l(o)<=min(l(t),w(e))
l(t)< min(l(o),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:
między wszystkimi parami wierzchołków przy użyciu algorytmu Floyda w stosunku do algorytmu Dijkstry
wynosi:
1/n
n/m
n
m/n
n/m
Przy wyszukiwaniu metodą interpolacyjną jednego spośród miliona elementów trzeba wykonać kroków
około:
około:
10
100
50
5
5
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/10
1
1/1000
1/100
1
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
n/logn
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
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:
kończymy, gdy:
wykonamy rehasz określoną liczbę razy
funkcja rehaszu zwróci tą samą wartość
napotkamy pozycję wolną
napotkamy pozycję zajętą przez inny element
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
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
Przy znajdowaniu maksymalnego przepływu, krawędzi nieskierowanej o przepustowości 1 i przepływie
1/2 w grafie resztkowym odpowiada:
1/2 w grafie resztkowym odpowiada:
krawędź nieskierowana o przepustowości 3/2
krawędź nieskierowana o przepustowości 1/2
krawędź skierowana zgodnie o przepustowości 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 przepustowości 1/2 i krawędź skierowana przeciwnie o przepustowości 3/2