|
Nr
|
Opcja
|
Punkty
|
Poprawna
|
Odpowiedź
|
|
1
|
Rozważmy
funkcje zmiennej  .
Które z poniższych zdań jest prawdziwe?
|
|
|
1
|
+
|
+
|
|
|
0
|
|
|
|
|
0
|
|
|
|
2
|
Rozważmy
drzewo  typu
AVL powstałe na skutek kolejnego wstawiania elementów ciągu  do
początkowo pustej struktury (przy użyciu operacji INSERT). Które z
poniższych zdań jest prawdziwe?
|
|
Łączna
liczba rotacji pojedynczych w lewo wykonanych w trakcie budowy drzewa jest
równa dokładnie 
|
0
|
|
+
|
|
Łączna
liczba rotacji pojedynczych w prawo wykonanych w trakcie budowy drzewa jest
równa dokładnie 
|
1
|
+
|
|
|
Łączna
liczba rotacji podwójnych w prawo-lewo wykonanych w trakcie budowy drzewa jest
równa dokładnie 
|
1
|
+
|
|
|
3
|
Rozważmy
drzewo typu
BST powstałe na skutek kolejnego wstawiania elementów ciągu  do
początkowo pustej struktury (przy użyciu operacji INSERT). Które z
poniższych zdań jest prawdziwe?
|
|
Liczba
wierzchołków wewnętrznych drzewa jest
równa dokładnie 
|
1
|
+
|
+
|
|
Wysokość
drzewa jest
równa dokładnie 
|
0
|
|
|
|
Liczba
wierzchołków wewnętrznych drzewa jest
równa dokładnie 
|
0
|
|
|
|
4
|
Rozważmy
pełne drzewo binarne wysokości
.
Które z poniższych zdań jest prawdziwe?
|
|
Jeżeli
wierzchołki drzewa w
kolejności InOrder tworzą ciąg  ,
to w kolejności PostOrder tworzą ciąg: 
|
1
|
+
|
+
|
|
Jeżeli
wierzchołki drzewa w
kolejności PreOrder tworzą ciąg ,
to w kolejności InOrder tworzą ciąg: 
|
0
|
|
|
|
Jeżeli
wierzchołki drzewa w
kolejności PreOrder tworzą ciąg ,
to w kolejności PostOrder tworzą ciąg: 
|
0
|
|
|
|
5
|
Rozważmy
nieskierowany graf prosty  ,
którego wierzchołki etykietowane są liczbami naturalnymi od  do
włącznie,
zadany tabicą list sąsiedztwa postaci:  ,
 ,
 ,
 ,
 ,
 ,
 ,
 ,
 ,
 i
przedstawiony na poniższym rysunku. Dla grafu stosujemy
algorytm kolorowania LF (largest first). 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 LF wierzchołek ma
przypisany kolor
|
1
|
+
|
+
|
|
Po
zastosowaniu algorytm LF wierzchołek ma
przypisany taki sam kolor jak wierzchołek
|
1
|
+
|
|
|
Po
zastosowaniu algorytm LF wierzchołek ma
przypisany taki sam kolor jak wierzchołek
|
0
|
|
|
|
6
|
Rozważmy
tablicę reprezentującą
 -elementowy
ciąg liczb naturalnych:  .
Do posortowania owej tablicy stosujemy algorytm CountingSort.
Które z poniższych zdań jest prawdziwe?
|
|
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: 
|
1
|
+
|
|
|
Po
pierwszej pętli iteracyjnej (zliczanie) postać tablicy pomocniczej
wykorzystywanej w rozważanym algorytmie jest następująca: 
|
0
|
|
|
|
7
|
Rozważmy
nieskierowany graf prosty z
wagami, którego wierzchołki etykietowane są liczbami naturalnymi od do
 włącznie,
zadany tabicą list sąsiedztwa postaci:  ,
 ,
 ,
 ,
 ,
 ,
 ,
 i
