Edukacja







M E N U  TESTY2 Zalogowany: Arkadiusz Bochenek  Kurs: Algorytmy i struktury danych (ASD) - studia dzienne  POMOCWYLOGUJTwój wynik: 4 punktów na 6 możliwych do uzyskania (66,67 %).Bochenek ArkadiuszNrOpcjaPunktyPoprawnaOdpowiedź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++Wysokość drzewa kodu Huffmana w rozważanym przypadku jest równa dokładnie 1+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 średnim przypadku, mierzoną liczbą operacji kolejki priorytetowej, 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 ś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 taki sam kolor jak wierzchołek 0Po zastosowaniu algorytm ColoringLF wierzchołek ma przypisany kolor 0Liczba chromatyczna grafu jest równa dokładnie 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 pesymstycznym 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: 1++Niech oznacza złożoność czasową algorytmu ColoringLF dla danych rozmiaru , w każdym przypadku, mierzoną liczbą operacji kolejki priorytetowej, 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ą.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: 0Niech oznacza złożoność pamięciową algorytmu DijkstraArray dla danych rozmiaru , 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: 0System edukacyjny. PJWSTK 2001-2007