Nauka
AiSDE Egzamin
Wyświetlane są wszystkie pytania.
Pytanie 49
Usuwanie minimalnego elementu z kolejki priorytetowej opartej na stogu jest w stosunku do zastosowania listy uporządkowanej:
n / log n razy szybsze
log n razy wolniejsze
n / log n razy wolniejsze
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ź 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
krawędź skierowana przeciwnie do przepływu o przepustowości 2/3
Pytanie 51
Problemy NP-trudne to
Podklasa problemów NP.- zupełnych
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
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 m
jest proporcjonalna do n log m
jest proporcjonalna do log m
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:
2 razy mniejszą
3 razy większą
taką samą
2 razy większą
Pytanie 54
W nierekurencyjnym algorytmie sortowania pozycyjnego n elementów, są sortowane:
od prawej strony. ze złożonością n
od prawej strony. ze złożonością n log n
od lewej strony. ze złożonością n
od lewej 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
-