1. Wskaż zdanie prawdziwe. Metoda programistyczna „dziel i zwyciężaj” wykorzystywana w celu sprawdzenia czy zadana wartość znajduje się w zbiorze, realizowana jest dla zbiorów …

Uporządkowanych

2. Stosując algorytm wyszukiwania przez połowienie dla zbioru uporządkowanego

17

3. Ile operacji porównania należy wykonać aby dla nieuporządkowanego zbioru dwudziesto elementowego, wyszukać wartość najmniejszą?

19

4. Jakie zadanie realizuje przedstawiony poniżej za pomocą listy kroków algorytm?

Krok 1 Dla j =1,2,..,n-1 wykonaj

Krok 1…Krok 4, a następnie zakończ algorytm

Krok 2 Pmin <- j

Krok 3 Dla i=j-1, j+2,…,n

Jeżeli d[i] < d[Pmin], to

Pmin <- i

Krok 4 d[j] <-> d[Pmin]

sortowanie przez wybór

5. Ile należy rozegrać dodatkowych meczy w turnieju tenisowym aby wyłonić drugiego najlepszego gracza turnieju wiedząc, że liczba uczestników jest równa n=8

2

6. Jakiej złożoności obliczeniowej jest algorytm sortowania MargeSort

Logarytmicznej

7. Który z poniżej wymienionych algorytmów najszybciej zrealizuje zadanie porządkowania zbioru

algorytm Quick Sort

8. Który z poniżej wymienionych algorytmów najszybciej wyświetli wynik operacji wyszukiwania w zbiorze nieuporządkowanym zadanej przez użytkownika wartości

algorytm wyszukiwania liniowego z wartownikiem

9. Ile porównań należy dokonać aby w zbiorze n – elementowym znaleźć wartość min i max stosując algorytm „dziel i zwyciężaj”

3n/2 - 2