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
10000
1000
100000
Pytanie 2
Liczba poziomów drzewa turniejowego zawierającego 1000 elementów wynosi:
12
11
10
9
Pytanie 3
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
Pytanie 4
W trakcie symulacji zdarzeniowej czas symulacji zmieniamy:
w momencie pobrania zdarzenia, na czas tego zdarzenia
w momencie wstawienia zdarzenia, na czas tego zdarzenia
po obsłużeniu zdarzenia, o jedną jednostkę czasu
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:
1
n / log n
log n
log n / 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
2
n
1 / n
Pytanie 7
Poszukując wśród n elementów k najmniejszych należy wstawić do stogu dokładnie:
k elementów
n - (k - 1) elementów
n - k elementów
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:
n
k
1
log n