Edukacja







M E N U  TESTY2 Zalogowany: Grzegorz Wierzowiecki  Kurs: Algorytmy i struktury danych (ASD) - studia dzienne  POMOCWYLOGUJTwój wynik: 3 punktów na 6 możliwych do uzyskania (50 %).Wierzowiecki GrzegorzNrOpcjaPunktyPoprawnaOdpowiedź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.Etykiety liści drzewa kodu Huffmana w rozważanym przypadku czytane od lewej do prawej strony tworzą ciąg 0Kod litery odczytany z drzewa jest następujący: 1++Etykiety liści drzewa kodu Huffmana w rozważanym przypadku czytane od lewej do prawej strony tworzą ciąg 0+2Rozważ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 pesymistycznym przypadku, mierzoną liczbą operacji porównań elementów wewnątrz struktury kolejki priorytetowej, wtedy: 1++Niech 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 średnim przypadku, mierzoną liczbą operacji 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 0Kolejność kolorowania wierzchołków grafu w trakcie wykonania algorytmu ColoringLF jest następująca: 1+Po zastosowaniu algorytm ColoringLF minimalna 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: 1++Niech oznacza złożoność czasową algorytmu ColoringLF dla danych rozmiaru , w pesymstycznym przypadku, mierzoną liczbą operacji kolejki priorytetowej, wtedy: 0Niech oznacza złożoność czasową algorytmu ColoringLF dla danych rozmiaru , w średnim przypadku, mierzoną liczbą odwiedzonych wierzchołków, wtedy: 1++5Rozważ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ą.Kolejność przyłączania wierzchołków do drzewa najkrótszych ścieżek grafu w trakcie wykonania algorytmu DijkstraArray jest następująca: 1++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 1++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 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: 0+Niech oznacza złożoność pamięciową algorytmu DijkstraArray dla danych rozmiaru , wtedy: 0System edukacyjny. PJWSTK 2001-2007