Pytania i odpowiedzi
AISDE Egzamin Komandosa
Zebrane pytania i odpowiedzi do zestawu.
Ilość pytań: 25
Rozwiązywany: 2097 razy
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
zdarzeń wynosi:
a) 100000
b) 10000
c) 1000
d) 100
c) 1000
Pytanie 2
Liczba poziomów drzewa turniejowego zawierającego 1000 elementów to:
a) 9
b) 10
c) 11
d) 12
a) 9
b) 10
c) 11
d) 12
c) 11
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
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
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
a) w momencie pobrania zdarzenia, na czas tego zdarzenia
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
przez wstawianie pozostaje w stosunku:
a) n / log n
b) 1
c) log n
d) log n / n
c) 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:
a) n
b) 1/n // różne zdania
c) 1 // także nie mam pojęcia
d) 2
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
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
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
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
najmniejszego przy użyciu algorytmu Hoare'a są w stosunku:
a) 1
b) log n
c) k
d) n
b) log n
Pytanie 9
Poszukując najlżejszego drzewa rozpinającego, konstruowanie drzewa:
a) w algorytmie Prima zaczynamy od najkrótszej krawędzi, a w Kruskalu nie
b) w algorytmie Kruskala zaczynamy od najkrótszej krawędzi, a w Prima nie
c) zarówno w algorytmie Kruskala i Prima zaczynamy od najkrótszej krawędzi
d) ani w algorytmie Kruskala ani w Prima nie zaczynamy od najkrótszej krawędzi
a) w algorytmie Prima zaczynamy od najkrótszej krawędzi, a w Kruskalu nie
b) w algorytmie Kruskala zaczynamy od najkrótszej krawędzi, a w Prima nie
c) zarówno w algorytmie Kruskala i Prima zaczynamy od najkrótszej krawędzi
d) ani w algorytmie Kruskala ani w Prima nie zaczynamy od najkrótszej krawędzi
b) w algorytmie Kruskala zaczynamy od najkrótszej krawędzi, a w Prima nie
Pytanie 10
Przy poszukiwaniu najlżejszego drzewa rozpinającego w grafie z n wierzchołkami, po k iteracjach
stosunek liczby rozważanych drzew w algorytmie Kruskala i Prima wynosi:
a) k
b) n-k
c) 1/k
d) 1/(n-k)
stosunek liczby rozważanych drzew w algorytmie Kruskala i Prima wynosi:
a) k
b) n-k
c) 1/k
d) 1/(n-k)
b) n-k
Pytanie 11
W algorytmie znajdowania najgrubszej ścieżki od źródła, węzeł t krawędzi e=(o,t) jest cechowany z o,
jeżeli (w - waga, l - etykieta):
a) l(o)
d) l(t)<=min(l(o),w(e))
jeżeli (w - waga, l - etykieta):
a) l(o)
d) l(t)<=min(l(o),w(e))
b) l(t)
Pytanie 12
Stosunek złożoności wyszukania w grafie o n wierzchołkach i m krawędziach najkrótszych ścieżek
między wszystkimi parami wierzchołków przy użyciu algorytmu Floyda w stosunku do algorytmu Dijkstry
wynosi:
a) n
b) 1/n
c) m/n
d) n/m
między wszystkimi parami wierzchołków przy użyciu algorytmu Floyda w stosunku do algorytmu Dijkstry
wynosi:
a) n
b) 1/n
c) m/n
d) n/m
d) n/m
Pytanie 13
rzy wyszukiwaniu metodą interpolacyjną jednego spośród miliona elementów trzeba wykonać kroków
około:
a) 5
b) 10
c) 50
d) 100
około:
a) 5
b) 10
c) 50
d) 100
a) 5
Pytanie 14
Stosunek pesymistycznej liczby kroków wymaganych do wyszukania elementu w słowniku 1000
elementów metodami przeszukiwania binarnego i drzewa AVT to:
a) 1
b) 1/10
c) 1/100
d) 1/1000
elementów metodami przeszukiwania binarnego i drzewa AVT to:
a) 1
b) 1/10
c) 1/100
d) 1/1000
a) 1
Pytanie 15
Złożoności pesymistyczne wyszukania elementu w słowniku opartym na drzewie BST i drzewie AVT
pozostają w stosunku:
a) 1
b) n
c) n / log n
d) log n / n
pozostają w stosunku:
a) 1
b) n
c) n / log n
d) log n / n
c) n / log n
Pytanie 16
W haszowaniu otwartym, przy n elementach i m możliwych wartościach kluczy wartości funkcji hasz.
powinno być rzędu:
a) n
b) m
c) m/n
d) n/m
powinno być rzędu:
a) n
b) m
c) m/n
d) n/m
b) m
Pytanie 17
W haszowaniu zamkniętym, gdy stosujemy rehasz przy szukaniu elementu, którego nie ma w słowniku,
kończymy, gdy:
a) napotkamy pozycję zajętą przez inny element
b) napotkamy pozycję wolną
c) funkcja rehaszu zwróci tą samą wartość
d) wykonamy rehasz określoną liczbę razy
kończymy, gdy:
a) napotkamy pozycję zajętą przez inny element
b) napotkamy pozycję wolną
c) funkcja rehaszu zwróci tą samą wartość
d) wykonamy rehasz określoną liczbę razy
d) wykonamy rehasz określoną liczbę razy
Pytanie 18
Liczba wierzchołków drzewa pozycyjnego struktury słownika (nie licząc korzenia) jest równa:
a) liczbie liter alfabetu
b) liczbie liter najdłuższego słowa
c) liczbie słów słownika
d) żadne z powyższych
a) liczbie liter alfabetu
b) liczbie liter najdłuższego słowa
c) liczbie słów słownika
d) żadne z powyższych
d) żadne z powyższych
Pytanie 19
W algorytmach znajdowania rozłącznych ścieżek przeplot to:
a) ścieżka nie korzystająca z krawędzi należących do dotychczasowych ścieżek
b) najkrótsza ścieżka nie korzystająca z krawędzi należących do dotychczasowych ścieżek
c) ścieżka nie korzystająca z krawędzi należących do dotychczasowych ścieżek zgodnie z ich skierowaniem
d) najkrótsza ścieżka nie korzystająca z krawędzi należących do dotychczasowych ścieżek zgodnie z ich
skierowaniem
a) ścieżka nie korzystająca z krawędzi należących do dotychczasowych ścieżek
b) najkrótsza ścieżka nie korzystająca z krawędzi należących do dotychczasowych ścieżek
c) ścieżka nie korzystająca z krawędzi należących do dotychczasowych ścieżek zgodnie z ich skierowaniem
d) najkrótsza ścieżka nie korzystająca z krawędzi należących do dotychczasowych ścieżek zgodnie z ich
skierowaniem
c) ścieżka nie korzystająca z krawędzi należących do dotychczasowych ścieżek zgodnie z ich skierowaniem
Pytanie 20
Przy znajdowaniu maksymalnego przepływu, krawędzi nieskierowanej o przepustowości 1 i przepływie
1/2 w grafie resztkowym odpowiada:
a) krawędź nieskierowana o przepustowości 3/2
b) krawędź nieskierowana o przepustowości 1/2
c) krawędź skierowana przeciwnie do przepływu o przepustowości 1/2
d) krawędź skierowana zgodnie o przepust. 1/2 i krawędź skierowana przeciwnie o przepustowości 3/2
1/2 w grafie resztkowym odpowiada:
a) krawędź nieskierowana o przepustowości 3/2
b) krawędź nieskierowana o przepustowości 1/2
c) krawędź skierowana przeciwnie do przepływu o przepustowości 1/2
d) krawędź skierowana zgodnie o przepust. 1/2 i krawędź skierowana przeciwnie o przepustowości 3/2
d) krawędź skierowana zgodnie o przepust. 1/2 i krawędź skierowana przeciwnie o przepustowości 3/2
Pytanie 21
Wyznaczanie maksymalnego przepływu wymaga iteracyjnego znajdowania ścieżki wzbogacającej:
a) najkrótszej, algorytmem Dijkstry
b) najkrótszej, algorytmem poprawiania etykiet
c) dowolnej, algorytmem Dijkstry
d) dowolnej, algorytmem poprawiania etykiet
a) najkrótszej, algorytmem Dijkstry
b) najkrótszej, algorytmem poprawiania etykiet
c) dowolnej, algorytmem Dijkstry
d) dowolnej, algorytmem poprawiania etykiet
d) dowolnej, algorytmem poprawiania etykiet
Pytanie 22
W grafie o m wierzchołkach i n krawędziach stosunek liczby ograniczeń dotyczących przepustowości w
sformułowaniach problemu przepływu d towarów i 1 towaru wynosi:
a) 1
b) d
c) m
d) n
sformułowaniach problemu przepływu d towarów i 1 towaru wynosi:
a) 1
b) d
c) m
d) n
a) 1
Pytanie 23
Dane są 4 krawędzie grafu i ich przepustowości: AB=1, BC=2, CD=1, DA=2 oraz zapotrzebowania
AC=3, BD=2. Przepływ wielotowarowy jest:
a) realizowany, bo 6>5
b) nierealizowany, bo 6<10
c) realizowany, bo 6<=10
d) nierealizowany, bo 6>=5
AC=3, BD=2. Przepływ wielotowarowy jest:
a) realizowany, bo 6>5
b) nierealizowany, bo 6<10
c) realizowany, bo 6<=10
d) nierealizowany, bo 6>=5
b) nierealizowany, bo 6<10
Pytanie 24
W algorytmie minimalizacji metodą sympleksu zawsze generowany jest kolejny wierzchołek zbioru
rozwiązań dopuszczalnych:
a) różniący się jedną zmienną bazową i poprawiający wartość funkcji kosztu
b) zachowujący jedną zmienną bazową i poprawiający wartość funkcji kosztu
c) różniący się jedną zmienną bazową i najbardziej poprawiający wartość funkcji kosztu
d) zachowujący jedną zmienną bazową i najbardziej poprawiający wartość funkcji kosztu
rozwiązań dopuszczalnych:
a) różniący się jedną zmienną bazową i poprawiający wartość funkcji kosztu
b) zachowujący jedną zmienną bazową i poprawiający wartość funkcji kosztu
c) różniący się jedną zmienną bazową i najbardziej poprawiający wartość funkcji kosztu
d) zachowujący jedną zmienną bazową i najbardziej poprawiający wartość funkcji kosztu
c) różniący się jedną zmienną bazową i najbardziej poprawiający wartość funkcji kosztu
Pytanie 25
W algorytmie minimalizacji metodą sympleksu faza analizy kolumny tablicy sympleksowej może
prowadzić do stwierdzenia:
a) że problem jest nieograniczony
b) że zostało znalezione optimum
c) która zmienna powinna wejść do bazy
d) że problem jest sprzeczny
prowadzić do stwierdzenia:
a) że problem jest nieograniczony
b) że zostało znalezione optimum
c) która zmienna powinna wejść do bazy
d) że problem jest sprzeczny
a) że problem jest nieograniczony