Strona 1
AiSDE Egzamin
Pytanie 1
Złożoność pesymistyczna wstawienia 100 nowych zdarzeń na listę zdarzeń symulacji zawierającą już 1000 zdarzeń wynosi:
100
100000
1000
10000
Pytanie 2
Liczba poziomów drzewa turniejowego zawierającego 1000 elementów wynosi:
9
11
10
12
Pytanie 3
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 dołu, n/2 razy
PushUp, od góry, n razy
Pytanie 4
W trakcie symulacji zdarzeniowej czas symulacji zmieniamy:
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
po wstawieniu zdarzenia, o jedną jednostkę czasu
Pytanie 5
Złożoność średnia sortowania prawie posortowanego ciągu n-elementowego algorytmami quicksort i przez wstawianie pozostaje w stosunku:
log n
1
log n / n
n / log n
Pytanie 6
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 / n
1
2
n
Pytanie 7
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
Pytanie 8
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:
log n
n
1
k