Strona 1
AISDE - bank pytań od Komandosa
Pytanie 1
Złożoność pesymistyczna wstawienia 100 nowych zdarzeń ma listę zdarzeń symulacji zawierającą 1000
zdarzeń wynosi:
zdarzeń wynosi:
10000
100
1000
100000
Pytanie 2
Liczba poziomów drzewa turniejowego zawierającego 1000 elementów to:
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ę:
operację:
PushDown, od góry, n/2 razy
PushUp, od góry, n razy
PushUp, od dołu, n/2 razy
PushDown, od dołu, n razy
Pytanie 4
W trakcie symulacji zdarzeniowej czas symulacji zmieniamy:
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
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:
przez wstawianie pozostaje w stosunku:
n / log n
1
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:
n-elementowego algorytmami przez wstawianie i przez wybieranie pozostaje w stosunku:
2
n
1
1/n
Pytanie 7
Poszukując wśród n elementów k najmniejszych należy wstawić do stogu dokładnie:
n-(k-1) elementów
k elementów
k-1 elementów
n-k 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:
najmniejszego przy użyciu algorytmu Hoare'a są w stosunku:
k
n
1
log n