przedstawiony na poniższym rysunku. Dla grafu i
wierzchołka startowego stosujemy
algorytm Dijkstry. 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
|
0
|
|
+
|
|
Wysokość
drzewa najkrótszych ścieżek będącego rezultatem działania algorytmu
Dijkstry jest równa dokładnie
|
1
|
+
|
|
|
Najkrótsza
ścieżka z wierzchołka do
wierzchołka w
rozważanym grafie jest długości dokładnie 
|
0
|
|
|
|
8
|
Rozważmy
nieskierowany graf prosty ,
którego wierzchołki etykietowane są liczbami naturalnymi od do
włącznie,
zadany tabicą list sąsiedztwa postaci:  ,
 ,
 ,
 ,
 ,
 ,
 i
przedstawiony na poniższym rysunku. Wierzchołki grafu odwiedzamy
w kolejności DFS z wierzchołka startowego  .
Które z poniższych zdań jest prawdziwe? Uwaga! W algorytmie DFS wierzchołki
grafu umieszczamy na stosie pomocniczym w kolejności malejących wartości
etykiet.
|
|
Liczba
operacji POP w stosie pomocniczym w trakcie wykonania algorytmu DFS jest
równa dokładnie
|
1
|
+
|
+
|
|
Kolejność
odwiedzenia wierzchołków jest następująca: 
|
0
|
|
|
|
Liczba
operacji PUSH na stosie pomocniczym w trakcie wykonania algorytmu DFS jest
równa dokładnie
|
1
|
+
|
|
|
9
|
Rozważmy
kopiec binarny  typu
min zaimplementowany w drzewie binarnym i powstały na skutek kolejnego
wstawiania elementów ciągu  do
początkowo pustej struktury (przy użyciu operacji INSERT). Które z
poniższych zdań jest prawdziwe?
|
|
Liczba
operacji przestawień elementów kopca wykonanych w trakcie jego budowy jest
równa co najwyżej 
|
1
|
+
|
+
|
|
Liczba
wierzchołków zewnętrznych drzewa-kopca jest
równa dokładnie 
|
0
|
|
|
|
Liczba
operacji porównań elementów kopca wykonanych w trakcie jego budowy jest
równa co najwyżej 
|
1
|
+
|
|
|
10
|
Rozważmy
tablicę reprezentującą
-elementowy
ciąg różnych liczb naturalnych:  .
W owej tablicy wyszukujemy indeksu elementu -go
co do wielkości za pomocą algorytmu Hoare'a z
procedurą podziału zgodną z metodą Partition.
Które z poniższych zdań jest prawdziwe?
|
|
Argumentem
-go
wykonania algorytmu Partition jest tablica
postaci:  ,
w której szukamy indeksu elementu -go
co do wielkości
|
0
|
|
+
|
|
W
rozważanym przypadku liczba wykonanań algorytmu Partition jest większa od liczby wykonań tego
algorytmu, gdy zamiast indeksu elementu -go
co do wielkości będziemy wyszukiwali indeksu elementu -go
co do wielkości
|
1
|
+
|
|
|
Argumentem
-go
wykonania algorytmu Partition jest tablica
postaci:  ,
w której szukamy indeksu elementu -go
co do wielkości
|
0
|
|
|
|
11
|
Rozważmy
drzewo kodowe Huffmana  powstałe
na skutek zastosowania algorytmu budowy drzewa kodu Huffmana
dla ciągu znaków zawierającego odpowiednio (znak - krotność wystąpień):  ,
 ,
 ,
 ,
 ,
 ,
 ,
 .
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.
|
|
Kod
litery  odczytany
z drzewa jest
następujący: 
|
0
|
|
+
|
|
Etykiety
liści drzewa czytane
od lewej do prawej strony tworzą ciąg 
|
0
|
|
|
|
Kod litery
 odczytany
z drzewa jest
następujący: 
|
1
|
+
|
|
|
12
|
Rozważmy
nieskierowany graf prosty z
wagami, którego wierzchołki etykietowane są liczbami naturalnymi od do
włącznie,
zadany tabicą list sąsiedztwa postaci:  ,
 ,
 ,
 ,
 ,
 ,
 ,
 i
