M E N U TESTY2 Zalogowany: Przemyslaw Panczyk Kurs: Algorytmy i struktury danych (ASD) - studia dzienne POMOCWYLOGUJTwój wynik: 1 punktów na 6 możliwych do uzyskania (16,67 %).Panczyk PrzemyslawNrOpcjaPunktyPoprawnaOdpowiedź1Rozważmy algorytm Huffmana budowy kodu prefiksowego:dla danych wejściowych (znak - krotność występowania):Które z poniższych zdań jest prawdziwe? Uwaga! W przypadku niejednoznacznego wyboru poddrzew, za mniejsze uznajemy to, którego etykiet liści czytane od lewej do prawej strony tworzą słowo mniejsze w sensie porządku leksykograficznego.Wysokość drzewa kodu Huffmana w rozważanym przypadku jest równa dokładnie 0Wysokość drzewa kodu Huffmana w rozważanym przypadku jest równa dokładnie 1+Kod litery odczytany z drzewa jest następujący: 02Rozważmy algorytm Huffman budowy kodu prefiksowego:Które z poniższych zdań jest prawdziwe, jeżeli oraz kolejka priorytetowa została zaimplementowana w kopcu-drzewie binarnym z operacją budowy kolejki priorytetowej zgodną z szybkim algorytmem konstrukcji kopca-drzewa?Niech oznacza złożoność czasową algorytmu Huffman dla danych rozmiaru , w każdym przypadku, mierzoną liczbą operacji kolejki priorytetowej, wtedy: 1+Niech oznacza złożoność pamięciową algorytmu Huffman dla danych rozmiaru , wtedy: 0Niech oznacza złożoność czasową algorytmu Huffman dla danych rozmiaru , w średnim przypadku, mierzoną liczbą operacji porównań elementów wewnątrz struktury kolejki priorytetowej, wtedy: 1++3Rozważmy algorytm kolorowania wierzchołków grafu ColoringLF postaci:dla grafu :zbiór wierzchołków grafu ,zbiór krawędzi grafu zadany tablicą list incydencji: ,przedstawionego na poniższym rysunku.Które z poniższych zdań jest prawdziwe? Uwaga! W przypadku niejednoznacznej możliwości wyboru wierzchołków, jako pierwszy wybieramy wierzchołek z mniejszą etykietą. Kolory indeksujemy od .Po zastosowaniu algorytm ColoringLF wierzchołek ma przypisany kolor 0Liczba chromatyczna grafu jest równa dokładnie 0Po zastosowaniu algorytm ColoringLF maksymalna liczba wierzchołków o tym samym kolorze jest równa dokładnie 04Rozważmy algorytm kolorowania wierzchołków grafu ColoringLF postaci:Które z poniższych zdań jest prawdziwe, jeżeli oraz i kolejka priorytetowa została zaimplementowana w kopcu-drzewie binarnym z operacją budowy kolejki priorytetowej zgodną z szybkim algorytmem konstrukcji kopca-drzewa?Niech oznacza złożoność czasową algorytmu ColoringLF dla danych rozmiaru , w średnim przypadku, mierzoną liczbą operacji kolejki priorytetowej, wtedy: 0+Niech oznacza złożoność czasową algorytmu ColoringLF dla danych rozmiaru , w średnim przypadku, mierzoną liczbą operacji porównań elementów wewnątrz struktury kolejki priorytetowej, wtedy: 1+Niech oznacza złożoność czasową algorytmu ColoringLF dla danych rozmiaru , w każdym przypadku, mierzoną liczbą odwiedzonych wierzchołków, wtedy: 05Rozważmy algorytm DijkstraArray w wersji z tablicą pomocniczą, postaci:dla grafu :zbiór wierzchołków grafu ,zbiór krawędzi grafu zadany tablicą list incydencji: wierzchołek startowy .przedstawionego na poniższym rysunku.Które z poniższych zdań jest prawdziwe? Uwaga! W przypadku niejednoznacznej możliwości wyboru wierzchołków, jako pierwszy wybieramy wierzchołek z mniejszą etykietą.Wierzchołek leży na najkrótszej ścieżce z wierzchołka startowego do wierzchołka w drzewie najkrótszych ścieżek będącym rezultatem działania rozważanego algorytmu dla grafu 0Liczba wierzchołków wewnętrznych w drzewie najkrótszych ścieżek będącym rezultatem działania algorytmu Dijkstry jest równa dokładnie 1+Koszt najkrótszej ścieżki z wierzchołka do wierzchołka w rozważanym grafie jest równy dokładnie 06Rozważmy algorytm DijkstraArray w wersji z tablicami pomocniczymi, postaci:Które z poniższych zdań jest prawdziwe, jeżeli oraz i ?Niech oznacza złożoność czasową algorytmu DijkstraArray dla danych rozmiaru , w każdym przypadku, mierzoną liczbą porównań odległości, wtedy: 1+Niech oznacza złożoność czasową algorytmu DijkstraArray dla danych rozmiaru , w każdym przypadku, mierzoną liczbą porównań odległości, wtedy: 1+Niech oznacza złożoność pamięciową algorytmu DijkstraArray dla danych rozmiaru , wtedy: 1++System edukacyjny. PJWSTK 2001-2007