20	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). 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 zewnętrznych drzewa jest równa dokładnie	0
	Łączna liczba rotacji pojedynczych w prawo wykonanych w trakcie budowy i usuwania elementów drzewa jest równa dokładnie	1	+
	Liczba wierzchołków zewnętrznych drzewa jest równa dokładnie	0

20	Rozważmy zachłanny algorytm PrimTSP 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 jeżeli wierzchołkiem startowym jest ? 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 konstruowanego cyklu Hamiltona w trakcie wykonania algorytmu PrimTSP jest następująca:	0
	Krawędź należy do wyznaczonego cyklu Hamiltona w grafie	0
	Krawędź należy do wyznaczonego cyklu Hamiltona w grafie	1	+

20	Dane są punkty , , . Które z poniższych zdań jest prawdziwe?
	Punkt leży na prawo od prostej wyznaczonej przez wektor	0		+
	Punkty , lub  punkty , są współliniowe	1	+	+
	Punkt leży na prawo od prostej wyznaczonej przez wektor	1	+	+

20	Rozważmy zachłanny algorytm PrimTSP 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 jeżeli wierzchołkiem startowym jest ? Uwaga! W przypadku niejednoznacznej możliwości wyboru wierzchołków, jako pierwszy wybieramy wierzchołek z mniejszą etykietą.
	Krawędź należy do wyznaczonego cyklu Hamiltona w grafie	0
	Maksymalna wysokość stosu pomocniczego użytego do realizacji przejścia grafu metodą DFS w celu wyznaczenia cyklu Hamiltona jest równa dokładnie	0
	Maksymalna wysokość stosu pomocniczego użytego do realizacji przejścia grafu metodą DFS w celu wyznaczenia cyklu Hamiltona jest równa dokładnie	1	+	+

20	Jaki jest stan tablicy po wykonaniu pierwszych dwóch iteracji algorytmu SelectionSort?
		0
	Taki sam jak po wykonaniu pierwszych  iteracji algorytmu InsertionSort	0
	Inny niż po wykonaniu pierwszych  iteracji algorytmu InsertionSort	1	+

20	Ile co najmniej liści musi mieć drzewo decyzyjne dla dowolnego algorytmu sortowania ciągu  elementowego przez porównywanie elementów?
		0
	Rzędu  razy tyle ile w przypadku ciągu wejściowego długości	1	+	+
		1	+

20	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 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 liczba wykonanań rekurencyjnych algorytmu MergeSort jest równa dokładnie	1	+

20	Rozważmy kopiec binarny typu min zaimplementowany w drzewie binarnym. Kopiec konstruujemy z elementów ciągu stosując szybki algorytm budowy kopca HeapConstruct. Które z poniższych zdań jest prawdziwe?
	Jeżeli zamiast drzewa binarnego do implementacji kopca binarnego użyjemy tablicy, to jej finalna postać będzie następująca:	0		+
	Etykiety wierzchołków drzewa-kopca wypisane w kolejności PostOrder tworzą ciąg:	0
	Etykiety wierzchołków drzewa-kopca wypisane w kolejności PreOrder tworzą ciąg:	1	+

20	Ile maksymalnie elementów można jeszcze umieścić w kopcu, w którym jest już wierzchołków, tak by nie zwiększyć jego wysokości?
	Tyle samo dla , co dla	0
	Tyle samo dla , co dla , dla dowolnego	1	+
	, gdy	0

20	Rozważmy tablicę indeksowaną od reprezentującą -elementowy częściowo uporządkowany ciąg liczb naturalnych: . Do całkowitego uporządkowania elementów owej tablicy stosujemy algorytm Merge. Które z poniższych zdań jest prawdziwe?
	Elementy tablicy , które w algorytmie Merge są argumentami ostatniej operacji porównania elmentów, to kolejno oraz	0
	Elementy tablicy , które w algorytmie Merge są argumentami ostatniej operacji porównania elmentów, to kolejno oraz	1	+
	Łączna liczba operacji porównań elementów tablicy wykonanych w trakcie realizacji algorytmu Merge jest taka sama jak w przypadku wykonania rozważonego algorytmu dla tablicy wejściowej postacji	0

20	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?
	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
	Maksymalna długość dowolnej kolejki (tj. maksymalna liczba jednocześnie przechowywanych elementów) w trakcie wykonania rozważanego algorytmu jest równa dokładnie	1	+
	Tuż po sortowaniu liczb względem cyfr na -ej pozycji dziesiętnej (liczonej od prawej do lewej strony), zawartość tablicy jest następująca:	1	+

20	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	0
	Ostateczna długość kolejki tuż po wykonaniu przedstawionego ciągu operacji jest równa dokładnie	1	+

20	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	0
	Ostateczna długość kolejki tuż po wykonaniu przedstawionego ciągu operacji jest równa dokładnie	1	+