przedstawiony na poniższym rysunku. Dla grafu stosujemy
algorytm Kruskala wyznaczenia minimalnego drzewa
rozpinającego. Które z poniższych zdań jest prawdziwe? Uwaga! W przypadku
niejednoznacznej możliwości wyboru krawędzi, jako pierwszą wybieramy
krawędź, której etykiety wierzchołków krańcowych w kolejności niemalejącej
tworzą mniejszą liczbę naturalną.
|
|
Maksymalna
waga krawędzi tworzącej otrzymane drzewo rozpinające grafu jest
równa co najmniej
|
0
|
|
+
|
|
Maksymalna
waga krawędzi tworzącej otrzymane drzewo rozpinające grafu jest
równa co najmniej
|
1
|
+
|
|
|
Liczba
krawędzi grafu odrzuconych (ze względu na możliwość utworzenia cyklu) w trakcie
konstrukcji drzewa rozpinającego, tuż po ustaleniu jego finalnej postaci,
jest równa dokładnie
|
1
|
+
|
|
|
13
|
Rozważmy
tablicę reprezentującą
 -elementowy
ciąg różnych liczb naturalnych:  .
Do posortowania owej tablicy stosujemy algorytm MergeSort
w implementacji rekurencyjnej, z procedurą scalania zgodną z metodą Merge. Które z poniższych zdań jest prawdziwe?
|
|
W
rozważanym przypadku liczba wykonanań algorytmu Merge 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 MergeSort jest równa
dokładnie wysokości drzewa wywołań rekurencyjnych rozważanego algorytmu dla
danych wejściowych 
|
1
|
+
|
|
|
Rezultatem
-go
wykonania algorytmu MergeSort jest tablica
postaci: 
|
0
|
|
|
|
14
|
Rozważmy
początkowo pustą strukturę kolejki  ,
do której wstawiono elementy:  .
Następnie na strukturze wykonano
kolejno ciąg operacji:  ,
 ,
 ,
 ,
 ,
 ,
 ,
 .
Które z poniższych zdań jest prawdziwe?
|
|
Maksymalna
długość kolejki w
trakcie wykonania przedstawionego ciągu operacji jest równa dokładnie 
|
1
|
+
|
+
|
|
Ostateczna
długość kolejki tuż
po wykonaniu przedstawionego ciągu operacji jest taka sama jak w przypadku
wykonania następującego ciągu operacji:  ,
,
,
,
 ,
,
 ,
|
0
|
|
|
|
Ostateczna
długość kolejki tuż
po wykonaniu przedstawionego ciągu operacji jest równa dokładnie
|
0
|
|
|
|
15
|
Rozważmy
tablicę reprezentującą
-elementowy
ciąg różnych liczb naturalnych:  .
Do posortowania owej tablicy stosujemy algorytm QuickSort
w implementacji rekurencyjnej, z procedurą podziału zgodną z metodą Partition. Które z poniższych zdań jest prawdziwe?
|
|
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 
|
0
|
|
+
|
|
W
rozważanym przypadku wyskokść drzewa wywołań
rekurencyjnych algorytmu QuickSort jest równa
dokładnie
|
1
|
+
|
|
|
W
rozważanym przypadku wyskokść drzewa wywołań
rekurencyjnych algorytmu QuickSort jest równa
dokładnie wysokości drzewa wywołań rekurencyjnych rozważanego algorytmu dla
danych wejściowych 
|
1
|
+
|
|
|
16
|
Rozważmy
tablicę reprezentującą
-elementowy
ciąg -cyfrowych
liczb naturalnych:  .
Do posortowania owej tablicy stosujemy algorytm RadixSort
zaimplementowany przy użyciu kolejek. Które z poniższych zdań jest
prawdziwe?
|
|
Tuż po
sortowaniu liczb względem cyfr na -ej
pozycji dziesiętnej (liczonej od prawej do lewej strony), zawartość tablicy
jest
następująca: 
|
0
|
|
+
|
|
Maksymalna
długość dowolnej kolejki (tj. maksymalna liczba jednocześnie
przechowywanych elementów) w trakcie wykonania rozważanego algorytmu jest
równa dokładnie
|
0
|
|
|
|
Łączna
liczba operacji IN we wszystkich kolejkach w trakcie wykonania rozważanego
algorytmu jest równa dokładnie 
|
1
|
+
|
|
|
17
|
Rozważmy
początkowo pustą strukturę stosu  ,
do której wstawiono elementy:  .
Następnie na strukturze wykonano
kolejno ciąg operacji:  ,
 ,
 ,
 ,
 ,
