Strona 7
AiSDE Egzamin
Pytanie 49
Usuwanie minimalnego elementu z kolejki priorytetowej opartej na stogu jest w stosunku do zastosowania listy uporządkowanej:
log n razy szybsze
n / log n razy szybsze
log n razy wolniejsze
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ź nieskierowana 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 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
Pytanie 51
Problemy NP-trudne to
problemy rozwiązywania przez niedeterministyczną maszynę Turinga w czasie wielomianowym
problemy rozwiązywania przez deterministyczną maszynę Turinga w czasie niewielomianowym
Nadklasa problemów NP.- zupełnych
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 log 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:
2 razy mniejszą
3 razy większą
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 lewej 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
Pytanie 55
W drzewie turniejowym, w porównaniu ze stogiem liczba wierzchołków jest:
-
dwukrotnie mniejsza
taka sama
dwukrotnie większa
Pytanie 56
Operacja dominująca algorytmu sortowania plików dyskowych przez scalanie to:
rozszerzanie posortowanych ciągów na taśmy wejściowe
-
odczytu lub zapisu sektora
scalanie dwóch posortowanych ciągów