|
Nr
|
Opcja
|
Punkty
|
Poprawna
|
Odpowiedź
|
|
1
|
Rozważmy
funkcje zmiennej  .
Które z poniższych zdań jest prawdziwe?
|
|
|
1
|
+
|
|
|
|
0
|
|
+
|
|
Ciąg
funkcji  jest
ciągiem ściśle rosnącym względem ich rzędów
|
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?
|
|
Etykiety
wierzchołków drzewa wypisane
w kolejności PreOrder tworzą ciąg: 
|
1
|
+
|
+
|
|
Łączna
liczba rotacji podwójnych w lewo-prawo wykonanych w trakcie budowy drzewa jest
równa dokładnie 
|
0
|
|
|
|
Liczba
wierzchołków wewnętrznych drzewa jest
równa dokładnie 
|
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
|
|
|
|
Kolejność
odwiedzenia wierzchołków jest następująca: 
|
1
|
+
|
+
|
|
Liczba
operacji IN w kolejce pomocniczej w trakcie wykonania algorytmu BFS jest
równa dokładnie 
|
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.
|
|
Liczba
wierzchołków wewnętrznych drzewa jest
równa dokładnie
|
1
|
+
|
|
|
Etykiety
wierzchołków drzewa wypisane
w kolejności PostOrder tworzą ciąg: 
|
1
|
+
|
|
|
Etykiety
wierzchołków drzewa  wypisane
w kolejności InOrder tworzą ciąg: 
|
0
|
|
+
|
|
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 PreOrder 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
|
|
|
|
6
|
Rozważmy
drzewo binarne zgodne
z poniższym rysunkiem. Które z następujacych zdań
jest prawdziwe?
|
|
Do
poziomu włącznie
rozważane drzewo jest
drzewem doskonałym (pełnym)
|
1
|
+
|
+
|
|
Liczba
wierzchołków wewnętrznych rozważanego drzewa jest
równa dokładnie 
|
1
|
+
|
|
|
Do
poziomu włącznie
rozważane drzewo jest
drzewem regularnym (lokalnie pełnym)
|
0
|
|
|
|
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 .
|
|
Po
zastosowaniu algorytm LF wierzchołek ma
przypisany kolor 
|
0
|
|
|
|
Liczba
chromatyczna  grafu
jest
równa dokładnie
|
0
|
|
|
|
Po
zastosowaniu algorytm LF wierzchołek ma
przypisany kolor
|
1
|
+
|
+
|
|
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
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
|
|
|
|
Po
pierwszej pętli iteracyjnej (zliczanie) 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
|
|
|
|
Wysokość
drzewa najkrótszych ścieżek będącego rezultatem działania algorytmu
Dijkstry jest równa dokładnie
|
0
|
|
+
|
|
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
|
+
|
|
|
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?
|
|
Etykiety
wierzchołków drzewa-kopca wypisane
w kolejności PostOrder tworzą ciąg: 
|
1
|
+
|
+
|
|
Etykiety
wierzchołków drzewa-kopca wypisane
w kolejności InOrder tworzą ciąg: 
|
0
|
|
|
|
Jeżeli
zamiast drzewa binarnego do implementacji kopca binarnego użyjemy
tablicy, to jej finalna postać będzie następująca: 
|
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?
|
|
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
|
|
+
|
|
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.
|
|
Kod
litery  odczytany
z drzewa jest
następujący: 
|
0
|
|
+
|
|
Wysokość
drzewa jest
równa dokładnie
|
0
|
|
|
|
Etykiety
liści drzewa czytane
od lewej do prawej strony tworzą ciąg 
|
1
|
+
|
+
|
|
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 .
|
|
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 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 dokładnie porównań
elementów tablicy
|
0
|
|
|
|
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ą.
|
|
Maksymalna
waga krawędzi tworzącej otrzymane drzewo rozpinające grafu jest
równa co najmniej
|
1
|
+
|
|
|
Maksymalna
waga krawędzi tworzącej otrzymane drzewo rozpinające grafu jest
równa dokładnie
|
0
|
|
+
|
|
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
|
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 wysokości drzewa wywołań rekurencyjnych rozważanego algorytmu dla
danych wejściowych 
|
1
|
+
|
+
|
|
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 liczba wykonanań algorytmu Merge 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?
|
|
Maksymalna
długość kolejki w
trakcie wykonania przedstawionego ciągu operacji jest równa dokładnie 
|
0
|
|
|
|
Maksymalna
długość kolejki w
trakcie wykonania przedstawionego ciągu operacji jest równa dokładnie
|
1
|
+
|
|
|
|
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 liczba wykonanań
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ń algorytmu Partition jest równa dokładnie liczbie wykonań
rozważanego algorytmu dla danych wejściowych 
|
1
|
+
|
|
|
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?
|
|
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
|
|
|
|
Łączna
liczba operacji IN we wszystkich kolejkach w trakcie wykonania rozważanego
algorytmu jest równa dokładnie 
|
1
|
+
|
|
|
Łączna
liczba operacji FIRST we wszystkich kolejkach w trakcie wykonania
rozważanego algorytmu jest równa dokładnie 
|
0
|
|
+
|
|
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:  ,
 ,
,
 ,
,
,
,
|
0
|
|
|
|
Ostateczna
wysokość stosu tuż
po wykonaniu przedstawionego ciągu operacji jest taka sama jak w przypadku
wykonania następującego ciągu operacji:  ,
 ,
 ,
 ,
,
,
,
|
0
|
|
|
|
 , gdzie  jest
stosem, którego proces konstrukcji przebiegł analogicznie jak dla stosu tyle,
że dla innego ciągu operacji:  ,
 ,
 ,
 ,
,
 ,
 ,
|
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ą.
|
|
Liczba wierzchołków
zewnętrznych w minimalym drzewie rozpinającym
będącym rezultatem działania algorytmu Prima jest równa dokładnie
|
0
|
|
+
|
|
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
|
+
|
|