,
 ,
.
Które z poniższych zdań jest prawdziwe?
|
|
|
1
|
+
|
+
|
|
Ostateczna
wysokość stosu tuż
po wykonaniu przedstawionego ciągu operacji jest równa dokładnie 
|
0
|
|
|
|
Maksymalna
wysokość stosu w
trakcie wykonania przedstawionego ciągu operacji jest równa dokładnie
|
1
|
+
|
|
|
18
|
Rozważmy
nieskierowany graf prosty z
wagami, którego wierzchołki etykietowane są liczbami naturalnymi od do
włącznie,
zadany tabicą list sąsiedztwa postaci:  ,
 ,
 ,
 ,
 ,
 ,
 ,
 i
przedstawiony na poniższym rysunku. Dla grafu i
wierzchołka startowego stosujemy
stosujemy algorytm Prima wyznaczenia minimalnego
drzewa rozpinającego. 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ą.
|
|
Suma wag
krawędzi tworzących minimalne drzewo rozpinające będące 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
|
|
|
|
Suma wag
krawędzi tworzących minimalne drzewo rozpinające będące rezultatem
działania algorytmu Prima jest równa dokładnie 
|
1
|
+
|
|
|
19
|
Rozważmy
tablicę reprezentującą
-elementowy
ciąg różnych liczb naturalnych:  .
Do posortowania owej tablicy stosujemy algorytm SelectionSort.
Które z poniższych zdań jest prawdziwe? Uwaga! Przy zliczaniu przestawień
elementów bierzemy pod uwagę jedynie transpozycje między różnymi indeksami
tablicy .
|
|
Wykonanie
pierwszych iteracji
pętli zewnętrznej algorytmu wymaga wykonania dokładnie porównań
elementów tablicy
|
0
|
|
+
|
|
Po
pierwszych iteracjach
pętli zewnętrznej algorytmu postać tablicy jest
następująca: 
|
0
|
|
|
|
Wykonanie
pierwszych iteracji
pętli zewnętrznej algorytmu wymaga wykonania o co najwyżej przestawień
elementów tablicy mniej
niż w przypadku wykonania pierwszych iteracji
rozważanego algorytmu
|
1
|
+
|
|
|
20
|
Rozważmy
zachłanny algorytm KruskalTSP rozwiązujący
problem komiwojażera w -wierzchołkowym
grafie ,
którego wierzchołki etykietowane są liczbami naturalnymi od do
włącznie
i rozmieszczone są w odpowiednio następujących punktach płaszczyzny euklidesowej:
 .
Które z poniższych zdań jest prawdziwe? Uwaga! W przypadku niejednoznacznej
możliwości wyboru krawędzi, jako pierwszą wybieramy krawędź, której
etykiety wierzchołków krańcowych w kolejności niemalejącej tworzą mniejszą
liczbę naturalną.
|
|
Liczba
krawędzi grafu odrzuconych (ze względu na możliwość utworzenia cyklu) w
trakcie konstrukcji drzewa rozpinającego stanowiącego podstawę
poszukiwanego cyklu Hamiltona, tuż po ustaleniu finalnej postaci owego
drzewa, jest równa dokładnie 
|
0
|
|
+
|
|
Krawędź  należy
do wyznaczonego cyklu Hamiltona w grafie
|
0
|
|
|
|
Kolejność
akceptowania krawędzi grafu do konstruowanego cyklu Hamiltona w trakcie
wykonania rozważanego algorytmu jest następująca: 
|
1
|
+
|
|