Edukacja


M E N U  TESTY2 Zalogowany:   Kurs: Algorytmy i struktury danych (ASD)  POMOCWYLOGUJTwój wynik: 2 punktów na 6 możliwych do uzyskania (33,33 %).NrOpcjaPunktyPoprawnaOdpowiedź1Powiemy, że dwa drzewa rozpinające pewnego grafu są różne jeżeli
istnieje krawędź, która należy do jednego i nie należy do drugiego
drzewa. Ile różnych drzew rozpinających można zbudować w
niezorientowanym grafie pełnym o wierzchołkach?1+0+ drzew, dla 02Niech będzie niezorientowanym grafem pełnym z funkcją wag krawędzi postaci , gdzie . Jaki jest koszt minimalnego drzewa rozpinającego otrzymanego w wyniku zastosowania algorytmu Kruskala do grafu ?1+Co najmniej 0Co najmniej 0+3Rozważmy początkowo pustą strukturę Find-Union dla przestrzeni elementów , na której wykonano kolejno następujące operacje:init(u); // tj. u={{a},{b},{c},{d},{e},{f},{g}}union(u,find(u,a),find(u,b));union(u,find(u,g),find(u,h));union(u,find(u,d),find(u,e));union(u,find(u,b),find(u,h));find(u,e);union(u,find(u,g),find(u,b));union(u,find(u,c),find(u,f));union(u,find(u,f),find(u,e));union(u,find(u,h),find(u,c));find(u,e);Zakładamy, że strukturę zaimplementowan w drzewach -arnych
z balansowaniem i kompresją ścieżek. Która z następujących własności
jest prawdziwa po wykonaniu rozważanego ciągu operacji na strukurze ?01++04Jaka jest złożoność, w przypadku pesymistycznym, optymalnego algorytmu sprawdzającego, czy zadany graf o wierzchołkach i krawędziach jest spójny?1+1+1++5Rozważmy graf , gdzie i ,
w którym algorytmy DFS oraz BFS (z ustaloną jednakową kolejnością
akceptacji wierzchołków) generują ten sam ciąg etykiet odwiedzanych
wierzchołków, z pewnego wierzchołka źródłowego . Stąd graf może być ... .Grafem-drzewem -narnym lokalnie pełnym, gdzie 0Grafem-drzewem binarnym wysokości 1++Grafem-drzewem -narnym pełnym, gdzie 1++6Które z wymienionych zdań jest prawdziwe?Istnieje
graf niezorientowany z wagami, dla którego algorytm Kruskala
konstruuje drzewo najkrótszych ścieżek z wybranego wierzchołka1++Dla dowolnego grafu niezorientowanego z wagami istnieje co najmniej jedno minimalne drzewo rozpinające0+Koszt algorytmu Kruskala można oszacować przez , gdzie jest liczbą wierzchołków grafu, a liczbą jego krawędzi1++System edukacyjny. PJWSTK 2001-2007