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

Powiązane tematy