Edukacja







M E N U  TESTY2 Zalogowany: Arkadiusz Bochenek  Kurs: Algorytmy i struktury danych (ASD) - studia dzienne  POMOCWYLOGUJTwój wynik: 4 punktów na 18 możliwych do uzyskania (22,22 %).Bochenek ArkadiuszNrOpcjaPunktyPoprawnaOdpowiedź1Rozważmy następujący algorytm Alg:
int Alg(int n) {  for (int i_1; i_1<; i_1++) do {    for (int i_2; i_2<; i_2++) do {      Alg_0(n);      Alg_0(n);    }    for (int i_2; i_2<; i_2++) do {      Alg_2(n);      Alg_0(n);    }    Alg_0(n);    Alg_2(n);    Alg_0(n);  }}
gdzie:





Które z poniższych zdań jest prawdziwe?1+Górne ograniczenie złożoności algorytmu Alg w każdym przypadku tj. można określić funkcją 1++02Rozważmy funkcje zmiennej . Które z poniższych zdań jest prawdziwe?Istnieje funkcja taka, że jeżeli , to 1+Dla każdej funkcji , jeżeli , to 1++Dla każdej funkcji , jeżeli , to 1++3Rozważmy algorytm HoareSplit wyszukania co do wielkości elementu postaci:
 

dla danych wejściowych:

tablica elementów: ,
element wyszukiwany: ,

Które z poniższych zdań jest prawdziwe?W rozważanym przypadku wysokość drzewa wykonań rekurencyjnych algorytmu HoareSplit jest równa dokładnie 1+Argumentem -go wykonania algorytmu składowego Split jest tablica postaci: , w której szukamy indeksu elementu -go co do wielkości1+Argumentem -go wykonania algorytmu składowego Split jest tablica postaci: , w której szukamy indeksu elementu -go co do wielkości04Rozważmy algorytm BinSearch postaci:
 

Które z poniższych zdań jest prawdziwe, jeżeli ?Niech oznacza złożoność czasową algorytmu BinSearch dla danych rozmiaru , w każdym przypadku, mierzoną liczbą porównań elementów tablicy , wtedy: 0Niech oznacza złożoność pamięciową algorytmu BinSearch (implementacja rekurencyjna) dla danych rozmiaru , wtedy: 1++Niech oznacza złożoność czasową algorytmu BinSearch dla danych rozmiaru , w pesymistycznym przypadku, mierzoną liczbą porównań elementów tablicy , wtedy: 05Rozważmy algorytm sortowania CountingSort postaci:

dla danych wejściowych:

tablica elementów: ,

Które z poniższych zdań jest prawdziwe? Uwaga! Tablicę pomocniczą indeksujemy od 0.Po pierwszej pętli iteracyjnej (zliczanie) postać tablicy pomocniczej wykorzystywanej w rozważanym algorytmie jest następująca: 0Po pierwszej pętli iteracyjnej (zliczanie) postać tablicy pomocniczej wykorzystywanej w rozważanym algorytmie jest następująca: 0Po trzeciej pętli iteracyjnej (wypisanie) postać tablicy pomocniczej wykorzystywanej w rozważanym algorytmie jest następująca: 1+6Rozważmy algorytm InsertionSort postaci:
 

Które z poniższych zdań jest prawdziwe, jeżeli ?Niech oznacza złożoność czasową algorytmu InsertionSort dla danych rozmiaru , w każdym przypadku, mierzoną liczbą porównań elementów tablicy , wtedy: 0Niech oznacza złożoność czasową algorytmu InsertionSort dla danych rozmiaru , w pesymistycznym przypadku, mierzoną liczbą porównań elementów tablicy , wtedy: 0+Niech oznacza złożoność czasową algorytmu InsertionSort dla danych rozmiaru , w średnim przypadku, mierzoną liczbą przestawień elementów tablicy , wtedy: 07Rozważmy algorytm sortowania QuickSortPartition postaci:

dla danych wejściowych:

tablica elementów: ,

