Strona 1

AISDE Egzamin Komandosa

Pytanie 1
Złożoność pesymistyczna wstawienia 100 nowych zdarzeń ma listę zdarzeń symulacji zawierającą 1000
zdarzeń wynosi:
a) 100000
b) 10000
c) 1000
d) 100
c) 1000
a) 100000
b) 10000
d) 100
Pytanie 2
Liczba poziomów drzewa turniejowego zawierającego 1000 elementów to:
a) 9
b) 10
c) 11
d) 12
a) 9
d) 12
c) 11
b) 10
Pytanie 3
Aby skonstruować stóg składający się z n elementów, trzeba wpisać elementy do stogu i wykonać
operację:
a) PushDown, od dołu, n razy
b) PushUp, od dołu, n/2 razy
c) PushDown, od góry, n/2 razy
d) PushUp, od góry, n razy
c) PushDown, od góry, n/2 razy
Pytanie 4
W trakcie symulacji zdarzeniowej czas symulacji zmieniamy:
a) w momencie pobrania zdarzenia, na czas tego zdarzenia
b) po obsłużeniu zdarzenia, o jedną jednostkę czasu
c) po wstawieniu zdarzenia, o jedną jednostkę czasu
d) w momencie wstawienia zdarzenia, na czas tego zdarzeni
b) po obsłużeniu zdarzenia, o jedną jednostkę czasu
d) w momencie wstawienia zdarzenia, na czas tego zdarzeni
a) w momencie pobrania zdarzenia, na czas tego zdarzenia
c) 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:
a) n / log n
b) 1
c) log n
d) log n / n
a) n / log n
c) log n
b) 1
d) 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:
a) n
b) 1/n // różne zdania
c) 1 // także nie mam pojęcia
d) 2
b) 1/n
a) n
d) 2
c) 1
Pytanie 7
Poszukując wśród n elementów k najmniejszych należy wstawić do stogu dokładnie:
a) k-1 elementów
b) k elementów
c) n-k elementów
d) n-(k-1) elementów
8. Złożoności średnie znalezid) n-(k-1) elementów
d) n-(k-1) elementów
a) k-1 elementów
c) n-k elementów
b) 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:
a) 1
b) log n
c) k
d) n
c) k
d) n
b) log n
a) 1

Powiązane tematy