Twój wynik: AiSDE Egzamin
Twój wynik
Wszystkie ({{dataStorage.userResults.answersTotal}})
Prawidłowe ({{dataStorage.userResults.answersGood}})
Błędne ({{dataStorage.userResults.answersBad}})
Pytanie 1
Złożoność pesymistyczna wstawienia 100 nowych zdarzeń na listę zdarzeń symulacji zawierającą już 1000 zdarzeń wynosi:
1000
100000
10000
100
Pytanie 2
Liczba poziomów drzewa turniejowego zawierającego 1000 elementów wynosi:
9
12
10
11
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:
po obsłużeniu zdarzenia, o jedną jednostkę czasu
po wstawieniu zdarzenia, o jedną jednostkę czasu
w momencie wstawienia zdarzenia, na czas tego zdarzenia
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:
log n
n / log n
log n / n
1
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
1 / n
1
2
Pytanie 7
Poszukując wśród n elementów k najmniejszych należy wstawić do stogu dokładnie:
k elementów
k - 1 elementów
n - (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:
1
k
n
log n
Pytanie 9
Poszukując najlżejszego drzewa rozpinającego, konstruowanie drzewa:
zarówno w algorytmie Kruskala jak i Prima zaczynamy od najkrótszej krawędzi
w algorytmie Prima zaczynamy od najkrótszej krawędzi, a w Kruskala nie
w algorytmie Kruskala zaczynamy od najkrótszej krawędzi, a w Prima nie
ani w algorytmie Kruskala ani Prima nie zaczynamy od najkrótszej
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:
1 / (n - k)
k
n - k
1 / 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):
l(t) < min (l(0), w(e))
l(o) <= min(l(o), w(e))
l(t) <= min (l(0), w(e))
l(o) < min(l(o), w(e))
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: (Komandos zdaje się nie dostrzegać lepszych implementacji Dijkstry)
m / n
n
1 / n
n /m
Pytanie 13
Przy wyszukiwaniu metodą interpolacyjną jednego spośród miliona elementów trzeba wykonać kroków około:
5
10
50
100
Pytanie 14
Stosunek pesymistycznej liczby kroków wymaganych do wyszukania elementu w słowniku 1000 elementów metodami przeszukiwania binarnego i drzewa AVL to:
1 / 100
1 / 1000
1 / 10
1
Pytanie 15
Złożoności pesymistyczne wyszukania elementu w słowniku opartym na drzewie BST i drzewie AVL pozostają w stosunku:
log n / n
1
n / log n
n
Pytanie 16
W haszowaniu otwartym, przy n elementach i m możliwych wartościach kluczy wartości funkcji haszującej powinno być rzędu:
m / n
n / m
m
n
Pytanie 17
W haszowaniu zamkniętym, gdy stosujemy rehasz przy szukaniu elementu, którego nie ma w słowniku, kończymy, gdy:
funkcja rehaszu zwróci tą samą wartość
wykonamy rehasz określoną liczbę razy
napotkamy pozycję zajętą przez inny element
napotkamy pozycję wolną
Pytanie 18
Liczba wierzchołków drzewa pozycyjnego struktury słownika (nie licząc korzenia) jest równa:
liczbie słów słownika
liczbie liter alfabetu
Żadne z powyższych
liczbie liter najdłuższego słowa
Pytanie 19
W algorytmach znajdowania rozłącznych ścieżek przeplot to:
najkrótsza ścieżka nie korzystająca z krawędzi należących do dotychczasowych ścieżek zgodnie z ich skierowaniem
ścieżka nie korzystająca z krawędzi należących do dotychczasowych ścieżek zgodnie z ich skierowaniem
ścieżka nie korzystająca z krawędzi należących do dotychczasowych ścieżek
najkrótsza ścieżka nie korzystająca z krawędzi należących do dotychczasowych ścieżek
Pytanie 20
Przy znajdowaniu maksymalnego przepływu, krawędzi nieskierowanej o przepustowości 1 i przepływie 1/2 w grafie resztkowym odpowiada:
krawędź skierowana przeciwnie do przepływu o przepustowości 1/2
krawędź skierowana zgodnie o przepust. 1/2 i krawędź skierowana przeciwnie o przepustowości 3/2
krawędź nieskierowana o przepustowości 1/2
krawędź nieskierowana o przepustowości 3/2
Pytanie 21
Wyznaczanie maksymalnego przepływu wymaga iteracyjnego znajdowania ścieżki wzbogacającej:
najkrótszej, algorytmem Dijkstry
najkrótszej, algorytmem poprawiania etykiet
dowolnej, algorytmem poprawiania etykiet
dowolnej, algorytmem Dijkstry
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:
m
d
n
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:
realizowany, bo 6>5
nierealizowany, bo 6>=5
realizowany, bo 6<=10
nierealizowany, bo 6<10
Pytanie 24
W algorytmie minimalizacji metodą sympleksu zawsze generowany jest kolejny wierzchołek zbioru rozwiązań dopuszczalnych:
różniący się jedną zmienną bazową i poprawiający wartość funkcji kosztu
óżniący się jedną zmienną bazową i najbardziej poprawiający wartość funkcji kosztu
zachowujący jedną zmienną bazową i najbardziej poprawiający wartość funkcji kosztu
zachowujący jedną zmienną bazową i poprawiający wartość funkcji kosztu
Pytanie 25
W algorytmie minimalizacji metodą sympleksu faza analizy kolumny tablicy sympleksowej może prowadzić do stwierdzenia:
że zostało znalezione optimum
że problem jest nieograniczony
która zmienna powinna wejść do bazy
że problem jest sprzeczny
Pytanie 26
Jeżeli jeden sektor mieści k rekordów danych albo k' rekordów indeksu, to przy n rekordach danych
indeks gęsty jest k razy większy niż indeks rzadki
indeks gęsty jest k' razy mniejszy niż indeks rzadki
indeks gęsty jest n/k' razy mniejszy niż indeks rzadki
indeks gęsty jest n/k' razy większy niż indeks rzadki
Pytanie 27
Jeżeli wielkość rekordu danych to 100B wielkość rekordu indeksu 10B, wielkość sektora 1kB. to wyszukanie jednego spośród 100 000 rekordów przy zastosowaniu indeksu gęstego w porównaniu z zastosowaniem funkcji haszującej o 100 wartościach jest:
10 razy wolniejsze
tak samo szybkie
10 razy szybsze
100 razy szybsze
Pytanie 28
W rekurencyjnym algorytmie sortowania pozycyjnego k ciągów binarnych o długości m znaków grupy bitów są sortowane:
od lewej strony ze złożonością k
od prawej strony ze złożonością k
od prawej strony ze złożonością k log m
od lewej strony ze złożonością k log m
Pytanie 29
W trakcie wyszukiwania wzorca w tekście gdy stwierdzamy niezgodność znaków wzorca i tekstu:
przesuwamy wzorzec o 1 znaków i zaczynamy porównywanie od pierwszego znaku wzorca
przesuwamy wzorzec o i znaków i zaczynamy porównywanie od pierwszego znaku wzorca
przesuwamy wzorzec o i znaków i zaczynamy porównywanie od bieżącego znaku tekstu
przesuwamy wzorzec o 1 znak i zaczynamy porównywanie od bieżącego znaku tekstu
Pytanie 30
Kompresja tekstu xyuzyzy z użyciem algorytmu Huffmana zwróci:
0111000101001
011001110110
010110110001
01110011011
Pytanie 31
W modelu klucza publicznego strona B udowadnia niezaprzeczalność wiadomości otrzymanej od strony A korzystając z klucza:
prywatnego A
publicznego A
prywatnego B
publicznego B
Pytanie 32
W modelu klucza publicznego treść wiadomości wysyłanej przez stronę A jest szyfrowana przy użyciu klucza:
tajnego wygenerowanego przez A
tajnego wygenerowanego przez B
prywatnego A
publicznego B
Pytanie 33
Przy minimalizacji funkcji metodą największego spadku wykonujemy złoty podział aby:
ograniczyć przedział poszukiwań minimum funkcji w kierunku
wyznaczyć kierunek najwiekszego spadku wartości funkcji
ograniczyć obszar poszukiwań do otoczenia minimum globalnego
wyznaczyć minimum funkcji w kierunku największego spadku
Pytanie 34
Przy maksymalizacji metodą podziałów i ograniczeń podzbioru rozwiązań można nie przeglądać jeśli:
oszacowanie dolne funkcji kosztu jest nie niższe od najlepszego znanego rozwiązania
oszacowanie górne funkcji kosztu jest nie wyższe od najlepszego znanego rozwiązania
oszacowanie dolne funkcji kosztu jest nie niższe od najlepszego znanego rozwiązania
oszacowanie dolne funkcji kosztu jest nie wyższe od najlepszego znanego rozwiązania
Pytanie 35
W metodzie programowania liniowego całkowitoliczbowego dzielimy problem zrelaksowany dodając dodatkowe ograniczenia jeśli:
problem zrelaksowany jest niesprzeczny i wszystkie zmienne przyjmują wartości całkowite
żadne z powyższych
problem zrelaksowany jest niesprzeczny i wartość funkcji kosztu jest nie lepsza od kosztu najlepszego rozwiązania całkowitoliczbowego
problem zrelaksowany jest sprzeczny
Pytanie 36
Niedeterministyczna maszyna Turinga:
w sposób losowy zmienia stan głowicy
w sposób losowy wybiera przejście
przesuwa głowicę w losowo wybranym kierunku
wypisuje losowy symbol na tasmie
Pytanie 37
Prawdopodobnie obowiązują następujące relacje między klasami problemów:
P =NP. i PSPACE = NPSPCAE
P <>NP. i PSPACE = NPSPCAE
P =NP. i PSPACE = NPSPCAE
P <>NP. i PSPACE <> NPSPCAE
Pytanie 38
Technika dowodzenia NP. – trudności polega na tym, by:
sprowadzić do niego znany problem NP.- zupełny w czasie niewielomianowym
sprowadzić go do znanego problemu NP.- zupełnego w czasie wielomianowym
sprowadzić go do znanego problemu NP.- zupełnego w czasie niewielomianowym
sprowadzic do niego znany problem NP.- zupełny w czasie wielomianowym
Pytanie 39
W przypadku kompresji tekstu metoda kodowania powtórzeń kodowanie licznika powtórzeń zależy od:
żadne z powyższych
średniej długości ciągu jednakowych znaków
minimalnej długości ciągu jednakowych znaków
maksymalnej długości ciągu jednakowych znaków
Pytanie 40
Algorytm sortowania przez zliczanie ma złożoność:
większa niż szybkie sortowanie i mniejsza niż sortowanie przez wstawianie
wiekszą niż sortowanie przez wybieranie
większą niż sortowanie przez wstawianie i mniejszą niż sortowanie przez wybieranie
mniejszą niż quicksort
Pytanie 41
Jeżeli wielkość rekordu danych to 1 kB. wielkość rekordu indeksu 10B. wielkość sektora 10kB. to wyszukanie jednego spośrod 1.000,000 rekordów przy zastosowaniu indeksu rzadkiego zajmie:
10 ms
100 ms
1 ms
1000ms
Pytanie 42
W systemie RDBMS zarządzania bazą danych:
sektor przechowuje kratkę a rekord pole
plik przechowuje relację a rekord kratkę
sektor przechowuje relację a rekord krotkę
plik przechowuje kolumnę a rekord pole
Pytanie 43
Przy sortowaniu przez scalanie w pamięci zewnętrznej użycie 3 taśm zamiast 4 (tzn 1 wyjściowej zamiast 2)
zwiększa liczbę faz o 33%
zwiększa liczbę faz o 100%
nie zmienia liczby faz
zmniejsza liczbę faz o 25%
Pytanie 44
Dla problemu P min c^T x: Ax>=b i jego problemu dualnego D
wartość kosztu optymalnego rozwiązania P jest większa-równa niż kosztu optymalnego rozwiązania D
wartość kosztu dowolnego rozwiązania D jest większa- równa niż kosztu dowolnego rozwiązania P
wartość kosztu dowolnego rozwiązania P jest większa- równa niż kosztu dowolnego rozwiązania D
wartość kosztu optymalnego rozwiązania D jest większa-równa niż kosztu optymalnego rozwiązania P
Pytanie 45
Którego algorytmu nie można użyć do radixsort iteracyjnego (od prawej)
Countsort
Insertsort
można wszystkie
Selectionsort
Pytanie 46
W grafie o m wierzchołkach i n krawędziach liczba ograniczeń dotyczących przepustowości w sformułowaniu problemu przepływu towarów wynosi:
d
mn
n
nd
Pytanie 47
Poszukując najgrubszej ścieżki przy użyciu algorytmu Dijkstry, do kolejnej iteracji należny wybrać wierzchołek:
ocechowany o największej wartości etykiety
nieocechowany o największej wartości etykiety
ocechowany o najmniejszej wartości etykiety
nieocechowany o najmniejszej wartości etykiety
Pytanie 48
Ile bitów jest potrzebne do zapisania skompresowanego tekstu xyuzyzy
11
13
10
12
Pytanie 49
Usuwanie minimalnego elementu z kolejki priorytetowej opartej na stogu jest w stosunku do zastosowania listy uporządkowanej:
log n razy wolniejsze
n / log n razy szybsze
log n razy szybsze
n / log n razy wolniejsze
Pytanie 50
Przy znajdowaniu maksymalnego przepływu, krawędzi nieskierowanej o przepustowości 1 i o przepływie 1/3 w grafie resztkowym odpowiada:
krawędź skierowana przeciwnie do przepływu o przepustowości 2/3
krawędź skierowana zgodnie o przepustowości 2/3 i krawędź skierowana przeciwnie o przepustowości 1/3
krawędź skierowana zgodnie o przepustowości 2/3 i krawędź skierowana przeciwnie o przepustowości 4/3
krawędź nieskierowana o przepustowości 2/3
Pytanie 51
Problemy NP-trudne to
problemy rozwiązywania przez niedeterministyczną maszynę Turinga w czasie wielomianowym
Podklasa problemów NP.- zupełnych
problemy rozwiązywania przez deterministyczną maszynę Turinga w czasie niewielomianowym
Nadklasa problemów NP.- zupełnych
Pytanie 52
Złożoność wyszukiwania wzorca o długości m, w tekście o długości n. algorytmem MCKP:
jest proporcjonalna do log m
nie zależy od m
jest proporcjonalna do m
jest proporcjonalna do n log m
Pytanie 53
Sortowanie przez scalanie przy wykorzystaniu 2 taśm wejściowych i 1 wyjściowej w porównaniu z 2 wejściowymi i 2 wyjściowymi ma złożoność w przybliżeniu:
3 razy większą
2 razy mniejszą
2 razy większą
taką samą
Pytanie 54
W nierekurencyjnym algorytmie sortowania pozycyjnego n elementów, są sortowane:
od lewej strony. ze złożonością n log n
od prawej strony. ze złożonością n
od lewej strony. ze złożonością n
od prawej strony. ze złożonością n log n
Pytanie 55
W drzewie turniejowym, w porównaniu ze stogiem liczba wierzchołków jest:
taka sama
-
dwukrotnie większa
dwukrotnie mniejsza
Pytanie 56
Operacja dominująca algorytmu sortowania plików dyskowych przez scalanie to:
scalanie dwóch posortowanych ciągów
odczytu lub zapisu sektora
rozszerzanie posortowanych ciągów na taśmy wejściowe
-
Pytanie 57
Klucz tajny przesyłany przez A do B jest szyfrowany kluczem
prywatnym B
publicznym A
prywatnym A
publicznym B
Pytanie 58
Algorytm Kruskala znajdowania najlżejszego drzewa rozpinającego, iteracyjnie:
powiększa konstruowane drzewo o najlżejszą krawędź
łączy dwa najtańsze drzewa
łączy dwa dowolne drzewa najlżejsza krawędzią
rozpina wierzchołki drzewa na najlżejszych krawędziach
Pytanie 59
W sformułowaniu problemu przepływu d towarów w grafie o m wierzchołkach i n krawędziach liczba ograniczeń wynosi:
nd+m
n + m
md+n
n + d
Pytanie 60
Obniżenie temperatury w procesie symulacyjnego wyżarzania powoduje zmniejszanie:
wartości funkcji kosztu generowanych rozwiązań
wartości funkcji kosztu przewidywanych rozwiązań
prawdopodobieństwa przyjęcia gorszego rozwiązania
prawdopodobieństwa wygenerowania gorszego rozwiązania
Pytanie 61
Operacja konstruowania stogu zawierającego n elementów ma złożoność
1
log n
n
n log n
Pytanie 62
Najmniejszą złożoność w sensie liczby zmian elementów ma algorytm sortowania:
przez wybieranie
przez wstawianie
quicksort
bąbelkowy
Pytanie 63
Dane sa 4 krawędzie grafu i ich przepustowości AB=1, BC=2, CD=1, DA=2 oraz 2 zapotrzebowania AC=2, BD=2. Przepływ wielkotowarowy jest:
realizowany bo 6>10
realizowany bo 6<=8
niezrealizowany bo 4<=4
niezrealizowany bo 6<8
Pytanie 64
W algorytmie optymalizacji gradientowej metodą największego spadku metoda złotego podziału służy do wyznaczania:
wektora przesunięcia
kierunku przesunięcia
rzutu kierunku największego spadku na przestrzeń rozwiązań
gradientu funkcji kosztu
Pytanie 65
Kompresja tekstu abcaca algorytmem Hoffmana zwróci:
010110110
1001110110
0111001011
1110010110
Pytanie 66
Wyznaczanie zbioru najkrótszych rozłącznych ścieżek wymaga iteracyjnego wyznaczenia przeplotu:
najkrótszego. algorytmem poprawiania etykiet
o ujemnej długości. algorytmem Dijkstry
o ujemnej długości. algorytmem poprawiania etykiet
najkrótszego. algorytmem Diikstry
Pytanie 67
Aby zadany przepływ d towarów o wspólnym ujściu sprowadzić do przepływu jednotowarowego konieczne jest dodanie:
1 wierzchołka i d krawędzi
d wierzchołków i d krawędzi
d wierzchołków i jednej krawędzi
1 wierzchołka i 1 krawędzi
Pytanie 68
W algorytmie Karmarkara dla zadania programowania liniowego Ax=b wektor przesunięcia z ...:
Ay=0
ADy=0
Ay=b
ADy=b
Pytanie 69
Scalanie ciągów o długościach n (b.duże) i m algorytmem wstawiania, w stosunku do algorytmu sekwencyjnego jest lepsze:
n razy
m razy
log n razy
n / log n razy
Pytanie 70
Jeżeli wielkość rekordu to 1kB, wielkość rekordu indeksu 10B, wielkość sektora 10KB?, to wyszukanie jednego spośród 100,000 rekordów przy zastosowaniu indeksu rzadkiego w porównaniu z zastosowaniem funkcji haszującej o 10 wartościach jest:
100 razy szybsze
1 razy szybsze
tak samo szybkie
10 razy szybsze
Pytanie 71
W przypadku znajdowania najdroższego rozwiązania metodą podziałów i ograniczeń, wartość funkcji kosztu ogranicza przeglądanie rozwiązań, gdy jest:
ograniczeniem dolnym. mniejszym od kosztu najlepszego rozwiązania
ograniczeniem dolnym. większym od kosztu najlepszego rozwiązania
ograniczeniem górnym. mniejszym od kosztu najlepszego rozwiązania
ograniczeniem dolnym. większym od kosztu najlepszego rozwiązania
Pytanie 72
Maszyna Turinga musi mieć własność stopu dla języków:
nierozstrzygalnych
rozstrzygalnych
akceptowalnych
nieakceptowalnych
Pytanie 73
W metodzie haszowania zamkniętego funkcja haszująca wyznacza:
indeks w tablicy dla danego klucza
wartość elementu na poszukiwanej liście
-
-