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: 5683 razy
Złożoność pesymistyczna wstawienia 100 nowych zdarzeń ma listę zdarzeń symulacji zawierającą 1000
zdarzeń wynosi:
zdarzeń wynosi:
100000
100
1000
10000
100000
Liczba poziomów drzewa turniejowego zawierającego 1000 elementów to:
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ę:
operację:
PushUp, od góry, n razy
PushDown, od góry, n/2 razy
PushDown, od dołu, n razy
PushUp, od dołu, n/2 razy
PushDown, od góry, n/2 razy
W trakcie symulacji zdarzeniowej czas symulacji zmieniamy:
po wstawieniu zdarzenia, o jedną jednostkę czasu
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
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
log n
n / 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-elementowego algorytmami przez wstawianie i przez wybieranie pozostaje w stosunku:
n
2
1/n
1
1
Poszukując wśród n elementów k najmniejszych należy wstawić do stogu dokładnie:
n-k elementów
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:
n
log n
1
k
log n
Poszukując najlżejszego drzewa rozpinającego, konstruowanie drzewa:
zarówno w algorytmie Kruskala i Prima zaczynamy od najkrótszej krawędzi
w algorytmie Kruskala zaczynamy od najkrótszej krawędzi, a w Prima nie
ani w algorytmie Kruskala ani w Prima nie zaczynamy od najkrótszej krawędzi
w algorytmie Prima zaczynamy od najkrótszej krawędzi, a w Kruskalu 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:
n-k
1/(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):
jeżeli (w - waga, l - etykieta):
l(t)< min(l(o),w(e))
l(o)<=min(l(t),w(e))
l(o)< min(l(o),w(e))
l(t)<=min(l(o),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:
n
m/n
1/n
n/m
n/m
Przy wyszukiwaniu metodą interpolacyjną jednego spośród miliona elementów trzeba wykonać kroków
około:
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 AVT to:
elementów metodami przeszukiwania binarnego i drzewa AVT to:
1/1000
1/100
1/10
1
1
Złożoności pesymistyczne wyszukania elementu w słowniku opartym na drzewie BST i drzewie AVT
pozostają w stosunku:
pozostają w stosunku:
n
1
logn/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
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:
kończymy, gdy:
napotkamy pozycję zajętą przez inny element
napotkamy pozycję wolną
funkcja rehaszu zwróci tą samą wartość
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:
żadne z powyższych
liczbie liter alfabetu
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
ś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
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:
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 przepustowości 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 przepustowości 1/2 i krawędź skierowana przeciwnie o przepustowości 3/2