pytania algorytmy, Algorytmy i złożoność obliczeniowa


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 jeœli:

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)



Wyszukiwarka

Podobne podstrony:
Algorytmy biologii obliczeniowej
ŚCINANIE algorytm i przykład obliczania
Algorytm obliczeń (Naprawiony)
Algorytmy obliczen id 57749 Nieznany
Algorytm obliczania parametrow Nieznany
Algorytmy sumowania w metodzie spektrum odpowiedzi i ich wpływ na obliczaną odpowiedź budynku wysoki
obliczenia cwu algorytm
ASD, algorytmybymonika, PYTANIE 1
kozik,projektowanie algorytmów,TEORIA ZŁOŻONOŚCI OBLICZENIOWEJ
zarzycki, algorytmy przetwarzania sygnałów ,pytania i opracowanie
lichtenstein, struktury?nych i złożoność obliczeniowa,Badanie?ektywności algorytmów pseudowielomiano
algorytmy pytania na egzamin, pytania asd1w5
Eurokod 2-algorytm obliczania zbrojenia dla elementów zginanych, przekrój podwójnie zbrojony
Algorytmy sumowania w metodzie spektrum odpowiedzi i ich wpływ na obliczaną odpowiedź budynku wysoki
Algorytmy wyklady, Złożoność obliczeniowa algorytmów
JAiO - Projekt 3, Studia, III Semestr, Języki, Algorytmy i Obliczenia, Projekty
JAiO - Projekt 4, Studia, III Semestr, Języki, Algorytmy i Obliczenia, Projekty

więcej podobnych podstron