Fiszki
AiSDE Egzamin
Test w formie fiszek Odpowiedzi na podstawie "biblii algorytmów"
Ilość pytań: 73
Rozwiązywany: 3913 razy
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
1000ms
W systemie RDBMS zarządzania bazą danych:
plik przechowuje relację a rekord kratkę
sektor przechowuje kratkę a rekord pole
sektor przechowuje relację a rekord krotkę
plik przechowuje kolumnę a rekord pole
sektor przechowuje relację a rekord krotkę
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%
nie zmienia liczby faz
zmniejsza liczbę faz o 25%
zwiększa liczbę faz o 100%
nie zmienia liczby faz
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
wartość kosztu dowolnego rozwiązania P jest większa- równa niż kosztu dowolnego rozwiązania D
Którego algorytmu nie można użyć do radixsort iteracyjnego (od prawej)
Countsort
można wszystkie
Insertsort
Selectionsort
Selectionsort
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
nd
n
mn
n
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 największej wartości etykiety
nieocechowany o najmniejszej wartości etykiety
ocechowany o największej wartości etykiety
nieocechowany o największej wartości etykiety
Ile bitów jest potrzebne do zapisania skompresowanego tekstu xyuzyzy
13
11
12
10
13
Usuwanie minimalnego elementu z kolejki priorytetowej opartej na stogu jest w stosunku do zastosowania listy uporządkowanej:
log n razy wolniejsze
log n razy szybsze
n / log n razy szybsze
n / log n razy wolniejsze
log n razy wolniejsze
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 4/3
krawędź skierowana zgodnie o przepustowości 2/3 i krawędź skierowana przeciwnie o przepustowości 1/3
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
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
Nadklasa problemów NP.- zupełnych
Złożoność wyszukiwania wzorca o długości m, w tekście o długości n. algorytmem MCKP:
jest proporcjonalna do m
jest proporcjonalna do log m
jest proporcjonalna do n log m
nie zależy od m
nie zależy od m
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:
2 razy większą
taką samą
3 razy większą
2 razy mniejszą
taką samą
W nierekurencyjnym algorytmie sortowania pozycyjnego n elementów, są sortowane:
od lewej strony. ze złożonością n
od lewej strony. ze złożonością n log n
od prawej strony. ze złożonością n
od prawej strony. ze złożonością n log n
od prawej strony. ze złożonością n
W drzewie turniejowym, w porównaniu ze stogiem liczba wierzchołków jest:
dwukrotnie większa
-
taka sama
dwukrotnie mniejsza
dwukrotnie większa
Operacja dominująca algorytmu sortowania plików dyskowych przez scalanie to:
rozszerzanie posortowanych ciągów na taśmy wejściowe
scalanie dwóch posortowanych ciągów
-
odczytu lub zapisu sektora
odczytu lub zapisu sektora
Klucz tajny przesyłany przez A do B jest szyfrowany kluczem
prywatnym B
publicznym A
prywatnym A
publicznym B
publicznym B
Algorytm Kruskala znajdowania najlżejszego drzewa rozpinającego, iteracyjnie:
łączy dwa dowolne drzewa najlżejsza krawędzią
rozpina wierzchołki drzewa na najlżejszych krawędziach
łączy dwa najtańsze drzewa
powiększa konstruowane drzewo o najlżejszą krawędź
łączy dwa dowolne drzewa najlżejsza krawędzią
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 + d
n + m
md+n
md+n
Obniżenie temperatury w procesie symulacyjnego wyżarzania powoduje zmniejszanie:
wartości funkcji kosztu przewidywanych rozwiązań
wartości funkcji kosztu generowanych rozwiązań
prawdopodobieństwa przyjęcia gorszego rozwiązania
prawdopodobieństwa wygenerowania gorszego rozwiązania
prawdopodobieństwa przyjęcia gorszego rozwiązania