Ucz się szybciej
Testy Fiszki Notatki
Zaloguj  

Strona 1

AISDE LAB5

Pytanie 1
Algorytm Prima:
po dodaniu każdej krawędzi wymaga sprawdzenia czy nie powstał cykl
usuwa krawędzie odrzucone aż zostanie odpowiednie drzewo
jego złożoność obliczeniowa zależy od ilości krawędzi
sukcesywnie dodaje krawędzie do drzewa, aż powstanie drzewo rozpinające
Pytanie 2
Algorytm Kruskala:
usuwa krawędzie odrzucone aż zostanie odpowiednie drzewo
sukcesywnie dodaje krawędzie do drzewa, aż powstanie drzewo rozpinające
po dodaniu każdej krawędzi wymaga sprawdzenia czy nie powstał cykl
jego złożoność obliczeniowa zależy od ilości krawędzi
Pytanie 3
Algorytm Boruvki:
tworzy drzewo Steinera
nie działa, gdy są cykle
działa tylko dla grafów skierowanych
na początku dokonuje sprawdzenia czy są cykle
Pytanie 4
Algorytm Floyda w stosunku do Dijkstry:
- może znajdować długości cykli
- może działać dla krawędzi o ujemnych wagach
- działa niezależnie od liczby krawędzi grafu
może działać nieprawidłowo dla grafu o wagach dodatnich nienaturalnych
Pytanie 5
Ogólne pytania:
graf niepełny nieskierowany ma max V*(V-1)/2 krawędzi
złożoność pamięciowa Floyda wynosi V^2
gdy wszystkie wagi grafu są różne, to istnieje tylko 1 drzewo rozpinające
macierz sąsiedztwa ma wymiar VxE, dla V-liczba wierzchołków, E-liczba krawędzi
Pytanie 6
Pytanie teoretyczne prawda/fałsz (1pkt) o Floyda
czy najlepiej implementowac na macierzy
czy czas trwania algorytmu zalezy bardziej od wiercholkow niz krawedzi
czy algorytm po skonczeniu dzialania daje w wyniku dlugosci cykli
czy wagi NIE moga byc ujemne
Pytanie 7
Algorytm Dijkstry nie nadaje sie do szukania najkrotszych sciezek
w grafach zawierajacych cykle
działać dla krawędzi o ujemnych wagach
w grafach planarnych
w grafach skieowanych
Przejdź na Memorizer+
W trybie testu zyskasz:
Brak reklam
Quiz powtórkowy - pozwoli Ci opanować pytania, których nie umiesz
Więcej pytań na stronie testu
Wybór pytań do ponownego rozwiązania
Trzy razy bardziej pojemną historię aktywności
Wykup dostęp
Pokaż wyniki To już koniec testu, na następnej stronie zobaczysz swoje odpowiedzi.