Twój wynik: AiSDE Egzamin
Analiza
Wszystkie ({{dataStorage.userResults.answersTotal}})
Prawidłowe ({{dataStorage.userResults.answersGood}})
Do powtórki ({{dataStorage.userResults.answersRepeat}})
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:
100000
1000
10000
100
Pytanie 2
Liczba poziomów drzewa turniejowego zawierającego 1000 elementów wynosi:
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
PushUp, od dołu, n/2 razy
PushUp, od góry, n razy
PushDown, od dołu, n razy
Pytanie 4
W trakcie symulacji zdarzeniowej czas symulacji zmieniamy:
w momencie pobrania zdarzenia, na czas tego zdarzenia
po obsłużeniu zdarzenia, o jedną jednostkę czasu
w momencie wstawienia 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:
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:
2
1 / n
n
1
Pytanie 7
Poszukując wśród n elementów k najmniejszych należy wstawić do stogu dokładnie:
k - 1 elementów
k elementów
n - k elementów
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:
1
log n
k
n
Pytanie 9
Poszukując najlżejszego drzewa rozpinającego, konstruowanie drzewa:
w algorytmie Kruskala zaczynamy od najkrótszej krawędzi, a w Prima nie
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
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:
k
n - k
1 / (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
1 / n
n
n /m
Pytanie 13
Przy wyszukiwaniu metodą interpolacyjną jednego spośród miliona elementów trzeba wykonać kroków około:
50
5
10
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 / 1000
1 / 100
1
1 / 10
Pytanie 15
Złożoności pesymistyczne wyszukania elementu w słowniku opartym na drzewie BST i drzewie AVL pozostają w stosunku:
n
1
log n / n
n / log 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
m / n
n / m
Pytanie 17
W haszowaniu zamkniętym, gdy stosujemy rehasz przy szukaniu elementu, którego nie ma w słowniku, kończymy, gdy:
wykonamy rehasz określoną liczbę razy
napotkamy pozycję wolną
funkcja rehaszu zwróci tą samą wartość
napotkamy pozycję zajętą przez inny element
Pytanie 18
Liczba wierzchołków drzewa pozycyjnego struktury słownika (nie licząc korzenia) jest równa:
Żadne z powyższych
liczbie liter alfabetu
liczbie słów słownika
liczbie liter najdłuższego słowa
Pytanie 19
W algorytmach znajdowania rozłącznych ścieżek przeplot to:
ścieżka nie korzystająca z krawędzi należących do dotychczasowych ścieżek zgodnie z ich skierowaniem
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
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ź nieskierowana o przepustowości 3/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ź skierowana przeciwnie do przepływu o przepustowości 1/2
Pytanie 21
Wyznaczanie maksymalnego przepływu wymaga iteracyjnego znajdowania ścieżki wzbogacającej:
dowolnej, algorytmem poprawiania etykiet
najkrótszej, algorytmem Dijkstry
dowolnej, algorytmem Dijkstry
najkrótszej, 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:
m
n
d
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<=10
nierealizowany, bo 6>=5
realizowany, bo 6>5
nierealizowany, bo 6<10
Pytanie 24
W algorytmie minimalizacji metodą sympleksu zawsze generowany jest kolejny wierzchołek zbioru rozwiązań dopuszczalnych:
óż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
różniący się jedną zmienną bazową i 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
która zmienna powinna wejść do bazy
że problem jest sprzeczny
że problem jest nieograniczony
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 n/k' razy mniejszy niż indeks rzadki
indeks gęsty jest n/k' razy większy niż indeks rzadki
indeks gęsty jest k' razy mniejszy 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:
tak samo szybkie
10 razy szybsze
10 razy wolniejsze
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 log m
od prawej strony ze złożonością k log m
od lewej strony ze złożonością k
od prawej strony ze złożonością k
Pytanie 29
W trakcie wyszukiwania wzorca w tekście gdy stwierdzamy niezgodność znaków wzorca i tekstu:
przesuwamy wzorzec o 1 znak i zaczynamy porównywanie od bieżącego znaku tekstu
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ów i zaczynamy porównywanie od pierwszego znaku wzorca
Pytanie 30
Kompresja tekstu xyuzyzy z użyciem algorytmu Huffmana zwróci:
011001110110
010110110001
01110011011
0111000101001
Pytanie 31
W modelu klucza publicznego strona B udowadnia niezaprzeczalność wiadomości otrzymanej od strony A korzystając z klucza:
prywatnego B
publicznego B
prywatnego A
publicznego A
Pytanie 32
W modelu klucza publicznego treść wiadomości wysyłanej przez stronę A jest szyfrowana przy użyciu klucza:
publicznego B
prywatnego A
tajnego wygenerowanego przez B
tajnego wygenerowanego przez A
Pytanie 33
Przy minimalizacji funkcji metodą największego spadku wykonujemy złoty podział aby:
wyznaczyć minimum funkcji w kierunku największego spadku
wyznaczyć kierunek najwiekszego spadku wartości funkcji
ograniczyć obszar poszukiwań do otoczenia minimum globalnego
ograniczyć przedział poszukiwań minimum funkcji w kierunku
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 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 niższe od najlepszego znanego rozwiązania
oszacowanie górne 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 wartość funkcji kosztu jest nie lepsza od kosztu najlepszego rozwiązania całkowitoliczbowego
problem zrelaksowany jest sprzeczny
żadne z powyższych
problem zrelaksowany jest niesprzeczny i wszystkie zmienne przyjmują wartości całkowite
Pytanie 36
Niedeterministyczna maszyna Turinga:
w sposób losowy zmienia stan głowicy
przesuwa głowicę w losowo wybranym kierunku
wypisuje losowy symbol na tasmie
w sposób losowy wybiera przejście
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ć 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
sprowadzić do niego znany problem NP.- zupełny w czasie niewielomianowym
Pytanie 39
W przypadku kompresji tekstu metoda kodowania powtórzeń kodowanie licznika powtórzeń zależy od:
żadne z powyższych
maksymalnej długości ciągu jednakowych znaków
minimalnej długości ciągu jednakowych znaków
średniej 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
większą niż sortowanie przez wstawianie i mniejszą niż sortowanie przez wybieranie
mniejszą niż quicksort
wiekszą niż sortowanie przez wybieranie
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:
100 ms
1 ms
10 ms
1000ms
Pytanie 42
W systemie RDBMS zarządzania bazą danych:
plik przechowuje relację a rekord kratkę
sektor przechowuje relację a rekord krotkę
sektor przechowuje kratkę a rekord pole
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 100%
zwiększa liczbę faz o 33%
zmniejsza liczbę faz o 25%
nie zmienia liczby faz
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 P jest większa- równa niż kosztu dowolnego rozwiązania D
wartość kosztu dowolnego rozwiązania D jest większa- równa niż kosztu dowolnego rozwiązania P
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)
można wszystkie
Insertsort
Countsort
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:
nd
n
mn
d
Pytanie 47
Poszukując najgrubszej ścieżki przy użyciu algorytmu Dijkstry, do kolejnej iteracji należny wybrać wierzchołek:
ocechowany o najmniejszej wartości etykiety
nieocechowany o najmniejszej wartości etykiety
ocechowany o największej wartości etykiety
nieocechowany o największej wartości etykiety
Pytanie 48
Ile bitów jest potrzebne do zapisania skompresowanego tekstu xyuzyzy
11
10
12
13
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 wolniejsze
n / log n razy szybsze
log n razy szybsze
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ź nieskierowana o przepustowości 2/3
krawędź skierowana zgodnie o przepustowości 2/3 i krawędź skierowana przeciwnie o przepustowości 4/3
krawędź skierowana zgodnie o przepustowości 2/3 i krawędź skierowana przeciwnie o przepustowości 1/3
krawędź skierowana przeciwnie do przepływu o przepustowości 2/3
Pytanie 51
Problemy NP-trudne to
problemy rozwiązywania przez deterministyczną maszynę Turinga w czasie niewielomianowym
Nadklasa problemów NP.- zupełnych
problemy rozwiązywania przez niedeterministyczną maszynę Turinga w czasie wielomianowym
Podklasa 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:
nie zależy od m
jest proporcjonalna do m
jest proporcjonalna do log 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:
taką samą
2 razy większą
3 razy większą
2 razy mniejszą
Pytanie 54
W nierekurencyjnym algorytmie sortowania pozycyjnego n elementów, są sortowane:
od prawej strony. ze złożonością n log n
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
Pytanie 55
W drzewie turniejowym, w porównaniu ze stogiem liczba wierzchołków jest:
dwukrotnie większa
dwukrotnie mniejsza
-
taka sama
Pytanie 56
Operacja dominująca algorytmu sortowania plików dyskowych przez scalanie to:
odczytu lub zapisu sektora
-
scalanie dwóch posortowanych ciągów
rozszerzanie posortowanych ciągów na taśmy wejściowe
Pytanie 57
Klucz tajny przesyłany przez A do B jest szyfrowany kluczem
prywatnym A
publicznym A
prywatnym B
publicznym B
Pytanie 58
Algorytm Kruskala znajdowania najlżejszego drzewa rozpinającego, iteracyjnie:
rozpina wierzchołki drzewa na najlżejszych krawędziach
powiększa konstruowane drzewo o najlżejszą krawędź
łączy dwa dowolne drzewa najlżejsza krawędzią
łączy dwa najtańsze drzewa
Pytanie 59
W sformułowaniu problemu przepływu d towarów w grafie o m wierzchołkach i n krawędziach liczba ograniczeń wynosi:
n + m
n + d
md+n
nd+m
Pytanie 60
Obniżenie temperatury w procesie symulacyjnego wyżarzania powoduje zmniejszanie:
prawdopodobieństwa przyjęcia gorszego rozwiązania
prawdopodobieństwa wygenerowania gorszego rozwiązania
wartości funkcji kosztu generowanych rozwiązań
wartości funkcji kosztu przewidywanych rozwiązań
Pytanie 61
Operacja konstruowania stogu zawierającego n elementów ma złożoność
log n
1
n
n log n
Pytanie 62
Najmniejszą złożoność w sensie liczby zmian elementów ma algorytm sortowania:
quicksort
przez wstawianie
bąbelkowy
przez wybieranie
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:
niezrealizowany bo 6<8
niezrealizowany bo 4<=4
realizowany bo 6<=8
realizowany bo 6>10
Pytanie 64
W algorytmie optymalizacji gradientowej metodą największego spadku metoda złotego podziału służy do wyznaczania:
rzutu kierunku największego spadku na przestrzeń rozwiązań
kierunku przesunięcia
wektora przesunięcia
gradientu funkcji kosztu
Pytanie 65
Kompresja tekstu abcaca algorytmem Hoffmana zwróci:
1001110110
0111001011
010110110
1110010110
Pytanie 66
Wyznaczanie zbioru najkrótszych rozłącznych ścieżek wymaga iteracyjnego wyznaczenia przeplotu:
o ujemnej długości. algorytmem Dijkstry
o ujemnej długości. algorytmem poprawiania etykiet
najkrótszego. 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
1 wierzchołka i 1 krawędzi
d wierzchołków i d krawędzi
d wierzchołków i jednej krawędzi
Pytanie 68
W algorytmie Karmarkara dla zadania programowania liniowego Ax=b wektor przesunięcia z ...:
ADy=b
Ay=b
Ay=0
ADy=0
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
log n razy
m 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:
10 razy szybsze
tak samo szybkie
100 razy szybsze
1 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 górnym. mniejszym od kosztu najlepszego rozwiązania
ograniczeniem dolnym. większym od kosztu najlepszego rozwiązania
ograniczeniem dolnym. 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:
akceptowalnych
nieakceptowalnych
nierozstrzygalnych
rozstrzygalnych
Pytanie 73
W metodzie haszowania zamkniętego funkcja haszująca wyznacza:
-
wartość elementu na poszukiwanej liście
-
indeks w tablicy dla danego klucza