Nr |
Opcja |
Punkty |
Poprawna |
Odpowiedź |
1 |
Rozważmy funkcje zmiennej |
|||
|
Ciąg funkcji |
1 |
+ |
|
|
|
0 |
|
|
|
|
0 |
|
|
2 |
Rozważmy drzewo |
|||
|
Łączna liczba rotacji pojedynczych w prawo wykonanych w trakcie budowy drzewa |
0 |
|
|
|
Etykiety wierzchołków drzewa |
1 |
+ |
|
|
Łączna liczba rotacji podwójnych w lewo-prawo wykonanych w trakcie budowy drzewa |
0 |
|
|
3 |
Rozważmy drzewo |
|||
|
Etykiety wierzchołków drzewa |
0 |
|
|
|
Etykiety wierzchołków drzewa |
0 |
|
|
|
Liczba wierzchołków zewnętrznych drzewa |
1 |
+ |
|
4 |
Rozważmy pełne drzewo binarne |
|||
|
Jeżeli wierzchołki drzewa |
0 |
|
|
|
Jeżeli wierzchołki drzewa |
1 |
+ |
|
|
Jeżeli wierzchołki drzewa |
0 |
|
|
5 |
Rozważmy nieskierowany graf prosty
|
|||
|
Po zastosowaniu algorytm LF wierzchołek |
0 |
|
|
|
Po zastosowaniu algorytm LF wierzchołek |
1 |
+ |
|
|
Po zastosowaniu algorytm LF wierzchołek |
0 |
|
|
6 |
Rozważmy tablicę |
|||
|
Po trzeciej pętli iteracyjnej (wypisanie) postać tablicy pomocniczej wykorzystywanej w rozważanym algorytmie jest następująca: |
0 |
|
|
|
Po pierwszej pętli iteracyjnej (zliczanie) postać tablicy pomocniczej wykorzystywanej w rozważanym algorytmie jest następująca: |
0 |
|
|
|
Po drugiej pętli iteracyjnej (sumowanie) postać tablicy pomocniczej wykorzystywanej w rozważanym algorytmie jest następująca: |
1 |
+ |
|
7 |
Rozważmy nieskierowany graf prosty
|
|||
|
Najkrótsza ścieżka z wierzchołka |
0 |
|
|
|
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 |
1 |
+ |
|
|
Najkrótsza ścieżka z wierzchołka |
0 |
|
|
8 |
Rozważmy nieskierowany graf prosty
|
|||
|
Maksymalna wysokość stosu pomocniczego w trakcie wykonania algorytmu jest równa co najwyżej maksymalnej wysokości stosu pomocniczego, w trakacie wykonania rozważnego algorytmu dla grafu |
1 |
+ |
|
|
Maksymalna wysokość stosu pomocniczego w trakcie wykonania algorytmu jest równa co najwyżej maksymalnej wysokości stosu pomocniczego, w trakacie wykonania rozważnego algorytmu dla grafu |
1 |
+ |
|
|
Liczba operacji PUSH na stosie pomocniczym w trakcie wykonania algorytmu DFS jest równa dokładnie |
0 |
|
|
9 |
Rozważmy kopiec binarny |
|||
|
Wysokość drzewa-kopca |
1 |
+ |
|
|
Wysokość drzewa-kopca |
0 |
|
|
|
Liczba operacji porównań elementów kopca wykonanych w trakcie jego budowy jest równa co najwyżej |
0 |
|
|
10 |
Rozważmy tablicę |
|||
|
W rozważanym przypadku liczba wykonanań algorytmu Partition jest większa od liczby wykonań tego algorytmu, gdy zamiast indeksu elementu |
1 |
+ |
|
|
Argumentem |
0 |
|
|
|
W rozważanym przypadku liczba wykonanań algorytmu Partition jest większa od liczby wykonań tego algorytmu, gdy zamiast indeksu elementu |
1 |
+ |
|
11 |
Rozważmy drzewo kodowe Huffmana |
|||
|
Wysokość drzewa |
1 |
+ |
|
|
Kod litery |
0 |
|
|
|
Wysokość drzewa |
0 |
|
|
12 |
Rozważmy nieskierowany graf prosty
|
|||
|
Liczba krawędzi grafu odrzuconych (ze względu na możliwość utworzenia cyklu) w trakcie konstrukcji drzewa rozpinającego, jeszcze przed ustaleniem jego finalnej postaci, jest równa dokładnie |
0 |
|
|
|
Maksymalna waga krawędzi tworzącej otrzymane drzewo rozpinające grafu |
1 |
+ |
|
|
Maksymalna waga krawędzi tworzącej otrzymane drzewo rozpinające grafu |
0 |
|
|
13 |
Rozważmy tablicę |
|||
|
Rezultatem |
0 |
|
|
|
W rozważanym przypadku liczba wykonanań rekurencyjnych algorytmu MergeSort jest równa dokładnie liczbie wywołań rekurencyjnych rozważanego algorytmu dla danych wejściowych |
0 |
|
|
|
W rozważanym przypadku wyskokść drzewa wywołań rekurencyjnych algorytmu MergeSort jest równa dokładnie wysokości drzewa wywołań rekurencyjnych rozważanego algorytmu dla danych wejściowych |
1 |
+ |
|
14 |
Rozważmy początkowo pustą strukturę kolejki |
|||
|
Ostateczna długość kolejki |
0 |
|
|
|
|
1 |
+ |
|
|
Ostateczna długość kolejki |
1 |
+ |
|
15 |
Rozważmy tablicę |
|||
|
W rozważanym przypadku liczba wykonanań algorytmu Partition jest równa dokładnie liczbie wykonań rozważanego algorytmu dla danych wejściowych |
0 |
|
|
|
W rozważanym przypadku wyskokść drzewa wywołań rekurencyjnych algorytmu QuickSort jest równa dokładnie |
0 |
|
|
|
W rozważanym przypadku liczba wykonanań rekurencyjnych algorytmu QuickSort jest równa dokładnie liczbie wywołań rekurencyjnych rozważanego algorytmu dla danych wejściowych |
1 |
+ |
|
16 |
Rozważmy tablicę |
|||
|
Tuż po sortowaniu liczb względem cyfr na |
0 |
|
|
|
Tuż po sortowaniu liczb względem cyfr na |
1 |
+ |
|
|
Tuż po sortowaniu liczb względem cyfr na |
0 |
|
|
17 |
Rozważmy początkowo pustą strukturę stosu |
|||
|
Ostateczna wysokość stosu |
1 |
+ |
|
|
|
0 |
|
|
|
Ostateczna wysokość stosu |
0 |
|
|
18 |
Rozważmy nieskierowany graf prosty
|
|||
|
Wysokość minimalego drzewa rozpinającego będącego rezultatem działania algorytmu Prima jest równa dokładnie |
1 |
+ |
|
|
Wysokość minimalego drzewa rozpinającego będącego rezultatem działania algorytmu Prima jest równa dokładnie |
0 |
|
|
|
Liczba wierzchołków wewnętrznych w minimalym drzewie rozpinającym będącym rezultatem działania algorytmu Prima jest równa dokładnie |
0 |
|
|
19 |
Rozważmy tablicę |
|||
|
Wykonanie pierwszych |
0 |
|
|
|
Wykonanie pierwszych |
1 |
+ |
|
|
Wykonanie pierwszych |
0 |
|
|
20 |
Rozważmy drzewo |
|||
|
Liczba wierzchołków zewnętrznych drzewa |
0 |
|
|
|
Łączna liczba rotacji pojedynczych w prawo wykonanych w trakcie budowy i usuwania elementów drzewa |
1 |
+ |
|
|
Liczba wierzchołków zewnętrznych drzewa |
0 |
|
|