Które z poniższych zdań jest prawdziwe?W rozważanym przypadku wyskokść drzewa wywołań rekurencyjnych algorytmu QuickSortPartition jest równa dokładnie 1+W rozważanym przypadku wyskokść drzewa wywołań rekurencyjnych algorytmu QuickSortPartition jest równa dokładnie 0W
rozważanym przypadku wyskokść drzewa wywołań rekurencyjnych algorytmu
QuickSortPartition jest równa dokładnie wysokości drzewa wywołań
rekurencyjnych rozważanego algorytmu dla danych wejściowych 1+8Rozważmy algorytm BFS 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 algorytmie BFS wierzchołki
grafu umieszczamy w kolejce pomocniczej w kolejności rosnących wartości
etykiet.Liczba operacji IN w kolejce pomocniczej w trakcie wykonania algorytmu BFS jest równa dokładnie 0Kolejność odwiedzenia wierzchołków jest następująca: 1+Liczba operacji OUT w kolejce pomocniczej w trakcie wykonania algorytmu BFS jest równa dokładnie 09Rozważmy algorytm ExpressionValue postaci:Które z poniższych zdań jest prawdziwe, jeżeli wyrażenie będące argumentem wywołania algorytmu składa się z operatorów?Niech oznacza złożoność czasową algorytmu ExpressionValue dla danych rozmiaru , w średnim przypadku, mierzoną liczbą operacji stosowych, wtedy: 1++Niech oznacza złożoność pamięciową algorytmu ExpressionValue (implementacja iteracyjna operacji stosowych) dla danych rozmiaru , wtedy: 0Niech oznacza złożoność czasową algorytmu ExpressionValue dla danych rozmiaru , w każdym przypadku, mierzoną liczbą porówań argumentów wyrażenia, wtedy: 1++10Rozważmy algorytm BSTConstruct postaci:Niech drzewo będzie rezultatem działania algorytmu BSTConstruct dla danych wejściowych:tablica elementów .Które z poniższych zdań jest prawdziwe?Liczba wierzchołków wewnętrznych drzewa jest równa dokładnie 0Liczba wierzchołków zewnętrznych drzewa jest równa dokładnie 1+Etykiety wierzchołków drzewa wypisane w kolejności InOrder tworzą ciąg: 1+11Rozważmy algorytm AVLSequence postaci:Niech drzewo będzie rezultatem działania algorytmu AVLSequence dla danych wejściowych:drzewo początkowe , gdzie algorytm AVLConstruct jest standardowym algorytmem budowy drzewa typu AVL przez kolejne wstawianie elementów,sekwencja operacji słownikowych :Które
z poniższych zdań jest prawdziwe? Uwaga! W trakcie wykonywania operacji
DELETE w miejsce usuwanego wierzchołka wstawiamy wierzchołek
bezpośrednio następny względem porządku etykiet.Maksymalna wysokość drzewa AVL w trakcie wykonania przedstawionego ciągu operacji jest równa dokładnie 0Ostateczna wysokość drzewa AVL tuż po wykonaniu przedstawionego ciągu operacji jest równa dokładnie 1+Ostateczna liczba wierzchołków drzewa AVL tuż po wykonaniu przedstawionego ciągu operacji jest równa dokładnie 012Rozważmy algorytm HeapDestroy postaci:Niech kopiec będzie rezultatem działania algorytmu HeapDestroy dla danych wejściowych:kopiec-drzewo początkowy , gdzie algorytm HeapSlowConstruct jest wolnym algorytmem budowy kopca-drzewa (przez kolejne wstawianie elementów),liczba usuwanych elementów .Które z poniższych zdań jest prawdziwe?Etykiety wierzchołków kopca-drzewa wypisane w kolejności PreOrder tworzą ciąg: 1+Liczba wierzchołków wewnętrznych kopca-drzewa jest równa dokładnie 0Liczba wierzchołków zewnętrznych kopca-drzewa jest równa dokładnie 013Rozważmy algorytm HeapSort postaci:gdzie
procedura składowa HeapConstuct jest implementacją algorymtu
HeapFastConstruct (szybki algorytm budowy kopca-drzewa binarnego). Które
z poniższych zdań jest prawdziwe, jeżeli ?Niech
oznacza złożoność pamięciową algorytmu HeapSort (implementacja
rekurencyjna operacji kolejki priorytetowej) dla danych rozmiaru , wtedy: 0Niech oznacza złożoność czasową algorytmu HeapSort dla danych rozmiaru , w średnim przypadku, mierzoną liczbą porównań etykiet wierzchołków konstruowanego kopca-drzewa, wtedy: 1++Niech oznacza złożoność czasową algorytmu HeapSort dla danych rozmiaru , w każdym przypadku, mierzoną liczbą porównań etykiet wierzchołków konstruowanego kopca-drzewa, wtedy: 014Rozważ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 015Rozważ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 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 0Kolejność przyłączania wierzchołków do drzewa najkrótszych ścieżek grafu w trakcie wykonania algorytmu DijkstraArray jest następująca: 1+16Rozważ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: 0+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: 017Rozważ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 minimalna liczba wierzchołków o tym samym kolorze jest równa dokładnie 0+Kolejność kolorowania wierzchołków grafu w trakcie wykonania algorytmu ColoringLF jest następująca: 1+Po zastosowaniu algorytm ColoringLF maksymalna liczba wierzchołków o tym samym kolorze jest równa dokładnie 1++18Niech , gdzie . Rozważmy algorytm int m:=3, wynik:=0;while (m < n+1) do    m:=m*3;    wynik:=wynik+1;odreturn wynik;Które z poniższych zdań jest prawdziwe?Niezmiennikiem pętli w algorytmie jest formuła 0+Po zakończeniu pętli w algorytmie prawdą jest, że 0Niezmiennikiem pętli w algorytmie jest formuła 1+System edukacyjny. PJWSTK 2001-2007