Pytania i odpowiedzi
AiSDE Egzamin
Zebrane pytania i odpowiedzi do zestawu. Odpowiedzi na podstawie "biblii algorytmów"
Ilość pytań: 73
Rozwiązywany: 3915 razy
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:
1000ms
Pytanie 42
W systemie RDBMS zarządzania bazą danych:
sektor przechowuje relację a rekord krotkę
Pytanie 43
Przy sortowaniu przez scalanie w pamięci zewnętrznej użycie 3 taśm zamiast 4 (tzn 1 wyjściowej zamiast 2)
nie zmienia liczby faz
Pytanie 44
Dla problemu P min c^T x: Ax>=b i jego problemu dualnego D
wartość kosztu dowolnego rozwiązania P jest większa- równa niż kosztu dowolnego rozwiązania D
Pytanie 45
Którego algorytmu nie można użyć do radixsort iteracyjnego (od prawej)
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:
n
Pytanie 47
Poszukując najgrubszej ścieżki przy użyciu algorytmu Dijkstry, do kolejnej iteracji należny wybrać wierzchołek:
nieocechowany o największej wartości etykiety
Pytanie 48
Ile bitów jest potrzebne do zapisania skompresowanego tekstu xyuzyzy
13
Pytanie 49
Usuwanie minimalnego elementu z kolejki priorytetowej opartej na stogu jest w stosunku do zastosowania listy uporządkowanej:
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 zgodnie o przepustowości 2/3 i krawędź skierowana przeciwnie o przepustowości 4/3
Pytanie 51
Problemy NP-trudne to
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:
nie zależy od 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ą
Pytanie 54
W nierekurencyjnym algorytmie sortowania pozycyjnego n elementów, są sortowane:
od prawej 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
Pytanie 56
Operacja dominująca algorytmu sortowania plików dyskowych przez scalanie to:
odczytu lub zapisu sektora
Pytanie 57
Klucz tajny przesyłany przez A do B jest szyfrowany kluczem
publicznym B
Pytanie 58
Algorytm Kruskala znajdowania najlżejszego drzewa rozpinającego, iteracyjnie:
łączy dwa dowolne drzewa najlżejsza krawędzią
Pytanie 59
W sformułowaniu problemu przepływu d towarów w grafie o m wierzchołkach i n krawędziach liczba ograniczeń wynosi:
md+n
Pytanie 60
Obniżenie temperatury w procesie symulacyjnego wyżarzania powoduje zmniejszanie:
prawdopodobieństwa przyjęcia gorszego rozwiązania