Edukacja M E N U  TESTY2 Zalogowany: Lukasz Tomaszewski  Kurs: Algorytmy i struktury danych (ASD) - studia dzienne  POMOCWYLOGUJTwój wynik: 3 punktów na 6 możliwych do uzyskania (50 %).Tomaszewski LukaszNrOpcjaPunktyPoprawnaOdpowiedź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 0Etykiety liści drzewa kodu Huffmana w rozważanym przypadku czytane od lewej do prawej strony tworzą ciąg 0Etykiety liści drzewa kodu Huffmana w rozważanym przypadku czytane od lewej do prawej strony tworzą ciąg 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 średnim przypadku, mierzoną liczbą operacji porównań elementów wewnątrz struktury kolejki priorytetowej, wtedy: 0Niech oznacza złożoność czasową algorytmu Huffman dla danych rozmiaru , w pesymistycznym przypadku, mierzoną liczbą operacji kolejki priorytetowej, wtedy: 0Niech oznacza złożoność czasową algorytmu Huffman dla danych rozmiaru , w każdym przypadku, mierzoną liczbą operacji porównań elementów wewnątrz struktury kolejki priorytetowej, wtedy: 03Rozważ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 0Po zastosowaniu algorytm ColoringLF minimalna liczba wierzchołków o tym samym kolorze jest równa dokładnie 0Kolejność kolorowania wierzchołków grafu w trakcie wykonania algorytmu ColoringLF jest następująca: 1+4Rozważ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 porównań elementów wewnątrz struktury kolejki priorytetowej, wtedy: 1++Niech oznacza złożoność czasową algorytmu ColoringLF dla danych rozmiaru , w średnim przypadku, mierzoną liczbą odwiedzonych wierzchołków, wtedy: 1+Niech oznacza złożoność czasową algorytmu ColoringLF dla danych rozmiaru , w każdym przypadku, mierzoną liczbą operacji kolejki priorytetowej, 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ą.Suma wag krawędzi tworzących drzewo najkrótszych ścieżek będące rezultatem działania algorytmu DijkstraArray jest równa dokładnie 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 0Liczba wierzchołków zewnętrznych w drzewie najkrótszych ścieżek będącym rezultatem działania algorytmu DijkstraArray jest równa 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: 0Niech oznacza złożoność czasową algorytmu DijkstraArray dla danych rozmiaru , w każdym przypadku, mierzoną liczbą porównań odległości, wtedy: 0Niech oznacza złożoność pamięciową algorytmu DijkstraArray dla danych rozmiaru , wtedy: 1+System edukacyjny. PJWSTK 2001-2007