Edukacja







M E N U  TESTY2 Zalogowany: Sebastian Galazka  Kurs: Algorytmy i struktury danych (ASD) - studia dzienne  POMOCWYLOGUJTwój wynik: 4 punktów na 6 możliwych do uzyskania (66,67 %).Galazka SebastianNrOpcjaPunktyPoprawnaOdpowiedź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 1++Kod litery odczytany z drzewa jest następujący: 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ść pamięciową algorytmu Huffman dla danych rozmiaru , wtedy: 0Niech 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: 0Niech oznacza złożoność czasową algorytmu Huffman dla danych rozmiaru , w każdym przypadku, mierzoną liczbą operacji 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 .Kolejność 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 1++Liczba chromatyczna grafu jest równa dokładnie 0+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 każdym przypadku, mierzoną liczbą operacji porównań elementów wewnątrz struktury kolejki priorytetowej, wtedy: 0Niech 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ą.Wysokość drzewa najkrótszych ścieżek będącego 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 1+Liczba
wierzchołków wewnętrznych w drzewie najkrótszych ścieżek będącym
rezultatem działania algorytmu Dijkstry jest równa dokładnie 0+6Rozważ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ść pamięciową algorytmu DijkstraArray dla danych rozmiaru , wtedy: 0Niech oznacza złożoność czasową algorytmu DijkstraArray dla danych rozmiaru , w każdym przypadku, mierzoną liczbą porównań odległości, wtedy: 1++System edukacyjny. PJWSTK 2001-2007