1) Jaki jest czas działania sortowania przez łączenie (z wykorzystaniem metody "dziel i zwyciężaj")?
a) O(NlogN) *
b) O(N^2)
c) O(N)
d) O(2N)
2) Który przykład algorytmów NIE korzysta z metody "dziel i zwyciężaj"?
a) quicksort
b) wyszukiwanie binarne
c) radix sort *
d) mergesort
3) Który z wymienionych etapów działania algorytmu nie występuje w metodzie "dziel i zwyciężaj"?
a) podział problemu na mniejsze, ale analogiczne podproblemy
b) elementy równomiernie umieszczane do odpowiednich kubełków *
c) rekursywne rozwiazywanie podproblemów
d) łaczenie otrzymanych rozwiazań
4) W jakim czasie scalne są dwa ciągi podczas sortowania wykorzystującego metodę "dziel i zwyciężaj"?
a) liniowym *
b) kwadratowym
c) logarytmicznym
d) żadna z proponowanych odpowiedzi
5) Ile kroków potrzebnych jest do rozwiazania problemu wież Hanoi dla 3 dysków?
a) 3
b) 7 *
c) 9
d) 15
6) Jaki jest czas działania poszukiwania binarnego (z wykorzystaniem metody "dziel i zwyciężaj")?
a) O(N)
b) O(N^2)
c) O(logN) *
d) O(NlogN)
7) Mamy dany ciąg liczb: 1 5 2 4 6 3 2 6. W ilu krokach uda nam się go posortować korzystając z metody "dziel i zwyciężaj"?
a) 6 *
b) 8
c) 10
d) 12
8) Algorytm:
void min_max(int i, int j, int *min, int *max)
int x, min1, max1, min2, max2;
{
if (i==j) { max=i; min=i; }
else
if (i+1==j)
if (aj > ai) {
max= j;
min= i;
}
else {
max= i;
min= j;
}
else {
x=(i+j-1)/2;
min_max(i, x, min1, max1);
min_max(x+1, j, min2, max2);
if (amin2 > amin1) min=min1
else min=min2;
if (amax2 > amax1) max=max2
else max=max1;
}}
jest algorytmem sortowania:
a) metodą "dziel i zwyciężaj" *
b) przez wstawianie
c) babelkowego
d) przez wybór
9) Mamy planszę o wymiarach 2^n x 2^n, która musimy wypełnić klockami o następujacym kształcie:
---
| |
| |
-------
| | |
| | |
-------
Zadanie posiada rozwiazanie jeli:
a) plansza ma wszystkie pola puste
b) jedno z pól planszy jest zapełnione *
c) jeden element znajduje się już na planszy
d) żadne z powyższych
10) Którego z podanych problemów nie da się rozwiazać za pomoca metody "dziel i zwyciężaj"?
a) wypełnianie planszy elementami
b) poszukiwanie binarne
c) sortowanie przez łaczenie
d) żadna z proponowanych odpowiedzi *
11) Metoda "dziel i zwyciężaj" jest:
a) jedna z najefektywniejszych metod algorytmicznych w informatyce *
b) mało efektywna
c) średnio efektywna
d) najbardziej efektywna
12) Etap "zwyciężania" w metodzie dziel i zwyciężaj to:
a) mergesort *
b) radixsort
c) shellsort
d) sortowanie przez wybór
13) Mamy następujcy ciag liczb 5, 7, 3, 1
sortujemy je następujaco:
krok 1: 5, 7 | 3, 1
krok 2: 5 | 7 | 3 | 1
krok 3: 5, 7 | 1, 3
krok 4: 1, 3, 5, 7
Jaka metoda sortowania została użyta?
a) dziel i zwyciężaj *
b) babelkowe
c) przez wybór
d) przez wstawianie
14) Metoda sortowania polegajaca na redukowaniu zadania do dwóch mniejszych problemów to:
a) mergesort *
b) babelkowe
c) przez zliczanie
d) heapsort
15) Mamy ciag liczb 5, 7, 3, 1. Zgodnie z metoda "dziel i zwyciężaj" w następnym kroku:
a) ciag zostanie podzielony na 2 mniejsze podciagi *
b) ciag zostanie podzielony na 4 mniejsze podciagi
c) minimalna wartoć przesunie się na pierwsza pozycję w ciagu, maksymalna na ostatnia
d) liczba 1 zamieni się miejscem z liczba 3
1.Jaka jest idea wykorzystania metody „Dziel i zwyciężaj” do rozwiązania problemu wypełnienia planszy z brakującym polem, klockami o zadanym kształcie?
a)podział planszy o wielkości 2n x 2n na 4 równe części
b)wypełniamy planszę dla n<=2
c)dzielimy planszę o wielkości 4n x 4n na 4 równe części
d)dzielimy planszę na 2n części
2.Jakie są kolejne kroki konstruowania algorytmów „Dziel i zwyciężaj”?
a)podział, rozwiązanie, łączenie *
b)podział, rekurencja, podział, łączenie
c)podział, łączenie, rozwiązanie
d)rekurencja, podział, rozwiązanie, łączenie
3.Na czym polega poszukiwanie binarne?
a)podział zbioru na 2 części i szukanie w każdym z tych podzbiorów osobno
b)podział zbioru na 2 części i rekurencyjne wywołanie poszukiwania binarnego dla każdego z nich *
c)podział zbioru na parzystą liczbę części i poszukiwanie we wszystkich jednocześnie
d)żadna z odpowiedzi nie jest poprawna
4.Czym się charakteryzuje metoda sortowania zwana Merge Sort?
a)dzielenie zbioru na części, sortowanie każdej z nich, połączenie posortowanych części
b)podział na 2 części, sortowanie każdej z nich, połączenie tych części i posortowanie ich
c)podział na 2n części, posortowanie każdej z nich i połączenie
5.Jaki jest czas działania sortowania quicksort w przypadku pesymistycznym?
a)O(log n)
b)O(n2/2) *
c)O (n)
d)O( 2n)
6.Co jest niedozwolone podczas rozwiązywania problemu Wież Hanoi?
a)Pozostawienie jednego z słupków wolnego.
b)Nałożenie większego dysku na mniejszy *
c)Nałożenie mniejszego dysku na większy
d)Przełożenie jednego dysku
7.W ilu krokach rozwiążemy problem Wież Hanoi dla odpowiednio 5 dysków?
a)32
b)5
c)31 *
d)16
8.Sortowanie przez łączenie (Merge Sort) wykorzystuje metodę:
a)Dziel i rządź
b)Dziel i zwyciężaj *
c)Radix sort
d)Sortowania bąbelkowego
9.Kiedy podczas stosowania algorytmów „Dziel i zwyciężaj” nie używamy etapu Zwyciężania:
a)Gdy złożoność obliczeniowa na to pozwala
b)Gdy rozmiar problemów nie pozwala na zastosowanie rekurencji
c)Gdy złożoność obliczeniowa na to nie pozwala
d)Gdy chcemy zmienić złożoność obliczeniową
10.Który z proponowanych algorytmów korzysta z metody „Dziel i rządź”?
a)Quicksort
b)Wyszukiwanie binarne
c)Mergesort
d)Żadna z odpowiedzi nie jest poprawna *
1. Każdy węzeł drzewa BST posiada pola:
* key, left, parent, child
* key, left, right
* key, left, right, parent
* key, left, right, child
2. Przeszukiwanie drzewa BST jest możliwe:
* tylko rekurencyjnie
* tylko iteracyjnie
* rekurencyjnie i iteracyjnie - z różną złożonością obliczeniową
* rekurencyjnie i iteracyjnie - z taką samą złożonością obliczeniową
3. W jaki sposób należy usuwać węzeł z drzewa BST, jeżeli ma on 2 potomków?
* należy zastąpić węzeł jego następnikiem
* należy przenieść dzieci do rodzica
* należy ustawić wskaźnik rodzica na null
* należy przenieść dzieci do przypadkowego węzła
4. Zasadniczo klucze drzewa BST:
* mogą być dowolne, z tym że korzeń musi mieć klucz numer 1
* mogą być dowolne, z tym że potomek nie może mieć takiego samego klucza jak jego rodzic
* muszą być unikatowe
* mogą być dowolne, z tym że korzeń musi mieć klucz o najwyższej wartości
5. Pesymistyczny koszt operacji dla zrównoważonego drzewa BST wynosi:
* n
* log_2 n
* n^2
* log_n 2
6. Pesymistyczny koszt operacji dla drzewa BST zdegenerowanego do listy wynosi:
* n
* log_2 n
* n^2
* log_n 2
7. Aby utworzyć drzewo BST posługujemy się drzewem:
* zstępującym 2-3-4
* binarnym
* B-drzewem
* wyważonym drzewem czerwono-czarnym
8. Następnik x w drzewie BST to:
* prawy potomek x
* lewy potomek x
* najmniejszy element y wśród elementów większych od x
* największy element y wśród elementów mniejszych od x
9. Następnikiem x w drzewie BST jest:
* null jeśli x jest najmniejszym z węzłów
* maksimum w prawym poddrzewie t jeśli ono istnieje
* największy z przodków x, dla których lewy potomek jest przodkiem x
* null jeśli x jest największym z węzłów
10. Wstawiając element do drzewa BST:
* można to zrobić w dowolnym miejscu
* nie ma znaczenia czy dowiążemy element jako potomek lewy czy prawy
* nie jest istotna wartość klucza wstawianego elementu
* położenie nowego elementu zależy od jego wartości klucza
11. Najbardziej skomplikowaną operacją na drzewach BST jest:
* usuwanie elementu
* dodawanie elementu
* wyszukiwanie elementu
* sortowanie elementów
12. Jeżeli węzeł drzewa BST nie ma potomków lub ma 1 potomka, to usuwanie wymaga
* O(n) operacji
* O(h) operacji
* O(1) operacji
* O(log_2 n) operacji
13. Węzeł dodawany do drzewa BST zawsze jest:
* następnikiem korzenia
* liściem
* elementem największym
* elementem najmniejszym
14. Po wstawieniu elementu z do drzewa BST, left(z) i right(z) wskazują na:
* element z
* na samych siebie
* na korzeń
* mają wartość null
15. W jaki sposób należy usunąć z drzewa BST węzeł z, jeśli ma on dokładnie jednego potomka?
* należy usunąć z, a potomka przypisać dowolnemu węzłowi
* należy zastąpić węzeł jego następnikiem
* należy usunąć z, a jego potomka zapisać jako potomka rodzica z
* należy ustawić wskaźnik rodzica na null
16. Aby uzyskać posortowany ciąg elementów drzewa BST należy:
* przejść po nim metodą in-order
* przejść po nim metodą pre-order
* przejść po nim medodą post-order
* konieczne jest przetworzenie drzewa dodatkową funkcją sortującą
17. [drzewo.png] Jaki rezultat otrzymamy przechodząc po tym drzewie metodą pre-order?
18. [drzewo.png] Jaki rezultat otrzymamy przechodząc po tym drzewie metodą post-order?
19. [drzewo.png] Jaki rezultat otrzymamy przechodząc po tym drzewie metodą in-o
rder?
20. Stwórz drzewo BST z elementami o kluczach : 8, 15, 2, 14, 5, 13, 9, 10, 1
21. Stwórz drzewo BST z elementami o kluczach : 1, 2, 3, 9, 8, 7, 5, 4, 6
22. [drzewo2.png] Jak będzie wyglądało to drzewo BST po usunięciu elementu o kluczu 2?
23. [drzewo2.png] Jak będzie wyglądało to drzewo BST po usunięciu elementu o kluczu 9?
24. [drzewo2.png] Jak będzie wyglądało to drzewo BST po usunięciu elementu o kluczu 17?
25. Poprzednik x w drzewie BST to:
* prawy potomek x
* lewy potomek x
* najmniejszy element y wśród elementów większych od x
* największy element y wśród elementów mniejszych od x
26. [drzewo3.png] Jaki rezultat otrzymamy przechodząc po tym drzewie metodą post-order?
27. [drzewo3.png] Jaki rezultat otrzymamy przechodząc po tym drzewie metodą in-order?
28. [drzewo3.png] Poprzednikiem elementu o kluczu 7 jest element:
* 6, ponieważ jest rodzicem 7
* 6, ponieważ jest największym kluczem z kluczy mniejszych od 7
* 4. ponieważ jest bratem 7
* 8, ponieważ jest korzeniem drzewa
29. Podczas budowania drzewa BST, danymi które mogą degenerować drzewo są dane:
* nieposortowane
* posortowane
* nieujemne
* w niewielkich ilościach
30. Budując drzewo BST bez założenia unikatowości kluczy należy pamiętać że:
* nie może dojść do sytuacji, gdy klucz rodzica jest równy kluczowi jego potomka
* elementy powtarzające się należy dowiązywać wyłącznie jako dzieci lewe
* elementy powtarzające się należy dowiązywać wyłącznie jako dzieci prawe
* należy samodzielnie ustalić sposób dowiązania powtarzających się elementów i konsekwentnie go przestrzegać w pracy z danym drzewem
1. Mamy tablicę zawierającą ciąg liczb, aby wykonać sortowanie w miejscu należy :
a sortować z wykorzystaniem dodatkowej tablicy
# b sortować bezpośrednio na danej tablicy
c nie zmieniać kolejności powtarzających się elementów
d zamieniać kolejność powtarzających się elementów
2. Mamy następujcy ciąg liczb 4, 7, 2, 1, 5 sortujemy je następująco:
krok 1: 4, 2, 7, 1, 5
krok 2: 2, 4, 1, 5, 7
krok 3: 2, 1, 4, 5, 7
krok 4: 1, 2, 4, 5, 7
Jaka metoda sortowania została użyta?
a przez wstawianie
b przez wybór
c shella
# d bąbelkowe
3. Czy sortowanie w którym znajdujemy najmniejszy element ciągu i zamieniamy go z pierwszym elementem, oraz powtarzamy to dla podciągu bez pierwszego elementu itd. nazywamy :
a bąbelkowym
b przez wstawianie
# c przez wybór
d mergesort
4. Które z poniższych sortowań mają zawsze złożoność O(N^2)?
a radix sort, shell sort
b quick sort, bąbelkowe
c przez wstawianie, przez zliczanie
# d żadna z powyższych
5. Przechodzimy przez ciąg od jego końca, porównując sąsiadujące elementy i ewentualnie zamieniając je miejscami. Powtarzamy tą procedurę aż do uporządkowania całego ciągu.Powyższa definicja mówi o sortowaniu :
a przez wstawianie
b shellsort
# c bąbelkowym
d żadne z powyższych
6. Które z poniższych algorytmów mają zawsze złożoność O(NlogN) ?
# a heapsort i mergesort
b radixsort i heapsort
c bąbelkowe i shellsort
d quicksort i shellsort
7. Które z poniższych algorytmów mają zawsze złożoność O(N)
a bąbelkowe i shellsort
b radixsort i heapsort
# c zliczanie i radixsort
d quicksort i shellsort
8. Rozszerzona wersja sortowania przez wstawianie to :
a przez wybór
b quicksort
c mergesort
# d shellsort
9. Mamy następujcy ciąg liczb 4, 7, 2, 1, 5 sortujemy je następująco:
krok 1: 1, 7, 2, 4, 5
krok 2: 1, 2, 7, 4, 5
krok 3: 1, 2, 4, 7, 5
krok 4: 1, 2, 4, 5, 7
Jaka metoda sortowania została użyta?
a przez wstawianie
# b przez wybór
c shella
d bąbelkowe
10. 2. Mamy następujcy ciąg liczb 4, 7, 2, 1, 5
sortujemy je następująco:
krok 1: 4, 7, 2, 1, 5
krok 2: 2, 4, 7, 1, 5
krok 3: 1, 2, 4, 7, 5
krok 4: 1, 2, 4, 5, 7
Jaka metoda sortowania została użyta?
# a przez wstawianie
b przez wybór
c shella
d bąbelkowe
11. Który z poniższych algorytmów sortowania ma zawsze złożoność O(N^(4/3)) ?
a heapsort
b mergesort
c zliczanie
# d shellsort
12. Dla każdego elementu ciągu (od lewej do prawej), wstawiamy go we właściwe miejsce ciągu elementów poprzedzających go (już posortowanych).Powyższa definicja mówi o sortowaniu :
# a przez wstawianie
b shellsort
c bąbelkowym
d żadne z powyższych
13. Poniższy kod przedstawia sortowanie:
for j -> 2 to length[A]
do key -> A[j]
i -> j-1
while i>0 and A[i]>key
do A[i+1] -> A[i]
i -> i-1
A[i+1] -> key
a bąbelkowe
b shellsort
# c przez wstawianie
d przez wybór
14. Poniższy kod przedstawia sortowanie:
for i -> 1 to length[A]
do for j -> length[A] downto i + 1
do if A[j] < A[j - 1]
then exchange A[j] -> A[j - 1]
# a bąbelkowe
b shellsort
c przez wstawianie
d przez wybór
15. Kolejne sortowanie dla złożonych obiektów nie psuje efektów poprzedniego sortowania. Mowa jest o :
a sortowaniu w miejscu
b sortowaniu nie w miejscu
# c sortownaiu stabilnym
d sortownaiu niestabilnym
16. Sortowanie wymagające dodatkowego przydzielenia pamięci nazywamy :
a sortowaniem w miejscu
# b sortowaniem nie w miejscu
c sortownaiem stabilnym
d sortownaiem niestabilnym
17. Sortowanie niestabilne polega na:
a sortowaniu z wykorzystaniem dodatkowej pamięci
b sortowaniu bez wykorzystania dodatkowej pamięci
c kolejne sortowanie nie psuje efektów poprzedniego sortowania
# c kolejne sortowanie psuje efektów poprzedniego sortowania
18. Poniższy kod przedstawia sortowanie(Exchange = zamień):
for i -> 1 to length[A]
do min -> i;
for j -> i+1 to length[A]
do if A[j] < A[min] then min -> j;
Exchange A[min] -> A[i]
a bąbelkowe
b shellsort
c przez wstawianie
# d przez wybór
19. Podział Knuth'a dla sortowania shellsort wygląda następująco:
a 1, 2, 4, 8, 16, 32, 64
b 1, 1, 2, 3, 5, 8, 13
c 1, 3, 5, 7, 9, 11, 13
# d 1, 4, 13, 40, 121, 364, 1093
20. Podział Shell'a dla sortowania shellsort wygląda następująco:
# a 1, 2, 4, 8, 16, 32, 64
b 1, 1, 2, 3, 5, 8, 13
c 1, 3, 5, 7, 9, 11, 13
d 1, 4, 13, 40, 121, 364, 1093
21. Która złożoność czasowa odpowiada sortowaniu shellsort?
a O(N^2)
b O(NlogN)
# c O(N^(4/3))
d O(N)
22. Która złożoność czasowa odpowiada sortowaniu radixsort?
a O(N^2)
b O(NlogN)
c O(N^(4/3))
# d O(N)
23. Która złożoność czasowa odpowiada sortowaniu przez wybór?
# a O(N^2)
b O(NlogN)
c O(N^(4/3))
d O(N)
24. Która złożoność czasowa odpowiada sortowaniu heapsort?
a O(N^2)
# b O(NlogN)
c O(N^(4/3))
d O(N)
25. Dzielimy ciąg na podciągi, sortujemy te podciągi, a następnie łączymy zachowując porządek.Mowa o sortowaniu :
a przez wstawianie
b heapsort
# c mergesort
d żadne z powyższych
26. Który z algorytmów sortowania jest typu "dziel i zwyciężaj"?
a przez wybór
b bąbelkowe
c przez wstawianie
# d mergesort
27. Który algorytm sortowania nie jest sortowaniem w miejscu?
a bąbelkowe
# b przez zliczanie (countingsort)
c heapsort
d przez wybór
28. Sortowanie quicksort jest :
a w miejscu i stabilne
# b w miejscu i niestabilne
c nie w miejscu i stabilne
d nie w miejscu i niestabilne
29. Sortowanie wstawianie jest :
# a w miejscu i stabilne
b w miejscu i niestabilne
c nie w miejscu i stabilne
d nie w miejscu i niestabilne
30. Algorytmy o liniowym czasie działania to:
a bąbelkowe, przez wstawianie, shellsort
b shellsort, radixsort, quicksort
c przez wybór, kubełkowe, mergesort
# d radixsort, kubełkowe, zliczanie(countingsort)