|
Nr
|
Opcja
|
Punkty
|
Poprawna
|
Odpowiedź
|
|
1
|
Rozważmy
funkcje zmiennej  .
Które z poniższych zdań jest prawdziwe?
|
|
|
1
|
+
|
|
|
|
1
|
+
|
|
|
|
1
|
+
|
+
|
|
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 podwójnych w lewo-prawo wykonanych w trakcie budowy drzewa jest
równa dokładnie 
|
0
|
|
|
|
Wysokość
drzewa jest
równa dokładnie 
|
1
|
+
|
+
|
|
Etykiety
wierzchołków drzewa wypisane
w kolejności PreOrder tworzą ciąg: 
|
0
|
|
|
|
3
|
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 BFS z wierzchołka startowego  .
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 OUT w kolejce pomocniczej w trakcie wykonania algorytmu BFS jest
równa dokładnie
|
0
|
|
|
|
Maksymalna
długość kolejki pomocniczej w trakcie wykonania algorytmu jest równa co
najwyżej maksymalnej długości kolejki pomocniczej, w trakacie
wykonania rozważnego algorytmu dla grafu i
wierzchołka startowego
|
1
|
+
|
+
|
|
Maksymalna
długość kolejki pomocniczej w trakcie wykonania algorytmu jest równa co
najwyżej maksymalnej długości kolejki pomocniczej, w trakacie
wykonania rozważnego algorytmu dla grafu i
wierzchołka startowego 
|
0
|
|
|
|
4
|
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). Następnie z
drzewa usuwamy
wierzchołki z etykietami  .
Które z poniższych zdań jest prawdziwe?. Uwaga! W razie konieczności w
operacji DELETE w miejsce usuwanego wierzchołka wstawiamy wierzchołek
bezpośrednio poprzedni (drzewo  )
albo następny (drzewo  )
względem porządku etykiet.
|
|
Etykiety
wierzchołków drzewa wypisane
w kolejności PreOrder tworzą ciąg: 
|
0
|
|
|
|
Liczba
wierzchołków wewnętrznych drzewa jest
równa dokładnie
|
0
|
|
|
|
Liczba
wierzchołków zewnętrznych drzewa jest
równa dokładnie
|
1
|
+
|
+
|
|
5
|
Rozważmy
pełne drzewo binarne wysokości
 .
Które z poniższych zdań jest prawdziwe?
|
|
Jeżeli
wierzchołki drzewa w
kolejności PostOrder tworzą ciąg  ,
to w kolejności InOrder tworzą ciąg: 
|
0
|
|
|
|
Jeżeli
wierzchołki drzewa w
kolejności InOrder tworzą ciąg ,
to w kolejności PreOrder tworzą ciąg: 
|
0
|
|
|
|
Jeżeli wierzchołki
drzewa w
kolejności InOrder tworzą ciąg ,
to w kolejności PreOrder tworzą ciąg: 
|
1
|
+
|
+
|
|
6
|
Rozważmy
drzewo binarne zgodne
z poniższym rysunkiem. Które z następujacych zdań
jest prawdziwe?
|
|
Wysokość
rozważanego drzewa jest
równa dokładnie
|
0
|
|
|
|
Do
poziomu włącznie
rozważane drzewo jest
drzewem regularnym (lokalnie pełnym)
|
0
|
|
|
|
Wysokość
rozważanego drzewa jest
równa dokładnie
|
1
|
+
|
+
|
|
7
|
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 .
|
|
Liczba
chromatyczna  grafu
jest
równa dokładnie
|
0
|
|
|
|
Po
zastosowaniu algorytm LF wierzchołek ma
przypisany kolor
|
1
|
+
|
+
|
|
Po
zastosowaniu algorytm LF wierzchołek  ma
przypisany taki sam kolor jak wierzchołek
|
0
|
|
|
|
8
|
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
drugiej pętli iteracyjnej (sumowanie) postać tablicy pomocniczej
wykorzystywanej w rozważanym algorytmie jest następująca: 
|
1
|
+
|
+
|
|
Po
drugiej pętli iteracyjnej (sumowanie) 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: 
|
0
|
|
|
|
9
|
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ą.
|
|
Kolejność
przyłączania wierzchołków do drzewa najkrótszych ścieżek grafu w
trakcie wykonania algorytmu Dijkstry jest następująca: 
|
0
|
|
|
|
Liczba
wierzchołków zewnętrznych w drzewie najkrótszych ścieżek będącym rezultatem
działania algorytmu Dijkstry jest równa dokładnie
|
0
|
|
|
|
Najkrótsza
ścieżka z wierzchołka do
wierzchołka w
rozważanym grafie jest długości dokładnie 
|
1
|
+
|
+
|
|
10
|
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
wierzchołków wewnętrznych drzewa-kopca jest
równa dokładnie
|
0
|
|
|
|
Liczba
wierzchołków wewnętrznych drzewa-kopca jest
równa dokładnie
|
1
|
+
|
+
|
|
Liczba
wierzchołków wewnętrznych drzewa-kopca jest
równa dokładnie
|
0
|
|
|
|
11
|
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?
|
|
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
|
|
|
|
W
rozważanym przypadku liczba wykonanań algorytmu Partition jest równa dokładnie
|
0
|
|
|
|
12
|
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.
|
|
Etykiety
liści drzewa czytane
od lewej do prawej strony tworzą ciąg 
|
0
|
|
|
|
Kod
litery odczytany
z drzewa jest
następujący: 
|
1
|
+
|
+
|
|
Kod
litery  odczytany
z drzewa jest
następujący: 
|
0
|
|
|
|
13
|
Rozważmy
tablicę reprezentującą
 -elementowy
ciąg różnych liczb naturalnych:  .
Do posortowania owej tablicy stosujemy algorytm InsertionSort.
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 przestawień
elementów tablicy
|
1
|
+
|
+
|
|
Wykonanie
pierwszych iteracji
pętli zewnętrznej algorytmu wymaga wykonania o co najwyżej porównań
elementów tablicy mniej
niż w przypadku wykonania pierwszych iteracji
rozważanego algorytmu
|
1
|
+
|
+
|
|
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
|
+
|
+
|
|
14
|
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ą.
|
|
Kolejność
akceptowania krawędzi grafu do drzewa rozpinającego w trakcie wykonania
rozważanego algorytmu jest następująca: 
|
0
|
|
|
|
Suma wag
krawędzi tworzących drzewo rozpinające grafu będące
rezultatem działania algorytmu Kruskala jest
równa dokładnie 
|
0
|
|
|
|
Maksymalna
waga krawędzi tworzącej otrzymane drzewo rozpinające grafu jest
równa co najwyżej
|
1
|
+
|
+
|
|
15
|
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 wyskokść drzewa wywołań
rekurencyjnych algorytmu MergeSort jest równa
dokładnie
|
1
|
+
|
+
|
|
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
|
+
|
+
|
|
W
rozważanym przypadku wyskokść drzewa wywołań
rekurencyjnych algorytmu MergeSort jest równa
dokładnie
|
0
|
|
|
|
16
|
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?
|
|
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 taka sama jak w przypadku
wykonania następującego ciągu operacji: ,
 ,
,
,
,
 ,
,
|
1
|
+
|
+
|
|
 , gdzie  jest
kolejką, której proces konstrukcji przebiegł analogicznie jak dla kolejki tyle,
że dla innego ciągu operacji:  ,
 ,
 ,
,
 ,
 ,
 ,
|
1
|
+
|
+
|
|
17
|
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 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 
|
0
|
|
|
|
W
rozważanym przypadku liczba wykonanań
rekurencyjnych algorytmu QuickSort jest równa
dokładnie 
|
0
|
|
|
|
18
|
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?
|
|
Łączna
liczba operacji FIRST we wszystkich kolejkach w trakcie wykonania
rozważanego algorytmu jest równa dokładnie 
|
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
|
+
|
+
|
|
19
|
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?
|
|
Ostateczna
wysokość stosu tuż
po wykonaniu przedstawionego ciągu operacji jest taka sama jak w przypadku
wykonania następującego ciągu operacji:  ,
,
 ,
 ,
 ,
 ,
,
|
1
|
+
|
+
|
|
Ostateczna
wysokość stosu tuż
po wykonaniu przedstawionego ciągu operacji jest taka sama jak w przypadku
wykonania następującego ciągu operacji: ,
,
,
,
 ,
,
,
|
0
|
|
|
|
Ostateczna
wysokość stosu tuż
po wykonaniu przedstawionego ciągu operacji jest równa dokładnie
|
1
|
+
|
+
|
|
20
|
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ą.
|
|
Kolejność
przyłączania wierzchołków do minimalnego drzewa rozpinającego grafu w
trakcie wykonania algorytmu Prima jest następująca: 
|
0
|
|
|
|
Wysokość
minimalego drzewa rozpinającego będącego
rezultatem działania algorytmu Prima jest równa dokładnie
|
1
|
+
|
+
|
|
Liczba
wierzchołków zewnętrznych w minimalym drzewie
rozpinającym będącym rezultatem działania algorytmu Prima jest równa
dokładnie
|
1
|
+
|
+
|